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

  • 开发
  • 9

片头

在上一篇文章中,我们介绍了链表的概念、结构、分类和单链表的增删改查接口的实现，同时提到了带头双向循环链表这一结构。本篇文章中，我们来详细的学习带头双向循环链表和它的增删改查接口实现。

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

上一篇文章中，我们提到过，带头双向循环链表结构最复杂，一般用来单独存储数据。实际中使用的链表结构都是带头双向循环链表。另外，这个结构虽然复杂，但是会带来很多优势，后面我们进行增删改查接口实现的时候就会感受到这个结构的奇妙之处了。

带头，即链表中带哨兵位。哨兵位属于附加的链表结点，本身不存储有效数值，仅作为头结点用来简化边界条件和方便操作。如果一个链表带哨兵位（带头）的话，第一个元素就应该是链表的第二个结点。

双向和循环很好理解，画图就行。接下来我们直接开始进行增删改查接口的实现。

二、带头双向循环链表增删改查接口实现

本次演示的是vs2019,我们先创建一个新工程,并新建一个头文件"DList.h"和2个源文件"DList.c" 和"Test.c",当然咯,命名可以根据自己的喜好来定义,它们的具体作用分别是:

DList.h 带头双向循环链表的结构体定义,头文件的引用和接口函数的声明
DList.c 接口函数的实现
Test.c 测试各个函数

首先,我们来展示"DList.h"的完整代码,不要忘记在2个源文件中引用"DList.h"

#pragma once				//防止头文件被二次引用
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

typedef int ElemType;		//如果要修改存储的数据类型可直接在此修改
typedef struct ListNode {
	ElemType data;			//结点存储的数据域
	struct ListNode* prev;	//指针保存前一个结点的地址
	struct ListNode* next;	//指针保存下一个结点的地址
}LTNode;

//带头双向循环链表增删查改接口实现

LTNode* BuyNode(ElemType x);	//创建一个新结点

//void LTInit(LTNode** pphead);
LTNode* LTInit();				//链表初始化

void LTPrint(LTNode* phead);	//链表打印

void LTPushBack(LTNode* phead, ElemType x);//链表尾插

void LTPushFront(LTNode* phead, ElemType x);//链表头插

void LTPopBack(LTNode* phead);//链表尾删

void LTPopFront(LTNode* phead);//链表头删

LTNode* LTFind(LTNode* phead, ElemType x);//在链表中查找数据

void LTInsert(LTNode* pos, ElemType x);//在pos位置之后插入数据

void LTErase(LTNode* pos);//删除pos结点

void LTDestroy(LTNode* phead);	//链表销毁

接下来我们逐步实现各个接口函数,每一步都进行注释说明,必须让你学会

(1)创建新结点
//创建新结点
LTNode* BuyNode(ElemType x) {
	LTNode* newNode = (LTNode*)malloc(sizeof(LTNode));//创建新结点
	if (newNode == NULL) //防止空间开辟失败
	{
		perror("malloc fail!\n");
		exit(1);
	}
	newNode->data = x;//新结点的数据域为x
	newNode->prev = newNode->next = newNode;//新结点的prev和next指针都指向自己

	return newNode;//返回新结点
}
(2)初始化带头双向循环链表

我们先来看看这里的代码:

void LTInit(LTNode** pphead) {
	assert(pphead);//断言,防止传入空指针
	*pphead = (LTNode*)malloc(sizeof(LTNode));//开辟一个哨兵结点
	if (*pphead == NULL) //如果内存不够,开辟失败
	{
		perror("malloc fail!\n");
		exit(1);
	}
	(*pphead)->data = -1;//哨兵结点的数据域为-1
	(*pphead)->prev = (*pphead)->next = *pphead;//哨兵结点的前驱和后继指针指向它自己
}

 emmm,这个代码和我们之前学过的单链表的初始化很相似,But ! ! ! 单链表中涉及到二级指针,是因为单链表中第一个结点(*pphead)可能为空; 但是双向链表中不需要二级指针,因为双向链表中phead(哨兵位)不可能为空。

因此，双向链表的初始化也可以这样写：

LTNode* LTInit() {
	LTNode* phead = (LTNode*)malloc(sizeof(LTNode));//初始化,创建一个哨兵位结点
	if (phead == NULL) //如果内存不够,开辟失败
	{
		perror("malloc fail!\n");
		exit(1);
	}
	phead->data = -1;//哨兵结点的数据域为-1
	phead->prev = phead->next = phead;//哨兵结点的前驱指针和后继指针指向它自己
	return phead;//将哨兵结点返回
}

