[数据结构与算法]C语言实现双向循环带哨兵链表

📋 个人简介

• 💖 作者简介：大家好，我是菀枯😜

• 🎉 支持我：点赞👍+收藏??+留言📝

• 💬格言：不要在低谷沉沦自己，不要在高峰上放弃努力！??

  

前言

上次我们用C语言实现了，单链表。但是单链表也存在着一些问题。

1. 只能单向遍历
2. 添加或删除元素时，情况多样，需要分别处理这些情况

为了解决上面的问题呢，这次我们就用C语言来实现一个带哨兵位的双向循环链表.

话不多说。

代码模块

头文件

1. 包含的标准库

   include <stdio.h>
   include <stdlib.h>
   include <assert.h>
   

2. 定义节点

   既然是双向链表，所以节点里面需要有两个指针，一个指向前面的节点，一个指向后面的节点

   typedef int LDateType;//链表中存储的数据类型
   typedef struct ListNode
   {
   	LDateType val;
   	struct ListNode* next; //指向后一个元素
   	struct ListNode* pre; //指向前一个元素
   }ListNode;
   
   

3. 声明函数

   ListNode* ListCreat();
   // 链表的创建
   ListNode* BuyListNode(LDateType x);
   // 节点的创建
   void ListDestory(ListNode** pphead);
   // 链表的销毁
   void ListPrint(ListNode* pHead);
   // 遍历链表
   void ListPushBack(ListNode* pHead, LDateType x);
   // 在链表尾部添加节点
   void ListPopBack(ListNode* pHead);
   // 删除链表尾部的节点
   void ListPushFront(ListNode* phead, LDateType x);
   // 在链表首部插入一个节点
   void ListPopFront(ListNode* phead);
   // 在链表头部删除一个节点
   ListNode* ListFind(ListNode* pHead, LDateType x);
   // 在链表中寻找一个节点的位置
   void ListInsert(ListNode* pos, LDateType x);
   // 在某个位置前插入一个节点
   void ListErase(ListNode* pos);
   // 删除位置节点
   

函数模块

链表的创建

和上一次创建单链表不同，这一次我们创建的链表是带哨兵节点的，所以不能直接将头指针赋值为空指针，而是需要给他一个节点作为哨兵节点??

ListNode* ListCreat()
{
 ListNode* phead = (ListNode*)malloc(sizeof(ListNode));
 if (NULL == phead)
 {
 	printf("malloc error\n");
 	exit(-1);
 }
 phead->next = phead;
 phead->pre = phead;
 //形成循环
 return phead;
}

遍历链表

与上次创建单链表不同，当时我们只需要找到空指针就可以结束循环，遍历完整个链表。而这次的链表为循环链表，链表中没有NULL，那么该怎么停止循环呢？

这个时候我们就可以用到我们之前设计的哨兵节点了，当找到哨兵节点的时候就可以停止循环了

void ListPrint(ListNode* pHead)
{
 assert(pHead);
 ListNode* cur = pHead->next;
 while (cur != pHead)
 {
 	printf("%d->", cur->val);
 	cur = cur->next;
 }
}

链表的头插

创建一个新的节点，然后让哨兵节点指向这个新的节点，然后新节点指向原来的第一个节点就可以了。?（详解请看代码以及动画 ）

void ListPushFront(ListNode* pHead, LDateType x)
{
 assert(pHead);

 ListNode* newNode = BuyListNode(x);//新节点
 ListNode* next = pHead->next;

 pHead->next = newNode;
 newNode->pre = pHead;
 newNode->next = next;
 next->pre = newNode;
}

链表的头删

刚刚写完了头插，让我们来看看头删，其实也非常简单👍(一定要防止哨兵节点被删除)

void ListPopFront(ListNode* pHead)
{
	assert(pHead);

	if (pHead->next == pHead)	//防止哨兵节点被删除
	{
		return;
	}
	ListNode* cur = pHead->next;
	ListNode* next = cur->next;

	next->pre = pHead;
	pHead->next = next;
	free(cur);
}

链表的尾插

比起前面的单链表，双向循环链表的尾插就要简单多了，不用和以前一样去一个一个变遍历，我们之间就可以找到链表的尾。👏

void ListPushBack(ListNode* pHead, LDateType x)
{
	assert(pHead);

	ListNode* newNode = BuyListNode(x);//新节点
	ListNode* tail = pHead->pre;

	newNode->pre = tail;
	tail->next = newNode;
	newNode->next = pHead;//使链表成环
	pHead->pre = newNode;
}

链表的尾删

通过phead->pre找到尾，然后创建一个pre指针指向tail的前一个节点，防止删除tail后找不到pre，然后删除即可。

