我们不仅仅做网站更懂得网络营销网站建设与行政管理

我们不仅仅做网站更懂得网络营销,网站建设与行政管理,浏览器网页版打开网页,景县网址建站1.链表的分类如图所示#xff0c;链表具有以下不同特征#xff0c;所以有2*2*28种不同的链表。在上一篇文章中我们介绍的是单链表#xff0c;Technically speaking,单向不带头不循环链表这次我们就要来实现一下双向带头循环链表。2.双向链表的具体实现我实在是太懒了#x…1.链表的分类如图所示链表具有以下不同特征所以有2*2*28种不同的链表。在上一篇文章中我们介绍的是单链表Technically speaking,单向不带头不循环链表这次我们就要来实现一下双向带头循环链表。2.双向链表的具体实现我实在是太懒了还是跟前面单链表和顺序表一样要用两个.c文件一个.h文件不多说了。双向链表的一个节点中包含三部分1.存储的数据2.指向下个节点的指针3.指向前一个节点的指针。用图表就是这样1初始化LTNode** pphead /LTNode* LTInit()第一种方法显而易见因为形参要对实参的改变做出影响所以需要传地址。第二种方法呢后面我们再介绍为什么要用。初始化的时候需要创建一个新节点也就是要动态开辟空间这就涉及到了第二个函数LTNode* LTBuyNode(LTDataType x)大体还是与之前单链表开辟空间大差不差一样要判断空间是否开辟成功然后将数据x存储在节点的data中但这里新开辟节点的两个指针都要指向本身而不能置为NULL因为我们要创建的是循环链表如果置为NULL就无法做到循环而如果指向自己则后面就可以通过插入数据实现循环效果这就是新开辟出来的节点的效果当然因为第一个开辟的节点是哨兵位不存储任何有效数据。在监视窗口中就可以清晰的看到plist已经有一个哨兵位节点next,prev指针均指向自己初始化步骤完成。最后跟大家区分一个点链表为空代表链表中没有有效节点也就是只有一个哨兵位节点而链表无效证明连哨兵位都没有这俩并不对等。2尾插void LTPushBack(LTNode* phead, LTDataType x);首先来画个图理解一下先开辟一个newnode节点并调整newnode中两个指针的指向,确保原链表不受影响。1.newnode此时的下个节点为哨兵位(newnode-nexthead)2.原来的尾节点d3的下一个节点调整为为newnode(newnode-prevhead-prev其中head-prev表示原先的尾节点)接下来调整剩下的两个指针1.让原先尾节点d3指向下个节点的指针现在指向newnode(head-prev-nextnewnode,其中head-prev表示原先的尾节点)2.哨兵位的上一个节点要调整为newnodehead-prevnewnode尾插代码完成进行测试前需要再写一个打印链表的函数与单链表基本一致断言链表有效且链表不为空定义pcur指向哨兵位的下一个节点也就是第一个有效节点而循环则是在pcur遍历到哨兵位时结束。打印结果尾插成功。3头插void LTPushFront(LTNode* phead, LTDataType x);头插并不是插在哨兵位之前否则就与尾插相同了头插是指插在哨兵位之后一个节点。参考尾插先改变newnode节点中的指针1.newnode的下个节点调整为d1(newnode-nexthead-nexthead-next即d1)2.newnode的前一个节点为哨兵位(newnode-prevhead)然后再改变指向newnode的指针1.哨兵位的下个节点为newnode(head-nextnewnode)2.d1的前一个节点为newnode(newnode-next-prevnewnode此时newnode-next就是d1节点)根据上述思路写出代码即可。测试成功。4尾删void LTPopBack(LTNode* phead);还是先看图为了方便理解定义del指针指向双向链表的尾节点防止后面要删除的节点丢失。1.哨兵位上一个节点为尾节点的前一个节点(head-prevdel-prev)2.尾节点的前一个节点此时指向哨兵位(del-prev-nexthead,del-prev即为尾节点的前一个节点)3.最后释放del指针指向的节点并手动置NULL测试5头删void LTPopFront(LTNode* phead);其实还是改变几个指针的指向断言链表有效且链表不为空。1.修改哨兵位的下一个节点为d2(head-nextdel-next)2.d2的前一个节点修改为哨兵位(del-next-prevhead此时del-next为d2)测试6查找LTNode*LTFind(LTNodephead,LTDataType x);不过多赘述断言遍历即可实现若找到则返回指向节点的指针若未找到则返回NULL。7插入void LTInsert(LTNode* pos, LTDataType x);利用查找时返回的下标(pos)实现这个功能还是一步步梳理改变的指针指向如图先改变插入的节点newnode中的两个指针的指向1.newnode的下一个节点是原先pos的下一个节点d3(newnode-nextpos-next)2.newnode的前一个节点是pos(newnode-prevpos)再改变指向newnode的两个指针(下面两行代码的顺序不能调换)1.d3的前一个节点要修改为newnode(pos-next-prevnewnode这里pos-next即为d3)2.pos的下一个节点是newnode(pos-nextnewnode)实现并测试完成。8删除指定位置void LTErase(LTNode* pos);处理与pos有关的四个指针1..d3指向上个节点的指针现在指向d1(pos-next-prevpos-prevpos-next即为d3)2.d1中指向下个节点的指针现在要指向pos的下个节点d3(pos-prev-nextpos-nextpos-prev即为d1)3.释放pos节点并置为NULL9销毁void LTDestroy(LTNode* phead);说到这里了还记得前面初始化的时候提到的另一种方法吗LTNode* LTInit()这种初始化与前面相比更好因为能够更好的保持接口一致性。也就是传递的都是一级指针就无需做区分。因此我们可采用这种返回节点的初始化方式更加清晰。那么说回销毁也是遍历然后释放节点即可。不过这里有些巧妙的是定义pcur遍历链表但是在循环内定义了一个next指针每次都指向pcur的下一个节点而释放完pcur节点后pcur会走到Next的位置还是比较巧妙的。最后pcur走到哨兵位跳出循环但是哨兵位还未被销毁因此还要再销毁一次。还没有结束因为我们传的是一级指针实参还要手动置为空验证一下监视中显示此时数据都被销毁而最后一步置空即可。这就是双向链表实现的全过程我发现不用遍历链表还是比较爽的。又要爽爽写高数和线代了