根据 <（1）创建新结点 >,我们可以将代码进行优化:

LTNode* LTInit() {
	LTNode* phead = BuyNode(-1);//初始化,创建一个哨兵位结点
	return phead;               //将哨兵结点返回
}
(3)链表打印
//打印链表
void LTPrint(LTNode* phead) {
	assert(phead);			   //断言,防止传入空指针
	LTNode* pcur = phead->next;//结点指针pcur指向第一个结点(哨兵结点的下一个结点)
	while (pcur != phead) //当pcur在链表中又循环回到哨兵位时,说明链表打印完毕
	{
		printf("%d<==>", pcur->data);//打印结点数据
		pcur = pcur->next;//找到下一个结点
	}
	printf("NULL\n");
}
(4)尾部插入结点

//尾插
void LTPushBack(LTNode* phead, ElemType x) {
	assert(phead);				 //断言,防止传入空指针
	LTNode* newNode = BuyNode(x);//创建一个新结点

	newNode->next = phead;		 //新结点的next指针指向哨兵结点
	newNode->prev = phead->prev; //新结点的prev指针指向最后一个结点
	phead->prev->next = newNode; //最后一个结点的next指针指向新结点
	phead->prev = newNode;		 //哨兵结点的prev指针指向新结点
}

测试一下:

(5)头部插入结点

//头插
void LTPushFront(LTNode* phead, ElemType x) {
	assert(phead);				 //断言,防止传入空指针
	LTNode* newNode = BuyNode(x);//创建一个新结点
	newNode->next = phead->next; //新结点的next指针指向第一个结点(哨兵结点的下一个结点)
	newNode->prev = phead;		 //新结点的prev指针指向哨兵结点
	phead->next->prev = newNode; //第一个结点的prev指针指向新结点
	phead->next = newNode;		 //哨兵结点的next指针指向新结点
}

测试一下:

(6)尾部删除结点

//尾删
void LTPopBack(LTNode* phead) {
	assert(phead);//断言,不能传入空指针
	assert(phead->next != phead);//断言,防止链表为空(只有哨兵位)

	LTNode* del = phead->prev;//用del将最后一个结点保存
	del->prev->next = phead;  //倒数第二个结点的next指针指向哨兵结点
	phead->prev = del->prev;  //哨兵结点的prev指针指向倒数第二个结点
	free(del);				  //将最后一个结点释放
	del = NULL;				  //置空
}

测试一下:

(7)头部删除结点

//头删
void LTPopFront(LTNode* phead) {
	assert(phead);				//断言,防止传入空指针
	assert(phead->next != phead);//断言,防止链表为空(只有哨兵位)

	LTNode* del = phead->next;	 //用del保存第一个结点(哨兵结点的向下一个结点)
	//phead->next = del->next;	 
	//del->next->prev = phead;
	//如果顺序调换,同样可以
	del->next->prev = phead;	//第二个结点的prev指针指向哨兵位
	phead->next = del->next;	//哨兵结点的next指针指向第二个结点
	free(del);					//释放第一个结点
	del = NULL;					//置空
}

测试一下:

(8)在链表中查找
LTNode* LTFind(LTNode* phead, ElemType x) {
	assert(phead);				//断言,防止传入空指针
	LTNode* pcur = phead->next; //查找前跳过哨兵位
	while (pcur != phead)		//判断,如果pcur遍历到哨兵位,则退出循环
	{
		if (pcur->data == x) {  //如果找到目标数据
			return pcur;		//返回目标结点的地址
		}
		pcur = pcur->next;		//继续查找下一个结点
	}
	return NULL;				//pcur遍历完链表,仍然为找到,返回NULL
}
(9)在pos之后插入节点

//在pos位置之后插入数据
void LTInsert(LTNode* pos, ElemType x) {
	assert(pos);//断言,防止传入空指针
	LTNode* newNode = BuyNode(x);//创建新结点
	newNode->next = pos->next;	 //新结点的next指针指向pos结点的下一个结点
	newNode->prev = pos;		 //新结点的prev指针指向pos结点
	pos->next->prev = newNode;	 //pos位置的下一个结点的prev指针指向新结点
	pos->next = newNode;		 //pos结点的next指针指向新结点
}

测试一下:

(10)删除pos位置的结点

 //删除pos结点
