范某帅的博客
0%

数据结构-第二章-线性表

发表于 更新于 分类于 阅读次数： Valine：
本文字数： 13k 阅读时长 ≈ 12 分钟

线性表的基本操作

顺序表的实现-静态分配

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
#include <stdio.h>
#define Maxsize 10

typedef struct {
	int data[Maxsize];
	int length;
}SqList;

//初始化顺序表
void InitList(SqList &L) {
	for (int i = 0; i < Maxsize; i++)
	{
		L.data[i] = 0;
	}
	L.length = 0;
}

//循环遍历打印顺序表
void ListItem(SqList &L) {
	for (int i = 0; i < Maxsize; i++)
	{
		printf("data[%d]=%d\n", i, L.data[i]);
	}
}

int main() {
	SqList L;
	InitList(L);
	ListItem(L);
    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
#include <stdio.h>
#include <malloc.h>
#define InitSize 15

typedef struct {
    //动态分配 声明指针
	int* data;
	int MaxSize;
	int length;
}SeqList;

void InitList(SeqList &L) {
    //申请一个长度15的数组
	L.data = (int*)malloc(InitSize * sizeof(int));
	L.length = 0;
	L.MaxSize = InitSize;
}

//动态增加顺序表的数组长度
void IncreaseList(SeqList &L, int size) {
	int* data = L.data;
	L.data = (int*)malloc((L.MaxSize + size) * sizeof(int));
	L.length = 0;
	L.MaxSize = L.MaxSize + size;
	free(data);
	printf("现在的顺序表长度为：%d\n", L.MaxSize);
}

//初始化数据
void InitData(SeqList &L) {
	for (int i = 0; i < L.MaxSize; i++)
	{
		L.data[i] = 0;
	}
}

//循环遍历打印数组
void ListItem(SeqList &L) {
	for (int i = 0; i < L.MaxSize; i++)
	{
		printf("data[%d]=%d\n", i, L.data[i]);
	}
}

int main() {
	SeqList L;
	InitList(L);
	IncreaseList(L, 5);
	InitData(L);
	ListItem(L);
	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
#include <stdio.h>
#define Maxsize 10

typedef struct {
	int data[Maxsize];
	int length;
}SqList;

//初始化数据
void InitList(SqList& L) {
	for (int i = 0; i < Maxsize; i++)
	{
		L.data[i] = 0;
	}
	L.length = 0;
}

//初始化数据
void InitData(SqList &L, int size) {
	for (int i = 0; i < size; i++)
	{
		L.data[i] = i;
	}
	L.length = size;
}

//循环遍历打印数组
void ListItem(SqList &L) {
	for (int i = 0; i < L.length; i++)
	{
		printf("data[%d]=%d\n", i, L.data[i]);
	}
}

//插入数据
bool ListInsert(SqList &L, int index, int element) {
    //插入位置的合法性判断
	if (index < 1 || index > L.length+1)
	{
		return false;
	}
    //判断是否已满
	if (L.length >= Maxsize)
	{
		return false;
	}
    //将插入位置后的数据全部后移
	for (int i = L.length; i >= index; i--)
	{
		L.data[i] = L.data[i - 1];
	}
	L.data[index-1] = element;
	L.length += 1;
	return true;
}

int main() {
	SqList L;
	InitList(L);
	InitData(L, 7);
	if (ListInsert(L, 7, 99))
	{
		printf("插入成功！\n");
		ListItem(L);
	}
	else
	{
		printf("插入失败！\n");
	}
	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
#include <stdio.h>
#define Maxsize 10

typedef struct {
	int data[Maxsize];
	int length;
}SqList;

void InitList(SqList& L) {
	for (int i = 0; i < Maxsize; i++)
	{
		L.data[i] = 0;
	}
	L.length = 0;
}

void InitData(SqList &L, int size) {
	for (int i = 0; i < size; i++)
	{
		L.data[i] = i;
	}
	L.length = size;
}

void ListItem(SqList &L) {
	for (int i = 0; i < 10; i++)
	{
		printf("data[%d]=%d\n", i, L.data[i]);
	}
}

bool ListDelete(SqList &L, int index) {
    //删除位置合法性判断
	if (index < 1 || index > L.length) {
		return false;
	}
	printf("正在删除的数据为：data[%d]=%d\n", index - 1, L.data[index - 1]);
    //逻辑删除元素
	for (int i = index; i < L.length; i++)
	{
		L.data[i - 1] = L.data[i];
		printf("正在赋值为：data[%d]=%d <= data[%d]=%d\n", i - 1, L.data[i - 1], i, L.data[i]);
	}
	L.data[L.length - 1] = 0;
	L.length -= 1;
	return true;
}

int main() {
	SqList L;
	InitList(L);
	InitData(L, 5);
	if (ListDelete(L, 2))
	{
		printf("删除成功！\n");
		ListItem(L);
	}
	else
	{
		printf("删除失败！\n");
	}
	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
#include <stdio.h>
#define Maxsize 10

typedef struct {
	int data[Maxsize];
	int length;
}SqList;

void InitList(SqList& L) {
	for (int i = 0; i < Maxsize; i++)
	{
		L.data[i] = i;
	}
	L.length = Maxsize;
}

//按位查找
void getListItem(SqList &L, int index) {
	printf("data[%d]=%d", index, L.data[index]);
}

int main() {
	SqList L;
	InitList(L);
	getListItem(L, 5);
	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
#include <stdio.h>
#define Maxsize 10

typedef struct {
	int data[Maxsize];
	int length;
}SqList;

void InitList(SqList& L) {
	for (int i = 0; i < Maxsize; i++)
	{
		L.data[i] = i;
	}
	L.length = Maxsize;
}

//按值查找
void getListItemByValue(SqList &L, int value) {
	for (int i = 0; i < L.length; i++)
	{
		if (L.data[i] == value) {
			printf("与%d匹配的有：data[%d]=%d", value, i, L.data[i]);
		}
	}
}

int main() {
	SqList L;
	InitList(L);
	getListItemByValue(L, 5);
	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
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
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
#include <stdio.h>
#include <malloc.h>

//struct LNode {
//	ElemType data;
//	struct LNode* next;
//};
//typedef struct LNode LNode；
//typedef struct LNode* LinkList;

//等价定义
typedef struct LNode {
	int data;
	struct LNode* next;
}LNode, *LinkList;

//无头结点创建
bool InitListNoHead(LinkList &L) {
	L = NULL;
	return true;
}

//有头节点创建
bool InitList(LinkList &L) {
	L = (LNode*)malloc(sizeof(LNode));
	if (L == NULL)
	{
		return false;
	}
	L->next = NULL;
	return true;
}

//头插法建立单链表
void ListHeadInsert(LinkList &L, int size) {
	LNode* new_point;
	for (int i = 0; i < size; i++)
	{
		new_point = (LNode*)malloc(sizeof(LNode));
		new_point->data = i + 1;
		new_point->next = L->next;
		L->next = new_point;
	}
}

//尾插法建立单链表
void ListTailInsert(LinkList &L, int size) {
	LNode* new_point;
	LNode* last_point = L;
	for (int i = 0; i < size; i++)
	{
		new_point = (LNode*)malloc(sizeof(LNode));
		new_point->data = i + 1;
		last_point->next = new_point;
		last_point = new_point;
	}
	last_point->next = NULL;
}

//求单链表的长度
void ShowListLenght(LinkList &L) {
	LNode* point = L->next;
	int num = 0;
	while (point != NULL)
	{
		point = point->next;
		num += 1;
	}
	printf("单链表长度为：%d\n", num);
}

//打印单链表
void ShowList(LinkList &L) {
	LNode* point = L->next;
	while (point != NULL)
	{
		printf("%d\n", point->data);
		point = point->next;
	}
}

//非空判断
bool isEmpty(LinkList L) {
	return (L == NULL || L->next == NULL);
}

//指定结点的后插操作
bool InsertNextNode(LNode* point, int element) {
	if (point == NULL)
	{
		return false;
	}
	LNode* next_point = (LNode*)malloc(sizeof(LNode));
	if (next_point == NULL)
	{
		return false;
	}
	next_point->data = element;
	next_point->next = point->next;
	point->next = next_point;
	return true;
}

//按位序插入（无头结点）
bool LinkInsertNoHead(LinkList &L, int index, int element) {
	if (index < 1)
	{
		return false;
	}
	if (index == 1)
	{
		LNode* next_point = (LNode*)malloc(sizeof(LNode));
		next_point->data = element;
		next_point->next = L->next;
		L = next_point;
		return true;
	}
	LNode* point = (LNode*)malloc(sizeof(LNode));
	int i = 1;
	point = L;
	while (point != NULL && i < index)
	{
		point = point->next;
		i += 1;
	}
	if (point == NULL)
	{
		return false;
	}
	return InsertNextNode(point, element);
}

//按位序插入（有头节点）
bool ListInsert(LinkList &L, int index, int element) {
	if (index < 1)
	{
		return false;
	}
	LNode* point;
	int i = 0;
	point = L;
	while (point != NULL && i < index - 1)
	{
		point = point->next;
		i += 1;
	}
	if (point == NULL)
	{
		return false;
	}
	return InsertNextNode(point, element);
}

//巧妙进行指定节点的前插操作
bool InsertPriorNode(LNode* point, int element) {
	if (point == NULL)
	{
		return false;
	}
	LNode* prior_point = (LNode*)malloc(sizeof(LNode));
	prior_point->next = point->next;
	point->next = prior_point;
	prior_point->data = point->data;
	point->data = element;
	return true;
}

//指定结点的前插操作
bool InsertPriorNode(LNode* point, LNode* prior_point) {
	if (point == NULL || prior_point == NULL)
	{
		return false;
	}
	prior_point->next = point->next;
	point->next = prior_point;
	int temp = point->data;
	point->data = prior_point->data;
	prior_point->data = temp;
	return true;
}

//带头结点的 按位序删除
bool ListDelete(LinkList &L, int index) {
	if (index < 1)
	{
		return false;
	}
	LNode* point = L;
	int i = 0;
	while (point != NULL && i < index - 1)
	{
		point = point->next;
		i += 1;
	}
	if (point->next == NULL)
	{
		return false;
	}
	LNode* delete_point = point->next;
	printf("正在删除的是 %d\n", delete_point->data);
	point->next = delete_point->next;
	free(delete_point);
	return true;
}

//指定节点的删除操作
bool ListDelete(LNode* point) {
	if (point == NULL)
	{
		return false;
	}
	LNode* temp_point = point->next;
	point->data = temp_point->data;
	point->next = temp_point->next;
	free(temp_point);
	return true;
}

void GetLNodeByIndex(LinkList L, int index) {
	if (index < 1)
	{
		printf("输入有误\n");
		return;
	}
	LNode* point = L;
	int i = 0;
	while (point != NULL && i < index)
	{
		point = point->next;
		i += 1;
	}
	printf("单链表中第%d位的值为：%d", index, point->data);
}

//根据值查找
void GetLNodeByValue(LinkList &L, int element) {
	LNode* point = L;
	int index = 0;
	while (point != NULL)
	{
		if (point->data == element)
		{
			printf("查询到单链表中第%d位为：%d\n", index, element);
		}
		point = point->next;
		index += 1;
	}
}

int main() {
	LinkList L;
	InitList(L);
	ListTailInsert(L, 10);
	ShowList(L);
	ShowListLenght(L);
	GetLNodeByValue(L, 5);
	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
#include <stdio.h>
#include <malloc.h>

//基本定义
typedef struct DNode {
	int data;
	struct DNode* next, * prior;
}DNode,* DLinklist;

//带头结点的初始化
bool InitDLinklist(DLinklist &L) {
	L = (DNode*)malloc(sizeof(DNode));
	if (L==NULL)
	{
		return false;
	}
	L->next = NULL;
	L->prior = NULL;
	return true;
}

//判断双链表是否为空
bool isEmpty(DLinklist &L) {
	return(!L->next);
}

//双链表的插入操作
bool InsertNextDNode(DNode *base_point, DNode *next_point) {
	if (base_point == NULL || next_point == NULL)
	{
		return false;
	}
	next_point->next = base_point->next;
	if (base_point->next != NULL)
	{
		base_point->next->prior = next_point;
	}
	next_point->prior = base_point;
	base_point->next = next_point;
	return true;
}

//删除某个点后的后继节点 只需要将两个元素链接起来就可以
bool DeleteNextDNode(DNode *point) {
	if (point == NULL)
	{
		return false;
	}
	DNode* delete_point = point->next;
	if (delete_point == NULL)
	{
		return false;
	}
	//设置该节点的后置节点
	point->next = delete_point->next;
	if (delete_point->next != NULL)
	{
		//设置后置节点的前置节点
		delete_point->next->prior = point;
	}
	free(delete_point);
}

//删除整个双链表
void DestoryList(DLinklist &L) {
	while (L->next !=NULL)
	{
		DeleteNextDNode(L);
	}
	free(L);
	L = NULL;
}

//遍历双链表
void showList(DNode *point) {
	//后向遍历
	while (point != NULL)
	{
		point = point->next;
	}
	//前向遍历
	while (point != NULL)
	{
		point = point->prior;
	}
	//前向遍历（跳过头结点）
	while (point->prior != NULL) {
		point = point->prior;
	}
}

int main() {
	DLinklist L;
	InitDLinklist(L);
	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
#include <stdio.h>
#include <malloc.h>

typedef struct LNode {
	int data;
	struct LNode* next;
}LNode, * Linklist;

bool InitList(Linklist &L) {
	L = (LNode*)malloc(sizeof(LNode));
	if (L == NULL)
	{
		return false;
	}
	L->next = L;
	return true;
}

bool isEmpty(Linklist &L) {
	return L->next == L;
}

bool isTail(Linklist &L, LNode *point) {
	return point->next == L;
}

循环双链表

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
#include <stdio.h>
#include <malloc.h>

typedef struct DNode {
	int data;
	struct DNode* prior, * next;
}DNode, * Dlinklist;

bool InitDLinklist(Dlinklist &L) {
	L = (DNode*)malloc(sizeof(DNode));
	if (L == NULL)
	{
		return false;
	}
	L->prior = L;
	L->next = L;
	return true;
}

bool isEmpty(Dlinklist &L) {
	return L->next = L;
}

bool isTail(Dlinklist &L, DNode *point) {
	return point->next == L;
}

bool InsertNextNode(DNode *point, DNode *next_point) {
	next_point->next = point->next;
	point->next->prior = next_point;
	next_point->prior = point;
	point->next = next_point;
}

bool DeleteNode(DNode *point) {
	DNode* prior_point = point->prior;
	prior_point->next = point->next;
	point->next->prior = prior_point;
	free(point);
}

静态链表

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
#include <stdio.h>
#include <malloc.h>
#define Maxsize 10

struct Node
{
	int data;
	int next;
};

typedef struct {
	int data;
	int next;
}SLinklist[Maxsize];

int main() {
	struct Node x;
	printf("%d\n", sizeof(x));

	struct Node l[Maxsize];
	printf("%d\n", sizeof(l));

	SLinklist L;
	printf("%d\n", sizeof(L));
	return 0;
}

顺序表和链表的比较

本文标题:数据结构-第二章-线性表

文章作者:fanchen

发布时间:2021年05月09日 - 14:59:36

最后更新:2021年05月28日 - 18:19:01

原始链接:http://88fanchen.github.io/posts/e87c7b5c/

许可协议:署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。