数据结构初级:链表-双向带头循环链表(C语言)_双向循环链表

1.双向循环链表思路解析

1.节点组成

双向循环链表是链表中较为常见使用起来也是极为方便的链表,它的特点是链表中的每个节点除了需要存 储的数据之外,还有两个分别为前驱(prev)和后继(next)的指针,以便快速访问目标节点前和后的节点:

2.循环体现

循环具体体现在双向链表的头节点上,在双向循环链表中,存在一个头节点,这个头节点并不存储任何数据(工具人而已),只是为了为链表的初始化传参方便和记录尾节点从而形成循环链表:

当我们创建了一个链表之后,如果想要对链表进行增删改查的操作,只需要将头节点传入就可以了,这样我们只是改变头节点这个结构体,因此只需要用到一级指针就可以了,如果没有这个头节点,我们想要对链表进行操作,在某些情况下就必须用到二级指针才能对链表的内容进行更改了.

但是,当这个链表是空链表的时候,因为这是一个带头的双向链表,因此即使是链表为空它的头节点依然是存在的,只是头节点中不用来存储任何数据而已,因此双向链表为空并不是真正意义上的全部为空,双向链表为空代表这个链表中仅仅只存在头节点,而此时的链表头节点的prev和next都指向自己

当一个链表它是循环的,双向的,还带有头节点的时候,一切事情就会变得简单起来,单链表中复杂的增删改查操作在这里几乎都是相同的操作就可以搞定.

3. 插入节点的思路

例如,插入新的节点只需要将当前位置节点的前驱和后继稍作改变:

4. 删除节点的思路

删除节点同理:

无论插入或者删除的是哪个位置,除了不能删除掉头节点外,对双向循环链表来说都是一样的,因为它的实质其实就是一个环而已,增和删对这个环的本质结构是造不成影响的

5.循环环状体现

2.代码剖析

1. 链表数据结构体的定义

typedef int LTDataType;  //自定义数据类型
typedef struct ListNode
{
	LTDataType data;         
	struct ListNode* prev;      //前驱指针
	struct ListNode* next;  	//后继指针
}ListNode;
1
2
3
4
5
6
7

2. 创建并返回链表的头结点

// 创建并返回链表的头结点.
ListNode* ListCreate(LTDataType x)
{
	//先创建一个新的节点
	ListNode* phead = (ListNode*)malloc(sizeof(ListNode));
	phead->data = x;  //此值没有任何意义
	phead->next = phead;   
	phead->prev = phead;	//让头节点的前驱和后继都指向自己

	return phead;	
}
1
2
3
4
5
6
7
8
9
10
11

3. 打印链表