void LTErase(LTNode* pos) {
	assert(pos);				 //断言,防止传入空指针
	assert(pos->next != NULL);	 //断言,防止传入空链表的哨兵位
	LTNode* del = pos;			 //用del保存pos结点的地址
	del->prev->next = pos->next; //pos位置前一个结点的next指针指向pos位置的后一个结点
	pos->next->prev = del->prev; //pos位置后一个结点的prev指针指向pos位置的前一个结点
	free(del);					 //释放pos结点
	del = NULL;					 //置空
}

测试一下:

(11)销毁链表
void LTDestroy(LTNode* phead) {
	assert(phead);//断言,防止传入空指针
	LTNode* p = phead->next;//p保存第一个结点
	while (p != phead)		//当p遍历到哨兵结点的时候,退出循环
	{
		LTNode* q = p->next;//q保存p指向的下一个结点
		free(p);			//释放p指向的结点
		p = q;				//将q指向的结点赋给p
	}
	free(phead);			//释放哨兵结点
	phead = NULL;			//将哨兵结点置空
	printf("链表销毁成功!\n");
}

OK啦!我们已经实现了带头双向循环链表的核心功能,下面是"DList.c"文件的完整代码:

#include"DList.h"
//带头双向循环链表增删查改接口实现

//创建新结点
LTNode* BuyNode(ElemType x) {
	LTNode* newNode = (LTNode*)malloc(sizeof(LTNode));//创建新结点
	if (newNode == NULL) //防止空间开辟失败
	{
		perror("malloc fail!\n");
		exit(1);
	}
	newNode->data = x;//新结点的数据域为x
	newNode->prev = newNode->next = newNode;//新结点的prev和next指针都指向自己

	return newNode;//返回新结点
}

//void LTInit(LTNode** pphead) {
//	assert(pphead);//断言,防止传入空指针
//	*pphead = (LTNode*)malloc(sizeof(LTNode));//开辟一个哨兵结点
//	if (*pphead == NULL) //如果内存不够,开辟失败
//	{
//		perror("malloc fail!\n");
//		exit(1);
//	}
//	(*pphead)->data = -1;//哨兵结点的数据域为-1
//	(*pphead)->prev = (*pphead)->next = *pphead;//哨兵结点的前驱和后继指针指向它自己
//}
LTNode* LTInit() {
	LTNode* phead = BuyNode(-1);//初始化,创建一个哨兵位结点
	return phead;//将哨兵结点返回
}
//LTNode* LTInit() {
//	LTNode* phead = (LTNode*)malloc(sizeof(LTNode));//初始化,创建一个哨兵位结点
//	if (phead == NULL) //如果内存不够,开辟失败
//	{
//		perror("malloc fail!\n");
//		exit(1);
//	}
//	phead->data = -1;//哨兵结点的数据域为-1
//	phead->prev = phead->next = phead;//哨兵结点的前驱指针和后继指针指向它自己
//	return phead;//将哨兵结点返回
//}

//销毁
void LTDestroy(LTNode* phead) {
	assert(phead);//断言,防止传入空指针
	LTNode* p = phead->next;//p保存第一个结点
	while (p != phead)		//当p遍历到哨兵结点的时候,退出循环
	{
		LTNode* q = p->next;//q保存p指向的下一个结点
		free(p);			//释放p指向的结点
		p = q;				//将q指向的结点赋给p
	}
	free(phead);			//释放哨兵结点
	phead = NULL;			//将哨兵结点置空
	printf("链表销毁成功!\n");
}

//打印链表
void LTPrint(LTNode* phead) {
	assert(phead);			   //断言,防止传入空指针
	LTNode* pcur = phead->next;//结点指针pcur指向第一个结点(哨兵结点的下一个结点)
	while (pcur != phead) //当pcur在链表中又循环回到哨兵位时,说明链表打印完毕
	{
		printf("%d<==>", pcur->data);//打印结点数据
		pcur = pcur->next;//找到下一个结点
	}
	printf("NULL\n");
}

//尾插
void LTPushBack(LTNode* phead, ElemType x) {
	assert(phead);				 //断言,防止传入空指针
	LTNode* newNode = BuyNode(x);//创建一个新结点

	newNode->next = phead;		 //新结点的next指针指向哨兵结点
	newNode->prev = phead->prev; //新结点的prev指针指向最后一个结点
	phead->prev->next = newNode; //最后一个结点的next指针指向新结点
	phead->prev = newNode;		 //哨兵结点的prev指针指向新结点
}

