数据结构与算法之《带头双向循环链表》详解
创始人
2024-06-02 12:32:37
0次

文章目录

一、带头双向循环链表概念及结构

1、1 带头双向循环链表的概念

1、2  带头双向循环链表的结构

二、带头双向循环链表的思路及代码实现详解

2、1 带头双向循环链表实现思路

2、2 带头双向循环链表的模块细节及代码实现

2、2、1 结构体的声明与定义

2、2、2 初始化结构体

2、2、3 打印链表数据

2、2、4 开辟节点

2、2、5 销毁链表

2、2、6 判断链表是否为空

2、2、7 头插

2、2、8 尾插

2、2、9 头删

2、2、10 尾删

2、2、11 查找结点

2、2、12 在pos位置前插入

2、2、13 删除pos位置节点

三、带头双向循环链表代码整合

QList.h

QList.c

test.c

标题：《链表》之带头双向循环链表

作者：@Ggggggtm

寄语：与其忙着诉苦，不如低头赶路，奋路前行，终将遇到一番好风景

    我们知道，链表实际上结构有很多种。我们大致可分为带头或者不带头、单向或者双向、循环或者非循环三种大类情况。而每种大类都可与其他类别组合形成新的一种结构，纵沟会有八种情况。  每种情况也是大同小异。其中常用的只有两种：无头单向非循环链表和带头双向循环链表。想要具体学习了解无头单向非循环链表可参考这篇文章：数据结构与算法之《单链表》详解。本篇文章会详细讲述带头双向循环链表。其实我们把最为常用的两篇文章掌握后，其他的链表结构也就很容易写出来了。

一、带头双向循环链表概念及结构

1、1 带头双向循环链表的概念

  我们学完无头单向非循环链表后，第一次见到带头双向循环链表感觉会很难，结构也很复杂。其实并不是这样的。带头双向循环链表甚至写起来和构思都十分简单。我们接着往下看就可以知道了。

  带头双向循环链表到底是个什么呢？如同正常链表一样，是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。无非结构上会有所差异，那我们来看一下结构带头双向循环链表的结构把。

1、2  带头双向循环链表的结构

  带头双向循环链表顾名思义，链表会有一个头节点（哨兵位），但是这个头节点不存储有效数据。同时，每个节点会有两个指针，一个指向后面的节点，另一个指向前面一个节点。循环的意思是尾结点指向头节点，头节点指向尾节点。如下图所示：  带头双向循环链表结构看上去很复杂，实现起来却很容易，我们接着往下看带头双向循环链表的实现。

二、带头双向循环链表的思路及代码实现详解

2、1 带头双向循环链表实现思路

  我们学习完无头单向非循环链表后，对带头双向循环链表理解上就会很简单。两者的实现思路大同小异。具体到每个模块细节的实现也是几乎相同的。我们先来看单链表整体思路分为多种不同的模块有哪几个：

  1. 定义一个结构体，该结构体包含一个可以存放数据的变量、一个能够指向下一个节点的指针和一个能够指向前面一个节点的指针。
  2. 初始化结构体。
  3. 打印链表数据。
  4. 开辟节点。
  5. 销毁链表。
  6. 判断链表是否为空。
  7. 头插。
  8. 尾插。
  9. 头删。
  10. 尾删。
  11. 查找节点。
  12. 任意位置插入。
  13. 任意位置删除。

   以上就是整个带头双向循环链表的不同模块，那我们接下来看一下不同模块思路及代码实现的细节吧。

2、2 带头双向循环链表的模块细节及代码实现

2、2、1 结构体的声明与定义

  上面我们提到，定义结构体时，该结构体包含一个可以存放数据的变量、一个能够指向下一个节点的指针和一个能够指向前面一个节点的指针。那么代码的实现就很简单了。

typedef int LNDataType;typedef struct DListNode
{struct DListNode* prev;struct DListNode* next;LNDataType data;
}LTNode;

2、2、2 初始化结构体

  初始化结构体的方式有很多种，在这里我们是先定义一个结构体指针为空，在对其进行初始化，这个时候我们要改变结构体指针的话，我们就需要传二级指针。我们在初始化时，此时链表中只有一个头节点，所以我们要头结点的next和prev都指向自己。我们看代码的实现。

LTNode* plist = NULL;
LTInit(&plist);void LTInit(LTNode** phead)
{(*phead) = BuyLTNode(-1);(*phead)->next = *phead;(*phead)->prev = *phead;
}

