个人主页ꪔ小林Y✨个人专栏《C小白闯关日记》《C语言小白闯关日记》《数据结构入门——从原理到实战》代码信条每一行代码都是成长的脚印每一次调试成功都是对坚持的回应目录链表单链表1.链表的定义2.在链表中插入数据1尾插2头插3.在链表中删除数据1尾删2头删4.在链表中查找数据5.在指定位置之前插入数据6.在指定位置之后插入数据7.删除pos节点8.删除pos之后的节点9.销毁链表学习完上节可知顺序表的存储空间是静态分配的在程序执行前必须明确规定它的存储规模设定过大造成浪费设定过小造成溢出且顺序表在头部/中间的插入操作所需的时间复杂度为ON可见若对线性表的长度或存储规模难以估计时则不宜采用顺序表。那么有没有一种数据结构头部插入删除的时间复杂度为O1且不需要增容且不存在空间浪费呢因此就有了链表的学习。链表链表可分为单链表循环单链表和双向链表单链表1.逻辑结构线性的物理结构不一定是线性的2.概念链表是一种物理存储结构上非连续非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一个一个的节点组成节点有两个组成部分保存的数据指针始终保存下一个节点的地址因而在定义链表的数据结构时就是定义结点的结构。1.链表的定义头文件SList.h#includestdio.h#includestdlib.h//链表的结构typedefintSLTDataType;structSListNode{SLTDataType data;structSListNode*next;//指向下一个结点的地址};typedefstructSListNodeSLTNode;//打印链表voidSLTPrint(SLTNode*phead);实现文件“SList.c”#includeSList.hvoidSLTPrint(SLTNode*phead){SLTNode*pcurphead;while(pcur!NULL){printf(%d - ,pcur-data);pcurpcur-next;}printf(NULL\n);}测试文件“test.c”#includeSList.hinttest01(){//创建一个链表SLTNode*node1(SLTNode*)malloc(sizeof(SLTNode));SLTNode*node2(SLTNode*)malloc(sizeof(SLTNode));SLTNode*node3(SLTNode*)malloc(sizeof(SLTNode));SLTNode*node4(SLTNode*)malloc(sizeof(SLTNode));node1-data1;node2-data2;node3-data3;node4-data4;node1-nextnode2;node2-nextnode3;node3-nextnode4;node4-nextNULL;//打印链表SLTNode*plistnode1;SLTPrint(plist);}intmain(){test01();return0;}2.在链表中插入数据1尾插phead始终指向头节点创建一个新变量pcur循环遍历链表查找尾节点如果链表为空则不需要找尾巴直接让phead指向newnode所以这里需要判断一下链表是否为空头文件SList.h//尾插voidSLTPushBack(SLTNode**pphead,SLTDataType x);实现文件“SList.c”//申请新节点SLTNode*SLTBuyNode(SLTDataType x){SLTNode*newnode(SLTNode*)malloc(sizeof(SLTNode));if(newnodeNULL){perror(malloc fail);exit(1);}newnode-datax;newnode-nextNULL;returnnewnode;}//尾插voidSLTPushBack(SLTNode**pphead,SLTDataType x)//这里是传址调用因而要使用二级指针{assert(pphead);//申请新节点SLTNode*newnodeSLTBuyNode(x);//链表为空if(*ppheadNULL){*ppheadnewnode;}else{SLTNode*ptail*pphead;while(ptail-next!NULL){ptailptail-next;}//找到了尾节点ptail newnodeptail-nextnewnode;}}测试文件“test.c”voidtest02(){//创建空链表SLTNode*plistNULL;SLTPushBack(plist,1);//形参的改变要改变实参// 因而注意这里传的是地址要加SLTPushBack(plist,2);SLTPushBack(plist,3);SLTPushBack(plist,4);SLTPrint(plist);}intmain(){test02();return0;}时间复杂度O(N)2头插头文件SList.hvoidSLTPushFront(SLTNode**pphead,SLTDataType x);实现文件“SList.c”//头插voidSLTPushFront(SLTNode**pphead,SLTDataType x){assert(pphead);//申请新节点SLTNode*newnodeSLTBuyNode(x);newnode-next*pphead;*ppheadnewnode;}测试文件“test.c”voidtest02(){//创建空链表SLTNode*plistNULL;SLTPushFront(plist,1);SLTPrint(plist);SLTPushFront(plist,2);SLTPrint(plist);SLTPushFront(plist,3);SLTPrint(plist);SLTPushFront(plist,4);SLTPrint(plist);}intmain(){test02();return0;}时间复杂度O(1)3.在链表中删除数据1尾删不仅要找尾节点用ptail标记还要找尾节点的前一个指针用prev标记尾删时只有一个节点则需要特殊处理不需要要创建新指针直接释放掉即可头文件SList.hvoidSLTPopBack(SLTNode**pphead);实现文件“SList.c”//尾删voidSLTPopBack(SLTNode**pphead){//链表不能为空assert(pphead*pphead);//链表只有一个结点的情况if((*pphead)-nextNULL){free(*pphead);*ppheadNULL;}else{SLTNode*prevNULL;SLTNode*ptail*pphead;while(ptail-next){prevptail;ptailptail-next;}prev-nextNULL;free(ptail);ptailNULL;}}测试文件“test.c”voidtest02(){//创建空链表SLTNode*plistNULL;//尾插SLTPushBack(plist,1);SLTPushBack(plist,2);SLTPushBack(plist,3);SLTPushBack(plist,4);SLTPrint(plist);//尾删SLTPopBack(plist);SLTPrint(plist);SLTPopBack(plist);SLTPrint(plist);SLTPopBack(plist);SLTPrint(plist);SLTPopBack(plist);SLTPrint(plist);}intmain(){//test01();test02();return0;}时间复杂度O(N)2头删头文件SList.h//头删voidSLTPopFront(SLTNode**pphead);实现文件“SList.c”//头删voidSLTPopFront(SLTNode**pphead){assert(pphead*pphead);SLTNode*next(*pphead)-next;free(*pphead);*ppheadnext;}测试文件“test.c”voidtest02(){//创建空链表SLTNode*plistNULL;//尾插SLTPushBack(plist,1);SLTPushBack(plist,2);SLTPushBack(plist,3);SLTPushBack(plist,4);SLTPrint(plist);//头删SLTPopFront(plist);SLTPrint(plist);SLTPopFront(plist);SLTPrint(plist);SLTPopFront(plist);SLTPrint(plist);SLTPopFront(plist);SLTPrint(plist);}intmain(){test02();return0;}时间复杂度O(N)4.在链表中查找数据头文件SList.hSLTNode*SLTFind(SLTNode*phead,SLTDataType x);实现文件“SList.c”//查找SLTNode*SLTFind(SLTNode*phead,SLTDataType x){//从第一个链表遍历至整个链表查找数据SLTNode*pcurphead;while(pcur){if(pcur-datax){returnpcur;}pcurpcur-next;}//未找到returnNULL;}测试文件“test.c”voidtest02(){//创建空链表SLTNode*plistNULL;//尾插SLTPushBack(plist,1);SLTPushBack(plist,2);SLTPushBack(plist,3);SLTPushBack(plist,4);SLTPrint(plist);//查找SLTNode*posSLTFind(plist,3);if(pos){printf(找到了\n);}else{printf(未找到\n);}}intmain(){test02();return0;}5.在指定位置之前插入数据若插入点在头节点前直接头插不需要前后建立联系实现文件“SList.c”//在指定位置之前插入数据voidSLTInsert(SLTNode**pphead,SLTNode*pos,SLTDataType x){assert(ppheadpos);SLTNode*newnodeSLTBuyNode(x);//pos指向头节点if(pos*pphead){//头插SLTPushFront(pphead,x);}else{//找pos的前一个节点SLTNode*prev*pphead;while(prev-next!pos){prevprev-next;}//prev newnode posprev-nextnewnode;newnode-nextpos;}}测试文件“test.c”voidtest02(){//创建空链表SLTNode*plistNULL;//尾插SLTPushBack(plist,1);SLTPushBack(plist,2);SLTPushBack(plist,3);SLTPushBack(plist,4);SLTPrint(plist);//指定节点前插入SLTNode*posSLTFind(plist,3);SLTInsert(plist,pos,100);SLTPrint(plist);}intmain(){test02();return0;}运行时间复杂度O(N)6.在指定位置之后插入数据实现文件“SList.c”//在指定位置之后插入数据voidSLTInsertAfter(SLTNode*pos,SLTDataType x){assert(pos);SLTNode*newnodeSLTBuyNode(x);//pos newnode pos-nextnewnode-nextpos-next;pos-nextnewnode;}测试文件“test.c”voidtest02(){//创建空链表SLTNode*plistNULL;//尾插SLTPushBack(plist,1);SLTPushBack(plist,2);SLTPushBack(plist,3);SLTPushBack(plist,4);SLTPrint(plist);//指定节点后插入SLTNode*posSLTFind(plist,3);SLTInsertAfter(pos,100);SLTPrint(plist);}intmain(){test02();return0;}运行结果时间复杂度O(1)7.删除pos节点若pos刚好是头节点只需头删实现文件“SList.c”//删除pos节点voidSLTErase(SLTNode**pphead,SLTNode*pos){assert(ppheadpos);//pos刚好就是头节点——直接头删if(pos*pphead){SLTPopFront(pphead);}else{SLTNode*prev*pphead;while(prev-next!pos){prevprev-next;}//prev pos pos-nextprev-nextpos-next;free(pos);posNULL;}}测试文件“test.c”voidtest02(){//创建空链表SLTNode*plistNULL;//尾插SLTPushBack(plist,1);SLTPushBack(plist,2);SLTPushBack(plist,3);SLTPushBack(plist,4);SLTPrint(plist);//删除pos节点SLTNode*posSLTFind(plist,3);SLTErase(plist,pos);SLTPrint(plist);}intmain(){test02();return0;}运行结果:8.删除pos之后的节点实现文件“SList.c”//删除pos之后的节点voidSLTEraseAfter(SLTNode*pos){assert(pospos-next);//注意pos的下一个节点也不能为空//pos del del-nextSLTNode*delpos-next;pos-nextdel-next;free(del);delNULL;}测试文件“test.c”voidtest02(){//创建空链表SLTNode*plistNULL;//尾插SLTPushBack(plist,1);SLTPushBack(plist,2);SLTPushBack(plist,3);SLTPushBack(plist,4);SLTPrint(plist);//删除pos后节点SLTNode*posSLTFind(plist,3);SLTEraseAfter(pos);SLTPrint(plist);}intmain(){test02();return0;}运行结果9.销毁链表一个一个销毁next指针指向下一个节点释放pcur指向的节点释放完成pcur继续往下走跳出循环next指针是在循环里定义的跳出循环自动销毁。函数执行结束pcur自动销毁实现文件“SList.c”//销毁链表voidSListDestroy(SLTNode**pphead){assert(pphead);SLTNode*pcur*pphead;while(pcur){SLTNode*nextpcur-next;free(pcur);pcurnext;}*ppheadNULL;}测试文件“test.c”voidtest02(){//创建空链表SLTNode*plistNULL;//尾插SLTPushBack(plist,1);SLTPushBack(plist,2);SLTPushBack(plist,3);SLTPushBack(plist,4);SLTPrint(plist);//销毁链表SLTNode*posSLTFind(plist,3);SListDestroy(plist);SLTPrint(plist);}intmain(){test02();return0;}运行结果本期数据结构的内容就结束了。如果文中有表述不准的地方或是你有更清晰的理解思路强烈欢迎在评论区留言交流——技术路上多碰撞才能更快进步觉得内容对你有帮助的话别忘了点赞❤️➕收藏方便后续回顾复习想跟着一起系统学习数据结构的朋友也可以点击关注下一期我们会聚焦更进一步的学习带你从理论走进实操。下期不见不散✌️ 数据结构入门：单链表详解——从原理到C语言实战
个人主页ꪔ小林Y✨个人专栏《C小白闯关日记》《C语言小白闯关日记》《数据结构入门——从原理到实战》代码信条每一行代码都是成长的脚印每一次调试成功都是对坚持的回应目录链表单链表1.链表的定义2.在链表中插入数据1尾插2头插3.在链表中删除数据1尾删2头删4.在链表中查找数据5.在指定位置之前插入数据6.在指定位置之后插入数据7.删除pos节点8.删除pos之后的节点9.销毁链表学习完上节可知顺序表的存储空间是静态分配的在程序执行前必须明确规定它的存储规模设定过大造成浪费设定过小造成溢出且顺序表在头部/中间的插入操作所需的时间复杂度为ON可见若对线性表的长度或存储规模难以估计时则不宜采用顺序表。那么有没有一种数据结构头部插入删除的时间复杂度为O1且不需要增容且不存在空间浪费呢因此就有了链表的学习。链表链表可分为单链表循环单链表和双向链表单链表1.逻辑结构线性的物理结构不一定是线性的2.概念链表是一种物理存储结构上非连续非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一个一个的节点组成节点有两个组成部分保存的数据指针始终保存下一个节点的地址因而在定义链表的数据结构时就是定义结点的结构。1.链表的定义头文件SList.h#includestdio.h#includestdlib.h//链表的结构typedefintSLTDataType;structSListNode{SLTDataType data;structSListNode*next;//指向下一个结点的地址};typedefstructSListNodeSLTNode;//打印链表voidSLTPrint(SLTNode*phead);实现文件“SList.c”#includeSList.hvoidSLTPrint(SLTNode*phead){SLTNode*pcurphead;while(pcur!NULL){printf(%d - ,pcur-data);pcurpcur-next;}printf(NULL\n);}测试文件“test.c”#includeSList.hinttest01(){//创建一个链表SLTNode*node1(SLTNode*)malloc(sizeof(SLTNode));SLTNode*node2(SLTNode*)malloc(sizeof(SLTNode));SLTNode*node3(SLTNode*)malloc(sizeof(SLTNode));SLTNode*node4(SLTNode*)malloc(sizeof(SLTNode));node1-data1;node2-data2;node3-data3;node4-data4;node1-nextnode2;node2-nextnode3;node3-nextnode4;node4-nextNULL;//打印链表SLTNode*plistnode1;SLTPrint(plist);}intmain(){test01();return0;}2.在链表中插入数据1尾插phead始终指向头节点创建一个新变量pcur循环遍历链表查找尾节点如果链表为空则不需要找尾巴直接让phead指向newnode所以这里需要判断一下链表是否为空头文件SList.h//尾插voidSLTPushBack(SLTNode**pphead,SLTDataType x);实现文件“SList.c”//申请新节点SLTNode*SLTBuyNode(SLTDataType x){SLTNode*newnode(SLTNode*)malloc(sizeof(SLTNode));if(newnodeNULL){perror(malloc fail);exit(1);}newnode-datax;newnode-nextNULL;returnnewnode;}//尾插voidSLTPushBack(SLTNode**pphead,SLTDataType x)//这里是传址调用因而要使用二级指针{assert(pphead);//申请新节点SLTNode*newnodeSLTBuyNode(x);//链表为空if(*ppheadNULL){*ppheadnewnode;}else{SLTNode*ptail*pphead;while(ptail-next!NULL){ptailptail-next;}//找到了尾节点ptail newnodeptail-nextnewnode;}}测试文件“test.c”voidtest02(){//创建空链表SLTNode*plistNULL;SLTPushBack(plist,1);//形参的改变要改变实参// 因而注意这里传的是地址要加SLTPushBack(plist,2);SLTPushBack(plist,3);SLTPushBack(plist,4);SLTPrint(plist);}intmain(){test02();return0;}时间复杂度O(N)2头插头文件SList.hvoidSLTPushFront(SLTNode**pphead,SLTDataType x);实现文件“SList.c”//头插voidSLTPushFront(SLTNode**pphead,SLTDataType x){assert(pphead);//申请新节点SLTNode*newnodeSLTBuyNode(x);newnode-next*pphead;*ppheadnewnode;}测试文件“test.c”voidtest02(){//创建空链表SLTNode*plistNULL;SLTPushFront(plist,1);SLTPrint(plist);SLTPushFront(plist,2);SLTPrint(plist);SLTPushFront(plist,3);SLTPrint(plist);SLTPushFront(plist,4);SLTPrint(plist);}intmain(){test02();return0;}时间复杂度O(1)3.在链表中删除数据1尾删不仅要找尾节点用ptail标记还要找尾节点的前一个指针用prev标记尾删时只有一个节点则需要特殊处理不需要要创建新指针直接释放掉即可头文件SList.hvoidSLTPopBack(SLTNode**pphead);实现文件“SList.c”//尾删voidSLTPopBack(SLTNode**pphead){//链表不能为空assert(pphead*pphead);//链表只有一个结点的情况if((*pphead)-nextNULL){free(*pphead);*ppheadNULL;}else{SLTNode*prevNULL;SLTNode*ptail*pphead;while(ptail-next){prevptail;ptailptail-next;}prev-nextNULL;free(ptail);ptailNULL;}}测试文件“test.c”voidtest02(){//创建空链表SLTNode*plistNULL;//尾插SLTPushBack(plist,1);SLTPushBack(plist,2);SLTPushBack(plist,3);SLTPushBack(plist,4);SLTPrint(plist);//尾删SLTPopBack(plist);SLTPrint(plist);SLTPopBack(plist);SLTPrint(plist);SLTPopBack(plist);SLTPrint(plist);SLTPopBack(plist);SLTPrint(plist);}intmain(){//test01();test02();return0;}时间复杂度O(N)2头删头文件SList.h//头删voidSLTPopFront(SLTNode**pphead);实现文件“SList.c”//头删voidSLTPopFront(SLTNode**pphead){assert(pphead*pphead);SLTNode*next(*pphead)-next;free(*pphead);*ppheadnext;}测试文件“test.c”voidtest02(){//创建空链表SLTNode*plistNULL;//尾插SLTPushBack(plist,1);SLTPushBack(plist,2);SLTPushBack(plist,3);SLTPushBack(plist,4);SLTPrint(plist);//头删SLTPopFront(plist);SLTPrint(plist);SLTPopFront(plist);SLTPrint(plist);SLTPopFront(plist);SLTPrint(plist);SLTPopFront(plist);SLTPrint(plist);}intmain(){test02();return0;}时间复杂度O(N)4.在链表中查找数据头文件SList.hSLTNode*SLTFind(SLTNode*phead,SLTDataType x);实现文件“SList.c”//查找SLTNode*SLTFind(SLTNode*phead,SLTDataType x){//从第一个链表遍历至整个链表查找数据SLTNode*pcurphead;while(pcur){if(pcur-datax){returnpcur;}pcurpcur-next;}//未找到returnNULL;}测试文件“test.c”voidtest02(){//创建空链表SLTNode*plistNULL;//尾插SLTPushBack(plist,1);SLTPushBack(plist,2);SLTPushBack(plist,3);SLTPushBack(plist,4);SLTPrint(plist);//查找SLTNode*posSLTFind(plist,3);if(pos){printf(找到了\n);}else{printf(未找到\n);}}intmain(){test02();return0;}5.在指定位置之前插入数据若插入点在头节点前直接头插不需要前后建立联系实现文件“SList.c”//在指定位置之前插入数据voidSLTInsert(SLTNode**pphead,SLTNode*pos,SLTDataType x){assert(ppheadpos);SLTNode*newnodeSLTBuyNode(x);//pos指向头节点if(pos*pphead){//头插SLTPushFront(pphead,x);}else{//找pos的前一个节点SLTNode*prev*pphead;while(prev-next!pos){prevprev-next;}//prev newnode posprev-nextnewnode;newnode-nextpos;}}测试文件“test.c”voidtest02(){//创建空链表SLTNode*plistNULL;//尾插SLTPushBack(plist,1);SLTPushBack(plist,2);SLTPushBack(plist,3);SLTPushBack(plist,4);SLTPrint(plist);//指定节点前插入SLTNode*posSLTFind(plist,3);SLTInsert(plist,pos,100);SLTPrint(plist);}intmain(){test02();return0;}运行时间复杂度O(N)6.在指定位置之后插入数据实现文件“SList.c”//在指定位置之后插入数据voidSLTInsertAfter(SLTNode*pos,SLTDataType x){assert(pos);SLTNode*newnodeSLTBuyNode(x);//pos newnode pos-nextnewnode-nextpos-next;pos-nextnewnode;}测试文件“test.c”voidtest02(){//创建空链表SLTNode*plistNULL;//尾插SLTPushBack(plist,1);SLTPushBack(plist,2);SLTPushBack(plist,3);SLTPushBack(plist,4);SLTPrint(plist);//指定节点后插入SLTNode*posSLTFind(plist,3);SLTInsertAfter(pos,100);SLTPrint(plist);}intmain(){test02();return0;}运行结果时间复杂度O(1)7.删除pos节点若pos刚好是头节点只需头删实现文件“SList.c”//删除pos节点voidSLTErase(SLTNode**pphead,SLTNode*pos){assert(ppheadpos);//pos刚好就是头节点——直接头删if(pos*pphead){SLTPopFront(pphead);}else{SLTNode*prev*pphead;while(prev-next!pos){prevprev-next;}//prev pos pos-nextprev-nextpos-next;free(pos);posNULL;}}测试文件“test.c”voidtest02(){//创建空链表SLTNode*plistNULL;//尾插SLTPushBack(plist,1);SLTPushBack(plist,2);SLTPushBack(plist,3);SLTPushBack(plist,4);SLTPrint(plist);//删除pos节点SLTNode*posSLTFind(plist,3);SLTErase(plist,pos);SLTPrint(plist);}intmain(){test02();return0;}运行结果:8.删除pos之后的节点实现文件“SList.c”//删除pos之后的节点voidSLTEraseAfter(SLTNode*pos){assert(pospos-next);//注意pos的下一个节点也不能为空//pos del del-nextSLTNode*delpos-next;pos-nextdel-next;free(del);delNULL;}测试文件“test.c”voidtest02(){//创建空链表SLTNode*plistNULL;//尾插SLTPushBack(plist,1);SLTPushBack(plist,2);SLTPushBack(plist,3);SLTPushBack(plist,4);SLTPrint(plist);//删除pos后节点SLTNode*posSLTFind(plist,3);SLTEraseAfter(pos);SLTPrint(plist);}intmain(){test02();return0;}运行结果9.销毁链表一个一个销毁next指针指向下一个节点释放pcur指向的节点释放完成pcur继续往下走跳出循环next指针是在循环里定义的跳出循环自动销毁。函数执行结束pcur自动销毁实现文件“SList.c”//销毁链表voidSListDestroy(SLTNode**pphead){assert(pphead);SLTNode*pcur*pphead;while(pcur){SLTNode*nextpcur-next;free(pcur);pcurnext;}*ppheadNULL;}测试文件“test.c”voidtest02(){//创建空链表SLTNode*plistNULL;//尾插SLTPushBack(plist,1);SLTPushBack(plist,2);SLTPushBack(plist,3);SLTPushBack(plist,4);SLTPrint(plist);//销毁链表SLTNode*posSLTFind(plist,3);SListDestroy(plist);SLTPrint(plist);}intmain(){test02();return0;}运行结果本期数据结构的内容就结束了。如果文中有表述不准的地方或是你有更清晰的理解思路强烈欢迎在评论区留言交流——技术路上多碰撞才能更快进步觉得内容对你有帮助的话别忘了点赞❤️➕收藏方便后续回顾复习想跟着一起系统学习数据结构的朋友也可以点击关注下一期我们会聚焦更进一步的学习带你从理论走进实操。下期不见不散✌️