鄂州市住房和城乡建设部网站长沙网站建设建

当前位置： 首页 > news >正文

鄂州市住房和城乡建设部网站,长沙网站建设建,网站目录编辑审核的注意事项,互联网产品运营文章目录 前言双向链表的结构功能的解析及实现1. 双向链表的创建2. 创建头节点#xff08;初始化#xff09;3. 创建新结点4. 尾插5. 尾删6. 头插7. 头删8. 查找9. 在pos位置前插入10. 删除pos位置的结点11. 销毁 代码实现1.ListNode.h2. ListNode.c3. test.c 总结 前言 前面… 文章目录 前言双向链表的结构功能的解析及实现1. 双向链表的创建2. 创建头节点初始化3. 创建新结点4. 尾插5. 尾删6. 头插7. 头删8. 查找9. 在pos位置前插入10. 删除pos位置的结点11. 销毁 代码实现1.ListNode.h2. ListNode.c3. test.c 总结 前言 前面我们学习了单链表的实现我们发现它在进行从后往前查找的时候有很大的不便为了解决这个问题双向链表油然而生。它可以很好的解决单链表无法从后往前查找的困难。 双向链表的结构 如图所示它是有两个指针域一个指向后一个结点一个指向前一个结点。它存储了前一个结点的地址与后一个结点的地址所以可以很方便的进行向前遍历或者向后遍历。同时它还是一个循环链表可以通过第一个结点直接找到最后一个结点。 功能的解析及实现

