• 数据结构与算法(C语言版)P3.2---链表之带头双向循环链表的实现

    1、前言

    前面一章详细介绍了链表的概念、结构以及分类。并且实现了无头单向非循环链表。
    这一篇主要实现带头双向循环链表的。由于需要串联前面的知识，把上一篇至此：链表之无头单向非循环链表的实现

    2、带头双向循环链表的特性和结构

    2.1、结构

    在这里插入图片描述
    （1）、每个结点有两个指针域（next，prev），一个数据域（data）。
    （2）前面结点的next指针域指向后一个结点的地址，并且后一个结点的prev指针域指向前一个结点的地址。
    （3）头结点的prev指针域指向尾节点的地址，并且尾节点的next指针域指向头结点地址。

    由以上复杂的结构构成了带头双向循环链表。

    2.2、特性

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

    为什么说带头双向循环链表的使用简单呢？
    其中有一个原因就是"带头"。
    那这里就不得不说链表中带头结点（哨兵位）的好处了。

    3、带头结点和不带头结点的区别

    链表中带哨兵位和不带哨兵位的主要区别在于对边界条件的处理。下面是它们的一些区别：

    哨兵位：

    • 带哨兵位的链表在头节点之前插入一个特殊的节点，称为哨兵节点或者虚拟头节点。
    • 哨兵节点的值一般为空，它的存在使得链表的操作更加简单，避免了很多边界条件的判断。
    • 带哨兵位的链表通常有更统一的代码结构，操作起来更加方便。

    边界条件处理：

    • 不带哨兵位的链表需要特殊处理空链表和只有一个节点的情况。
    • 在不带哨兵位的链表中，需要单独对头节点为空或者只有一个节点的情况进行处理，增加了代码编写和维护的复杂度。

    空间开销：

    • 带哨兵位的链表相比不带哨兵位的链表会多占用一个节点的空间。

    总结来说就是，如果使用带哨兵位的链表，我们在遇见插入和删除结点的操作时不用再特殊考虑一些边界情况。比如：没有头结点，只有一个结点或者有多个结点时的3种情况。

    所以说使用带哨兵位可以降低链表的难度。

    那下面就来实现带头双向循环链表。

    4、带头双向循环链表的实现

    主要实现接口功能：

    • 哨兵位初始化（ListInit）
    • 扩容（BuyListNode）
    • 头插（ListPushFront）
    • 打印（ListPrint）
    • 销毁（ListDestroy）
    • 头删（ListPopFront）
    • 尾插（ListPushBack）
    • 尾删（ListPopBack）
    • 查询指定pos位置元素（ListFind）
    • 在pos位置之前插入（ListInsert）
    • 删除pos位置结点（ListErase）

    4.1、定义结构体

    #pragma once

#include 
#include 
#include 

