DS-顺序表/链表

一.线性表

线性表 (linear list) 是n个具有相同特性的数据元素的有限序列。

线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

二.顺序表

1.顺序表的概念与结构

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。

顺序表一般可分为：

静态顺序表：使用定长数组存储元素

动态顺序表：使用动态开辟的数组存储。

2.接口实现

静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，所以下面我们实现动态顺序表。

SeqList.h

typedef int SLDateType;//定义数据类型
typedef struct SeqList
{
	SLDateType* a;
	int size;
	int capacity;
}SeqList;
// 顺序表扩容
void SeqListexpand(SeqList* ps);

// 对数据的管理:增删查改 
void SeqListInit(SeqList* ps);//初始化
void SeqListDestroy(SeqList* ps);//释放
bool SeqListEmpty(SeqList* ps);//判空
void SeqListPrint(SeqList* ps);//打印
void SeqListPushFront(SeqList* ps, SLDateType x);//头插
void SeqListPushBack(SeqList* ps, SLDateType x);//尾插
void SeqListPopFront(SeqList* ps);//头删
void SeqListPopBack(SeqList* ps);//尾删
int SeqListLength(SeqList* ps);//表长

// 顺序表查找
int SeqListFind(SeqList* ps, SLDateType x);
// 顺序表在pos位置的值
int SeqListGet(SeqList* ps, int pos);
// 顺序表在pos位置插入x
void SeqListInsert(SeqList* ps, int pos, SLDateType x);
// 顺序表删除pos位置的值
void SeqListErase(SeqList* ps, int pos);

// 归并顺序表
void SeqListMerge(SeqList* ps1, SeqList* ps2, SeqList* ret);
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

SeqList.c

#define _CRT_SECURE_NO_WARNINGS
#include "SeqList.h"

//顺序表扩容
void SeqListexpand(SeqList* ps)
{
	assert(ps);
	int* temp = realloc(ps->a, SEQ_MAX * sizeof(SLDateType) * 2);
	if (!temp)
	{
		perror("realloc-error");
		exit(1);
	}
	ps->a = temp;
	ps->capacity *= 2;
	return;
}

void SeqListInit(SeqList* ps)
{
	assert(ps);
	ps->a = (SLDateType*)malloc(SEQ_MAX, sizeof(SLDateType));
	if (!ps->a)
	{
		perror("malloc-error");
		exit(1);
	}
	ps->size = 0;
	ps->capacity = SEQ_MAX;
	return;
}
void SeqListDestroy(SeqList* ps)
{
	assert(ps);
	int* temp = ps->a;
	ps->a = NULL;
	free(ps->a);
	ps->size = ps->capacity = 0;
	return;
}

bool SeqListEmpty(SeqList* ps)
{
	assert(ps);
	if (ps->size == 0)
	{
		return true;
	}
	else
	{
		return false;
	}
}

void SeqListPrint(SeqList* ps)
{
	assert(ps);
	for (int i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->a[i]);
	}
	printf("\n");
	return;
}
void SeqListPushFront(SeqList* ps, SLDateType x)
{
	assert(ps);
	if (ps->size >= ps->capacity)
	{
		SeqListexpand(ps);
	}
	ps->size++;
	for (int i = ps->size - 1; i > 0; i--)
	{
		ps->a[i] = ps->a[i - 1];
	}
	ps->a[0] = x;
	return;
}
void SeqListPushBack(SeqList* ps, SLDateType x)
{
	assert(ps);
	if (ps->size >= ps->capacity)
	{
		SeqListexpand(ps);
	}
	ps->a[ps->size++] = x;
	return;
}
void SeqListPopFront(SeqList* ps)
{
	assert(ps);
	assert(ps->size);
	for (int i = 0; i < ps->size - 1; i++)
	{
		ps->a[i] = ps->a[i + 1];
	}
	ps->size--;
	return;
}
void SeqListPopBack(SeqList* ps)
{
	assert(ps);
	assert(ps->size);
	ps->size--;
	return;
}


int SeqListLength(SeqList* ps)
{
	assert(&ps);
	return ps->size;
}

// 顺序表查找
int SeqListFind(SeqList* ps, SLDateType x)
{
	assert(ps);
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->a[i] == x)
		{
			return i;
		}
	}
	return -1;
}
// 顺序表在pos位置插入x
void SeqListInsert(SeqList* ps, int pos, SLDateType x)
{
	assert(ps);
	if (pos >= 0 && pos <= ps->size)
	{
		if (ps->size >= ps->capacity)
		{
			SeqListexpand(ps);
		}
		for (int i = ps->size; i > pos; i--)
		{
			ps->a[i] = ps->a[i - 1];
		}
		ps->size++;
		ps->a[pos] = x;
	}
	return;
}

// 顺序表在pos位置的值
int SeqListGet(SeqList* ps, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);
	return ps->a[pos];
}

// 顺序表删除pos位置的值
void SeqListErase(SeqList* ps, int pos)
{
	assert(ps);
	if (pos >= 0 && pos <= ps->size)
	{
		assert(ps->size);
		for (int i = pos; i < ps->size - 1 ; i++)
		{
			ps->a[i] = ps->a[i + 1];
		}
		ps->size--;
	}
	return;
}

// 归并顺序表
void SeqListMerge(SeqList* ps1, SeqList* ps2, SeqList* ret)
{
	assert(ps1 && ps2 && ret);
	int i = 0, j = 0, k = 0;
	int sl1_len = SeqListLength(ps1), sl2_len = SeqListLength(ps2);
	while (i < sl1_len && j < sl2_len)
	{
		if (ps1->a[i] <= ps2->a[j])
		{
			SeqListPushBack(ret, ps1->a[i++]);
		}
		else
		{
			SeqListPushBack(ret, ps2->a[j++]);
		}
	}
	while (i < sl1_len)
	{
		SeqListPushBack(ret, ps1->a[i++]);
	}
	while (j < sl2_len)
	{
		SeqListPushBack(ret, ps2->a[j++]);
	}
	return;
}
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

