【C语言】用纯C来创建顺序表

🐖前言

⭐什么是顺序表？

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

🐖顺序表的创建

需要创建一个小项目工程
创建三个文件
⭐seqlist.h放顺序表的头文件，函数声明
⭐seqlist.c放顺序表的函数
⭐test.c是主函数。存放框架

(1)🐕创建一个静态顺序表

对于这个来说，顺序表就是一个数组，但是我们需要记录顺序表的有效数据，所以我们就用结构体创建一个顺序表，为了让后续用顺序表的时候更加的方便，我们可以typedef一下让我的代码看起来更加简洁。

#define N 10
//静态顺序表
typedef struct Seqlist
{
	int a[N];
	int size;//记录存储多少个有效数据
}SL;//重新命名一下让后面的操作更加方便
1
2
3
4
5
6
7

但是呢我们再用的时候是不是只能用int型的数据了，所以我们可以将数据类型直接typedef改个名字，当我们想改数据类型的时候就可以直接再typedef上改。

#define N 10

//将数据类型重定义一下
typedef int DataType;
//静态顺序表
typedef struct Seqlist
{
	DataType a[N];
	int size;//记录存储多少个有效数据
}SL;//重新命名一下让后面的操作更加方便
1
2
3
4
5
6
7
8
9
10

但是呢对于静态的顺序表，他是不是有点太死板了，我们开辟多了空间，用不完怎么办，开辟少了空间，不够用这么办这都是需要我们考虑的东西。所以开一个动态的就好了呀。

(1.2)🐕创建一个动态的顺序表

为了合理安排我们的需求，我们就可以动态开辟空间，我们需要多少空间就开辟多少空间，请看下面的代码

//动态顺序表---按照需求扩空间
typedef struct Seqlist
{
	DataType *a;//动态开辟数组的指针
	int size;//记录存储多少个有效数据
	int capacity;//空间容量，当sz大于他的时候再扩容
}SL;//重新命名一下让后面的操作更加方便
1
2
3
4
5
6
7

(2)🐕初始化顺序表

将数据都设为0，并且这是用指针的，这样才能改变原数据。

//初始化顺序表将数据都设为0
void SLInit(SL* ps)
{
	ps->a = NULL;
	ps->sz = 0;
	ps->capacity = 0;
}
1
2
3
4
5
6
7

(3)🐕销毁顺序表

再用动态内存开辟玩空间，我们需要销毁开辟的空间，将其free掉，为什们要现在写呢 ，就是为了一会测试我们写的函数的时候，不会报错。并且顺便把顺序表中的sz,capacity置为0.

