数据结构：单链表

本专栏的上一篇文章讲的是线性表的顺序存储结构存在着一些弊端比如在在中间位置或者头部位置插入删除的时候时间复杂度是O(n),每次扩容都是以二倍的形式来扩容的很有可能会导致空间大了用不完的情况用一组任意的存储单元存储线性表的数据元素这组存储单元可以是连续的也可以是不连续的意味着数据可以存储到内存未被占用的任意位置。在顺序存储结构中只需要存储数据元素的信息就可以但是在链式存储结构中除了存储数据元素的信息外还是需要存储它后继元素的存储地址一、线性表的链式存储结构的特点1. 定义链表由一系列节点组成每个节点包含两部分数据域和指针域。数据域用于存储具体的数据指针域则存储指向下一个节点的地址引用。通过这种指针的连接各个节点得以串连起来形成链表。指向链表第一个节点的指针叫做头指针链表的第一个节点通常被称作头节点而最后一个节点的指针域一般会指向空(NULL)。单链表是逻辑上相邻物理上不一定相邻的链式存储结构2. 特点优点1链表可以动态的添加和删除节点不需要提前确定申请的大小不用担心内存浪费的情况2插入删除操作高效只需要修改结点的指针域时间复杂度为O(1)【只是插入删除的过程不包括遍历如果是加上遍历的话尾插尾删O(n),头插头删O(1)】缺点1由于链表的结点在内存中不是连续存储的所以要访问其中一个元素就必须从开始遍历直到找到目标节点因此链表随机访问的时间复杂度是O(n),就跟顺序表的按值查找的时间复杂度一样2额外的内存开销除了需要开辟内存空间还需要开辟额外的空间来存储指针域二、单链表的实现1. 结构体定义//类型重命名 typedef int Elemtype; //结构体定义 typedef struct Node { Elemtype data;//数据域 struct Node* next;//指针域指向下一个同类型链表结点 }Node;2. 初始化函数plist是指向头结点的头指针plist-nextnullptr,代表当前链表没有其他结点//初始化 void Init_Node(Node* plist) { //1.安全判断 assert(plist ! nullptr); if (plist nullptr) { exit(EXIT_FAILURE); } //2.对辅助结点初始化 //数据域浪费掉 // plist-data //指针域指向空 plist-next nullptr; }3. 购买新节点//购买新节点同类型结点 Node* buyNode(Elemtype val) { //1.购买新节点 Node* pnewnode (Node*)malloc(sizeof(Node)); //2.判断结点是否购买成功 if (pnewnode nullptr) exit(EXIT_FAILURE); //3.将数据域和指针域更新 pnewnode-data val; pnewnode-next nullptr; //4.购买成功返回新节点的地址 return pnewnode; }首先需要用malloc在堆区申请一个新节点然后判断节点是否购买成功然后将需要插入的数据放入新节点新节点的指针域置空然后返回新购买节点的地址4. 获取有效长度//获取有效长度 int get_length(Node* plist) { //1.安全判断 assert(plist ! nullptr); if (plist nullptr) return false; //2.循环遍历 int len 0; for (Node* p plist-next; p ! nullptr; p p-next) len; return len; }5. 判空如果辅助节点的指针域指向空就证明链表空了bool IsEmpty(Node* plist) { //1.安全判断 assert(plist ! nullptr); if (plist nullptr) return false; //2.如果辅助节点的指针域指向空就证明链表空了 return plist-next nullptr; }6. 插入数据6.1 头插bool Insert_head(Node* plist,Elemtype val) { //1.安全判断 assert(plist ! nullptr); if (plist nullptr) return false; //2.购买新结点 Node* pnewnode buyNode(val); //3.将新节点插入链表 //先将新节点接上后继结点 pnewnode-next plist-next; plist-next pnewnode; return true; }首先需要进行安全判断然后调用购买新节点的函数购买新节点将新节点插入链表首先需要新节点需要先保存后继节点的地址然后辅助节点再连接新节点6.2 尾插//尾插 bool Insert_back(Node* plist, Elemtype val) { //1.安全判断 assert(plist ! nullptr); if (plist nullptr) return false; //2.申请新结点 Node* pnewnode buyNode(val); //3.遍历到链表结尾将新节点接入链表 Node* p plist; for (; p-next ! nullptr; p p-next); p-next pnewnode; return true; }首先是安全判断然后申请新节点然后申请一个Node* 类型的指针指向辅助节点然后循环遍历的条件是指向的下一个指针域不为空遍历到最后然后将新节点插入6.3 任意位置插入//任意位置插入 bool Insert_pos(Node* plist, Elemtype val, int pos) { //1.安全判断 assert(plist ! nullptr); if (plist nullptr) return false; //2.边界判断 if (pos1 || posget_length(plist) 1) return false; //2.申请新结点 Node* pnewnode buyNode(val); //3.遍历到pos Node* p plist; for (int i 0; i pos - 1; i) p p-next; //4.将新节点插入链表 pnewnode-next p-next; p-next pnewnode; return true; }首先安全判断然后进行pos的边界条件判断pos的合法范围是1posget_length1,因为是从第一个有效节点开始算的申请一个新节点然后遍历到要插入位置的前一位进行新节点的插入7. 删除数据7.1 头删//头删 bool delete_head(Node* plist) { //1.安全判断 assert(plist ! nullptr); if (plist nullptr) return false; //2.判空 if (IsEmpty(plist)) return false; //3.待删除节点 Node* q plist-next; //3.用辅助节点接上待删除结点的后继 plist-next q-next; free(q); q NULL; return true; }首先进行安全判断然后判空如果链表已空结束找到待删除结点先用辅助节点连接待删除节点的后继结点然后再释放待删除节点,将堆空间释放然后再将待删除置节点置空防止二次释放7.2 尾删//尾删 bool delete_back(Node* plist) { //1.安全判断 assert(plist ! nullptr); if (plist nullptr) return false; //2.判空 if (IsEmpty(plist)) return false; //3.待删除节点 Node* q plist; //4.待删除节点的前驱结点 Node* p plist; //5.找到待删除节点 for (; q-next ! nullptr; q q-next); //6.找到待删除节点的前驱 for (; p-next ! q; p p-next); //7.跨越指向 p-next q-next; free(q); q NULL; return true; }首先安全性处理并判断当前链表是否为空链表如果是空链表则结束当前进程。若不是定义一个Node* 类型的指针p 让其指向头节点通过循环遍历使 p 指向待删除节点的前一个节点位置再定义一个辅助节点q 使其指向待删除节点即 p-next然后跨越待删除结点(修改辅助结点的指针域)。最后free(q)将堆空间释放然后再将待删除置节点置空防止二次释放7.3 按位置删//按位置删 bool delete_pos(Node* plist, int pos) { //1.安全判断 assert(plist ! nullptr); if (plist nullptr) return false; //2.判空 if (IsEmpty(plist)) return false; //2.5 边界判断 if (pos 1 || posget_length(plist) 1); //3.定义待删除节点的前驱节点 Node* p plist; //4.定义待删除节点 Node* q plist; //5.找到待删除节点的前驱 for (int i 0; i pos - 1; i) p p-next; //6.找到待删除结点 q p-next; //7.跨越指向 p-next q-next; free(q); q NULL; return true; }首先安全判断边界值判断1posget_length()1定义待删除节点的前驱结点和待删除节点遍历到待删除节点的前驱直接得到待删除节点然后跨越指向释放待删除节点将待删除节点置空防止二次释放7.4 按值删只删除这个值出现的第一次和按位置删除很相似就是把给的pos换成了search(plist,val)返回地址//按值删只删除这个值出现的第一次 bool Del_Val_First(Node* plist, Elemtype val) { //1.安全判断 assert(plist ! nullptr); if (plist nullptr) return false; //2.判空 if (IsEmpty(plist)) return false; //3.查找这个值的地址(就是待删除节点的地址) Node* q search(plist, val); //4.找到待删除的前驱结点 Node* p plist; for (; p-next ! q; p p-next); //5.跨越指向 p-next q-next; free(q); q NULL; return true; }7.4 按值删删除这个值出现的所有//按值删只删除这个值出现的所有位置 bool Del_Val_ALL(Node* plist, Elemtype val) { //1.安全判断 assert(plist ! nullptr); if (plist nullptr) return false; //2.判空 if (IsEmpty(plist)) return false; //3.待删除节点的前驱和待删除节点 Node* p plist; Node* q plist-next; //4.进入while,条件是q!nullptr while (q-next ! nullptr) { //5.如果是要删的值跨越指向然后q等于前驱的下一个节点 if (q-data val) { p-next q-next; free(q); q p-next; } //如果不等两指针均后移一个 else { p p-next; q q-next; } } }首先安全判断然后判空若为空返回然后申请待删除结点和待删除节点的前驱节点然后判断q的数据域是否为val,是的话跨越执向然后释放q然后给q移到p的下一个不是的话两个指针均后移一个8.元素查找//有效元素查找 Node* search(Node* plist, Elemtype val) { //1.安全判断 assert(plist ! nullptr); if (plist nullptr) exit(EXIT_FAILURE); //2.返回有效元素地址 for (Node* p plist-next; p ! nullptr; p p-next) { if (p-data val) { return p; } } return NULL; }9. 销毁//销毁 void destory(Node* plist) { //1.安全判断 assert(plist ! nullptr); if (plist nullptr) exit(EXIT_FAILURE); //2.无限头删 while (delete_head(plist)); }10. 打印//打印 void show(Node* plist) { //1.安全判断 assert(plist ! nullptr); if (plist nullptr) exit(EXIT_FAILURE); //2.循环遍历 printf(当前链表元素有); for (Node* p plist-next; p!nullptr; p p-next) { printf(%d , p-data); } printf(\n); }11. 测试int main() { Node s; Init_Node(s); Insert_head(s, 3); show(s); Insert_back(s, 5); Insert_back(s, 3); Insert_back(s, 5); Insert_back(s, 5); Insert_back(s, 3); Insert_back(s, 3); show(s); printf(%d\n, get_length(s)); printf(%d\n, IsEmpty(s)); Insert_pos(s, 5, 2); show(s); delete_head(s); show(s); delete_back(s); show(s); delete_pos(s, 2); show(s); printf(%p\n, search(s, 3)); Del_Val_First(s, 3); show(s); Del_Val_ALL(s, 3); show(s); destory(s); return 0; }