顺序表：概念解析与C语言代码实现

一、顺序表介绍

1.1 顺序表概念介绍

顺序表是线性表的一种。

顺序表的底层是数组。那么，为什么要在数组的基础上，再引入顺序表这种数据结构呢？

我们知道，数组本身可以用来存放数据，并实现增、删、查、改等基本操作。但数组在使用时存在明显不足：

• 数组不记录有效元素个数、总容量等信息；
• 插入、删除、扩容等操作都需要手动编写代码实现，使用繁琐且容易出错。

而顺序表是对数组的一层封装：它在数组的基础上，增加了对有效元素长度、存储空间容量的管理，并提供了统一、封装好的增删查改接口，使用更简便、规范、安全。

1.2 顺序表分类

1、静态顺序表

静态顺序表的定义需要包含一个结构体，结构体包含两个成员：一个定长数组和一个整型数据（表示顺序表当前有效的数据个数）

struct SeqList
{
int arr[100];
int size;
}

2、动态顺序表

动态顺序表的定义也需要定义一个结构体，其中包含三个成员：一个数组指针，一个整型数据（表示有效的数据个数）和另一个整型数据（表示空间大小）。

struct SeqList
{
int* arr;
int size;
int capacity;
}

如果使用静态顺序表，定长数组大小给小了，空间不够用（在公司里造成用户信息丢失是非常大的事故！！）数组大小给大了又会浪费空间。因此推荐使用动态顺序表。

二、代码实现

我们来实现一下动态顺序表。

我们创建三个文件：

2.1 定义顺序表的结构

我们首先在SeqList.h中定义顺序表的结构

typedef int SLDataType;

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

我们将int类型重定义为SLDataType是为了如果以后将来想要用这个顺序表管理其他类型的数据，只需要进行一次修改，例如：

typedef char SLDataType;

2.2 顺序表初始化

接下来我们写一个方法用于顺序表的初始化（将数组指针置为空，有效数据个数、空间大小均为0）：

//SeqList.c
void SLInit(SL* s)
{
s->arr = NULL;
s->size = s->capacity = 0;
}

【注意】顺序表初始化函数必须传入结构体指针，不能采用传值调用。原因是：函数参数传递时，编译器会将实参的内容逐字节拷贝到函数栈帧中。而顺序表结构体在未初始化之前，内部成员（如数据指针、长度、容量）均为无效值，此时直接传值会导致非法拷贝，程序运行时会报错：

2.3 顺序表销毁

顺序表用完之后，将数组占用的空间释放，将两个整型数据置为0。

void SLDestroy(SL* ps)
{
if (ps->arr)
{
free(ps->arr);
}
ps->arr = NULL;
ps->size = ps->capacity = 0;
}

2.3 插入

2.3.1 尾部插入

我们写一个方法来完成在顺序表尾部插入一个元素的功能。

首先插入之前要先判断顺序表当前的空间够不够用，如果不够要申请空间。

那么要申请多大的空间 / 一次增容增多大？

增容通常来说是成倍数地增加，一般是2或3倍。

原因如下：每次增容都要另外开辟一块更大的空间，并且把旧数据都拷贝到新的空间；所以频繁的增容意味着频繁的申请+拷贝+释放操作，会造成程序运行效率大大降低。

经过数学推理，每次扩容2-3倍最合理。

扩容的时候我们还要考虑capacity为0的情况。我们用一个三目表达式，如果capacity为0，我们就扩容4个字节。

void SLPushBack(SL* ps, SLDataType x)
{
assert(ps);
if (ps->capacity == ps->size)
{
//申请空间
int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
SLDataType* tmp = realloc(ps->arr, newCapacity * sizeof(SLDataType));
if (tmp == NULL)
{
perror("realloc fail");
exit(1);
}
ps->arr = tmp;
ps->capacity = newCapacity;
}
//ps->arr[ps->size] = x;
//ps->size++;
ps->arr[ps->size++] = x;
}

这段代码中，assert语句、将realloc返回值先赋给临时变量，确认其不为零后再赋给ps->arr,都是增强代码健壮性的操作。

2.3.2 头部插入

我们发现这里仍然需要判断顺序表里的空间够不够用，不够用要申请空间。所以不妨把这一段代码封装成一个函数：

void SLCheckCapacity(SL* ps)
{
if (ps->capacity == ps->size)
{
//申请空间
int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
SLDataType* tmp = realloc(ps->arr, newCapacity * sizeof(SLDataType));
if (tmp == NULL)
{
perror("realloc fail");
exit(1);
}
ps->arr = tmp;
ps->capacity = newCapacity;
}
}

然后，只需使用一个for循环来把顺序表中的元素向后移动一位，再把下标为零的元素赋值为需要插入的数据即可。

void SLPushFront(SL* ps, SLDataType x)
{
assert(ps);
SLCheckCapacity(ps);
//先让顺序表中的元素整体向后挪一位
for (int i = ps->size; i > 0; i–)
{
ps->arr[i] = ps->arr[i – 1];
}
ps->arr[0] = x;
ps->size++;
}

2.4 删除

2.4.1 尾部删除

删数据之前要确保顺序表不为空。因为size这个成员就是用来管理顺序表中有效元素的个数，所以尾部删除只需size–即可。

void SLPopBack(SL* ps)
{
assert(ps);
assert(ps->size);
ps->size–;
}

2.4.2 头部删除

只要将所有元素向前移动1位并让ps->size–即可。

void SLPopFront(SL* ps)
{
assert(ps);
assert(ps->size);
for (int i = 1; i < ps->size; i++)
{
ps->arr[i – 1] = ps->arr[i];
}
ps->size–;
}

2.5 指定位置插入

画张示意图：

pos指的是指定位置的数组元素的下标。我们只需让pos及pos以后的数据向后移动一位，再把pos位置的数据改成我们想插入的数据即可:

插入之前，依旧要检查空间够不够，还要确定pos这个数据是大于等于0，小于等于size的。

void SLErase(SL* ps, int pos)
{
assert(ps);
assert(ps->size);
assert(pos >= 0 && pos < ps->size);
for (int i = pos; i < ps->size – 1; i++)
{
ps->arr[i] = ps->arr[i + 1];
}
ps->size–;
}

2.6 指定位置删除

画张示意图：

只要让pos之后的数据都向前移动一位，然后让size–即可。

void SLErase(SL* ps, int pos)
{
assert(ps);
assert(pos >= 0 && pos < ps->size);
for (int i = pos; i < ps->size – 1; i++)
{
ps->arr[i] = ps->arr[i + 1];
}
ps->size–;
}

 2.6 顺序表的查找

遍历数组元素即可。

int SLFind(SL* ps, SLDataType x)
{
assert(ps);
for (int i = 0; i < ps->size; i++)
{
if (ps->arr[i] == x)
{
return i;
}
}
return -1;
}

现在所有功能都实现完了。

void SLInit(SL* ps);
void SLDestroy(SL* ps);

void SLPushBack(SL* ps, SLDataType x);
void SLPushFront(SL* ps, SLDataType x);

void SLPopBack(SL* ps);
void SLPopFront(SL* ps);

void SLInsert(SL* ps, int pos, SLDataType x);

int SLFind(SL* ps, SLDataType x);

void SLPrint(SL s);

【注意】

• 写完一个方法，测试一个，别等都写完了再测试，会崩溃。
• 测试要测一般位置也要测特殊位置（开头，结尾）。