1. 双向链表的创建 就像前文所说它包含了两个指针域和一个数据域用来存放它前一个结点的地址和后一个结点的地址以及本身的数据。 typedef struct LTNode {LTDataType data;struct LTNode* prev;struct LTNode* next; }LTNode;2. 创建头节点初始化 此次双向链表的结构我是采用了带头结点的结构好处就是头节点是malloc出来的是在堆区上存放不会因为出了函数就被销毁也意味着后续的各种操作我们只需要传递一级指针就会有实现单链表时传递二级指针的效果。 LTNode* ListInit() {LTNode* phead (LTNode)malloc(sizeof(LTNode));if (phead NULL){return NULL;}phead-prev phead;phead-next phead;return phead; }3. 创建新结点 每次插入新的数据都需要开辟新的结点因此把它单独拿出来放到一个函数中实现。 LTNode BuyListNode(LTDataType x) {LTNode* newnode (LTNode)malloc(sizeof(LTNode));if (newnode NULL){return NULL;}newnode-data x;newnode-prev NULL;newnode-next NULL;return newnode; }4. 尾插 因为是循环链表我们可以通过第一个头节点直接找到尾结点而在连接的时候需要将新结点分别连接到头节点的prev以及尾结点的next同时自身的prev存放尾结点的地址next存放头节点的地址。如图
   void ListPushBack(LTNode phead, LTDataType x) {assert(phead);LTNode* tail phead-prev;LTNode* newnode BuyListNode(x);newnode-data x;newnode-next phead;phead-prev newnode;newnode-prev tail;tail-next newnode; }5. 尾删 在创建头节点时我们是将头节点的prev与next都指向了它自身因此我们可以通过头节点的next指向的是不是自身来判断是否为存放了数据。(头节点自身不存放数据)。与尾插类似如图
   void ListPopBack(LTNode* phead) {assert(phead);if (phead-next phead)//判断链表是否存放了数据{return;}LTNode* tail phead-prev;LTNode* prev tail-prev;prev-next phead;phead-prev prev;free(tail);tail NULL; }6. 头插 与尾插类似只不过这个放到了最前面。在尾插是我们是有tail与phead来与新结点连接头插也一样。先保存当前的第一个结点地址然后再将新结点连接到头节点与原第一个结点的中间即可。 void ListPushFront(LTNode* phead, LTDataType x) {assert(phead);LTNode* next phead-next;//保存当前的第一个结点地址LTNode* newnode BuyListNode(x);newnode-prev phead;phead-next newnode;newnode-next next;next-prev newnode; }7. 头删 我们只需要保存第一个结点与第二节结点的地址然后在将第二个与头节点连接再释放掉第一个结点即可。同时还需要判断链表是否为空(即有没有元素存放其中)。 void ListPopFront(LTNode* phead) {//assert(phead-next ! phead); //暴力解决//温和解决if (phead-next phead){return;}LTNode* prev phead-next;LTNode* next prev-next;phead-next next;next-prev phead;free(prev);prev NULL; }8. 查找 依次遍历链表即可从phead开始一直到再次遇到phead结束循环链表。 LTNode* ListFind(LTNode* phead, LTDataType x) {LTNode* cur phead-next;while (cur ! phead){if (cur-data x){return cur;}cur cur-next;}printf(该元素不存在\n);return NULL; }9. 在pos位置前插入 与头插相似这里只需要用prev保存pos位置的前一个结点地址然后将新结点与prev与pos相连接即可。 void ListInsert(LTNode* pos, LTDataType x) {LTNode* prevPos pos-prev;LTNode* newnode BuyListNode(x);newnode-next pos;pos-prev newnode;newnode-prev prevPos;prevPos-next newnode; }10. 删除pos位置的结点 保存pos的前一个结点地址与后一个结点地址然后将彼此相连接然后free掉pos结点就完成了。 void ListErase(LTNode* pos) {LTNode* nextPos pos-next;LTNode* prevPos pos-prev;nextPos-prev prevPos;prevPos-next nextPos;free(pos);pos NULL; }11. 销毁 动态开辟的结点在最后结束时都需要进行释放防止出现内存泄漏。用cur保存当前准备要释放的结点用next保存cur的下一个结点释放完cur后再将cur指向next进行循环。 void ListDestroy(LTNode* phead) {LTNode* cur phead;LTNode* next cur-next;while (cur){free(cur);cur NULL;if (cur ! NULL){cur next;next next-next;}} }代码实现 1.ListNode.h #pragma once #includestdio.h #includeassert.h #includestdlib.htypedef int LTDataType;typedef struct LTNode {LTDataType data;struct LTNode* prev;struct LTNode* next; }LTNode;// 创建返回链表的头结点. LTNode* ListInit();// 双向链表销毁 void ListDestroy(LTNode* phead);// 双向链表打印 void ListPrint(LTNode* phead);// 双向链表尾插 void ListPushBack(LTNode* phead, LTDataType x);// 双向链表尾删 void ListPopBack(LTNode* phead);// 双向链表头插 void ListPushFront(LTNode* phead, LTDataType x);// 双向链表头删 void ListPopFront(LTNode* phead);// 双向链表查找 LTNode* ListFind(LTNode* phead, LTDataType x);// 双向链表在pos的前面进行插入 void ListInsert(LTNode* pos, LTDataType x);// 双向链表删除pos位置的节点 void ListErase(LTNode* pos);2. ListNode.c #includeListNode.hLTNode* BuyListNode(LTDataType x) {LTNode* newnode (LTNode)malloc(sizeof(LTNode));if (newnode NULL){return NULL;}newnode-data x;newnode-prev NULL;newnode-next NULL;return newnode; } LTNode ListInit() {LTNode* phead (LTNode)malloc(sizeof(LTNode));if (phead NULL){return NULL;}phead-prev phead;phead-next phead;return phead; }void ListPushBack(LTNode phead, LTDataType x) {assert(phead);LTNode* tail phead-prev;LTNode* newnode BuyListNode(x);newnode-data x;newnode-next phead;phead-prev newnode;newnode-prev tail;tail-next newnode; }void ListPrint(LTNode* phead) {LTNode* cur phead-next;while (cur ! phead){printf(%d , cur-data);cur cur-next;}printf(\n); }void ListPopBack(LTNode* phead) {assert(phead);if (phead-next phead){return;}LTNode* tail phead-prev;LTNode* prev tail-prev;prev-next phead;phead-prev prev;free(tail);tail NULL; }void ListPushFront(LTNode* phead, LTDataType x) {assert(phead);LTNode* next phead-next;LTNode* newnode BuyListNode(x);newnode-prev phead;phead-next newnode;newnode-next next;next-prev newnode; }void ListPopFront(LTNode* phead) {//assert(phead-next ! phead); //暴力解决//温和解决if (phead-next phead){return;}LTNode* prev phead-next;LTNode* next prev-next;phead-next next;next-prev phead;free(prev);prev NULL; }LTNode* ListFind(LTNode* phead, LTDataType x) {LTNode* cur phead-next;while (cur ! phead){if (cur-data x){return cur;}cur cur-next;}printf(该元素不存在\n);return NULL; }void ListInsert(LTNode* pos, LTDataType x) {LTNode* prevPos pos-prev;LTNode* newnode BuyListNode(x);newnode-next pos;pos-prev newnode;newnode-prev prevPos;prevPos-next newnode; }void ListErase(LTNode* pos) {LTNode* nextPos pos-next;LTNode* prevPos pos-prev;nextPos-prev prevPos;prevPos-next nextPos;free(pos);pos NULL; }void ListDestroy(LTNode* phead) {LTNode* cur phead;LTNode* next cur-next;while (cur){free(cur);cur NULL;if (cur ! NULL){cur next;next next-next;}} }3. test.c #includeListNode.hvoid test() {LTNode* phead ListInit();if (phead NULL){return;}ListPushBack(phead, 1);//测试:尾插ListPushBack(phead, 2);ListPushBack(phead, 3);ListPushBack(phead, 4);ListPrint(phead);ListPopBack(phead);//测试:尾删ListPopBack(phead);ListPopBack(phead);ListPrint(phead);ListPopBack(phead);//测试:如果链表为空继续删除会不会报错ListPopBack(phead);ListPushBack(phead, 1);//尾插一个数据来对比头插ListPushFront(phead, 1);//测试:头插ListPushFront(phead, 2);ListPushFront(phead, 3);ListPushFront(phead, 4);ListPrint(phead);ListPopFront(phead);//测试:头删ListPopFront(phead);ListPopFront(phead);ListPrint(phead);ListPopFront(phead);//测试:如果链表删除完毕继续删除会不会报错ListPopFront(phead);ListPopFront(phead);ListPrint(phead);ListPushBack(phead, 1);//插入新元素进行后续测试ListPushBack(phead, 2);ListPushBack(phead, 3);ListPushBack(phead, 4);ListPrint(phead);ListFind(phead, 5);LTNode* pos ListFind(phead, 2);//测试:在2前面插入数字5ListInsert(pos, 5);ListPrint(phead);pos ListFind(phead, 2);//测试:删除结点2ListErase(pos);ListPrint(phead);ListDestroy(phead);//测试:销毁链表 }int main() {test();return 0; }总结 总体而言难度不大并且双向链表解决了单链表的很多问题值得好好学习一下。并且在这里总结一下数据结构中形参能对实参产生影响的三种方式二级指针头节点在堆区返回值。   双向循环链表就先告一段落了如果发现文章哪里有问题可以在评论区提出来或者私信我嗷。接下来我会继续学习栈与队列开启新的篇章那么本期就到此结束让我们下期再见觉得不错可以点个赞以示鼓励喔