三.链表

1.链表的概念与结构

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。

2.链表的分类

链表的结构非常多样，以下情况组合起来就有8种链表结构：

单向或者双向

带头或者不带头

循环或者非循环

3.链表的实现

SLIst.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>

typedef int SLTDateType;
typedef struct SListNode
{
	SLTDateType data;
	struct SListNode* next;
}SListNode;

// 动态申请一个节点
SListNode* BuySListNode(SLTDateType x);
// 单链表打印
void SListPrint(SListNode* plist);
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x);
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x);
// 单链表的尾删
void SListPopBack(SListNode** pplist);
// 单链表头删
void SListPopFront(SListNode** pplist);
// 单链表的长度
int SListLength(SListNode* plist, int pos);
// 单链表第pos个元素的值
SLTDateType SListGetElem(SListNode* plist, int pos);
// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x);
// 单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDateType x);
// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos);

// 单链表的销毁
void SListDestroy(SListNode* plist);

// 单链表的判空
bool SListEmpty(SListNode* plist);

// 归并链表
SListNode* SListMerge(SListNode* ps1, SListNode* ps2);
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

SList.c

#include "SList.h"

//动态申请一个节点
SListNode* BuySListNode(SLTDateType x)
{
	SListNode* Nextnode = malloc(sizeof(SListNode));
	if (!Nextnode)
	{
		perror("malloc fail");
		return NULL;
	}
	Nextnode->data = x;
	Nextnode->next = NULL;
	return Nextnode;
}

//打印单链表
void SListPrint(SListNode* plist)
{
	SListNode* cur = plist;
	while (cur)
	{
		printf("%d -> ", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
	return;
}

// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x)
{
	assert(pplist);
	SListNode* Newnode = BuySListNode(x);
	SListNode* tail = *pplist;
	if (!*pplist)
	{
		*pplist = Newnode;
	}
	else
	{
		while (tail->next)
		{
			tail = tail->next;
		}
		tail->next = Newnode;
	}
	return;
}

// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x)
{
	assert(pplist);
	SListNode* Newnode = BuySListNode(x);
	Newnode->next = *pplist;
	*pplist = Newnode;
}
// 单链表的尾删
void SListPopBack(SListNode** pplist)
{
	assert(pplist);
	SListNode* tail = *pplist;
	if (!*pplist)
	{
		return;
	}
	else if (!(*pplist)->next)
	{
		*pplist = NULL;
	}
	else
	{
		while (tail->next->next)
		{
			tail = tail->next;
		}
		free(tail->next);
		tail->next = NULL;
	}
	return;
}
// 单链表头删
void SListPopFront(SListNode** pplist)
{
	assert(pplist);
	if (!*pplist)
	{
		return;
	}
	else
	{
		SListNode* first = *pplist;
		*pplist = (*pplist)->next;
		free(first);
		first = NULL;
	}
}
// 单链表的长度
int SListLength(SListNode* plist, int pos)
{
	assert(plist);
	int count = 0;
	SListNode* cur = plist->next;
	while (cur = cur->next)
	{
		++count;
	}
	return count;
}
// 单链表第pos个元素的值
SLTDateType SListGetElem(SListNode* plist, int pos)
{
	assert(plist);
	SListNode* cur = plist;
	while (pos--)
	{
		assert(cur);
		cur = cur->next;
	}
	assert(cur);
	return cur->data;
}
// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x)
{
	assert(plist);
	SListNode* cur = plist;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		else
		{
			cur = cur->next;
		}
	}
	return NULL;
}

// 单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDateType x)
{
	assert(pos);
	SListNode* Nextnode = BuySListNode(x);
	Nextnode->next = pos->next;
	pos->next = Nextnode;
	return;
}

// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos)
{
	assert(pos);
	assert(pos->next);
	SListNode* temp = pos->next;
	pos->next = pos->next->next;
	free(temp);
	return;
}

// 单链表的销毁
void SListDestroy(SListNode* plist)
{
	SListNode* next = NULL;
	while (plist)
	{
		next = plist->next;
		free(plist);
		plist = next;
	}
}

bool SListEmpty(SListNode* plist)
{
	assert(plist);
	if (plist->next == NULL)
	{
		return true;
	}
	else
	{
		return false;
	}
}

// 归并链表
SListNode* SListMerge(SListNode* ps1, SListNode* ps2)
{
	SListNode* ret = NULL;
	SListNode* tps1 = ps1;
	SListNode* tps2 = ps2;
	while (tps1 != NULL && tps2 != NULL)
	{
		if (tps1->data < tps2->data)
		{
			SListPushBack(&ret, tps1->data);
			tps1 = tps1->next;
		}
		else
		{
			SListPushBack(&ret, tps2->data);
			tps2 = tps2->next;
		}
	}
	while (tps1)
	{
		SListPushBack(&ret, tps1->data);
		tps1 = tps1->next;
	}
	while (tps2)
	{
		SListPushBack(&ret, tps2->data);
		tps2 = tps2->next;
	}
	return ret;
}
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

4.顺序表与链表的区别

不同点	顺序表	链表
存储空间上	物理上一定连续	逻辑上连续，但物理上不一定连续
随机访问	支持O(1)	不支持：O(N)
任意位置插入或者删除元素	可能需要搬移元素，效率低O(N)	只需修改指针指向
插入	动态顺序表，空间不够时需要扩容	没有容量的概念
应用场景	元素高效存储+频繁访问	任意位置插入和删除频繁
缓存利用率	高	低