单链表专题

前言顺序表和单链表都是两种常见的数据结构他们的区别究竟在哪里顺序表顺序表是一种连续的存储结构数据元素在内存中占据一块连续的空间。因为连续空间存储的特性顺序表可以直接通过下表遍历元素。单链表单链表是一种离散的存储结构数据元素存储在节点中节点中包含数据和下一节点的指针。总结顺序表和单链表的区别在于他们的存储方式不同顺序表是连续存储单链表则是离散存储单链表相对于顺序表的优势是单链表可以降低操作时的时间复杂度。1.链表的概念及结构概念链表是一种物理存储结构上非连续、非顺序的存储结构数据元素的逻辑顺序使通过链表中的指针链接次序实现的。链表的结构就像这个小火车每一个车厢就是一个节点节点包括数据车厢里的货物和下一个节点的指针车厢之间的抓钩。在链表中的小火车就像这样每个节点对应的结构体代码就可以这样写出假设当前保存的节点为整型typedef struct SListNode { int data; //节点数据 struct SListNode* next //指针变量 用来保存下一个节点的地址 }SLTNode;我们想要保存⼀个数据时实际是向操作系统申请了⼀块内存这个内存不仅要保存数据也需要保存下⼀个节点的地址当下⼀个节点为空时保存的地址为空。当我们想要从第⼀个节点⾛到最后⼀个节点时只需要在前⼀个节点拿上下⼀个节点的地址就可以了。那在链表结构中如何实现节点从头到尾的打印void SLTPrint(SLTNode* phead){ SLTNode *pcur phead; while(pcur) { printf(%d ,pcur-data); pcur pcur-next; } printf(\n); }测试样例void SlistTest01(){ SLTNode* node1 (SLTNode* )malloc(sizeof(SLTNode)); node1-data 1; SLTNode* node2 (SLTNode* )malloc(sizeof(SLTNode)); node1-data 2; SLTNode* node3 (SLTNode* )malloc(sizeof(SLTNode)); node1-data 3; SLTNode* node4 (SLTNode* )malloc(sizeof(SLTNode)); node1-data 4; //此时创建好了节点数据 但还没有实现节点链接 node1- node2; node2- node3; node3- node4; node4- NULL; } void SLTPrint(SLTNode* phead){ SLTNode *pcur phead; while(pcur) { printf(%d ,pcur-data); pcur pcur-next; } printf(NULL\n); } SLTNode* plist node1; SLtPrint(plist);测试结果2.单链表的实现2.1单链表的尾插typedef char SLTDataType; SLTNode* SLTBuyNode(SLTDataType x) { SLTNode* newnode (SLTNode* )malloc(sizeof(SLTNode)); if(newnode NULL) { perror(malloc fail!); exit(1); } newnode-data x; newnode-next NULL; return newnode; } void SLTPushBack(SLTNode** pphead,SLTDataType x){ assert(pphead); SLTNode* newnode SLTBuyNode(x); //链表为空 新节点为phead if(*pphead NULL) { *pphead newnode; return; } //链表不为空 找尾结点 //为了不改变头结点 设置临时结构体变量 SLTNode* ptail *pphead; while(ptail-next) { ptail ptail-next; } //ptail就是尾结点 ptail-next newnode; }测试样例void SlistTest02() { SLTnode* plist NULL; SLTPushback(plist,1); SLTPushback(plist,2); SLTPushback(plist,3); SLTPushback(plist,4); SLTPrint(plist); //结果 1-2-3-4-NULL }运行结果2.2单链表的头插void SLTPushFront(SLTNode** pphead,SLTDataType x) { assert(pphead); SLTNode* newnode SLTBuyNode(x); new-next*pphead; *pphead newnode; }测试样例void SlistTest03(){ SLTPushFront(plist,5); SLTPrint(plist); SLTPushFront(plist,6); SLTPrint(plist); SLTPushFront(plist,7); SLTPrint(plist); }结果7-6-5-NULL2.3 链表的头删和尾删//单链表的尾删 void SLTPopBack(SLTNode** pphead){ assert(pphead); //pphead链表不能为空 *phead首节点也不能为空 assert(*pphead); //链表不为空 //链表只有一个节点有多个节点 if((*pphead)-next NULL) { free(*pphead); *pphead NULL; return; } SLTNode* ptail *pphead; SLTNode* prev NULL; //存放前区节点 while(ptail-next) { prev ptail; ptail ptail-next; } prev-next NULL; //销毁尾结点 free(ptail); ptail NULL; } //单链表的头删 void SLTPopFront(SLTNode** pphead) { assert(pphead); assert(*pphead); //链表不能为空 //让第二个节点成为新的头 同时把旧的头结点释放掉 SLTNode* next (*pphead)-next; free(*pphead); *pphead next; } //测试 SLTPopBack(plist); SLTPrint(plist); SLTPopFront(plist); SLTPrint(plist);2.4 链表的查找SLTNode* SLTFind(SLTNode** pphead,SLTDataType x) { assert(pphead); //遍历链表 SLTNode* pcur *pphead while(pcur) //等价于pcur ! NULL { if(pcur-data x){ return pcur;} } //没有找到 return NULL; } //测试 SLTNode* FindRet SLTFind(plist); if(FindRet) { printf(找到了!); } else{ printf(未找到!); }2.5 在指定位置之前插入数据void SLTInsert(SLTNode** pphead,SLTNode* pos,SLTDataType x){ assert(pphead); assert(pos); assert(*pphead); //链表也不能为空 因为传入的指定节点也不能为空 SLTNode* newnode SLTBuyNode(x); //当pos刚好是头结点时 if(pos *pphead) { SLTPushFront(pphead,x);/头插 return; } //以下为pos不是头结点的情况 SLTNode* prev *pphead; while(prev-next!pos) { prev prev-next; } } //测试 SLTNode* FindRet SLTFind(plist,4); SLTInsert(plist,FindRet,100); SLTPrint(plist);2.6 在指定位置之后插入数据void SLTInsertAfter(SLTNode* pos,SLTDataType x) { assert(pos); //传入节点不能为空 SLTNode* newnode SLTBuyNode(x); //创建新节点 newnode-next pos-next; //先接新节点后 再接新节点前 pos-next newnode; } //测试 void SlistTest03(){ SLTNode* plist NULL; SLTPushBack(plist,1); SLTPushBack(plist,2); SLTPushBack(plist,3); SLTPushBack(plist,4); SLTPrint(plist); //1-2-3-4-NULL SLTNode* FindRet SLTFind(plist,1); SLTInsertAfter(FindRet,100); SLTPrint(plist); //1-100-2-3-4-NULL }