//销毁顺序表
void SLDistory(SL* ps)
{
	//防止他是空指针
	if (ps->a != NULL)
	{
		free(ps->a);
		ps->a = NULL;
		ps->capacity = 0;
		ps->sz = 0;
	}

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

(4)🐕顺序表的尾插

如果你认为就是再顺序表的结尾插入数据，那你就想简单了，我们在上面还没有动态开辟空间呢，并且如果当你开辟的空间用完了，怎么办，这都是我们需要考虑的

我们这样想，顺序表是空的，我们刚开始肯定要插入空间，所以我们可以在顺序表的尾插中开辟空间，就不用再初始化的时候开辟空间，并且我们通过C语言中动态内存的知识,我们知道realloc当他用NULL的时候，功能相当于malloc,所以我们可以利用这个特点来写。
其他细节就看代码吧。

//顺序表的尾插
void SLPushBack(SL* ps,DataType n)
{
	
	//当空间不够的时候扩容
	if (ps->sz == ps->capacity)
	{
		//这时候就将capacity改变为新的大小
		//但是刚开始的时候capacity等于0，就算×2他还是0.
		//所以我们用一个三目表达式
		int newcapacity = ps->capacity == 0 ? 4: ps->capacity * 2;

		//当我知道开辟多少空间我们就可以用realloc
		//刚开始ps->a,是空指针，所以他这时就相当于malloc
		SLDataType* tmp = (SLDataType*)realloc(ps->a, newcapacity * sizeof(DataType));
		//防止realloc开辟一个空指针。
		if (tmp == NULL)
		{
			perror("realloc");
			exit(-1);
		}
		//将开辟空间的指针传给ps->a
		ps->a = tmp;
		//将容量也改变
		ps->capacity = newcapacity;
	}
	ps->a[ps->sz] = n;
	ps->sz++;
}
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

(4)🐕打印顺序表

该操作就是简单打印一下，我们每写一个部分，我们就检查一部分，打印就是为了看我们写的最后的效果达到了没有，这个非常简单，大家直接看代码。
⭐对于这个部分，我们需要提醒一下大家，不要等我们将全部代码写完在进行调试，我们写一个部分就测试一部分，看看这个部分有没有问题，没有问题我们再进行下一部分。

//打印顺序表
void SLPrint(SL* ps)
{
	int i = 0;
	for (i = 0; i < ps-> sz; i++)
	{
		printf("%d ", ps->a[i]);
	}
}
1
2
3
4
5
6
7
8
9

(5)🐕尾删

有同学可能想能不能直接将最后一个数据直接变成0，是不是将相当于将最后一个数据删除了呢
但是同学们可以这也想，本来人家原本的数据就是0，那你再改成0，好像什么都没做，
其实可以直接将sz–，不就巧妙的将最后一个数据删掉了吗，有的人想不明白的，他明明还在哪呀，怎么叫删掉了呢，其实你sz–，你不用他了，下一回插入的时候不就直接覆盖掉了吗？

//尾删顺序表
void SLPopBack(SL* ps)
{
	//检查顺序表是否为空
	//温柔的检查
	/*if (ps->sz == 0)
	{
		printf("顺序表为空\n");
		return;
	}*/

	//暴力的检查
	//断言看他是否空了
	assert(ps->sz > 0);

	//将sz的值直接减一就相当于删除了
	ps->sz--;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

(6)🐕头插

我们在想一下，在进行头插的时候我们需要从第一个位置开始依次向后移一个位置，如果我们从sz=1的时候向后移。我们会将后面的东西覆盖掉，说明从前到后是不可取的，我们应该从sz最大的时候向后移动一位，再将前面的依次向后退一个。

我们还需要注意一点，我们再插入的时候还需要检查一下，顺序表的容量是不是满了，因为我们再尾插中用过这个，所以我们可以将这个封装一个检查容量函数

(7)🐕检查容量函数

: 代码如下

//检查顺序表容量
void SLCheckCapacity(SL* ps)
{
	assert(ps);
	//当空间不够的时候扩容
	if (ps->sz == ps->capacity)
	{
		//这时候就将capacity改变为新的大小
		//但是刚开始的时候capacity等于0，就算×2他还是0.
		//所以我们用一个三目表达式
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;

		//当我知道开辟多少空间我们就可以用realloc
		//刚开始ps->a,是空指针，所以他这时就相当于malloc
		SLDataType* tmp = (SLDataType*)realloc(ps->a, newcapacity * sizeof(SLDataType));
		//防止realloc开辟一个空指针。
		if (tmp == NULL)
		{
			perror("realloc");
			exit(-1);
		}
		//将开辟空间的指针传给ps->a
		ps->a = tmp;
		//将容量也改变
		ps->capacity = newcapacity;
	}
}
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

头插函数

代码

//头插顺序表
void SLPushFront(SL* ps, SLDataType n)
{
	//检查容量是否满了
	SLCheckCapacity(ps);
	int i = 0;
	//下面这个大家画图自己看看，肯定能弄出来
	int end = ps->size - 1;
	while (end >= 0)
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}
	ps->a[0] = n;
	ps->sz++;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

在这里提一个问题

头插和尾插的时间复杂度是多少
我们可以清楚的看到尾插的时间复杂度是O(1),直接动最后一个就行了
而头插需要从最后一个开始挪，所以他的时间复杂度是O(N).
所以我们再用的时候一般都用尾插

(8)🐕头删

头删和尾删基本相同，最关键的问题就是越界问题，
我们需要知道，越界不一定会报错，但是后续的操作一定会受影响
越界读，不一定会报错。
越界写，可能会被检查出来，他是一种抽查。不会一个一个查。

//头删顺序表
void SLPopFront(SL* ps)
{
	assert(ps);
	int i = 0;
	//他删除可能会越界，因为删除次数大于sz的时候
	assert(ps->sz > 0);
	//画图确认逻辑很简单的
	int begin = 1;
	while (begin < ps->sz)
	{
		ps->a[begin - 1] = ps->a[begin];
		begin++;
	}
	ps->sz--;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

(9)🐕从中间插入数据

我们想一个问题，对于我们这从中间插入的数据，是不是包括头插和尾插呀，直接将参数改一下是不是能轻松的，所以我们头插尾插可以直接调用这个函数，就变得很简单。

//中间的插入
//在pos位置插入数据n
void SLInsert(SL* ps, int pos, SLDataType n)
{
	assert(ps);
	//pos也需要检查一下，防止pos不在范围内
	assert(pos >= 0);
	assert(pos <= ps->sz);

	//挪动数据
	//先检查容量
	SLCheckCapacity(ps);
	int end = ps->sz - 1;
	while (end >= pos)
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}

	ps->a[pos] = n;
	ps->sz++;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

(10)🐕从中间删除数据

我们想一个问题，对于我们这从中间删除的数据，是不是包括头删和尾删呀，直接将参数改一下是不是能轻松的，所以我们头删尾删可以直接调用这个函数，就变得很简单。

//删除pos位置的数据
void SLErase(SL* ps, int pos)
{
	assert(ps);
	assert(pos >= 0);
	assert(pos < ps->sz);
	
	//挪动数据覆盖
	int begin = pos + 1;
	while (begin < ps->sz)
	{
		ps->a[begin - 1] = ps->a[begin];
		begin++;
	}
	ps->sz--;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

(11)🐕查找数据

我们如果想通过找到数据，然后再做删除插入操作，那么我们需要在封装一层函数，找到数据对应的下标，然后我在进行插入删除操作。

//查找数据的位置
int SLFind(SL* ps, SLDataType x)
{
	assert(ps);
	for (int i = 0; i < ps->sz; i++)
	{
		if (ps->a[i] == x)
		{
			return i ;
		}
	}
	return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

(12)写菜单

对于数据结构来说，我们的菜单其实就是起一个交互作用，对于我们学习知识来说没有太大的影响，并且对于调试我们每写一个功能来说也是不方便的，所以我们就简单做一个框架，大家把前面的东西弄明白就行。

#define _CRT_SECURE_NO_WARNINGS 1
#include"seqlist.h"
void menu()
{
	printf("**************************************\n");
	printf("****1.尾插数据   2.尾删数据      *****\n");
	printf("****3.头插数据   4 头删数据      *****\n");
	printf("****5.插入数据   6.删除指定数据  *****\n");
	printf("****7.查找数据   8.打印数据      *****\n");
	printf("****0.退出                       *****\n");
	printf("**************************************\n");
}
int main()
{
	SL sl;
	SLInit(&sl);
	int option = 0;
	int tmp = 0;
	do 
	{
		printf("请输入操作数\n");
		scanf("%d", &option);
		switch(option)
		{
		case 1:
			printf("请输入尾插的数据以-1结束\n");
			while (tmp!=-1)
			{
				scanf("%d", &tmp);
			}
			SLPushBack(&sl,tmp);
			break;
		case 2:
			break; 
		case 3:
			break; 
		case 4:
			break; 
		case 5:
			break; 
		case 6:
			break; 
		case 7:
			break;
		case 8:
			printf("打印数据\n");
			SLPrint(&sl);
			break;
		case 0:
			printf("退出程序\n");
			break;
		default:
			printf("输入错误请重新输入\n");
			break;
		}
		menu();

	} while (option);
	SLDistory(&sl);
	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

seqlist.c的内容

我们在这里存放，函数的内部是实现

#define _CRT_SECURE_NO_WARNINGS 1

#include "seqlist.h"

//初始化顺序表将数据都设为0
void SLInit(SL* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->sz = 0;
	ps->capacity = 0;
}

//销毁顺序表
void SLDistory(SL* ps)
{
	assert(ps);
	//防止他是空指针
	if (ps->a != NULL)
	{
		free(ps->a);
		ps->a = NULL;
		ps->capacity = 0;
		ps->sz = 0;
	}

}
//检查顺序表容量
void SLCheckCapacity(SL* ps)
{
	assert(ps);
	//当空间不够的时候扩容
	if (ps->sz == ps->capacity)
	{
		//这时候就将capacity改变为新的大小
		//但是刚开始的时候capacity等于0，就算×2他还是0.
		//所以我们用一个三目表达式
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;

		//当我知道开辟多少空间我们就可以用realloc
		//刚开始ps->a,是空指针，所以他这时就相当于malloc
		SL* tmp = (SL*)realloc(ps->a, newcapacity * sizeof(SLDataType));
		//防止realloc开辟一个空指针。
		if (tmp == NULL)
		{
			perror("realloc");
			exit(-1);
		}
		//将开辟空间的指针传给ps->a
		ps->a = tmp;
		//将容量也改变
		ps->capacity = newcapacity;
	}
}

//顺序表的尾插
void SLPushBack(SL* ps,SLDataType n)
{
	assert(ps);
	//SLCheckCapacity(ps);
	//ps->a[ps->sz] = n;
	//ps->sz++;
	SLInsert(ps, ps->sz, n);
}
//打印顺序表
void SLPrint(SL* ps)
{
	assert(ps);
	int i = 0;
	for (i = 0; i < ps-> sz; i++)
	{
		printf("%d ", ps->a[i]);
	}
	printf("\n");
}

//尾删顺序表
void SLPopBack(SL* ps)
{
	//检查顺序表是否为空
	//温柔的检查
	/*if (ps->sz == 0)
	{
		printf("顺序表为空\n");
		return;
	}*/

	//暴力的检查
	//断言看他是否空了
	assert(ps->sz > 0);

	//将sz的值直接减一就相当于删除了
	/*ps->sz--;*/
	SLErase(ps, ps->sz-1);
}

//头插顺序表
void SLPushFront(SL* ps, SLDataType n)
{
	assert(ps);
	//检查容量是否满了
	//SLCheckCapacity(ps);
	//int end = ps->size - 1;
	//while (end >= 0)
	//{
	//	ps->a[end + 1] = ps->a[end];
	//	end--;
	//}
	//ps->a[0] = n;
	//ps->sz++;
	SLInsert(ps, 0, n);
}
//头删顺序表
void SLPopFront(SL* ps)
{
	assert(ps);
	//int i = 0;
	他删除可能会越界，因为删除次数大于sz的时候
	//assert(ps->sz > 0);
	画图确认逻辑很简单的
	//int begin = 1;
	//while (begin < ps->sz)
	//{
	//	ps->a[begin - 1] = ps->a[begin];
	//	begin++;
	//}
	//ps->sz--;
	SLErase(ps, 1);
}

//中间的插入
//在pos位置插入数据n
void SLInsert(SL* ps, int pos, SLDataType n)
{
	assert(ps);
	//pos也需要检查一下，防止pos不在范围内
	assert(pos >= 0);
	assert(pos <= ps->sz);

	//挪动数据
	//先检查容量
	SLCheckCapacity(ps);
	int end = ps->sz - 1;
	while (end >= pos)
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}

	ps->a[pos] = n;
	ps->sz++;
}
//删除pos位置的数据
void SLErase(SL* ps, int pos)
{
	assert(ps);
	assert(pos >= 0);
	assert(pos < ps->sz);
	
	//挪动数据覆盖
	int begin = pos + 1;
	while (begin < ps->sz)
	{
		ps->a[begin - 1] = ps->a[begin];
		begin++;
	}

	ps->sz--;
}


//查找数据的位置
int SLFind(SL* ps, SLDataType x)
{
	assert(ps);
	for (int i = 0; i < ps->sz; i++)
	{
		if (ps->a[i] == x)
		{
			return i ;
		}
	}
	return -1;
}
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

seqlist,.h的内容

我们在这里放函数的声明

#pragma once
#include
#include
#include
#define N 10

//将数据类型重定义一下
typedef int SLDataType;


静态顺序表
// 
//typedef struct Seqlist
//{
//	DataType a[N];
//	int size;//记录存储多少个有效数据
//}SL;//重新命名一下让后面的操作更加方便

//动态顺序表---按照需求扩空间
typedef struct Seqlist
{
	SLDataType *a;//动态开辟数组的指针
	int sz;//记录存储多少个有效数据
	int capacity;//空间容量，当sz大于他的时候再扩容
}SL;//重新命名一下让后面的操作更加方便

//顺序表的初始化
void SLInit(SL* ps);
//销毁顺序表
void SLDistory(SL* ps);
//打印顺序表
void SLPrint(SL* ps);
//检查顺序表容量
void SLCheckCapacity(SL* ps);

//尾插顺序表
void SLPushBack(SL* ps,SLDataType n);
//尾删顺序表
void SLPopBack(SL* ps);

//头插顺序表
void SLPushFront(SL* ps, SLDataType n);
//头删顺序表
void SLPopFront(SL* ps);

//中间的插入删除
//在pos位置插入数据n
void SLInsert(SL* ps, int pos, SLDataType n);
//在pos位置删除数据n，
void SLErase(SL* ps, int pos);

//查找数据的位置
int SLFind(SL* ps, SLDataType 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

总结

毫不夸张的说，这个其实是数据结构中最简单的部分，大家只有将这个部分弄明白，后面的学习才会更加通顺，大家一起加油。