【手撕数据结构】（三）顺序表和链表

一、线性表

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

二、顺序表

1.概念及结构

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

顺序表的本质是一个数组；要求数据必须从前往后连续存储。

2.关于数组

（1）数组怎么管理？

指针指向数组开始的位置，就能找到后面的位置。

（2）数组的缺陷

数组删除数据时，不能把数据所在的这块空间释放掉，只能把这一片数组空间都释放掉。数组删除元素的方式是挪动覆盖。

（3）数组的优势

下标的随机访问（原因是数组的物理空间连续）
a[i]等价于*(a+i)

（4）怎样弥补数组的缺陷

用链表。链表是一块一块的小空间，不是一个完整的连续空间。
如果有一个指针指向链表的第一个位置，不能找到后面的位置。因为他们是一块一块独立的空间，是多次malloc出来的，它们之间在地址上是没有关联的。
要想找到下一个位置，就得在上一个位置处存一个指针，指针指向下一个地址。

（二分查找不能在链表中使用，能在数组中使用；
排序不能在链表中使用，能在数组中使用）

3.顺序表分类

🎗️静态顺序表

使用定长数组存储元素。

#define N 7
typedef int SLDataType;
typedef struct SeqList {
	SLDataType array[N];  //定长数组
	int size;     //有效数据的个数
}SeqList;
1
2
3
4
5
6

总结：
静态顺序表缺点：空间是固定的，给小了不够用，给多了浪费

🎗️动态顺序表

使用动态开辟的数组存储。

typedef int SLDataType;
typedef struct SeqList {
	SLDataType* array;  //指向动态开辟的数组
	int size;  //存储的有效数据个数（知道什么时候扩容）
	int capacity;  //容量空间的大小
};
1
2
3
4
5
6

4.接口实现

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

（1）思路

建立三个文件
SeqList.c写接口的实现
SeqList.h写接口的声明
test.c写调用测试接口

（2）SeqList.h文件代码

首先，在里面定义动态顺序表的结构体

功能1：顺序表初始化

🎗️注意：在形参部分不要写成下面这样：

如果写成这样，就会出现经典的传值传参问题。此时，传过去的是值，实参传给形参，是一种拷贝。把s传给形参sl，形参sl变量的改变不会影响实参s,因为他们是在两个栈帧里面。
所以不要传结构体的值，而要传结构体的地址。

功能2：销毁顺序表

功能3：尾插

功能4：头插

功能5：尾删

功能6：头删

功能7：打印

功能8：在pos位置处插入数据

功能9：在pos位置处删除数据

功能10：查找，找到返回下标，没有找到返回-1

功能11：修改pos位置处的值

完整代码展示

#define _CRT_SECURE_NO_WARNINGS 1

#pragma once
#include
#include
#include


typedef int SLDataType;
typedef struct SeqList {
	SLDataType* a;
	int size;
	int capacity;
}SL;

void SLInit(SL* psl);//顺序表初始化
void SlDestroy(SL* psl);//销毁顺序表
void SLPushBack(SL* psl, SLDataType x);//尾插
void SLPushFront(SL* psl, SLDataType x);//头插
void SLPopBack(SL* psl);//尾删
void SLPopFront(SL* psl);//头删
void SLPrint(SL* psl);//打印
void SLInsert(SL* psl, int pos, SLDataType x); //在pos位置处插入数据
void SLErase(SL* psl, int pos);  //在pos位置处删除数据（也经常写作SLRemove)
int SLFind(SL* psl, SLDataType x);  //查找，找到返回下标，没有找到返回-1
void SLModify(SL* psl, int pos, SLDataType x); //修改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

（3）SeqList.c文件代码

实现功能1：顺序表初始化

实现功能2：销毁顺序表

实现功能3：尾插

辅助功能：检查容量

实现功能4：头插

实现功能5：尾删

实现功能6：头删

实现功能7：打印

实现功能8：在pos位置处插入数据

复写功能：复用SLInsert重写头插、尾插

实现功能9：在pos位置处删除数据

复写功能：复用SLErase覆写头删、尾删

实现功能10：查找

实现功能11：修改pos位置处的值

完整代码

#define _CRT_SECURE_NO_WARNINGS 1
#include "SeqList.h"

//顺序表初始化
void SLInit(SL* psl) {
	assert(psl);//断言，判断传进来的指针不是空指针，避免后续对空指针解引用出错
	psl->a = (SLDataType*)malloc(sizeof(SLDataType) * 4);//在初始化的时候，最好的写法是一开始就开辟一点空间，开四个（不长也不短，是一个合适的数字）
	if (psl->a == NULL) {                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                   
		perror("malloc fail"); 
		return;
	}
	psl->size = 0;
	psl->capacity = 4;
}

//销毁顺序表---意思是把空间还给操作系统，像退房一样
void SLDestroy(SL* psl) {
	assert(psl);
	free(psl->a);
	psl->a = NULL;
	
	psl->size = 0;
	psl->capacity = 0;
}

