您现在的位置是：首页 >技术教程 >带头双向循环链表--数据结构网站首页技术教程

带头双向循环链表--数据结构

大魔王（已黑化） 2023-06-20 04:00:02
简介带头双向循环链表--数据结构

在这里插入图片描述

  • 魔王的介绍：😶‍🌫️一名双非本科大一小白。
  • 魔王的目标：🤯努力赶上周围卷王的脚步。
  • 魔王的主页：🔥🔥🔥大魔王.🔥🔥🔥请添加图片描述
    ❤️‍🔥大魔王与你分享：樱花掉落的速度是五厘米 那么两颗心需要多久才能靠近——《秒速五厘米》

文章目录

前言

带头双向循环链表是性能非常好的线性表，它在增删查改时不需要很多其他操作，直接就可以进行，虽然实现比其他复杂，但是如果和用起来相比，那双向链表肯定是舒服的，本篇将讲述带头双向循环链表的实现。

  • 本篇链表为双向带头循环链表，所以会用到哨兵位头节点，哨兵位头节点只会用到前（最后一个结点地址）后（第二个结点，也就是存储数据的第一个结点）结点地址，所以只存储前后结点地址，该位置的数据成员不会用到，所以可以给随机值。
  • 哨兵位头结点最大的优势就是不需要动不动就判度是否为空这种分情况，它使得为空和不为空都能用一个代码。看完本篇你会了解到哨兵位头结点的方便。

在这里插入图片描述

一、创建结点的结构体

我们需要让每个结点有三个结构体成员：前后结点地址和存储数据的成员。

//重命名数据类型
typedef int ListNodeDate;

//创建结点的结构体并重命名
typedef struct ListNode
{
	struct ListNode* next;
	struct ListNode* prev;
	ListNodeDate date;
}ListNode;

二、创建新结点

每次增加结点，都需要创建一个新节点（哨兵位头节点也是这样，只不过需要特殊初始化，下面会写）。

//创建新节点
ListNode* BuyNewnode(ListNodeDate x)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	newnode->next = NULL;
	newnode->prev = NULL;
	newnode->date = x;
	return newnode;
}

三、初始化双向链表（创建哨兵位头节点）

哨兵位头节点也是结点，需要先调用上面的创建新结点函数，然后再进行特殊的初始化：因为是双向循环链表，所以要让里面存的两个地址都指向自己，这样才能循环，即使没有其他结点。

//初始化双向链表（创建哨兵位头节点）
ListNode* InitListNode()
{
	ListNode* phead = BuyNewnode(-1);
	phead->prev = phead;
	phead->next = phead;
	return phead;
}

四、双链表销毁

创建了链表，而且是动态开辟的，那肯定要手动释放，当我们弄完时手动释放申请的空间。

