【数据结构从青铜到王者】第三篇:数据结构之双向带头循环链表

分手后的思念是犯贱 2023-01-15 11:22 87阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70_pic_center]

# 系列文章目录 #

--------------------

### 文章目录 ###

*  系列文章目录
 *  前言
 *  一、链表的概念及结构
 *   *   *  1.链表的概念
         *  2.双向带头循环链表结构
 *  二、双向带头循环链表实现
 *   *   *  1.定义链表节点struct ListNode
         *  2.创建链表节点BuyListNode函数
         *  3.链表初始化ListInit函数
         *  4.链表尾部插入数据ListPushBack函数
         *  5.链表头部插入数据ListPushFront函数
         *  6.链表尾部删除数据ListPopBack函数
         *  7.链表头部删除数据ListPopFront函数
         *  8.链表查找数据ListFind函数
         *  9.链表插入数据ListInsert函数
         *  10.链表删除数据ListEarse函数
         *  12.链表清空数据ListEmpty函数
         *  13.链表求解长度ListSize函数
         *  14.链表销毁ListDestory函数
         *  15.链表打印数据ListPrint函数
 *  总结

--------------------

# 前言 #

带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。

--------------------

![在这里插入图片描述][20210422142559791.png]

# 一、链表的概念及结构 #

### 1.链表的概念 ###

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。

### 2.双向带头循环链表结构 ###

![在这里插入图片描述][20210422142921329.png]

# 二、双向带头循环链表实现 #

### 1.定义链表节点struct ListNode ###

数据域data,指针域中包括指向前面节点的前驱指针prev，指向后面的后驱指针next  
代码如下：

typedef struct ListNode
    { 
    	LTDataType data;
    	struct ListNode* next;
    	struct ListNode* prev;
    };

### 2.创建链表节点BuyListNode函数 ###

代码如下：

struct ListNode* BuyListNode(LTDataType x)
    { 
    	struct ListNode* Node = (struct ListNode*)malloc(sizeof(struct ListNode));
    	Node->next = NULL;
    	Node->prev = NULL;
    	Node->data = x;
    	return Node;
    }

### 3.链表初始化ListInit函数 ###

代码如下：

struct ListNode* ListInit()
    { 
    	struct ListNode* phead = BuyListNode(0);
    	phead->next = phead;
    	phead->prev = phead;
    	return phead;
    }

### 4.链表尾部插入数据ListPushBack函数 ###

![在这里插入图片描述][20210422143634114.png]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70]  
代码如下：

void  ListPushBack(struct ListNode* phead, LTDataType x)
    { 
    	assert(phead);
    	struct ListNode* tail = phead->prev;
    	struct ListNode* newnode = BuyListNode(x);
    	tail->next = newnode;
    	newnode->prev = tail;
    	newnode->next = phead;
    	phead->prev = newnode;
    }

### 5.链表头部插入数据ListPushFront函数 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 1]  
代码如下：

void ListPushFront(struct ListNode* phead, LTDataType x)
    { 
    	assert(phead);
    	struct ListNode* newnode = BuyListNode(x);
    	struct ListNode* first = phead->next;
    	phead->next = newnode;
    	newnode->prev = phead;
    	newnode->next = first;
    	first->prev = newnode;
    }

### 6.链表尾部删除数据ListPopBack函数 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 2]  
代码如下：

void ListPopBack(struct ListNode* phead)
    { 
    	assert(phead);
    	assert(phead != phead->next);
    	struct ListNode* tail = phead->prev;
    	struct ListNode* second = tail->prev;
    	free(tail);
    	tail = NULL;
    	second->next = phead;
    	phead->prev = second;
    }

### 7.链表头部删除数据ListPopFront函数 ###

![在这里插入图片描述][20210422144048380.png]  
代码如下：

void ListPopFront(struct ListNode* phead)
    { 
    	assert(phead);
    	assert(phead != phead->next);
    	struct ListNode* first = phead->next;
    	struct ListNode* firstNext = first->next;
    	free(first);
    	first = NULL;
    	phead->next = firstNext;
    	first->prev = phead;
    }