// 双向链表打印
void ListPrint(ListNode* pHead)
{
	assert(pHead);	//断言一下,防止空指针误传
	printf("head<==>");
	ListNode* 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
13

4. 判断链表是否不为空链表

此段代码是为后面的增删查改做准备,若链表为空,则不能进行增删查改的操作,返回false,若不为空,则返回true

//判断链表是否不为空链表
bool ListNotEmpty(ListNode* pHead)
{
	assert(pHead);

	return pHead != pHead->next;
}
1
2
3
4
5
6
7

5. 查找并返回找到的节点

ListNode* ListFind(ListNode* pHead, LTDataType x)
{
	assert(pHead);
	assert(ListNotEmpty(pHead)); //判断一下是否为空链表,若为空则不能查找

	ListNode* cur = pHead->next;
	while (cur != pHead)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	printf("没找到\n");
	return NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

6. 在pos位置插入一个新的节点

// 双向链表在pos的前面进行插入一个节点
void ListInsert(ListNode* pos, LTDataType x)
{
	assert(pos);
	//创建一个新的节点
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	newnode->data = x;
	ListNode* posPrev = pos->prev;	//记录一下pos前一个节点的位置

	//建立新的链接,断开旧的链接
	posPrev->next = newnode;
	newnode->prev = posPrev;
	newnode->next = pos;
	pos->prev = newnode;

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

7. 删除pos位置的节点

// 双向链表删除pos位置的节点
void ListErase(ListNode* pos)
{
	assert(pos);
	
	//先记录下pos位置的前一个节点和后一个节点
	ListNode* posPrev = pos->prev;
	ListNode* posNext = pos->next;

	//再将前后链接
	posPrev->next = posNext;
	posNext->prev = posPrev;

	//free掉pos节点
	free(pos);

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

8. 尾插

// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{
	assert(pHead);
	//尾插即是在 pHead 的前面插入
	ListInsert(pHead, x);
}
1
2
3
4
5
6
7

9. 头插

// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x)
{
	assert(pHead);
	//头插即是在 pHead->next 的前面插入
	ListInsert(pHead->next, x);
}
1
2
3
4
5
6
7

10. 头删

// 双向链表头删
void ListPopFront(ListNode* pHead)
{
	assert(pHead);
	assert(ListNotEmpty(pHead));  //空链表不能进行删除操作

	//头删即是删掉 pHead->next 位置的节点
	ListErase(pHead->next);
}
1
2
3
4
5
6
7
8
9

11. 尾删

// 双向链表尾删
void ListPopBack(ListNode* pHead)
{
	assert(pHead);
	assert(ListNotEmpty(pHead));  //空链表不能进行删除操作

	//尾删即是删掉 pHead->prev 位置的节点
	ListErase(pHead->prev);
}
1
2
3
4
5
6
7
8
9

12. 双向链表的销毁

// 双向链表销毁
void ListDestroy(ListNode* pHead)
{
	assert(pHead);

	ListNode* cur = pHead->next ;
	while (cur != pHead)
	{
		ListNode* Next = cur->next;
		free(cur);
		cur = Next;
	}
	free(pHead); //此时不能对pHead进行置空,因为一级传参是无法改变实参的值的
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

3. 源码实现

List.h

#pragma once

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


// 带头+双向+循环链表增删查改实现
typedef int LTDataType;
typedef struct ListNode
{
	LTDataType data;
	struct ListNode* next;
	struct ListNode* prev;
}ListNode;

// 创建返回链表的头结点.
ListNode* ListCreate(LTDataType x);

// 双向链表销毁
void ListDestroy(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);
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

List.c

#define _CRT_SECURE_NO_WARNINGS 1

#include"List.h"

// 创建并返回链表的头结点.
ListNode* ListCreate(LTDataType x)
{
	//先创建一个新的节点
	ListNode* phead = (ListNode*)malloc(sizeof(ListNode));
	phead->data = x;  //此值没有任何意义
	phead->next = phead;   
	phead->prev = phead;	//让头节点的前驱和后继都指向自己

	return phead;	
}

//判断链表是否不为空链表
bool ListNotEmpty(ListNode* pHead)
{
	assert(pHead);

	return pHead != pHead->next;
}

// 双向链表打印
void ListPrint(ListNode* pHead)
{
	assert(pHead);	//断言一下,防止空指针误传
	printf("head<==>");
	ListNode* cur = pHead->next;	//创建一个遍历指针
	while (cur != pHead)	//遍历:当遍历指针不等于头节点时打印数据
	{
		printf("%d<==>", cur->data);
		cur = cur->next;
	}
	printf("\n");
}


// 双向链表查找并返回找到的节点	
ListNode* ListFind(ListNode* pHead, LTDataType x)
{
	assert(pHead);
	assert(ListNotEmpty(pHead)); //判断一下是否为空链表,若为空则不能查找

	ListNode* cur = pHead->next;
	while (cur != pHead)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	printf("没找到\n");
	return NULL;
}

// 双向链表在pos的前面进行插入一个节点
void ListInsert(ListNode* pos, LTDataType x)
{
	assert(pos);

	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	newnode->data = x;
	ListNode* posPrev = pos->prev;	//记录一下pos前一个节点的位置

	//建立新的链接,断开旧的链接
	posPrev->next = newnode;
	newnode->prev = posPrev;
	newnode->next = pos;
	pos->prev = newnode;

}


// 双向链表删除pos位置的节点
void ListErase(ListNode* pos)
{
	assert(pos);
	
	//先记录下pos位置的前一个节点和后一个节点
	ListNode* posPrev = pos->prev;
	ListNode* posNext = pos->next;

	//再将前后链接
	posPrev->next = posNext;
	posNext->prev = posPrev;

	//free掉pos节点
	free(pos);

}

// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{
	assert(pHead);
	//尾插即是在 pHead 的前面插入
	ListInsert(pHead, x);
}


// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x)
{
	assert(pHead);
	//头插即是在 pHead->next 的前面插入
	ListInsert(pHead->next, x);
}

// 双向链表头删
void ListPopFront(ListNode* pHead)
{
	assert(pHead);
	assert(ListNotEmpty(pHead));  //空链表不能进行删除操作

	//头删即是删掉 pHead->next 位置的节点
	ListErase(pHead->next);
}

// 双向链表尾删
void ListPopBack(ListNode* pHead)
{
	assert(pHead);
	assert(ListNotEmpty(pHead));  //空链表不能进行删除操作

	//尾删即是删掉 pHead->prev 位置的节点
	ListErase(pHead->prev);
}

// 双向链表销毁
void ListDestroy(ListNode* pHead)
{
	assert(pHead);

	ListNode* cur = pHead->next ;
	while (cur != pHead)
	{
		ListNode* Next = cur->next;
		free(cur);
		cur = Next;
	}
	free(pHead); //此时不能对pHead进行置空,因为一级传参是无法改变实参的值的
}
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

test.c

#define _CRT_SECURE_NO_WARNINGS 1

#include"List.h"

void test1()
{
	//创建带头的链表
	ListNode* plist = ListCreate(-1);	//给头节点的值赋 -1 ,此值没有任何实际意义
	//尾插
	printf("尾插1-5\n");
	ListPushBack(plist,1);
	ListPushBack(plist,2);
	ListPushBack(plist,3);
	ListPushBack(plist,4);
	ListPushBack(plist,5);
	//打印
	ListPrint(plist);
	
	头插
	//ListPushFront(plist, 1);
	//ListPushFront(plist, 2);
	//ListPushFront(plist, 3);
	//ListPushFront(plist, 4);
	//ListPushFront(plist, 5);

	//找到3的值并在3之前插入 88
	printf("找到3的值并在3之前插入 88\n");
	ListNode* pos = ListFind(plist, 3);
	ListInsert(pos, 88);

	//打印
	ListPrint(plist);

	//找到88 的值并删除
	printf("找到88 的值并删除\n");
	pos = ListFind(plist, 88);
	ListErase(pos);

	//打印
	ListPrint(plist);

	//销毁
	printf("销毁链表\n");
	ListDestroy(plist);
	plist = NULL;
	printf("链表已销毁\n");
}


int main()
{
	test1();


	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

4. 部分主要功能测试

完结撒花❀❀❀~