typedef int LTDataType;

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14

    next指针变量用于本结点链接后继节点。
    prev指针变量用于本结点链接前继节点。
    data变量用于存储数据。

    4.2、哨兵位初始化

    LNode* ListInit()
{
	LNode* phead = (LNode*)malloc(sizeof(LNode));

	phead->next = phead;
	phead->prev = phead;
	return phead;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    这里的哨兵位初始化，一定要注意，由于带头双向循环链表结构的特殊性，哨兵位的首尾是相连的。所以我们需要将哨兵位的next和prev都指向本身。

    4.3、扩容

    扩容的思想千篇一律，不在介绍。

    LNode* BuyListNode(LTDataType x)
{
	LNode* newnode = (LNode*)malloc(sizeof(LNode));
	if (newnode == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = newnode->prev = NULL;
	return newnode;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    4.4、头插

    除了要考虑相邻结点之间的链接，这里还要考虑首结点和尾节点的首尾相连。

    void ListPushFront(LNode* phead, LTDataType x)
{
	assert(phead);
	LNode* newnode = BuyListNode(x);

	newnode->next = phead->next;
	phead->next->prev = newnode;

	phead->next = newnode;
	newnode->prev = phead;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    4.5、打印

    这里打印接口说明一下，和无头单向非循环相比，这里的while循环结束的条件不同。因为带头双向循环链表结点是首尾相连的，所以这里的尾节点不在是NULL了，而phead，所以当cur == phead说明链表遍历结束。

    void ListPrint(LNode* phead)
{
	assert(phead);

	LNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    4.6、销毁

    while循环条件结束和打印接口的一样，都是cur == phead时链表遍历结束。

    void ListDestroy(LNode* phead)
{
	assert(phead);
	LNode* cur = phead->next;
	while (cur != phead)
	{
		LNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    4.7、以上接口功能测试

    实现了头插，打印，销毁，扩容，初始化等接口功能，就可以测试以下基本插入程序了。

    #include "list.h"

void TestList1()
{
	LNode* plist = ListInit();

	ListPushFront(plist, 1);
	ListPushFront(plist, 2);
	ListPushFront(plist, 3);
	ListPushFront(plist, 4);
	ListPushFront(plist, 5);
	ListPushFront(plist, 6);

	ListPrint(plist);

	ListDestroy(plist);
}

int main()
{
	TestList1();
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23

    输出：
    在这里插入图片描述

    基础接口功能没问题，继续向下完善。

    4.8、头删

    void ListPopFront(LNode* phead)
{
	//断言是否只有哨兵位
	assert(phead);
	assert(phead->next != NULL);

	LNode* first = phead->next;
	LNode* second = first->next;
	phead->next = second;
	second->prev = phead;
	free(first);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    4.9、尾插

    这里需要说明，在以往的无头单向非循环链表中，我们需要依次向后遍历的找尾节点。但是在这里找为节点是很简单的操作。因为带头双向循环链表时首位结点相互链接的。哨兵位的prev指向的就是尾节点。

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    4.10、尾删

    void ListPopBack(LNode* phead)
{
	assert(phead);
	assert(phead->next != NULL);

	LNode* tail = phead->prev;
	LNode* tailPrev = tail->prev;
	free(tail);
	phead->prev = tailPrev;
	tailPrev->next = phead;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    4.11、查询指定pos位置元素，返回结点地址pos

    LNode* ListFind(LNode* phead, LTDataType x)
{
	assert(phead);

	LNode* cur = phead->next;
	while (cur)
	{
		if (x == cur->data)
		{
			return cur;
		}
		else
		{
			cur = cur->next;
		}
	}
	return NULL;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18

    4.12、在pos位置之前插入

    核心思想：记录pos前继结点，然后依次链接即可。

    void ListInsert(LNode* pos,LTDataType x)
{
	assert(pos);
	LNode* newnode = BuyListNode(x);
	LNode* posPrev = pos->prev;

	posPrev->next = newnode;
	newnode->prev = posPrev;

	newnode->next = pos;
	pos->prev = newnode;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    4.13、删除pos位置

    核心思想：记录pos的前继、后驱结点，然后依次链接即可。

    void ListErase(LNode* pos)
{
	assert(pos);

	LNode* posPrev = pos->prev;
	LNode* posNext = pos->next;
	free(pos);
	posPrev->next = posNext;
	posNext->prev = posPrev;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    那到此为止带头双向循环链表的基础接口就实现完毕了。

    其实在进行__头插、头删、尾插、尾删__的时候有个高级的处理方式。就是借助__ListFind、ListInsert、ListErase__接口进行处理。下面我们来具体写代码演示。

    5、头插、头删、尾插、尾删的高级实现方式

    5.1、头插

    核心思想：ListInsert接口本身就是完成指定pos位置之前的插入。如果我们想要在头插种使用，那只需要传参头结点后驱结点的地址即可。在头结点的后驱结点使用ListInsert就是头插。

    void ListPushFront(LNode* phead, LTDataType x)
{
	assert(phead);
	/*
	LNode* newnode = BuyListNode(x);

	newnode->next = phead->next;
	phead->next->prev = newnode;

	phead->next = newnode;
	newnode->prev = phead;
	*/

	//使用ListInsert接口完成头插功能
	ListInsert(phead->next, x);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16

    5.2、头删

    void ListPopFront(LNode* phead)
{
	assert(phead);
	assert(phead->next != NULL);

	/*
	LNode* first = phead->next;
	LNode* second = first->next;
	phead->next = second;
	second->prev = phead;
	free(first);
	*/

	//使用ListErase接口完成头删功能
	ListErase(phead->next);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16

    5.3、尾插

    核心思想：这里有个地方难理解。为什么我们使用ListInsert接口函数进行尾插，需要传参phead？我们不应该传尾节点的地址吗？那是因为带头双向循环链表的首位结点时相连的，因为phead就是尾节点的地址，所以就需要传参phead。

    void ListPushBack(LNode* phead, LTDataType x)
{
	assert(phead);

	/*
	LNode* newnode = BuyListNode(x);
	LNode* tail = phead->prev;
	tail->next = newnode;
	newnode->prev = tail;
	phead->prev = newnode;
	newnode->next = phead;
	*/

	//使用ListInsert接口完成尾插功能
	ListInsert(phead,x);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16

    5.4、尾删

    void ListPopBack(LNode* phead)
{
	assert(phead);
	assert(phead->next != NULL);

	/*
	LNode* tail = phead->prev;
	LNode* tailPrev = tail->prev;
	free(tail);
	phead->prev = tailPrev;
	tailPrev->next = phead;
	*/

	//使用ListErase接口完成尾删功能
	ListErase(phead->prev);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16

    至此带头双向循环链表主要功能已全部实现，下面展示全代码验证其正确性。

    6、全代码展示

    这里使用三个文件：

    • list.h：用于结构体、各种函数接口的声明
    • list.c：用于各种函数接口的定义。
    • test.c：用于创建链表，实现链表。

    6.1、list.h

    #pragma once

#include 
#include 
#include 

typedef int LTDataType;

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


//哨兵位初始化
LNode* ListInit();

//扩容
LNode* BuyListNode(LTDataType x);

//头插
void ListPushFront(LNode* phead, LTDataType x);

//打印
void ListPrint(LNode* phead);

//销毁
void ListDestroy(LNode* phead);

//头删
void ListPopFront(LNode* phead);

//尾插
void ListPushBack(LNode* phead, LTDataType x);

//尾删
void ListPopBack(LNode* phead);

//查询指定pos位置元素，返回结点pos地址
LNode* ListFind(LNode* phead, LTDataType x);

//在pos位置之前插入
void ListInsert(LNode* pos,LTDataType x);

//删除当前pos位置结点
void ListErase(LNode* pos);

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48

    6.2、list.c

    #include "list.h"

//哨兵位初始化
LNode* ListInit()
{
	LNode* phead = (LNode*)malloc(sizeof(LNode));

	phead->next = phead;
	phead->prev = phead;
	return phead;
}

//扩容
LNode* BuyListNode(LTDataType x)
{
	LNode* newnode = (LNode*)malloc(sizeof(LNode));
	if (newnode == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = newnode->prev = NULL;
	return newnode;
}

//头插
void ListPushFront(LNode* phead, LTDataType x)
{
	assert(phead);
	/*
	LNode* newnode = BuyListNode(x);

	newnode->next = phead->next;
	phead->next->prev = newnode;

	phead->next = newnode;
	newnode->prev = phead;
	*/

	//使用ListInsert接口完成头插功能
	ListInsert(phead->next, x);
}

//打印
void ListPrint(LNode* phead)
{
	assert(phead);

	LNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

//销毁
void ListDestroy(LNode* phead)
{
	assert(phead);
	LNode* cur = phead->next;
	while (cur != phead)
	{
		LNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
}

//头删
void ListPopFront(LNode* phead)
{
	assert(phead);
	assert(phead->next != NULL);

	/*
	LNode* first = phead->next;
	LNode* second = first->next;
	phead->next = second;
	second->prev = phead;
	free(first);
	*/

	//使用ListErase接口完成头删功能
	ListErase(phead->next);
}

//尾插
void ListPushBack(LNode* phead, LTDataType x)
{
	assert(phead);

	/*
	LNode* newnode = BuyListNode(x);
	LNode* tail = phead->prev;
	tail->next = newnode;
	newnode->prev = tail;
	phead->prev = newnode;
	newnode->next = phead;
	*/

	//使用ListInsert接口完成尾插功能
	ListInsert(phead,x);
}

//尾删
void ListPopBack(LNode* phead)
{
	assert(phead);
	assert(phead->next != NULL);

	/*
	LNode* tail = phead->prev;
	LNode* tailPrev = tail->prev;
	free(tail);
	phead->prev = tailPrev;
	tailPrev->next = phead;
	*/

	//使用ListErase接口完成尾删功能
	ListErase(phead->prev);
}

//查询指定pos位置元素，返回结点pos地址
LNode* ListFind(LNode* phead, LTDataType x)
{
	assert(phead);

	LNode* cur = phead->next;
	while (cur)
	{
		if (x == cur->data)
		{
			return cur;
		}
		else
		{
			cur = cur->next;
		}
	}
	return NULL;
}

//在pos位置之前插入
void ListInsert(LNode* pos,LTDataType x)
{
	assert(pos);
	LNode* newnode = BuyListNode(x);
	LNode* posPrev = pos->prev;

	posPrev->next = newnode;
	newnode->prev = posPrev;

	newnode->next = pos;
	pos->prev = newnode;
}

//删除当前pos位置结点
void ListErase(LNode* pos)
{
	assert(pos);

	LNode* posPrev = pos->prev;
	LNode* posNext = pos->next;
	free(pos);
	posPrev->next = posNext;
	posNext->prev = posPrev;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162
    • 163
    • 164
    • 165
    • 166
    • 167
    • 168
    • 169
    • 170
    • 171

    6.3、test.c

    #include "list.h"

void TestList1()
{
	LNode* plist = ListInit();

	ListPushFront(plist, 11);
	ListPushFront(plist, 22);
	ListPushFront(plist, 33);
	ListPushFront(plist, 44);
	ListPushFront(plist, 55);
	ListPushFront(plist, 66);

	ListPopBack(plist);

	//LNode* pos = ListFind(plist, 4);
	//ListErase(pos);

	ListPrint(plist);

	ListDestroy(plist);
}

int main()
{
	TestList1();
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
  • 相关阅读:
    2022版shardingsphere4.1.1结合mybatis-plus进行简单依赖YML文件进行分片、自定义生成主键、自定义水平分片的相关策略
    Linux系统安装Ruby语言
    cookies，sessionStorage 和 localStorage 的区别
    每日三题 6.30
    【游戏编程扯淡精粹】工作两年总结
    TCP之三次握手四次挥手
    【数据结构】反射、枚举
    Python源码剖析1-整数对象PyIntObject
    Trie字符串统计
    微信可以定时发朋友圈吗？
  • 原文地址：https://blog.csdn.net/m0_57776598/article/details/132916760