//双链表的销毁
void DestoryListNode(ListNode* phead)
{
	assert(phead);
	ListNode* cur = phead->next;
	ListNode* next = NULL;
	while (cur!=phead)
	{
		next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
}
  • 注意出函数后要让指针指向空，因为指向已经释放了，所以是野指针。因为传的是自己（一级指针），而不是自己的指针（二级指针），所以在函数里无法改变实参，只能出函数后再改变指向位置。

五、判断链表是否为空

后面删除元素我们需要先判断是否为空，如果为空（也就是只有哨兵位头结点，没有存储数据的结点），那就没有删除的必要了。

//判断双向链表是否为空（只有哨兵位头节点）
bool EmptyListNode(ListNode* phead)
{
	if (phead->next == phead)
	{
		return true;
	}
	else
		return false;
}

六、双向链表打印

为了验证代码的正确性，需要打印出来看。
打印：从哨兵位头结点指向的下一个结点的数据成员开始打印，直到地址又等于哨兵位头结点，结束。

//双向链表打印
void PrintListNode(ListNode* phead)
{
	assert(phead);
	ListNode* cur = phead->next; 
	while (cur != phead)
	{
		if (cur == phead->next)
			printf("<=>");
		printf("%d<=>",cur->date);
		cur = cur->next;
	}
}

七、双向链表尾插

尾插很简单，直接改变尾部结点、尾插的节点、哨兵位头结点三者之间的指向关系就OK了。

//双向链表尾插
void PushBackListNode(ListNode* phead, ListNodeDate x)
{
	assert(phead);
	ListNode* tail = phead->prev;
	ListNode* newnode = BuyNewnode(x);
	tail->next = newnode;
	newnode->prev = tail;
	phead->prev = newnode;
	newnode->next = phead;
}

八、双向链表尾删

首先判断是否为空，然后开始删，记着释放删除结点的空间。

//双向链表尾删
void PopBackListNode(ListNode* phead)
{
	assert(phead);
	assert(!EmptyListNode(phead));
	ListNode* newtail = phead->prev->prev;
	free(phead->prev);
	newtail->next = phead;
	phead->prev = newtail;
}

九、双向链表头插

改变哨兵位头结点、插入节点和第二个结点的指向关系。

//双向链表头插
void PushFrontListNode(ListNode* phead,ListNodeDate x)
{
	assert(phead);
	ListNode* plist = phead;
	ListNode* newnode = BuyNewnode(x);	
	newnode->next = plist->next;
	newnode->prev = plist;
	plist->next->prev = newnode;
	plist->next = newnode;
}

十、双向链表头删

首先判断是否为空，然后就是改变指向，释放删除的结点空间。

//双向链表头删
void PopFrontListNode(ListNode* phead)
{
	assert(phead);
	assert(!EmptyListNode(phead));
	ListNode* plist = phead;
	ListNode* next = plist->next->next;
	free(plist->next);
	next->prev = plist;
	plist->next = next;
}

十一、双向链表查找

查找某个数值是否在该链表中，并返回其结点的地址。

//双向链表查找
ListNode* FindListNode(ListNode* phead,ListNodeDate x)
{
	ListNode* plist = phead->next;
	assert(!EmptyListNode(plist));
	while (plist != phead)
	{
		if (plist->date == x)
			return plist;
		plist = plist->next;
	}
	return NULL;//找不到或者空链表都返回NULL
}

十二、双向链表插入

在pos位置前插入，也就是正常逻辑的插入，然后我们需要用到上面的那个查找函数，先查找出想要插入的位置，然后插入。

//双向链表在pos前面插入
void InsertListNode(ListNode* phead,ListNodeDate x, ListNode* pos)
{
	assert(phead);
	assert(pos);
	ListNode* ListPrev = pos->prev;
	ListNode* newnode = BuyNewnode(x);
	ListPrev->next = newnode;
	newnode->prev = ListPrev;
	newnode->next = pos;
	pos->prev = newnode;
}

十三、双向链表删除

删除并释放某个数据所对应的结点，首先需要判断是否为空链表，如果只有哨兵位头结点肯定不能删，所以需要判断是否为空链表。

//双向链表删除pos位置结点
void EraseListNode(ListNode* phead, ListNode* pos)
{
	assert(phead);
	assert(pos);
	assert(!EmptyListNode(phead));
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;
	free(pos);//让pos出函数后置空。
}

十五、总代码

ListNode.h

ListNode.h

#pragma once

//带头双向循环链表

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

//重命名数据类型
typedef int ListNodeDate;

//创建结点的结构体并重命名
typedef struct ListNode
{
	struct ListNode* next;
	struct ListNode* prev;
	ListNodeDate date;
}ListNode;

//创建新节点
ListNode* BuyNewnode(ListNodeDate x);

//初始化双向链表（创建哨兵位头节点）
ListNode* InitListNode();

//双链表的销毁
void DestoryListNode(ListNode* phead);

//双向链表打印
void PrintListNode(ListNode* phead);

//双向链表尾插
void PushBackListNode(ListNode* phead, ListNodeDate x);

//双向链表尾删
void PopBackListNode(ListNode* phead);

//双向链表头插
void PushFrontListNode(ListNode* phead,ListNodeDate x);

//双向链表头删
void PopFrontListNode(ListNode* phead);

//双向链表查找
ListNode* FindListNode(ListNode* phead, ListNodeDate x);

//双向链表在pos前面插入
void InsertListNode(ListNode* phead, ListNodeDate x, ListNode* pos);

//双向链表删除pos位置结点
void EraseListNode(ListNode* phead, ListNode* pos);

ListNode.c

ListNode.c

#define _CRT_SECURE_NO_WARNINGS 1

#include "ListNode.h"

//创建新节点
ListNode* BuyNewnode(ListNodeDate x)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	newnode->next = NULL;
	newnode->prev = NULL;
	newnode->date = x;
	return newnode;
}

//初始化双向链表（创建哨兵位头节点）
ListNode* InitListNode()
{
	ListNode* phead = BuyNewnode(-1);
	phead->prev = phead;
	phead->next = phead;
	return phead;
}

//双链表的销毁
void DestoryListNode(ListNode* phead)
{
	assert(phead);
	ListNode* cur = phead;
	ListNode* next = cur->next;
	while (cur!=phead)
	{
		next = cur->next;
		free(cur);
		cur = next;
	}
}