### 8.链表查找数据ListFind函数 ###

代码如下：

struct ListNode* ListFind(struct ListNode* phead, LTDataType x)
    { 
    	assert(phead);
    	struct ListNode* cur = phead->next;
    	while (cur != phead)
    	{ 
    		if (cur->data == x)
    		{ 
    			return cur;
    		}
    		cur = cur->next;
    	}
    	return NULL;
    }

### 9.链表插入数据ListInsert函数 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 3]  
代码如下：

void ListInsert(struct ListNode* pos, LTDataType x)
    { 
    	assert(pos);
    	struct ListNode* newnode = BuyListNode(x);
    	struct ListNode* prev = pos->prev;
    	prev->next = newnode;
    	newnode->prev = prev;
    	newnode->next = pos;
    	pos->prev = newnode;
    }

### 10.链表删除数据ListEarse函数 ###

![在这里插入图片描述][20210422144315369.png]

代码如下：

void ListEarse(struct ListNode* pos)
    { 
    	assert(pos);
    	struct ListNode* prev = pos->prev;
    	struct ListNode* next = pos->next;
    	prev->next = next;
    	next->prev = prev;
    	free(pos);
    	pos = NULL;
    }

### 12.链表清空数据ListEmpty函数 ###

代码如下：

int ListEmpty(struct ListNode* phead)
    { 
    	assert(phead);
    	return phead->next == phead ? 1 : 0;
    }

### 13.链表求解长度ListSize函数 ###

代码如下：

int ListSize(struct ListNode* phead)
    { 
    	assert(phead);
    	int size = 0;
    	struct ListNode* cur = phead->next;
    	while (cur != phead)
    	{ 
    		size++;
    		cur = cur->next;
    	}
    	return size;
    }

### 14.链表销毁ListDestory函数 ###

代码如下：

void ListDestory(struct ListNode* phead)
    { 
    	assert(phead);
    	struct ListNode* cur = phead->next;
    	while (cur != phead)
    	{ 
    		struct ListNode* next = cur->next;
    		free(cur);
    		cur = next;
    	}
    	free(phead);
    	phead = NULL;
    }

### 15.链表打印数据ListPrint函数 ###

代码如下：

void ListPrint(struct ListNode* phead)
    { 
    	assert(phead);
    	struct ListNode* cur = phead->next;
    	while (cur != phead)
    	{ 
    		printf("%d-->", cur->data);
    		cur = cur->next;
    	}
    	printf("NULL\n");
    }

--------------------

# 总结 #

以上就是今天要讲的内容，本文仅仅简单介绍了双向带头循环链表的使用，带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，我们务必掌握。另外，如果有需要源码的私信我即可。还有，，如果上述有任何问题，请懂哥指教，不过没关系，主要是自己能坚持，更希望有一起学习的同学可以帮我指正，但是如果可以请温柔一点跟我讲，爱与和平是永远的主题，爱各位了。  
![在这里插入图片描述][20210422144652969.png_pic_center]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70_pic_center]: /images/20221022/bb190b5f630b4b48af619be1276f5b72.png
[20210422142559791.png]: /images/20221022/0dd913dab43d484687cc162e276ef35a.png
[20210422142921329.png]: /images/20221022/75b4818382f242a084f7df194f27501b.png
[20210422143634114.png]: /images/20221022/2e9eda8ab62f42fea43637a50a8f9f12.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70]: /images/20221022/bc8de1da249e4277b90f8fb8596444ec.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 1]: /images/20221022/d357483469f64cf49466eeeb7ade852f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 2]: /images/20221022/bc7eb9eae8564cf0b88294feeeebe871.png
[20210422144048380.png]: /images/20221022/255bdbe37030448693c3d696b9a6e95a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 3]: /images/20221022/92ce0920f5c04722b978f1db41a85d31.png
[20210422144315369.png]: /images/20221022/1ea513fb72424a089170f98823782345.png
[20210422144652969.png_pic_center]: /images/20221022/e56c0faa5fdd48f398f93d9abbb1da5a.png