2、2、3 打印链表数据

  注意，带头双向循环链表可不是随便的遍历打印哦。带头双向循环链表是一个循环的结构，一但不加操作遍历，就会死循环。我们可以从头节点的下一个位置开始遍历，结束条件就是回到头节点。这样就解决问题了，我们结合代码理解一下：

void LTPrint(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;printf("<-head->");while (cur != phead){printf("%d<-->", cur->data);cur = cur->next;}printf("\n");
}

2、2、4 开辟节点

  这里为什么要把开辟节点单独里一个函数呢？在我们插入数据之前，不管是头插还是尾插，还是任意插入，我们都需要新开辟一个节点。然后把要插入的数据存储到新节点当中，然后进行连接即可。所以这里我们把开辟节点单独分为一个模块来解释。我们来看一下代码的是实现。  

LTNode* BuyLTNode(LNDataType x)
{LTNode* tmp = (LTNode*)malloc(sizeof(LTNode));if (tmp == NULL){perror("malloc fail");exit(-1);}tmp->data = x;tmp->next = NULL;tmp->prev = NULL;return tmp;
}

2、2、5 销毁链表

  因为链表是我们动态开辟出来的，所以我们要释放掉，避免空间泄露。销毁链表时，我们不只是释放头节点的空间，每个节点的空间都要释放。  

void LTDestory(LTNode** pphead)
{LTNode* cur = (*pphead)->next;while (cur != *pphead){LTNode* tmp = cur->next;free(cur);cur = tmp;}free(*pphead);*pphead = NULL;
}

2、2、6 判断链表是否为空

  判断链表为空的情况在我们后面对链表删除节点的时候需要的，所以这里我们单独列出一个函数，判断也较为简单，我们直接看代码。 

bool LTEmpty(LTNode* phead)
{assert(phead);return phead->next == phead;
}

2、2、7 头插

  在带头双向循环链表中，头插我们直接插入就行，并没什么特殊的情况。我们只需要把结构修改到位就行。我们看代码实现。

void LTPushFront(LTNode* phead, LNDataType x)
{assert(phead);LTNode* newnode = BuyLTNode(x);newnode->next = phead->next;phead->next->prev = newnode;phead->next = newnode;newnode->prev = phead;
}

2、2、8 尾插

  尾插同样也很简单。我们可以直接通过头节点phead的prev找到尾节点，然后直接连接截取就行。也无特殊情况。而在无头单向非循环链表中，我们不仅要遍历找尾节点，还要判断特使为空的情况。带头双向循环链表的头节点和双向循环的结构给我们带来了很大的便利。我们直接看代码的实现。

void LTPushBack(LTNode* phead, LNDataType x)
{assert(phead);LTNode* newnode = BuyLTNode(x);LTNode* tail=phead->prev;tail->next = newnode;newnode->prev = tail;newnode->next = phead;phead->prev = newnode;
}

2、2、9 头删

  在删除之前，我们应该首先判断链表中是否包含有效的节点（不包含头节点）。然后正常删除链接即可。我们看代码的实现。

void LTPopFront(LTNode* phead)
{assert(phead);assert(!LTEmpty(phead));LTNode* tmp = phead->next;phead->next = tmp->next;tmp->next->prev = phead;
}

2、2、10 尾删

  尾删的情况与头删的情况相似。同样，  在删除之前，我们应该首先判断链表中是否包含有效的节点（不包含头节点）。然后正常删除链接即可。我们看代码：

void LTPopFront(LTNode* phead)
{assert(phead);assert(!LTEmpty(phead));LTNode* tmp = phead->next;phead->next = tmp->next;tmp->next->prev = phead;free(tmp);
}

2、2、11 查找结点

  这里查找节点是为我们后面的任意插入和删除做铺垫，我们是需要在查找出的位置进行删除和插入操作。我们遍历查找的方法与上述打印查找的方法是一样的，避免陷入死循环。

LTNode* LTNodeFind(LTNode* phead, LNDataType x)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){if (cur->data == x)return cur;cur = cur->next;}return NULL;  // 找不到
}

2、2、12 在pos位置前插入

  在pos位置前插入和头插基本相同。我们在这里不过多解释，直接看代码。