//判断双向链表是否为空（只有哨兵位头节点）
bool EmptyListNode(ListNode* phead)
{
	if (phead->next == phead)
	{
		return true;
	}
	else
		return false;
}

//双向链表打印
void PrintListNode(ListNode* phead)
{
	assert(phead);
	ListNode* cur = phead->next; 
	while (cur != phead)
	{
		if (cur == phead->next)
			printf("<=>");
		printf("%d<=>",cur->date);
		cur = cur->next;
	}
}

//双向链表尾插
void PushBackListNode(ListNode* phead, ListNodeDate x)
{
	assert(phead);
	ListNode* tail = phead->prev;
	ListNode* newnode = BuyNewnode(x);
	tail->next = newnode;
	newnode->prev = tail;
	phead->prev = newnode;
	newnode->next = phead;
}

//双向链表尾删
void PopBackListNode(ListNode* phead)
{
	assert(phead);
	assert(!EmptyListNode(phead));
	ListNode* newtail = phead->prev->prev;
	free(phead->prev);
	newtail->next = phead;
	phead->prev = newtail;
}

//双向链表头插
void PushFrontListNode(ListNode* phead,ListNodeDate x)
{
	assert(phead);
	ListNode* plist = phead;
	ListNode* newnode = BuyNewnode(x);	
	newnode->next = plist->next;
	newnode->prev = plist;
	plist->next->prev = newnode;
	plist->next = newnode;
}

//双向链表头删
void PopFrontListNode(ListNode* phead)
{
	assert(phead);
	assert(!EmptyListNode(phead));
	ListNode* plist = phead;
	ListNode* next = plist->next->next;
	free(plist->next);
	next->prev = plist;
	plist->next = next;
}

//双向链表查找
ListNode* FindListNode(ListNode* phead,ListNodeDate x)
{
	ListNode* plist = phead->next;
	assert(!EmptyListNode(plist));
	while (plist != phead)
	{
		if (plist->date == x)
			return plist;
		plist = plist->next;
	}
	return NULL;//找不到或者空链表都返回NULL
}

//双向链表在pos前面插入
void InsertListNode(ListNode* phead,ListNodeDate x, ListNode* pos)
{
	assert(phead);
	assert(pos);
	ListNode* ListPrev = pos->prev;
	ListNode* newnode = BuyNewnode(x);
	ListPrev->next = newnode;
	newnode->prev = ListPrev;
	newnode->next = pos;
	pos->prev = newnode;
}

//双向链表删除pos位置结点
void EraseListNode(ListNode* phead, ListNode* pos)
{
	assert(phead);
	assert(pos);
	assert(!EmptyListNode(phead));
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;
	free(pos);//让pos出函数后置空。
}

Test.c

Test.c

#define _CRT_SECURE_NO_WARNINGS 1

#include "ListNode.h"

int main()
{
	//创建哨兵位头节点
	ListNode* plist = InitListNode();//pointer List

	//尾插尾删打印
	//PushBackListNode(plist, 0);
	//PushBackListNode(plist, 1);
	//PushBackListNode(plist, 2);
	//PushBackListNode(plist, 3);
	//PushBackListNode(plist, 4);
	//PopBackListNode(plist);
	//PopBackListNode(plist);
	//PopBackListNode(plist);
	//PrintListNode(plist);
	//头插头删打印
	//PushFrontListNode(plist, 0);
	//PushFrontListNode(plist, 1);
	//PushFrontListNode(plist, 2);
	//PushFrontListNode(plist, 3);
	//PushFrontListNode(plist, 4);
	//PopFrontListNode(plist);
	//PrintListNode(plist);

	//综合验证
	PushBackListNode(plist, 0);
	PushBackListNode(plist, 1);
	PushBackListNode(plist, 2);
	PushFrontListNode(plist, 3);
	PushFrontListNode(plist, 4);
	PushFrontListNode(plist, 5);
	PopBackListNode(plist);
	PopFrontListNode(plist);
	
	//插入
	ListNode* pos = FindListNode(plist,0);
	InsertListNode(plist, 10, pos);

	//删除
	pos = FindListNode(plist, 10);
	EraseListNode(plist,pos);
	pos = NULL;

	PrintListNode(plist);
	DestoryListNode(plist);
	plist = NULL;
	return 0;
}

十四、总结

在这里插入图片描述

✨请点击下面进入主页关注大魔王
如果感觉对你有用的话，就点我进入主页关注我吧！

风语者！平时喜欢研究各种技术，目前在从事后端开发工作，热爱生活、热爱工作。

站长推荐