数据结构之线性表中的双向循环链表【详解】

前言：

嗯！昨天我们的无头单向非循环链表咱已经是可以顺利完成出来了的，今天我们就来看一下什么是有头双向循环链表，不要看着这个链表又双向又循环的就比单向不循环链表难，其实这个更加的简单哦！前提是你有自己去完成单链表，此时你就会觉得双链表是比单链表更加简单的，所以不要害怕，不就是一个链表吗？

一、有头双向循环链表

（一、）我们先讲一些学习的小知识点和注意点

我们不管它昨天几点睡和今天有没有学习，把握好当下，我们今天要进行双向链表的学习

1.什么是双向链表（最主要讲的就是每个节点不仅是上一个结点存了下一个结点的地址（此时后一个结点也存了上一个结点的地址），这个就是双向链表）

2.所以现在我们还是一样不管那么多，我们先进行一个结构体的创建（但是此时的这个结构体不同于单链表的结构体，此时的结构体是多了一个指针的结构体）

3.单链表的题目考察较多，双链表没什么题目

4.二叉树也是两个指针

5.带头和不带头（就看与没有哨兵位），就是看头指针是否存放数据（头指针单独是一个指针就是哨兵位）

6.循环和非循环（如果是双向链表它的头结点和尾结点都是指向空指针的，但是如果是循环链表则不是）

7.循环链表的最后一个结点指向的位置是头结点

8.所以链表为什么会有8中结构（单、双）（带头、不带头）（循环、非循环）这些的排列组合刚好8种

9.但是在这8种中比较有价值（最常用的）的就是（最简单的和最复杂的）：无头单向非循环链表、带头双向循环链表

10.所以我们就开始带头双向循环链表的学习（比无头单向非循环链表更简单哦）
（二、）有关的图解（便于理解）

（三、）有头双向循环链表的实现
可以分为一下这些接口：
1.初始化
2.打印
3.尾插
4.尾删
5.头插
6.头删
7.查找
8.销毁
9.任意位置插入
10.任意位置删除

//1.初始化
DLNode* ListInit();
//2.打印
void ListPrint(DLNode* phead);
//3.尾插
void ListPushBack(DLNode* phead, DSListType x);
//4.尾删
void ListPoptBack(DLNode* phead);
//5.头插
void ListPushFront(DLNode* phead, DSListType x);
//6.头删
void ListPoptFront(DLNode* phead);
//7.查找
DLNode* ListFindname(DLNode* phead, DSListType x);
//8.销毁
void ListDestory(DLNode* phead);
//9.任意位置插入
void ListInsert(DLNode* pos, DSListType x);
//10.任意位置删除
void ListDete(DLNode* pos);
//11.上面的这两个函数是整个双向循环链表中最重要的
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

1.初始化接口

//1.初始化
//因为此时我有对这个传过来的指针进行改变（进行了初始化）所以此时的头结点是发生的改变的，所以这边一定要有返回值
DLNode* ListInit()
{
	//因为我们是玩带哨兵位的，所以此时我们应该要先malloc出来一个结点（让这个结点成为我的哨兵位）
	//哨兵位头结点：（但是我函数外面的plist并拿不到这个哨兵位（也就是plist不会发生改变），所以需要有一个返回值来处理这个问题或者用二级指针也行）
	DLNode* phead = (DLNode*)malloc(sizeof(DLNode));
	//因为此时的结构是一个双向的循环，所以(此时结构体中的两个指针应该要有不同的指向)
	//一个指针指向自己
	phead->next = phead;
	//另一个指针也指向它自己
	phead->prev = phead;

	return phead;

}//以上就是对一个带头循环双向链表的初始化（这个就是C语言的魅力，什么都是靠自己来弄，你只是给了我一个概念的模型，剩下的东西都是要靠我自己来搞定这个结构应该是怎样的）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

2.打印接口