void LTInsert(LTNode* pos, LNDataType x)
{assert(pos);LTNode* newnode = BuyLTNode(x);LTNode* prev = pos->prev;prev->next = newnode;newnode->prev = prev;newnode->next = pos;pos->prev = newnode;
}

2、2、13 删除pos位置节点

  删除pos位置节点与尾删也是大同小异，直接看代码：

void LTErase(LTNode* pos)
{assert(pos);LTNode* prev = pos->prev;prev->next = pos->next;pos->prev = prev;free(pos);
}

三、带头双向循环链表代码整合

  由于代码量相对来说有一点多，所以我们就将函数的声明的定义分开，这样有利于提高代码的可读性，同时会保持一个良好的思路，且方便编写代码。

  我们将函数的声明放在单独的一个QList.h的头文件，函数的实现放在一个单独的QList.c源文件，函数的主方法及调用放在另一个单独的test.c源文件。

QList.h

#define _CRT_SECURE_NO_WARNINGS 1#include
#include
#include
#includetypedef int LNDataType;typedef struct DListNode
{struct DListNode* prev;struct DListNode* next;LNDataType data;
}LTNode;LTNode* BuyLTNode(LNDataType x);
void LTInit(LTNode** phead);
void LTPrint(LTNode* phead);
void LTDestory(LTNode** phead);
bool LTEmpty(LTNode* phead);void LTPushBack(LTNode* phead, LNDataType x);
void LTPopBack(LTNode* phead);void LTPushFront(LTNode* phead, LNDataType x);
void LTPopFront(LTNode* phead);// 在pos前一个位置插入
LTNode* LTNodeFind(LTNode* pos, LNDataType x);
void LTInsert(LTNode* pos, LNDataType x);// 删除pos节点
void LTErase(LTNode* pos);

QList.c

#define _CRT_SECURE_NO_WARNINGS 1#include"Qlist.h"LTNode* BuyLTNode(LNDataType x)
{LTNode* tmp = (LTNode*)malloc(sizeof(LTNode));if (tmp == NULL){perror("malloc fail");exit(-1);}tmp->data = x;tmp->next = NULL;tmp->prev = NULL;return tmp;
}void LTInit(LTNode** phead)
{(*phead) = BuyLTNode(-1);(*phead)->next = *phead;(*phead)->prev = *phead;
}void LTPrint(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;printf("<-head->");while (cur != phead){printf("%d<-->", cur->data);cur = cur->next;}printf("\n");
}void LTDestory(LTNode** pphead)
{LTNode* cur = (*pphead)->next;while (cur != *pphead){LTNode* tmp = cur->next;free(cur);cur = tmp;}free(*pphead);*pphead = NULL;
}bool LTEmpty(LTNode* phead)
{assert(phead);return phead->next == phead;
}void LTPushBack(LTNode* phead, LNDataType x)
{assert(phead);LTNode* newnode = BuyLTNode(x);LTNode* tail=phead->prev;tail->next = newnode;newnode->prev = tail;newnode->next = phead;phead->prev = newnode;
}void LTPopBack(LTNode* phead)
{assert(phead);assert(!LTEmpty(phead));LTNode* tail = phead->prev;LTNode* tailprev = tail->prev;tailprev->next = phead;phead->prev = tailprev;free(tail);tail = NULL;
}void LTPushFront(LTNode* phead, LNDataType x)
{assert(phead);LTNode* newnode = BuyLTNode(x);newnode->next = phead->next;phead->next->prev = newnode;phead->next = newnode;newnode->prev = phead;
}void LTPopFront(LTNode* phead)
{assert(phead);assert(!LTEmpty(phead));LTNode* tmp = phead->next;phead->next = tmp->next;tmp->next->prev = phead;free(tmp);
}// pos位置插入
LTNode* LTNodeFind(LTNode* phead, LNDataType x)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){if (cur->data == x)return cur;cur = cur->next;}return NULL;
}
void LTInsert(LTNode* pos, LNDataType x)
{assert(pos);LTNode* newnode = BuyLTNode(x);LTNode* prev = pos->prev;prev->next = newnode;newnode->prev = prev;newnode->next = pos;pos->prev = newnode;
}
void LTErase(LTNode* pos)
{assert(pos);LTNode* prev = pos->prev;prev->next = pos->next;pos->prev = prev;free(pos);
}

test.c