//尾插
void SLPushBack(SL* psl, SLDataType x) {
	assert(psl);
	psl->a[psl->size] = x;
	psl->size++;
}

//检查容量
void SLCheckCapacity(SL* psl) {
	assert(psl);
	if (psl->size == psl->capacity) {
		SLDataType* tmp = (SLDataType*)realloc(psl->a, sizeof(SLDataType) * psl->capacity * 2);
		if (tmp == NULL) {
			perror("realloc fail");
			return;
		}
		psl->a = tmp;
		psl->capacity *= 2;
	}
}

//打印
void SLPrint(SL* psl) {
	assert(psl);
	for (int i = 0; i < psl->size; i++) {
		printf("%d ", psl->a[i]);
	}
	printf("\n");
}

//头插
void SLPushFront(SL* psl, SLDataType x) {
	assert(psl);
	SLCheckCapacity(psl);

	//挪动数据
	int end = psl->size - 1;
	while (end >= 0) {
		psl->a[end + 1] = psl->a[end];
		--end;
	}
	psl->a[0] = x;
	psl->size++;
}

//由在pos位置插入数据的功能函数重写头插、尾插，复用SLInsert
//void SLPushFront(SL* psl, SLDataType x) {
//	SLInsert(psl, 0, x);
//}
//void SLPushBack(SL* psl, SLDataType x) {
//	SLInsert(psl, psl->size, x);
//}

//尾删
void SLPopBack(SL* psl) {
	assert(psl);
	/*
	顺序表为空时，就不要再删了
	温柔的检查
	if (psl->size == 0) {
		return 0;
	}
	暴力检查（推荐）:断言，如果psl->size>0为真就通过了，如果为假就会报错
	assert(psl->size > 0);
	*/
	
	//暴力检查（推荐）
	assert(psl->size > 0);


	//psl->a[psl->size-1]=0;
	//注意这样写不好，万一最后一个位置是0，这样做没意义，如果在数组中的元素类型是double，如今改为0不好，最好改为0.0
	//所以最好的做法是不管尾部数据是多少，只修改顺序表的长度size（有效数据个数）

	psl->size--;
}

//头删
void SLPopFront(SL* psl) {
	assert(psl);
	//暴力检查顺序表是不是为空
	assert(psl->size);

	//把下标start+1的元素挪给下标start处
	int start = 0; 
	while (start < psl->size - 1) {
		psl->a[start] = psl->a[start + 1];
		start++;
	}
	

	/*
	start为1时，将下标start的元素挪给下标start-1处
	int start = 1;
	while (start < psl->size) {
		psl->a[start - 1] = psl->a[start];
		start++;
	}
	*/

	psl->size--;
	
}

//在pos位置处插入数据
void SLInsert(SL* psl,int pos, SLDataType x) {
	assert(psl);
	assert(0 <= pos && pos <= psl->size); //断言pos,不要让插入的位置下标越界

	SLCheckCapacity(psl);  //只要是插入数据，都要关注容量
	int end = psl->size - 1;
	while (end >= pos) {
		psl->a[end + 1] = psl->a[end];
		--end;
	}
	psl->a[pos] = x;
	psl->size++;
}


//在pos位置处删除数据
void SLErase(SL* psl, int pos){
	assert(psl);
	assert(0 <= pos && pos < psl->size); //注意这里的pos不能等于psl->size
	//assert(psl->size>0);  这句代码是用来断言有效数据个数为不为空，为空时不用删，但是这句代码加不加都行，因为上一句已经间接检查了

	int start = pos + 1;
	while (start < psl->size) {
		psl->a[start - 1] = psl->a[start];
		++start;
	}
	psl->size--;
}

//复用SLErase覆写头删、尾删
//void SLPopFront(SL* psl) {
//	SLErase(psl, 0);
//}
//void SLPopBack(SL* psl) {
//	SLErase(psl, psl->size - 1);
//}


//查找
int SLFind(SL* psl, SLDataType x) {
	assert(psl);
	for (int i = 0; i < psl->size; i++) {
		if (psl->a[i] == x) {
			return i;
		}
	}
	return -1;
}

//修改
void SLModify(SL* psl, int pos,SLDataType x) {
	assert(psl);
	assert(0 <= pos && pos < psl->size);

	psl->a[pos] = x;
}
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

（4）test.c文件代码

测试1：尾插

测试2：头插

测试3：尾删

测试4：头删

测试5：pos位置处插入

测试6：pos位置处删除

测试7：查找

测试8：如果有人传进来空指针怎么办？

所以说怎么办？

在每个函数内部做一下断言，暴力检查一下。暴力检查的好处是不用调试，出错时会出现错误提示。如下图：

为什么不在main函数中做断言？

写的函数才是给我们用的，不要在调用函数时去检查（也就是说让调用的人去检查，如果他会检查，就不会传空进来了）

---

总结

顺序表的内容就到这里啦~欢迎大家关注后续内容
👻