【线性存储结构总结】

前言

打怪升级：第四天

在前几篇文章中我们讲解了线性表一系列的经典例题，比如：
顺序表：无重复字符的最长子串
链表：分割链表、环形链表、复杂链表的复制
以及栈的：表达式求值等等
在写题的过程中我们对工具使用的熟练度正在不断提高，打怪所需要的时间也在不断缩短；
今天我们有两个任务：
1.了解带头双向循环链表的基本操作
2.分析常用线性表的特点以及使用方式

---

一、带头双向循环链表

首先分析一下该链表的特点：
1.带头：初始化的时候设置一个哨兵头节点
2.双向：增加了一个指向前一节点的prev指针
3.循环：尾结点的next指针指向哨兵节点
“带头双向循环链表”，看名字我们肯定会有一种“这是什么魔鬼链表”的感觉，不过在这里我想和大家说的是：这个链表其实非常非常的简单好用，比起单链表来简直一个天上一个地下，
当然，此时熊猫我“口说无凭”，那就让我们在下面的实践中逐渐感受“带头双向循环链表”的魅力吧。

（一）结构类型设计

typedef int LTDataType;

typedef struct list
{
	LTDataType data;
	struct list* prev;
	struct list* next;
}list;

1
2
3
4
5
6
7
8
9

---

（二）基本操作

使用到的头文件如下：

#include
#include
#include

1
2
3
4

总览：

// 带头+双向+循环链表增删查改实现
//初始化
list* LTInit();
//销毁
void LTDestroy(list* plist);
//头插
void LTPushFront(list* plist, LTDataType x);
//头删
void LTEraseFront(list* plist);
//尾插
void LTPushBack(list* plist, LTDataType x);
//尾删
void LTEraseBack(list* plist);
//在POS位置插入
void LTInsert(list* pos, LTDataType x);
//删除POS位置节点
void LTErase(list* pos);
//查找
list* LTFind(list* plist, LTDataType x);
//打印
void LTPrint(list* plist);
//清空
void LTClear(list* plist);

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

1.初始化

我们需要在初始化的时候创建哨兵节点，此时我们有两种方法让原节点指针指向该哨兵节点：
1.传参时传节点指针的指针（既二级指针）；
2.使用返回值，用节点指针进行接收。