//3.打印
//
void ListPrint(DLNode* phead)
{
	//因为此时phead中存的并不是一个有效的数据，所以此时不需要从头结点开始遍历（下一个结点开始）
	//判断结束条件就是通过：此时的这些数据在循环的过程之中最后会等于我的头结点（哨兵位），因为是循环的，所以不要以为它是一个循环就不能打印（只是停止的条件发生了一些的改变而已）
	assert(phead);
	DLNode* cur = phead->next;
	while (cur != phead)
	{
		printf("<-%d->", cur->data);
		cur = cur->next;

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

3.尾插接口

//2.尾插
//因为此时我的头结点plist传过来之后我并没有对其进行改变（因为我在初始化那步就已经改变过了，此时的这个plist就是已经拥有了两个指针（已经把哨兵位给创建好了），所以此时我在尾插时，就不会对plist进行任何形式的改变，所以此时我就不需要有返回值，当然也不需要有二进指针（这个也就是哨兵位的好处））
void ListPushBack(DLNode* phead, DSListType x)
{
	assert(phead);
	//DLNode* tail = phead->prev;//这步就是循环链表的大好处了（直接就可以找到最后一个结点的位置）
	//DLNode* newnode = (DLNode*)malloc(sizeof(DLNode));//这个就是开辟新结点（尾插就一定要开辟一个新结点不然插什么）
	//newnode->data = x;

	以上就是一个准备工作，下面就是真正的双向的循环的原理实现（最好是附上一幅图）
	//tail->next = newnode;//这步的意思是因为此时的tail就是尾结点（就是让我的尾结点的最后一个指针去指向我新开辟出来的结点，这样就实现了尾插）
	//newnode->prev = tail;//这个就是为了实现双向循环链表（因为双向循环链表有两个指针，此时的一个指针就要指向刚刚那个尾结点（tail），只有这样我的newnode才可以取而代之）
	//newnode->next = phead;//然后此时的另一个指针就去指向我的头指针（为了实现循环，尾—>头）
	//phead->prev = newnode;//然后这步就是把刚刚的头的其中一个指针指向我的newnoode（还是为了循环）（头->尾），这样就实现了循环双指针链表
	
	//附用任意插
	ListInsert(phead, x);

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

4.尾删接口

//4.尾删（我的正确写法）
void ListPoptBack(DLNode* phead)
{
	assert(phead);
	assert(phead->next != phead);//这边就是说明我不可以把哨兵位给删掉（就是当phead->next=phead;时，此时就是代表我这个循环双链表就只剩下哨兵位自己了（因为这是一个循环的链表），此时就不能再进行删除了）
	首先肯定是不需要开辟新结点的
	//DLNode* tail = phead->prev;
	while (cur->next != tail)//找尾的上一个
	{
		cur = cur->next;
	}
	 不敢把这个单链表的理解带过来我们的双链表（因为此时的整体的结构就是不一样的，因为此时的双链表是有两个指针的，一个是next指针，一个是prev指针，所以此时的尾的前一个只需要用prev这个指针去找就可以了）
	//DLNode* prev = tail->prev;
	//free(tail);
	//prev->next = NULL;
	此时以上只是大致的把尾给删除了，但是我还没有重新将这个循环链表给链接起来
	//prev->next = phead;
	//phead->prev = prev;

	//附用任意删
	ListDete(phead->prev);

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

5.头插接口

//5.头插
void ListPushFront(DLNode* phead, DSListType x)
{
	assert(phead);

	//DLNode* newnode = (DLNode*)malloc(sizeof(DLNode));
	//newnode->data = x;
	//DLNode* tail = phead->next;
	//newnode->next = tail;
	//tail->prev = newnode;

	//newnode->prev = phead;
	//phead->next = newnode;
	
	//附用任意插
	ListInsert(phead->next, x);//这个位置一定要记住是phead->next,不然就会出问题，因为哨兵位的后一个才是头结点，所以在这个头结点前面插入才是我的头插
    
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

6.头删接口

//6.头删
void ListPoptFront(DLNode* phead)
{
	//这边只要是与删除有关的代码，就要多断言一下，防止把哨兵位给删掉
	//assert(phead);
	//assert(phead->next != phead);//表示链表为空就不再需要断言了
	//
	//DLNode* tail = phead->next;
	//DLNode* next = tail->next;
	//free(tail);//这个free什么时候free就看你自己的方式了，可以最后free也可以后面free

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

	//附用任意删
	ListDete(phead->next);

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

7.查找接口

//7.查找
DLNode* ListFindname(DLNode* phead, DSListType x)//这个是为了找x，不敢当傻子了
{
	assert(phead);
	//这个的逻辑就有点像是print的逻辑，就是靠那个循环条件来完成
	DLNode* cur = phead->next;
	while (cur != phead)//这个循环是在保证我这个链表中不止只有哨兵位，而是有数据结点才开始找
	{
		if (cur->data == x)
		{
			return cur;
		}
		//这个位置就表示找到了
		cur = cur->next;

	}
	return NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

8.销毁接口

//8.销毁
void ListDestory(DLNode* phead)
{
	DLNode* cur = phead->next;
	DLNode* next = NULL;
	//while (cur->next != phead)//这步一开始你是这样写的，但是如果你写成这样的话，就会导致最后一个结点free不了，所以应该写成下面这样
	while (cur != phead)
	{
		//可以的怎么野指针怎么来（这就是我吗？）
		next = cur->next;
		free(cur);
		cur = NULL;
		cur = next;

	}
	//并且在你把所有的结点释放完之后（不能把哨兵位这个动态开辟的内存空间给忘记掉释放了），所以这边还要加一步
	free(phead);//但是这边要注意一个二级指针的问题（因为这步现在再改变我的函数外部的plist哨兵位）
	phead = NULL;
	
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

9.任意位置插入接口

//9.任意位置插入(pos位置)
void ListInsert(DLNode* pos, DSListType x)//这个位置不一定要用pos，用一个int pos的下标也是一样的,但一定注意这个pos是一个DLNode结构体，里面是有两个指针和一个数据的
{
	assert(pos);

	DLNode* newnode = (DLNode*)malloc(sizeof(DLNode));
	newnode->data = x;
	DLNode* prev = pos->prev;
	newnode->prev = prev;
	prev->next = newnode;

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

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

10.任意位置删除接口

//10.任意位置删除(pos位置)
void ListDete( DLNode* pos)
{
	assert(pos);
	/*assert(phead->next != phead);*/

	DLNode* next = pos->next;
	DLNode* prev = pos->prev;
	free(pos);
	next->prev = prev;
	prev->next = next;

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

附上图解：

（四、）测试代码

void Test1()
1

中的测试内容：

void Test2()
1

中的测试内容：

void Test3()
1

完整的测试代码：

#include"标头.h"


void Test1()
{
	//DLNode* plist = NULL;//（此时我的头结点是一个带哨兵位的，）
	//先初始化
	/*ListInit(&plist);*///我们在使用哨兵位的就不用这种传地址的方式
	DLNode* plist = ListInit();//而是使用这种直接获得返回值的方式
    //再尾插
	ListPushBack(plist, 1);
	ListPushBack(plist, 2);
	ListPushBack(plist, 3);
	ListPushBack(plist, 4);
	ListPushBack(plist, 5);

	ListPrint(plist);
	printf("\n");
	//再尾删
	ListPoptBack(plist);
	ListPoptBack(plist);
	ListPoptBack(plist);
	ListPoptBack(plist);

	ListPrint(plist);
	printf("\n");
	//再头插
	ListPushFront(plist, 2);
	ListPushFront(plist, 3);
	ListPushFront(plist, 4);
	ListPushFront(plist, 5);

	ListPrint(plist);
	printf("\n");
	//再头删
	ListPoptFront(plist);
	ListPoptFront(plist);
	ListPoptFront(plist);

    //打印
 	printf("NULL");
	ListPrint(plist);
	printf("NULL\n");

	ListDestory(plist);

}

void Test2()
{
	DLNode* plist = ListInit();//而是使用这种直接获得返回值的方式

	//先尾插
	ListPushBack(plist, 1);
	ListPushBack(plist, 2);
	ListPushBack(plist, 3);
	ListPushBack(plist, 4);
	ListPushBack(plist, 5);
	ListPrint(plist);
	printf("\n");
	//再头插
	ListPushFront(plist, 1);
	ListPushFront(plist, 2);
	ListPushFront(plist, 3);
	ListPushFront(plist, 4);
	ListPushFront(plist, 5);
	ListPrint(plist);
	printf("\n");
	//查找
	DLNode* pos = ListFindname(plist, 1);
	printf("\n");
	//打印
	printf("NULL");
	ListPrint(plist);
	printf("NULL\n");

	ListDestory(plist);
}

void Test3()
{
	DLNode* plist = ListInit();

	//先尾插
	ListPushBack(plist, 1);
	ListPushBack(plist, 2);
	ListPushBack(plist, 3);
	ListPushBack(plist, 4);
	ListPushBack(plist, 5);
	//再头插
	ListPushFront(plist, 1);
	ListPushFront(plist, 2);
	ListPushFront(plist, 3);
	ListPushFront(plist, 4);
	ListPushFront(plist, 5);

	ListPrint(plist);
	printf("\n");
	//再尾删
	ListPoptBack(plist);
	ListPoptBack(plist);
	ListPoptBack(plist);
	ListPoptBack(plist);

	ListPrint(plist);
	printf("\n");
	//再头删
	ListPoptFront(plist);
	ListPoptFront(plist);
	ListPoptFront(plist);

	ListPrint(plist);
	printf("\n");

	ListDestory(plist);
	//可以不使用二级指针，直接自己在外面置空指针(为了保持接口的一致性，所以不使用二级指针)
	plist = NULL;
}

int main()
{
	//Test1();
	//Test2();
	Test3();

    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
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