C语言带头双向循环链表的示例代码

2022-12-02 13:42 开发作者：南猿北者

前言

对于链表来说，不只有单链表这一个品种；

链表有很多种形态

按方向分：单向、双向

按带不带头：带头、不带头

按循环：循环、不循环

1、单向或则双向：

C语言带头双向循环链表的示例代码

2、带头或者不带头：

C语言带头双向循环链表的示例代码

3、循环或者不循环：

C语言带头双向循环链表的示例代码

组合排列一下的话，链表一共有8种形态！！！

今天我们就来学习一下结构最复杂的带头双向循环链表！！！；

虽然名字听上去比较复杂，但是实现起来比单链表（全名：不带头、不循环、单向链表）更加简单，也不需要过多考虑特殊情况；

两种链表的比较：（上面是单链表，下面是带头双向循环链表）

C语言带头双向循环链表的示例代码

结构分析

C语言带头双向循环链表的示例代码

首先链表的头节点是不存储有效数据的（该节点被称为哨兵位），其次我们只需要知道改头节点的指针就能找到整个链表，并且便于对整个链表进行维护；

当然既然是双向的嘛，那节点一定有个指针域指向前一个节点，另一个指针域指向后一个节点；

那么我们的单个节点的数据结构就是：

开发者_Python入门

C语言带头双向循环链表的示例代码

现在我们定义了一个plist指针用来维护整个链表，根据上面说的plist就应该用来存储哨兵位的头节点的指针，那么如何表示链表为NULL的情况？

链表为空：

C语言带头双向循环链表的示例代码

就是:

head->next=head;

head->prev=head;

链表的基本操作实现

创建节点

ListNode* ListCreate(LTDataType x)
{
	ListNode* NewNode = (ListNode*)malloc(sizeof(ListNode));
	if (!NewNode)
		exit(-1);
	NewNode->val = x;
	NewNode->prev = NULL;
	NewNode->next = NULL;
	return NewNode;
}

我们在创建节点的时候就一起将数据域初始化，方标后续操作；

初始化链表

void InitDummyHead(ListNode* pHead)
{
	assert(pHead);
	pHead->prev = pHead;
	pHead->next = pHead;
}

链表销毁

// 双向链表销毁
void ListDestory(ListNode* pHead)
{
	assert(pHead);
	ListNode* cur = pHead->next;
	ListNode* next = NULL;
	while (cur!=pHead)
	{
		next = cur->next;
		free(cur);
		cur = next;
	}
	free(cur);
}

实现思路：

C语言带头双向循环链表的示例代码

打印链表

除了哨兵位的节点存到是无效数据不打印外，其他节点的数据都要打印：

// 双向链表打印
void ListPrint(ListNode* pHead)
{
	assert(pHead);
	ListNode* cur = pHead->next;
	while (cur != pHead)
	{
		ListNode* next = cur->next;
		printf("%d->",cur->val);
		cur = next;
	}
	printf("NULL\n");
}

链表尾插

该链表的尾插，比单链表的尾插简单太多了，不用遍历找尾：

// 双向链表尾插
void ListPushBack(ListNode* p编程Head, LTDataType x)
{
	assert(pHead);
    ListNode* NewNode = ListCreate(x);
	ListNode* tail = pHead->prev;
	tail->next = NewNode;
	NewNode->prev = tail;
	pHead->prev = NewNode;
	NewNode->next = pHead;
}

链表尾删

由于是循环的，哨兵位的前一个节点就是尾节点，同时尾节点的前一个节点我们也不用遍历，可以很轻松的拿到：

// 双向链表尾删
void ListPopBack(ListNode* pHead)
{
	编程客栈assert(pHead);
	assert(!is_Empty(pHead));//判空
	ListNode* tail = pHead->prev;
	ListNode* prev = tail->prev;
	ListNode* next = pHead;
	free(tail);
	prev->next = next;
	next->prev = prev;
}

链表头插

// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x)
{
	assert(pHead);
	ListNode* prev = pHead;
	ListNode* cur = pHead->next;
	ListNode* NewNode = ListCreate(x);
	prev->next = NewNode;
	NewNode->prev = prev;
	NewNode->next = cur;
	cur->prev = NewNode;
}

链表头删

// 双向链表头删
void ListPopFront(ListNode* pHead)
{
	assert(pHead);
	assert(!is_Empty(pHead));//判空
	ListNode* prev = pHead;
	ListNode* cur = pHead->next;
	ListNode* next = cur->next;
	free(cur);
	prev->next = next;
	next->prev = prev;
}

链表查找

// 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x)
{
	assert(pHead);
	assert(!is_Empty(pHead));//表都为NULL了，就没办法找了
	ListNode* cur = pHead->next;
	while (cur != pHead)
	{
		if (cur->val == x)
			return cur;
		else
			cur = cur->next;
	}
	return NULL;
}

链表pos位置前面去插入

// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x)
{
	assert(pos);//pos不能为NULL,由于参数限制我们无法对pos判断是否为哨兵位头节点，因此我们假设pos传的都是合法指针和NULL
	ListNode* NewNode = ListCreate(x);
	ListNode* prev = pos->prev;
	NewNode->next = pos;
	pos->prev = NewNode;
	prev->next = NewNode;
	NewNode->prev = prev;
}

删除pos位置

// 双向链表删除pos位置的节点
void ListErase(ListNode* pos)
{
	assert(pos);//由于参数限制，我们无法判断表是否为NULL；
	ListNode* prev = pos->prev;
	ListNode* next = pos->next;
	free(pos);
	prev->next = next;
	next->prev = prev;
}

链表判空

//判断链表是否为NULL
bool is_Empty(ListNode* pHead)
{
	assert(pHead);
	return pHead == pHead->prev;
}

代码复用

我们上面既然实现了在pos位置之前插入和删除pos位置的数据；

那么：

ListInsert(plist,x);//相当于尾插
ListInsert(plist->next, x);//相当于头插
ListErase(plist->next);//相当于头删
ListErase(plist->prev);//相当于尾删;

那么实际上我们只要实现ListInsert、ListErase这两个接口就能快速实现出带头双向循环链表了；

总代码及头文件

头文件的包含：

#pragma once
#include<stdjavascriptio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
// 带头+双向+循环链表增删查改实现
typedef int LTDataType;
typedef struct ListNode
{
	LTDataType val;
	struct ListNode* next;
	struct ListNode* prev;
}ListNode;

// 创建返回链表的头结点.
ListNode* ListCreate(LTDataType x);
//初始化哨兵位的头节点;
void InitDummyHead(ListNode* pHead);
// 双向链表销毁
void ListDestory(ListNode* pHead);
// 双向链表打印
void ListPrint(ListNode* pHead);
// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x);
// 双向链表尾删
void ListPopBack(ListNode* pHead);
// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x);
// 双向链表头删
void ListPopFront(ListNode* pHead);
// 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x);
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x);
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos);
//判断链表是否为NULL
bool is_Empty(ListNode* pHead);

功能代码实现：

