数据结构与算法之《带头双向循环链表》详解

女爷i 2023-09-26 18:37 62阅读 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 ##
> 
> ## 寄语：与其忙着诉苦，不如低头赶路，奋路前行，终将遇到一番好风景 ##
> 
> ![56d9ecd434254b54a2b47d3ee029d491.png][]

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

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

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

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

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

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

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

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

### 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<assert.h>
    #include<stdio.h>
    #include<stdlib.h>
    #include<stdbool.h>
    
    typedef 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~

[56d9ecd434254b54a2b47d3ee029d491.png]: https://img-blog.csdnimg.cn/56d9ecd434254b54a2b47d3ee029d491.png
[a973ceb4c50e4a6388e59b3e28bb41bc.png]: https://img-blog.csdnimg.cn/a973ceb4c50e4a6388e59b3e28bb41bc.png
[Link 1]: https://blog.csdn.net/weixin_67596609/article/details/128046161
[7a0ec890fb184dfebea3c6bd0870d244.png]: https://img-blog.csdnimg.cn/7a0ec890fb184dfebea3c6bd0870d244.png