#define _CRT_SECURE_NO_WARNINGS 1#include "Qlist.h"void TestNode()
{LTNode* plist = NULL;LTInit(&plist);LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPrint(plist);LTPopBack(plist);LTPrint(plist);LTPopBack(plist);LTPrint(plist);LTPopBack(plist);LTPrint(plist);LTPopBack(plist);LTPrint(plist);LTPushFront(plist, 1);LTPrint(plist);LTPushFront(plist, 2);LTPrint(plist);LTPushFront(plist, 3);LTPrint(plist);LTPushFront(plist, 4);LTPrint(plist);LTPushFront(plist, 5);LTPrint(plist);LTPopFront(plist);LTPrint(plist);LTPopFront(plist);LTPrint(plist);LTPopFront(plist);LTPrint(plist);LTPopFront(plist);LTPrint(plist);LTPopFront(plist);LTPrint(plist);LTDestory(&plist);
}
int main()
{TestNode();return 0;
}

  我们对带头双向循环链表的讲解就到这里，希望以上内容会对你有所帮助，感谢阅读ovo~

词库加载错误:未能找到文件“E:\highferrum_mysql\Configuration\Dict_Stopwords.txt”。

上一篇：AI 让梵高、维米尔、高更、比亚兹莱和莫迪利亚尼重画《蒙娜丽莎》？

下一篇：Flutter IOS 新建打包发布全流程 2023 版

相关内容

热门资讯

常用商务英语口语 　　商务英语是以适应职场生活的语言要求为目的，内容涉及到商务活动的方方面面。下面是小编收集的常用商务...
六年级上册英语第一单元练习题 　　一、根据要求写单词。　　1.dry（反义词）__________________　　2.writ...
复活节英文怎么说 复活节英文怎么说?复活节的英语翻译是什么?复活节：Easter;"Easter,anniversar...
2008年北京奥运会主题曲 2008年北京奥运会(第29届夏季奥林匹克运动会)，2008年8月8日到2008年8月24日在中华人...
英语道歉信 英语道歉信15篇　　在日常生活中，道歉信的使用频率越来越高，通过道歉信，我们可以更好地解释事情发生的...
六年级英语专题训练(连词成句... 六年级英语专题训练(连词成句30题)　　1. have,playhouse,many,I,toy,i...
上班迟到情况说明英语 　　每个人都或多或少的迟到过那么几次，因为各种原因，可能生病，可能因为交通堵车，可能是因为天气冷，有...
小学英语教学论文 小学英语教学论文范文　　引导语：英语教育一直都是每个家长所器重的，那么有关小学英语教学论文要怎么写呢...
英语口语学习必看的方法技巧 英语口语学习必看的方法技巧如何才能说流利的英语？ 说外语时，我们主要应做到四件事：理解、回答、提问、...
四级英语作文选:Birth ... 四级英语作文范文选:Birth controlSince the Chinese Governmen...
金融专业英语面试自我介绍 金融专业英语面试自我介绍3篇　　金融专业的学生面试时，面试官要求用英语做自我介绍该怎么说。下面是小编...
我的李老师走了四年级英语日记... 我的李老师走了四年级英语日记带翻译　　我上了五个学期的小学却换了六任老师，李老师是带我们班最长的语文...
小学三年级英语日记带翻译捡玉... 小学三年级英语日记带翻译捡玉米　　今天，我和妈妈去外婆家，外婆家有刚剥的`玉米棒上带有玉米籽，好大的...
七年级英语优秀教学设计 七年级英语优秀教学设计　　作为一位兢兢业业的人民教师，常常要写一份优秀的教学设计，教学设计是把教学原...
我的英语老师作文 我的英语老师作文（通用21篇）　　在日常生活或是工作学习中，大家都有写作文的经历，对作文很是熟悉吧，...
英语老师教学经验总结 英语老师教学经验总结（通用19篇）　　总结是指社会团体、企业单位和个人对某一阶段的学习、工作或其完成...
初一英语暑假作业答案 初一英语暑假作业答案　　英语练习一(基础训练)第一题1.D2.H3.E4.F5.I6.A7.J8.C...
大学生的英语演讲稿 大学生的英语演讲稿范文（精选10篇）　　使用正确的写作思路书写演讲稿会更加事半功倍。在现实社会中，越...
VOA美国之音英语学习网址 VOA美国之音英语学习推荐网址 美国之音网站已经成为语言学习最重要的资源站点，在互联网上还有若干网站...
商务英语期末试卷 Part I Term Translation (20%)Section A: Translate ...