//初始化
list* LTInit()
{
	list* plist = (list*)malloc(sizeof(list));
	assert(plist);

	plist->prev = plist->next = plist;

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

2.清空

//清空
void LTClear(list* plist)
{
	assert(plist);

	list* cur = plist->next;
	while (cur != plist)
	{
		list* next = cur->next;
		free(cur);
		cur = next;
	}
	plist->prev = plist->next = plist;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

3.销毁

//销毁--连同哨兵节点一同释放
void LTDestroy(list* plist)
{
	assert(plist);
	LTClear(plist);
	free(plist);
}
1
2
3
4
5
6
7

4.获取新节点

//获取新节点
static list* GetLTNode(LTDataType x)
{
	list* newnode = (list*)malloc(sizeof(list));
	assert(newnode);

	newnode->data = x;
	newnode->prev = newnode->next = NULL;

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

5.头插

我们在进行插入删除操作时只需要注意：谁动就改它、以及与它相邻的两个节点就可以。
和单链表不同，头插的时候我们需要改变四个指针：
新节点的prev指针
新节点的next指针
哨兵节点的后一个节点的prev指针
哨兵节点的next指针

//头插
void LTPushFront(list* plist, LTDataType x)
{
	assert(plist);

	list* newnode = GetLTNode(x);
	
	newnode->prev = plist;
	newnode->next = plist->next;
	plist->next->prev = newnode;
	plist->next = newnode;
}
1
2
3
4
5
6
7
8
9
10
11
12

6.头删

与单链表不同，我们需要改变两个指针：
被删除节点的前一个节点的next指针
被删除节点的后一个节点的prev指针

//头删
void LTEraseFront(list* plist)
{
	assert(plist);

	list* cur = plist->next;
	plist->next =cur->next;
	cur->next->prev = plist;
	free(cur);
}
1
2
3
4
5
6
7
8
9
10

7.尾插

//尾插
void LTPushBack(list* plist, LTDataType x)
{
	assert(plist);

	list* newnode = GetLTNode(x);

	newnode->next = plist;
	newnode->prev = plist->prev;
	plist->prev->next = newnode;
	plist->prev = newnode;
}
1
2
3
4
5
6
7
8
9
10
11
12

8.尾删

//尾删
void LTEraseBack(list* plist)
{
	assert(plist);

	list* prev = plist->prev;

	plist->prev = prev->prev;
	prev->prev->next = plist;
	free(prev);
}
1
2
3
4
5
6
7
8
9
10
11

9.在POS位置插入

与单链表不同，单链表如果需要在POS位置插入节点，需要进行遍历链表找到该节点的前一个节点，
而在本链表中我们可以直接通过POS位置节点的prev指针找到它的前一个节点。

//在POS位置插入
void LTInsert(list* pos, LTDataType x)
{
	assert(pos);

	list* newnode = GetLTNode(x);
	list* prev = pos->prev;

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

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

10.删除POS位置节点

//删除POS位置节点
void LTErase(list* pos)
{
	assert(pos);

	/*list* prev = pos->prev;
	list* next = pos->next;
	prev->next = next;
	next->prev = prev;*/
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;
}
1
2
3
4
5
6
7
8
9
10
11
12

11.查找

与单链表不同，由于该链表是双向循环的，所以我们在查找以及下面的打印的时候既可以正着查找也可以倒着查找。

//查找
list* LTFind(list* plist, LTDataType x)
{
	assert(plist);

	list* cur = plist->next;
	while (cur != plist)
	{
		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

12.打印

//打印--正序打印
void LTPrint(list* plist)
{
	assert(plist);

	list* cur = plist->next;
	while (cur != plist)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}
1
2
3
4
5
6
7
8
9
10
11
12
13

补充：我们这里写的LTInsert函数和LTErase函数可以在任意位置（哨兵节点除外）进行插入和删除操作，因此，
前面的头插、头删 以及 尾插、尾删操作都可以复用这两个函数。

---

（三）整体代码

//初始化
list* LTInit()
{
	list* plist = (list*)malloc(sizeof(list));
	assert(plist);

	plist->prev = plist->next = plist;

	return plist;
}

//清空
void LTClear(list* plist)
{
	assert(plist);

	list* cur = plist->next;
	while (cur != plist)
	{
		list* next = cur->next;
		free(cur);
		cur = next;
	}
	plist->prev = plist->next = plist;
}

//销毁--连同哨兵节点一同销毁
void LTDestroy(list* plist)
{
	assert(plist);
	LTClear(plist);
	free(plist);
}

//头插
void LTPushFront(list* plist, LTDataType x)
{
	assert(plist);

	list* newnode = GetLTNode(x);
	
	newnode->next = plist->next;
	newnode->prev = plist;
	plist->next->prev = newnode;
	plist->next = newnode;
}
//头删
void LTEraseFront(list* plist)
{
	assert(plist);

	list* cur = plist->next;
	plist->next =cur->next;
	cur->next->prev = plist;
	free(cur);
}
//尾插
void LTPushBack(list* plist, LTDataType x)
{
	assert(plist);

	list* newnode = GetLTNode(x);

	newnode->next = plist;
	newnode->prev = plist->prev;
	plist->prev->next = newnode;
	plist->prev = newnode;
}
//尾删
void LTEraseBack(list* plist)
{
	assert(plist);

	list* prev = plist->prev;

	plist->prev = prev->prev;
	prev->prev->next = plist;
	free(prev);
}
//在POS位置插入
void LTInsert(list* pos, LTDataType x)
{
	assert(pos);

	list* newnode = GetLTNode(x);
	list* prev = pos->prev;

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

}
//删除POS位置节点
void LTErase(list* pos)
{
	assert(pos);

	/*list* prev = pos->prev;
	list* next = pos->next;
	prev->next = next;
	next->prev = prev;*/
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;
}
//查找
list* LTFind(list* plist, LTDataType x)
{
	assert(plist);

	list* cur = plist->next;
	while (cur != plist)
	{
		if (cur->data == x)
			return cur;
		cur = cur->next;
	}

	return NULL;
}
//打印--正序打印
void LTPrint(list* plist)
{
	assert(plist);

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

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

二、线性表总结

在我们的日常生活中，线性表的使用是非常广泛的，我们数据结构中所讲的线性表实际上就是数据对象之间是一对一的关系且呈线性排列的一组数据，总的来说就是两种：顺序表和链表

（一）顺序表

顺序表就是我们平时使用的数组，我们在使用数组时如果设置为静态数组会给我们的使用造成很大的不变：我们不知道需要多大的空间，开大了浪费，开小了不够。
因此我们平时使用的都是动态数组，每次不够用了就再分配一段空间，那么我们在使用顺序表的时候就需要保存表中当前数据的个数，以及表的容量，
为了避免在传参时传递过多的参数，我们一般将它们封装在一个结构体中。

示例：

typedef int SQLDataType; 
typedef struct SeqList
{
	SQLDataType* data; // data也可以char、double、甚至结构体类型
	int size;
	int capacity;
}SeqList;

//  在使用的时候我们会创建一个结构体变量
void test()
{
	SeqList s;
	SeqListInit(&s);
}

//初始化的时候对它进行空间分配，注意，这里需要改变结构体元素，因此需要传结构体的指针
void SeqListInit(SeqList* ps)
{
	assert(ps);
	
	ps->data = (SQLDataType*)malloc(sizeof(SQLDataType)*4); // 申请四个空间
	if(ps->data == NULL)
	{
		perror("ListInit::malloc");
		exit(-1);
	}
	
	ps->size = 0;
	ps->capacity = 4;
}
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

---

（二）链表

我们使用链表时是通过在堆区申请一个一个节点来存储数据的，但是由于malloc申请的空间位置是随机的，所以这个时候我们不仅需要存储数据，还需要存储各个节点之间的关系，在单链表中我们只需要一个存储下一个节点地址的指针就可以，当然在双链表中就需要增加一个存储前一个节点地址的指针了。

示例：

// 无头不循环单链表
typedef int SLTDataType;
typedef struct SList
{
	SLTDataType data;
	struct SList* next;
}SList;

// 在使用时创建一个结构体指针，无头单链表不需要单独写一个进行初始化函数

void test()
{
	SList* plist;
}

// 因为没有哨兵头结点，所以我们在进行插入删除操作时plist的指向很有可能会改变，
// 而如果我们需要改变它的指向的话就需要传二级指针，或者通过函数返回值来改变它的指向

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

示例：

// 带头循环双链表
typedef int LTDataType;
typedef struct List
{
	LTDataType data;
	struct List* prev;
	struct List* next;
}List;

//使用的时候创建一个结构体指针
void test()
{
	List* plist;
	plist = ListInit();
}

//初始化时为它创建一个哨兵结点，这里通过返回值的方式使得plist指向哨兵节点
List* ListInit()
{
	List*phead=(List*)malloc(sizeof(List));
	 // 判断malloc是否成功开辟空间
	if(phead == NULL)
	{
		perror("ListInit::malloc");
		exit(-1);
	}
	// 循环链表，此时只有一个哨兵节点，所以它的prev指针和next指针都指向它自己
	phead->prev = phead->next = phead; 
	return 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

---

总结

1.通过上面“带头双向循环链表”的基本操作中发现它与单链表最大的的不同之处：不会出现空指针
由于尾结点的next指针指向的是头结点，因此我们在使用此链表的时候完全不需要考虑对空指针的解引用问题，
并且，我们咋在进行插入删除操作时可以直接通过prev和next指针找到它的前后指针，不需要再像单链表那样从第一个节点开始遍历了，可以说“带头双向循环链表”就是一个完美的单链表，不仅操作起来十分简单，而且全方位无死角的特点充满了魅力，简直是极致的优雅。
2.顺序表适合尾插尾删，单链表适合头插头删，这两者相辅相成，缺一不可，而我们今天介绍的“带头循环双向链表”则适合所以情况。
3.而至于 栈 和 队列 就是操作受限的线性表，在我们掌握了顺序表和链表的操作之后，栈和队列还不是手到擒来嘛，hh。
以上就是熊猫对线性表部分内容的总结，如果有什么疑问或者建议都可以在评论区留言，感谢大家对的支持。