[TOC]
前言
顺序表是我们学习数据结构第一阶段的必经之路
什么是顺序表，且听我慢慢道来
本篇博客用到的知识点：
1.什么是顺序表？
1.1线性表
线性表是数据结构的一种，它是n个具有相同特性的数据元素的有限序列。 常见的线性表：顺序表、链表、栈、队列、字符串……
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理内存上存储时，通常以数组和链式结构的形式存储。
本篇博客所讲述的顺序表，就是以数组结构存储的线性表
2.编写你的顺序表！
为了保证写完之后不要进入贤者debug状态，建议每编写一个模块，就在test.c的main函数中进行测试，保证当前编写的模块正确后再进行下一步！
不然问题多了，改起来很头疼的！
2.0 赛前准备
和我们日常所用的数组不同，顺序表的这个结构，主要的组成部分是一个结构体（本篇博客中的线性表以int为例）
1
2
3
4
5
6
| struct SeqList
{
int* a;
int size;
int capacity;
};
|
为了方便使用，我们可以使用typedef对符号进行重定义
1
2
3
4
5
6
7
8
9
10
11
| typedef int SLDataType;
typedef struct SeqList
{
SLDataType* a;
int size;
int capacity;
}SeqList;
|
2.1 初始化
本次编写顺序表代码，我们采用“多文件编程”方式，将函数的实现，函数的声明与主函数分开，分别放入两个源文件和一个头文件
先在main函数中定义一个顺序表的结构体，编写SQLinst函数进行初始化
在.h文件中，我们写入函数声明和库函数的引用。
注意需要在另外两个.c文件中以"Seqlist.h"方式引用自定义头文件
初始化方式如下，我们先给a用calloc函数开辟3个SLDataType(int)类型的空间
- CAPA：由define定义的符号，方便后续修改初始容量
1
2
3
4
5
6
7
8
9
10
| void SQLinst(SeqList* sql)
{
assert(sql);
sql->a = (SLDataType*)calloc(CAPA,sizeof(SLDataType));
sql->capacity = CAPA;
sql->size = 0;
return;
}
|
2.2 容量检查
既然我们的函数是由calloc开辟的动态内存空间，就需要在顺序表内空间不够用的时候，检查容量，判断是否需要扩容
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| void CheckCapacity(SeqList* sql)
{
assert(sql);
if (sql->size < sql->capacity)
return;
else
{
size_t newcapacity = 2 * (sql->capacity);
SLDataType* tmp = (SLDataType*)realloc(sql->a,newcapacity*sizeof(SLDataType));
if (tmp == NULL)
{
printf("realloc failed\n");
exit(0);
}
else
{
sql->a = tmp;
sql->capacity = newcapacity;
}
}
return;
}
|
使用realloc函数的时候需要注意，它可能扩容失败，所以我们不能直接让sql->a来接收realloc函数的返回值（扩容失败返回NULL，相当于前功尽弃）
而是需要用一个中间变量tmp来接收开辟后的地址，确认realloc成功后再赋值给a。同时，也需要将sql->capacity更改成新的容量
2.3 打印顺序表
1
2
3
4
5
6
7
8
9
10
11
12
| void SQLprint(SeqList* sql)
{
assert(sql);
for (int i = 0; i < (sql->size); i++)
{
printf("%d ", sql->a[i]);
}
printf("\n");
return;
}
|
2.4 尾插和尾删
和平时使用数组不同的是，线性表中把在表尾插入数据称作尾插、删除数据叫做尾删，对应的是pushback和popback
如果你看过之前我的那篇函数调用参数压栈的博客，应该还记得，汇编代码中入栈和出栈也是push和pop
1
2
| void SQLpushback(SeqList* sql, size_t x);
void SQLpopback(SeqList* sql);
|
实现方式很是简单，和我们日常在数组尾部插入元素相同
需要注意的是，这里我们插入的数据是size_t（unsigned int)类型，也就是说，这个顺序表中并没有负数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| void SQLpushback(SeqList* sql, size_t x)
{
assert(sql);
CheckCapacity(sql);
sql->a[sql->size] = x;
sql->size++;
return;
}
void SQLpopback(SeqList* sql)
{
assert(sql);
sql->size--;
return;
}
|
2.5 头插和头删
和尾部修改数据不同，在头部修改数据，必须要把已有数据整体往后移动
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
| void SQLpushfront(SeqList* sql, size_t x)
{
assert(sql);
CheckCapacity(sql);
int i = sql->size;
while (i >= 0)
{
sql->a[i] = sql->a[i - 1];
i--;
}
sql->a[0] = x;
sql->size++;
return;
}
void SQLpopfront(SeqList* sql)
{
assert(sql);
int i = 0;
while (i < (int)sql->size)
{
sql->a[i] = sql->a[i + 1];
i++;
}
sql->size--;
return;
}
|
2.6 插入和删除
除了头尾的操作，我们还需要编写在顺序表中间的插入和删除操作
- 插入：需要将插入位置之后的数据整体后移
- 删除：删除位置之后的数据整体前移
- 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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| void SQLinsert(SeqList* sql, size_t pos, size_t x)
{
assert(sql);
if (pos >= (int)sql->size)
{
printf("input err\n");
return;
}
CheckCapacity(sql);
int i = sql->size;
while (i > (int)pos)
{
sql->a[i] = sql->a[i - 1];
i--;
}
sql->a[pos]=x;
sql->size++;
return;
}
void SQLerase(SeqList* sql, size_t pos)
{
assert(sql);
if (pos >= (int)sql->size)
{
printf("input err\n");
return;
}
int i = pos;
while (i < (int)sql->size-1)
{
sql->a[i] = sql->a[i + 1];
i++;
}
sql->size--;
return;
}
|
2.7 查找和更改
当我们需要查找的时候，必须从头开始遍历整个数组，来找到待查找元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| int SQLfind(SeqList* sql, size_t x)
{
assert(sql);
for (int i = 0; i < sql->size; i++)
{
if (sql->a[i] == x)
{
return i;
}
}
printf("find err\n");
return -1;
}
|
而修改函数则是在查找的基础上，更改掉目标元素
1
2
3
4
5
6
7
8
| void SQLmodify(SeqList* sql, size_t pos, size_t x)
{
assert(sql);
sql->a[pos] = x;
return;
}
|
如果用户不知道自己想修改的元素的下标，可以通过find函数查找，再调用修改函数
3.菜单
一个小建议是，不要在一开始编写函数的时候就写出菜单！
因为这样非常不方便debug，你需要按菜单上的函数调用再进行下一步操作
话说是不是应该在前面就告诉大家？😂
菜单的使用需要配合switch/case语句来执行，方便用户输入操作数进行函数调用
1
2
3
4
5
6
7
8
9
10
11
| void menu()
{
printf("*****************************\n");
printf("******1.头插 2.尾插*********\n");
printf("******3.头删 4.尾删*********\n");
printf("******5.插入 6.删除*********\n");
printf("******7.查找 8.更改*********\n");
printf("******9.打印 0.exit*********\n");
printf("*****************************\n");
}
|
我们可以在每个模块printf对应的提示，方便用户操作顺序表
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
| int main()
{
SeqList s;
SQLinst(&s);
#if M
test1(&s);
#endif
menu();
printf("请输入命令>");
int option;
scanf("%d", &option);
do{
switch (option)
{
case 0:
{
SQLdestory(&s);
printf("destory SQL\n");
exit(0);
}
case 1:
{
int x;
printf("请输入需要头插的数>");
scanf("%d", &x);
SQLpushfront(&s, x);
break;
}
case 2:
{
int y;
printf("请输入需要尾插的数>");
scanf("%d", &y);
SQLpushback(&s, y);
break;
}
case 3:
SQLpopfront(&s);
break;
case 4:
SQLpopback(&s);
break;
case 5:
{
int m, n;
printf("请输入插入位置和插入数>");
scanf("%d %d", &m, &n);
SQLinsert(&s, m, n);
break;
}
case 6:
{
int d;
printf("请输入待删除数的位置>");
scanf("%d", &d);
SQLerase(&s, d);
break;
}
case 7:
{
int f;
printf("请输入需要查找的数>");
scanf("%d", &f);
printf("该数下标为:%d\n", SQLfind(&s, f));
break;
}
case 8:
{
int h, i;
printf("请输入需要更改的下标和新的数字\n");
printf("如果您不知道该数的位置，可以调用查找模块\n");
printf("请输入>");
scanf("%d %d", &h, &i);
SQLmodify(&s, h, i);
break;
}
case 9:
SQLprint(&s);
break;
}
printf("请输入命令>");
} while (scanf("%d", &option) != EOF);
return 0;
}
|
最终效果如图
一些err
当我使用switch/case语句，在case语句中定义局部变量的时候，VS报错“声明不能包含标签”
这个报错并不会阻止程序运行
解决办法是在case语句后带上大括号，报错就消失了
总结
顺序表内容算是对前面学习的一些C语言知识的运用，数据结构的严谨性更胜一筹。
比如在判断pos和size的大小的时候，会报错类型不一致。
这时候我们需要把无符号整型的size强制转换为int类型，再和pos进行比较！
如果这篇博客对你有帮助，还请点个👍吧
爱发电