#include"DList.h"
ListNode* ListCreate(LTDataType x)
{
	ListNode* NewNode = (ListNode*)malloc(sizeof(ListNode));
	if (!NewNode)
		exit(-1);
	NewNode->val = x;
	NewNode->prev = NULL;
	NewNode->next = NULL;
	return NewNode;
}
void InitDummyHead(ListNode* pHead)
{
	assert(pHead);
	pHead->prev = pHead;
	pHead->next = pHead;
}
// 双向链表销毁
void ListDestory(ListNode* pHead)
{
	assert(pHead);
	ListNode* cur = pHead->next;
	ListNode* next = NULL;
	while (cur!=pHead)
	{
		next = cur->next;
		free(cur);
		cur = next;
	}
	free(cur);
}
// 双向链表打印
void www.devze.comListPrint(ListNode* pHead)
{
	assert(pHead);
	ListNode* cur = pHead->next;
	while (cur != pHead)
	{
		ListNode* next = cur->next;
		printf("%d->",cur->val);
		cur = next;
	}
	printf("NULL\n");
}
// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{
	assert(pHead);
	/*ListNode* NewNode = ListCreate(x);
	Lis编程tNode* tail = pHead->prev;
	tail->next = NewNode;
	NewNode->prev = tail;
	pHead->prev = NewNode;
	NewNode->next = pHead;*/
	ListInsert(pHead,x);//函数复用
}
// 双向链表尾删
void ListPopBack(ListNode* pHead)
{
	assert(pHead);
	assert(!is_Empty(pHead));//判空
	/*ListNode* tail = pHead->prev;
	ListNode* prev = tail->prev;
	ListNode* next = pHead;
	free(tail);
	prev->next = next;
	next->prev = prev;*/
	ListErase(pHead->prev);//函数复用
}
// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x)
{
	assert(pHead);
	/*ListNode* prev = pHead;
	ListNode* cur = pHead->next;
	ListNode* NewNode = ListCreate(x);
	prev->next = NewNode;
	NewNode->prev = prev;
	NewNode->next = cur;
	cur->prev = NewNode;*/
	ListInsert(pHead->next,x);//函数复用
}
// 双向链表头删
void ListPopFront(ListNode* pHead)
{
	assert(pHead);
	assert(!is_Empty(pHead));//判空
	/*ListNode* prev = pHead;
	ListNode* cur = pHead->next;
	ListNode* next = cur->next;
	free(cur);
	prev->next = next;
	next->prev = prev;*/
	ListErase(pHead->next);//函数复用
}
// 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x)
{
	assert(pHead);
	assert(!is_Empty(pHead));//表都为NULL了，就没办法找了
	ListNode* cur = pHead->next;
	while (cur != pHead)
	{
		if (cur->val == x)
			return cur;
		else
			cur = cur->next;
	}
	return NULL;
}
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x)
{
	assert(pos);//pos不能为NULL,由于参数限制我们无法对pos判断是否为哨兵位头节点，因此我们假设pos传的都是合法指针和NULL
	ListNode* NewNode = ListCreate(x);
	ListNode* prev = pos->prev;
	NewNode->next = pos;
	pos->prev = NewNode;
	prev->next = NewNode;
	NewNode->prev = prev;
}
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos)
{
	assert(pos);//由于参数限制，我们无法判断表是否为NULL；
	ListNode* prev = pos->prev;
	ListNode* next = pos->next;
	free(pos);
	prev->next = next;
	next->prev = prev;
}
//判断链表是否为NULL
bool is_Empty(ListNode* pHead)
{
	assert(pHead);
	return pHead == pHead->prev;
}

以上就是C语言带头双向循环链表的示例代码的详细内容，更多关于C语言带头双向循环链表的资料请关注我们其它相关文章！

继续阅读：C语言双向循环链表 C语言循环链表 C语言带头双向循环链表

C语言带头双向循环链表的示例代码

目录

前言

结构分析

链表的基本操作实现

创建节点

初始化链表

链表销毁

打印链表

链表尾插

链表尾删

链表头插

链表头删

链表查找

链表pos位置前面去插入

删除pos位置

链表判空

代码复用

总代码及头文件

更多精彩内容

精彩评论

最新开发

SpringBoot整合Liquibase实现对数据库管理和迁移

java8升级java21方法步骤(完整pom文件升级及代码修改)

javacv ffmpeg使用原生ffmpeg命令方式

golang进行xml文件解析的操作方法

如何使用go实现创建WebSocket服务器

开发排行榜

springboot后端存储富文本内容的思路与步骤(含图片内容)

PyCharm运行python测试,报错“没有发现测试”/“空套件”的解决

return base64.b64encode(b).decode(

基于C语言实现钻石棋游戏的示例代码

Sublime Text 3解决中文乱码问题（实测可用）