)
文章目录数据结构3链表(上)链表的概念及结构链表的分类链表的实现数据结构3链表(上)本章节链表将解决上一章顺序表所遇到的问题比如浪费空间头和中间的插入和删除时间复杂度为O(N)的增容为了避免malloc开辟失败而导致数据丢失使用了realloc导致每次扩容都需要需要申请新空间拷贝数据释放旧空间。会有不小的消耗。那么链表是如何解决上述问题的呢链表的概念及结构概念上链表是一种物理存储结构上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。现实中数据结构中注意从上图可看出链式结构在逻辑上是连续的但是在物理上不一定连续现实中的结点一般都是从堆上申请出来的从堆上申请的空间是按照一定的策略来分配的两次申请的空间可能连续也可能不连续假设在64位系统上结点中值域为int类型则一个结点的大小为8个字节则也可能有下述链表。链表的分类实际中链表的结构非常多样以下情况组合起来就有8种链表结构单向或双向带头或不带头循环或非循环虽然有这么多的链表的结构但是我们实际中最常用还是两种结构无头单向非循环链表结构简单一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。带头双向循环链表结构最复杂一般用在单独存储数据。实际中使用的链表数据结构都是带头双向循环链表。另外这个结构虽然结构复杂但是使用代码实现以后会发现结构会带来很多优势实现反而简单了后面我们代码实现了就知道了。本章节先实现无头单向非循环链表下一章再在此链表的基础上进行修改成带头双向循环链表。链表的实现#pragmaonce#includeassert.h#includestdlib.h#includestdio.htypedefintSLTDateType;typedefstructSListNode{SLTDateType data;structSListNode*next;}SLTNode;// 动态申请一个节点SLTNode*BuySListNode(SLTDateType x);// 单链表打印voidSListPrint(SLTNode*plist);// 单链表尾插voidSListPushBack(SLTNode**pplist,SLTDateType x);// 单链表的头插voidSListPushFront(SLTNode**pplist,SLTDateType x);// 单链表的尾删voidSListPopBack(SLTNode**pplist);// 单链表头删voidSListPopFront(SLTNode**pplist);// 单链表查找SLTNode*SListFind(SLTNode*plist,SLTDateType x);// 单链表在pos位置之后插入xvoidSListInsertAfter(SLTNode*pos,SLTDateType x);// 单链表删除pos位置之后的值voidSListEraseAfter(SLTNode*pos);动态申请结点// 动态申请一个节点SLTNode*BuySListNode(SLTDateType x);我们在最初的时候就说到过顺序表的开辟内存问题会降低效率和造成浪费那么链表在开辟内存空间是如何规避顺序表的问题呢因为链表它们是通过一条一条的链子连接起来的也就是说我们每次申请内存空间然后将其连接到原链表上就可以这种方法就避免了内存空间一次性申请太多从而浪费。但是我们知道多次申请内存空间实际上一件很麻烦的事情但是顺序表的开辟内存是先申请再拷贝然后销毁的一系列操作很明显在数据量多的情况链表在开辟内存空间效率会高一点。注实际上顺序表的创建一开始都会进行计算要存多少数据都是一次性给它开辟等后续数据多的时候才会进行二次申请。所以严格来说顺序表在效率方面还是比链表强的。SLTNode*BuySListNode(SLTDateType x){SLTNode*newNode(SLTNode*)malloc(sizeof(SLTNode));if(newNodeNULL){perror(malloc fail);returnNULL;}newNode-datax;newNode-nextNULL;returnnewNode;}尾插和头插// 单链表尾插voidSListPushBack(SLTNode**pplist,SLTDateType x);// 单链表的头插voidSListPushFront(SLTNode**pplist,SLTDateType x);我们发现这里尾插和头插的参数里面都有二级指针为什么因为我们这里需要将新创建的链表接到原链表的后面那么我们要传址才行传参得到的只是一份被拷贝的数据而非本体并且传参的话函数调用完就销毁了就会导致申请的链表变成了野指针。我们在指针章节了解到传一级指针就需要用二级指针来接收所以这里是二级指针。解决了上述问题那么尾插和头插该怎么插入呢实现链表或者去写链表的算法题遇到插入最好的办法是画图// 单链表尾插voidSListPushBack(SLTNode**pplist,SLTDateType x){assert(pplist);SLTNode*newNodeBuySListNode(x);if(*pplistNULL){*pplistnewNode;}else{// 找尾SLTNode*tail*pplist;while(tail-next!NULL){tailtail-next;}tail-nextnewNode;}}// 单链表的头插voidSListPushFront(SLTNode**pplist,SLTDateType x){assert(pplist);SLTNode*newNodeBuySListNode(x);newNode-next*pplist;*pplistnewNode;}测试一下功能为了方便测试先去实现一个打印链表的函数// 单链表打印voidSListPrint(SLTNode*plist){SLTNode*currentplist;while(current){printf(%d-,current-data);currentcurrent-next;}printf(NULL\n);}测试一下插入功能是否是没问题的。#includeSList.h#includestdio.hvoidtest1(){SLTNode*plistNULL;SListPushBack(plist,1);SListPushBack(plist,2);SListPushBack(plist,3);SListPushBack(plist,4);SListPrint(plist);SListPushFront(plist,5);SListPushFront(plist,6);SListPushFront(plist,7);SListPushFront(plist,8);SListPrint(plist);}intmain(){test1();return0;}尾删和头删// 单链表的尾删voidSListPopBack(SLTNode**pplist);// 单链表头删voidSListPopFront(SLTNode**pplist);和插入一样我们先画图再写代码// 单链表的尾删voidSListPopBack(SLTNode**pplist){assert(pplist);if((*pplist)-nextNULL){free(*pplist);*pplistNULL;}else{SLTNode*tail*pplist;while(tail-next-next!NULL){tailtail-next;}free(tail-next);tail-nextNULL;}}// 单链表头删voidSListPopFront(SLTNode**pplist){assert(pplist);SLTNode*cur*pplist;*pplistcur-next;free(cur);curNULL;}依旧测试一下删除功能是否有问题。voidtest2(){SLTNode*plistNULL;SListPushBack(plist,1);SListPushBack(plist,2);SListPushBack(plist,3);SListPushBack(plist,4);SListPrint(plist);SListPopBack(plist);SListPopBack(plist);SListPrint(plist);SListPopBack(plist);SListPopBack(plist);SListPrint(plist);SListPushFront(plist,5);SListPushFront(plist,6);SListPushFront(plist,7);SListPushFront(plist,8);SListPopFront(plist);SListPopFront(plist);SListPrint(plist);SListPopFront(plist);SListPopFront(plist);SListPrint(plist);SListPrint(plist);}intmain(){//test1();test2();return0;}查找、随机插入和删除// 单链表查找SLTNode*SListFind(SLTNode*plist,SLTDateType x);// 单链表在pos位置之后插入xvoidSListInsertAfter(SLTNode*pos,SLTDateType x);// 单链表删除pos位置之后的值voidSListEraseAfter(SLTNode*pos);为什么插入和删除都是在pos位置之后插入呢因为单链表只有next没有prev为了找到前驱只能从链表头开始遍历逐个比较节点地址直到找到 next pos 的节点。这个过程的时间复杂度是 O(n)其中 n 是链表长度。所以pos之前的插入就在带头双向循环链表里面去实现。// 单链表查找SLTNode*SListFind(SLTNode*plist,SLTDateType x){assert(plist);SLTNode*curplist;while(cur){if(cur-datax){returncur;}curcur-next;}returnNULL;}// 单链表在pos位置之后插入xvoidSListInsertAfter(SLTNode*pos,SLTDateType x){assert(pos);SLTNode*newNodeBuySListNode(x);SLTNode*nextpos-next;newNode-nextnext;pos-nextnewNode;}// 单链表删除pos位置之后的值voidSListEraseAfter(SLTNode*pos){assert(pos);assert(pos-next);SLTNode*delpos-next;pos-nextdel-next;free(del);delNULL;}为什么这里查找要一起实现呢因为这里的随机插入和删除我们这里是直接给pos的所以必须搭配我们这里的查找函数一起才能使用。如果想在pos位置之前删除其实还可以在插入和删除函数内部定义一个prev代码就是遍历插入/删除。有兴趣的可以去实现一下。测试一下上面实现的代码吧。voidtest3(){SLTNode*plistNULL;SListPushBack(plist,1);SListPushBack(plist,2);SListPushBack(plist,3);SListPushBack(plist,4);SListPrint(plist);// 值为2那个节点 *2SLTNode*retSListFind(plist,2);SListInsertAfter(ret,20);SListPrint(plist);SListEraseAfter(ret);SListPrint(plist);}intmain(){//test1();//test2();test3();return0;}完整代码#includeSList.hSLTNode*BuySListNode(SLTDateType x){SLTNode*newNode(SLTNode*)malloc(sizeof(SLTNode));if(newNodeNULL){perror(malloc fail);returnNULL;}newNode-datax;newNode-nextNULL;returnnewNode;}// 单链表尾插voidSListPushBack(SLTNode**pplist,SLTDateType x){assert(pplist);SLTNode*newNodeBuySListNode(x);if(*pplistNULL){*pplistnewNode;}else{// 找尾SLTNode*tail*pplist;while(tail-next!NULL){tailtail-next;}tail-nextnewNode;}}// 单链表的头插voidSListPushFront(SLTNode**pplist,SLTDateType x){assert(pplist);SLTNode*newNodeBuySListNode(x);newNode-next*pplist;*pplistnewNode;}// 单链表打印voidSListPrint(SLTNode*plist){SLTNode*currentplist;while(current){printf(%d-,current-data);currentcurrent-next;}printf(NULL\n);}// 单链表的尾删voidSListPopBack(SLTNode**pplist){assert(pplist);if((*pplist)-nextNULL){free(*pplist);*pplistNULL;}else{SLTNode*tail*pplist;while(tail-next-next!NULL){tailtail-next;}free(tail-next);tail-nextNULL;}}// 单链表头删voidSListPopFront(SLTNode**pplist){assert(pplist);SLTNode*cur*pplist;*pplistcur-next;free(cur);curNULL;}// 单链表查找SLTNode*SListFind(SLTNode*plist,SLTDateType x){assert(plist);SLTNode*curplist;while(cur){if(cur-datax){returncur;}curcur-next;}returnNULL;}// 单链表在pos位置之后插入xvoidSListInsertAfter(SLTNode*pos,SLTDateType x){assert(pos);SLTNode*newNodeBuySListNode(x);SLTNode*nextpos-next;newNode-nextnext;pos-nextnewNode;}// 单链表删除pos位置之后的值voidSListEraseAfter(SLTNode*pos){assert(pos);assert(pos-next);SLTNode*delpos-next;pos-nextdel-next;free(del);delNULL;}下一章节我们就要去实现带头双向循环链表了。完 数据结构3：链表(上)
文章目录数据结构3链表(上)链表的概念及结构链表的分类链表的实现数据结构3链表(上)本章节链表将解决上一章顺序表所遇到的问题比如浪费空间头和中间的插入和删除时间复杂度为O(N)的增容为了避免malloc开辟失败而导致数据丢失使用了realloc导致每次扩容都需要需要申请新空间拷贝数据释放旧空间。会有不小的消耗。那么链表是如何解决上述问题的呢链表的概念及结构概念上链表是一种物理存储结构上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。现实中数据结构中注意从上图可看出链式结构在逻辑上是连续的但是在物理上不一定连续现实中的结点一般都是从堆上申请出来的从堆上申请的空间是按照一定的策略来分配的两次申请的空间可能连续也可能不连续假设在64位系统上结点中值域为int类型则一个结点的大小为8个字节则也可能有下述链表。链表的分类实际中链表的结构非常多样以下情况组合起来就有8种链表结构单向或双向带头或不带头循环或非循环虽然有这么多的链表的结构但是我们实际中最常用还是两种结构无头单向非循环链表结构简单一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。带头双向循环链表结构最复杂一般用在单独存储数据。实际中使用的链表数据结构都是带头双向循环链表。另外这个结构虽然结构复杂但是使用代码实现以后会发现结构会带来很多优势实现反而简单了后面我们代码实现了就知道了。本章节先实现无头单向非循环链表下一章再在此链表的基础上进行修改成带头双向循环链表。链表的实现#pragmaonce#includeassert.h#includestdlib.h#includestdio.htypedefintSLTDateType;typedefstructSListNode{SLTDateType data;structSListNode*next;}SLTNode;// 动态申请一个节点SLTNode*BuySListNode(SLTDateType x);// 单链表打印voidSListPrint(SLTNode*plist);// 单链表尾插voidSListPushBack(SLTNode**pplist,SLTDateType x);// 单链表的头插voidSListPushFront(SLTNode**pplist,SLTDateType x);// 单链表的尾删voidSListPopBack(SLTNode**pplist);// 单链表头删voidSListPopFront(SLTNode**pplist);// 单链表查找SLTNode*SListFind(SLTNode*plist,SLTDateType x);// 单链表在pos位置之后插入xvoidSListInsertAfter(SLTNode*pos,SLTDateType x);// 单链表删除pos位置之后的值voidSListEraseAfter(SLTNode*pos);动态申请结点// 动态申请一个节点SLTNode*BuySListNode(SLTDateType x);我们在最初的时候就说到过顺序表的开辟内存问题会降低效率和造成浪费那么链表在开辟内存空间是如何规避顺序表的问题呢因为链表它们是通过一条一条的链子连接起来的也就是说我们每次申请内存空间然后将其连接到原链表上就可以这种方法就避免了内存空间一次性申请太多从而浪费。但是我们知道多次申请内存空间实际上一件很麻烦的事情但是顺序表的开辟内存是先申请再拷贝然后销毁的一系列操作很明显在数据量多的情况链表在开辟内存空间效率会高一点。注实际上顺序表的创建一开始都会进行计算要存多少数据都是一次性给它开辟等后续数据多的时候才会进行二次申请。所以严格来说顺序表在效率方面还是比链表强的。SLTNode*BuySListNode(SLTDateType x){SLTNode*newNode(SLTNode*)malloc(sizeof(SLTNode));if(newNodeNULL){perror(malloc fail);returnNULL;}newNode-datax;newNode-nextNULL;returnnewNode;}尾插和头插// 单链表尾插voidSListPushBack(SLTNode**pplist,SLTDateType x);// 单链表的头插voidSListPushFront(SLTNode**pplist,SLTDateType x);我们发现这里尾插和头插的参数里面都有二级指针为什么因为我们这里需要将新创建的链表接到原链表的后面那么我们要传址才行传参得到的只是一份被拷贝的数据而非本体并且传参的话函数调用完就销毁了就会导致申请的链表变成了野指针。我们在指针章节了解到传一级指针就需要用二级指针来接收所以这里是二级指针。解决了上述问题那么尾插和头插该怎么插入呢实现链表或者去写链表的算法题遇到插入最好的办法是画图// 单链表尾插voidSListPushBack(SLTNode**pplist,SLTDateType x){assert(pplist);SLTNode*newNodeBuySListNode(x);if(*pplistNULL){*pplistnewNode;}else{// 找尾SLTNode*tail*pplist;while(tail-next!NULL){tailtail-next;}tail-nextnewNode;}}// 单链表的头插voidSListPushFront(SLTNode**pplist,SLTDateType x){assert(pplist);SLTNode*newNodeBuySListNode(x);newNode-next*pplist;*pplistnewNode;}测试一下功能为了方便测试先去实现一个打印链表的函数// 单链表打印voidSListPrint(SLTNode*plist){SLTNode*currentplist;while(current){printf(%d-,current-data);currentcurrent-next;}printf(NULL\n);}测试一下插入功能是否是没问题的。#includeSList.h#includestdio.hvoidtest1(){SLTNode*plistNULL;SListPushBack(plist,1);SListPushBack(plist,2);SListPushBack(plist,3);SListPushBack(plist,4);SListPrint(plist);SListPushFront(plist,5);SListPushFront(plist,6);SListPushFront(plist,7);SListPushFront(plist,8);SListPrint(plist);}intmain(){test1();return0;}尾删和头删// 单链表的尾删voidSListPopBack(SLTNode**pplist);// 单链表头删voidSListPopFront(SLTNode**pplist);和插入一样我们先画图再写代码// 单链表的尾删voidSListPopBack(SLTNode**pplist){assert(pplist);if((*pplist)-nextNULL){free(*pplist);*pplistNULL;}else{SLTNode*tail*pplist;while(tail-next-next!NULL){tailtail-next;}free(tail-next);tail-nextNULL;}}// 单链表头删voidSListPopFront(SLTNode**pplist){assert(pplist);SLTNode*cur*pplist;*pplistcur-next;free(cur);curNULL;}依旧测试一下删除功能是否有问题。voidtest2(){SLTNode*plistNULL;SListPushBack(plist,1);SListPushBack(plist,2);SListPushBack(plist,3);SListPushBack(plist,4);SListPrint(plist);SListPopBack(plist);SListPopBack(plist);SListPrint(plist);SListPopBack(plist);SListPopBack(plist);SListPrint(plist);SListPushFront(plist,5);SListPushFront(plist,6);SListPushFront(plist,7);SListPushFront(plist,8);SListPopFront(plist);SListPopFront(plist);SListPrint(plist);SListPopFront(plist);SListPopFront(plist);SListPrint(plist);SListPrint(plist);}intmain(){//test1();test2();return0;}查找、随机插入和删除// 单链表查找SLTNode*SListFind(SLTNode*plist,SLTDateType x);// 单链表在pos位置之后插入xvoidSListInsertAfter(SLTNode*pos,SLTDateType x);// 单链表删除pos位置之后的值voidSListEraseAfter(SLTNode*pos);为什么插入和删除都是在pos位置之后插入呢因为单链表只有next没有prev为了找到前驱只能从链表头开始遍历逐个比较节点地址直到找到 next pos 的节点。这个过程的时间复杂度是 O(n)其中 n 是链表长度。所以pos之前的插入就在带头双向循环链表里面去实现。// 单链表查找SLTNode*SListFind(SLTNode*plist,SLTDateType x){assert(plist);SLTNode*curplist;while(cur){if(cur-datax){returncur;}curcur-next;}returnNULL;}// 单链表在pos位置之后插入xvoidSListInsertAfter(SLTNode*pos,SLTDateType x){assert(pos);SLTNode*newNodeBuySListNode(x);SLTNode*nextpos-next;newNode-nextnext;pos-nextnewNode;}// 单链表删除pos位置之后的值voidSListEraseAfter(SLTNode*pos){assert(pos);assert(pos-next);SLTNode*delpos-next;pos-nextdel-next;free(del);delNULL;}为什么这里查找要一起实现呢因为这里的随机插入和删除我们这里是直接给pos的所以必须搭配我们这里的查找函数一起才能使用。如果想在pos位置之前删除其实还可以在插入和删除函数内部定义一个prev代码就是遍历插入/删除。有兴趣的可以去实现一下。测试一下上面实现的代码吧。voidtest3(){SLTNode*plistNULL;SListPushBack(plist,1);SListPushBack(plist,2);SListPushBack(plist,3);SListPushBack(plist,4);SListPrint(plist);// 值为2那个节点 *2SLTNode*retSListFind(plist,2);SListInsertAfter(ret,20);SListPrint(plist);SListEraseAfter(ret);SListPrint(plist);}intmain(){//test1();//test2();test3();return0;}完整代码#includeSList.hSLTNode*BuySListNode(SLTDateType x){SLTNode*newNode(SLTNode*)malloc(sizeof(SLTNode));if(newNodeNULL){perror(malloc fail);returnNULL;}newNode-datax;newNode-nextNULL;returnnewNode;}// 单链表尾插voidSListPushBack(SLTNode**pplist,SLTDateType x){assert(pplist);SLTNode*newNodeBuySListNode(x);if(*pplistNULL){*pplistnewNode;}else{// 找尾SLTNode*tail*pplist;while(tail-next!NULL){tailtail-next;}tail-nextnewNode;}}// 单链表的头插voidSListPushFront(SLTNode**pplist,SLTDateType x){assert(pplist);SLTNode*newNodeBuySListNode(x);newNode-next*pplist;*pplistnewNode;}// 单链表打印voidSListPrint(SLTNode*plist){SLTNode*currentplist;while(current){printf(%d-,current-data);currentcurrent-next;}printf(NULL\n);}// 单链表的尾删voidSListPopBack(SLTNode**pplist){assert(pplist);if((*pplist)-nextNULL){free(*pplist);*pplistNULL;}else{SLTNode*tail*pplist;while(tail-next-next!NULL){tailtail-next;}free(tail-next);tail-nextNULL;}}// 单链表头删voidSListPopFront(SLTNode**pplist){assert(pplist);SLTNode*cur*pplist;*pplistcur-next;free(cur);curNULL;}// 单链表查找SLTNode*SListFind(SLTNode*plist,SLTDateType x){assert(plist);SLTNode*curplist;while(cur){if(cur-datax){returncur;}curcur-next;}returnNULL;}// 单链表在pos位置之后插入xvoidSListInsertAfter(SLTNode*pos,SLTDateType x){assert(pos);SLTNode*newNodeBuySListNode(x);SLTNode*nextpos-next;newNode-nextnext;pos-nextnewNode;}// 单链表删除pos位置之后的值voidSListEraseAfter(SLTNode*pos){assert(pos);assert(pos-next);SLTNode*delpos-next;pos-nextdel-next;free(del);delNULL;}下一章节我们就要去实现带头双向循环链表了。完