void ListPopBack(ListNode* pHead)
{
	assert(pHead);
	if (pHead->next == pHead)//防止哨兵节点被删除
	{
		return;
	}

	ListNode* tail = pHead->pre;
	ListNode* pre = tail->pre;
	pre->next = pHead;
	pHead->pre = pre;
	free(tail);
}

指定位置插入节点

我们只需要用ListFind函数找到需要插入元素的位置，然后插入节点即可

void ListInsert(ListNode* pos/*插入位置*/, LDateType x)
{
	if (NULL == pos) //防止pos为空指针
	{
		return;
	}
	
	ListNode* newNode = BuyListNode(x);
	ListNode* pre = pos->pre;

	newNode->next = pos;
	newNode->pre = pre;
	pre->next = newNode;
	pos->pre = newNode;
}

删除指定位置的节点

只需要找到位置，然后改变此位置的前一个节点和后一个节点的链接即可

void ListErase(ListNode* pos)
{
	if (NULL == pos)
	{
		return;
	}

	ListNode* pre = pos->pre;
	ListNode* next = pos->next;
	
	pre->next = next;
	next->pre = pre;
	free(pos);
}

链表的销毁

销毁和前面的函数都不同，因为我们需要对头指针进行修改，所以需要给函数传递二级指针。代码如下：

void ListDestory(ListNode** pphead)
{
	assert(*pphead);

	ListNode* cur = (*pphead)->next;
	while (cur != *pphead) //指针不等于哨兵节点
	{
		(*pphead)->next = cur->next;
		free(cur);
		cur = (*pphead)->next;
	}
	free(*pphead);
	*pphead = NULL;
}

这样我们就成功把这个链表销毁了。

完整代码

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int LDateType;
typedef struct ListNode
{
	LDateType val;
	struct ListNode* next;
	struct ListNode* pre;
}ListNode;

ListNode* ListCreat()
{
	ListNode* phead = (ListNode*)malloc(sizeof(ListNode));
	if (NULL == phead)
	{
		printf("malloc error\n");
		exit(-1);
	}
	phead->next = phead;
	phead->pre = phead;
	return phead;
}

void ListPrint(ListNode* pHead)
{
	assert(pHead);
	ListNode* cur = pHead->next;
	while (cur != pHead)
	{
		printf("%d->", cur->val);
		cur = cur->next;
	}
}

ListNode* BuyListNode(LDateType x)
{
	ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
	if (NULL == newNode)
	{
		printf("malloc error\n");
		exit(-1);
	}
	newNode->val = x;
	return newNode;
}

void ListPushBack(ListNode* pHead, LDateType x)
{
	assert(pHead);

	ListNode* newNode = BuyListNode(x);
	ListNode* tail = pHead->pre;

	newNode->pre = tail;
	tail->next = newNode;
	newNode->next = pHead;
	pHead->pre = newNode;
}

void ListPopBack(ListNode* pHead)
{
	assert(pHead);
	if (pHead->next == pHead)
	{
		return;
	}

	ListNode* tail = pHead->pre;
	ListNode* pre = tail->pre;
	pre->next = pHead;
	pHead->pre = pre;
	free(tail);
}

void ListPushFront(ListNode* pHead, LDateType x)
{
	assert(pHead);

	ListNode* newNode = BuyListNode(x);
	ListNode* next = pHead->next;

	pHead->next = newNode;
	newNode->pre = pHead;
	newNode->next = next;
	next->pre = newNode;
}

void ListPopFront(ListNode* pHead)
{
	assert(pHead);

	if (pHead->next == pHead)	//防止哨兵节点被删除
	{
		return;
	}
	ListNode* cur = pHead->next;
	ListNode* next = cur->next;

	next->pre = pHead;
	pHead->next = next;
	free(cur);
}

ListNode* ListFind(ListNode* pHead, LDateType x)
{
	assert(pHead);
	
	ListNode* cur = pHead->next;
	while (cur != pHead)
	{
		if (cur->val == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	printf("未找到\n");
	return NULL;
}

void ListInsert(ListNode* pos, LDateType x)
{
	if (NULL == pos)
	{
		return;
	}
	
	ListNode* newNode = BuyListNode(x);
	ListNode* pre = pos->pre;

	newNode->next = pos;
	newNode->pre = pre;
	pre->next = newNode;
	pos->pre = newNode;
}


void ListErase(ListNode* pos)
{
	if (NULL == pos)
	{
		return;
	}

	ListNode* pre = pos->pre;
	ListNode* next = pos->next;
	
	pre->next = next;
	next->pre = pre;
	free(pos);
}

void ListDestory(ListNode** pphead)
{
	assert(*pphead);

	ListNode* cur = (*pphead)->next;
	while (cur != *pphead)
	{
		(*pphead)->next = cur->next;
		free(cur);
		cur = (*pphead)->next;
	}
	*pphead = NULL;
}

结语

欢迎各位参考与指导！！！