//头插
void LTPushFront(LTNode* phead, ElemType x) {
	assert(phead);				 //断言,防止传入空指针
	LTNode* newNode = BuyNode(x);//创建一个新结点
	newNode->next = phead->next; //新结点的next指针指向第一个结点(哨兵结点的下一个结点)
	newNode->prev = phead;		 //新结点的prev指针指向哨兵结点
	phead->next->prev = newNode; //第一个结点的prev指针指向新结点
	phead->next = newNode;		 //哨兵结点的next指针指向新结点
}

//尾删
void LTPopBack(LTNode* phead) {
	assert(phead);//断言,不能传入空指针
	assert(phead->next != phead);//断言,防止链表为空(只有哨兵位)

	LTNode* del = phead->prev;//用del将最后一个结点保存
	del->prev->next = phead;  //倒数第二个结点的next指针指向哨兵结点
	phead->prev = del->prev;  //哨兵结点的prev指针指向倒数第二个结点
	free(del);				  //将最后一个结点释放
	del = NULL;				  //置空
}

//头删
void LTPopFront(LTNode* phead) {
	assert(phead);				//断言,防止传入空指针
	assert(phead->next != phead);//断言,防止链表为空(只有哨兵位)

	LTNode* del = phead->next;	 //用del保存第一个结点(哨兵结点的向下一个结点)
	//phead->next = del->next;	 
	//del->next->prev = phead;
	//如果顺序调换,同样可以
	del->next->prev = phead;	//第二个结点的prev指针指向哨兵位
	phead->next = del->next;	//哨兵结点的next指针指向第二个结点
	free(del);					//释放第一个结点
	del = NULL;					//置空
}

//在pos位置之后插入数据
void LTInsert(LTNode* pos, ElemType x) {
	assert(pos);//断言,防止传入空指针
	LTNode* newNode = BuyNode(x);//创建新结点
	newNode->next = pos->next;	 //新结点的next指针指向pos结点的下一个结点
	newNode->prev = pos;		 //新结点的prev指针指向pos结点
	pos->next->prev = newNode;	 //pos位置的下一个结点的prev指针指向新结点
	pos->next = newNode;		 //pos结点的next指针指向新结点
}
 //删除pos结点
void LTErase(LTNode* pos) {
	assert(pos);				 //断言,防止传入空指针
	assert(pos->next != NULL);	 //断言,防止传入空链表的哨兵位
	LTNode* del = pos;			 //用del保存pos结点的地址
	del->prev->next = pos->next; //pos位置前一个结点的next指针指向pos位置的后一个结点
	pos->next->prev = del->prev; //pos位置后一个结点的prev指针指向pos位置的前一个结点
	free(del);					 //释放pos结点
	del = NULL;					 //置空
}
LTNode* LTFind(LTNode* phead, ElemType x) {
	assert(phead);				//断言,防止传入空指针
	LTNode* pcur = phead->next; //查找前跳过哨兵位
	while (pcur != phead)		//判断,如果pcur遍历到哨兵位,则退出循环
	{
		if (pcur->data == x) {  //如果找到目标数据
			return pcur;		//返回目标结点的地址
		}
		pcur = pcur->next;		//继续查找下一个结点
	}
	return NULL;				//pcur遍历完链表,仍然为找到,返回NULL
}

片尾

今天我们学习了什么是带头双向循环链表,以及如何实现带头双向链表,希望看完这篇文章能对友友们有所帮助 !   !   !

求点赞收藏加关注 !   !   !

谢谢大家 !   !   !

阅读全部

相关推荐

  4. 数据结构_带头双向循环链表

    2024-04-25 22:56:01       16 阅读

  5. 数据结构基础（带头节点的双向循环链表）

    2024-04-25 22:56:01       42 阅读

最近更新

  4. TCP协议是安全的吗?

    2024-04-25 22:56:01       16 阅读

  12. 阿里云服务器执行yum，一直下载docker-ce-stable失败

    2024-04-25 22:56:01       16 阅读

  13. 【Python教程】压缩PDF文件大小

    2024-04-25 22:56:01       15 阅读

  18. 通过文章id递归查询所有评论（xml）

    2024-04-25 22:56:01       18 阅读

热门阅读

  11. MyBatis笔记——参数处理

    2024-04-25 22:56:01       13 阅读

  23. 玩转nginx的配置文件2

    2024-04-25 22:56:01       8 阅读

  26. 字符串、数组的反转

    2024-04-25 22:56:01       10 阅读

  30. SAP fiori 第三方网页认证登录（伪）

    2024-04-25 22:56:01       14 阅读