本文介绍了 C 语言中顺序表的实现原理及代码。内容涵盖线性表概念、静态与动态顺序表的区别、内存管理（malloc/realloc）、初始化与销毁函数。详细讲解了尾插、头插、尾删、头删及指定位置插入删除的操作逻辑与代码实现。包含空间检查机制、野指针处理以及完整的头文件、源文件和测试文件示例。旨在帮助读者理解顺序表的数据结构特性及其在 C 语言中的具体应用。
线性表是 n 个具有相同特性的数据元素的有限序列，是一种在实际中广泛应用的数据结构，常见的线性表有：顺序表、链表、栈、队列、字符串等。
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。
顺序表是线性表的一种，顺序表的特性是：逻辑结构连续，物理结构也是连续的。顺序表的最底层结构是数组，但顺序表在数组的基础上实现了对数组的封装及增删查改等接口。我们可以把数组看成路边小摊，而顺序表就是米其林餐厅，二者虽然结构类似，但发挥的功能却不一样，档次也就自然有所差别。
静态顺序表也就表示顺序表存储空间是提前给定的，无法改变。即使用定长数组来进行数据的存储。如下：
struct SeqList//用结构体来完成顺序表的操作 {
int arr[100];//定长数组
int size;//顺序表中有效的数据个数
};
如果使用静态顺序表就要面临两个严峻的问题：
一、数组空间开辟小了，空间不够用
二、数组空间开辟大了，空间浪费
基于这种情况我们选择使用动态内存开辟，即使用动态顺序表。
动态顺序表需要使用到动态内存开辟，所以在结构体内我们对数组要使用指针进行定义，同时需要增加一个申请的空间大小的变量 capacity。
struct SeqList//定义结构体 {
int* arr;//定义数组
int size;//顺序表中有效的数据个数
int capacity;//空间大小
};
当代码量非常庞大，我们若想将部分 int 类型替换为 char 类型时，使用上面的定义方式就会引来麻烦。所以在这里我们将涉及到顺序表的 int 类型重命名一下，如此一来就方便了我们去对源程序进行查找替换等操作。（同时我们也可以对结构体类型进行重命名）
typedef int SLDataType;
typedef struct SeqList//定义结构体 {
SLDataType* arr;//定义数组
int size;//顺序表中有效的数据个数
int capacity;//空间大小
}SL;
在结构体中，为了使每部分功能都独立存在，我们只是对顺序表中的内容进行了定义，而并未进行初始化。故此时我们定义一个初始化函数来完成这部分功能。
void SLInit(SL* ps)//将结构体变量作为参数传到形参 {
ps->arr = NULL;//初始化置为空
ps->size = ps->capacity = 0;//初始化置为 0
}
在我们初始化并插入数据后，我们可以自定义一个打印函数对该顺序表内数据进行打印。
在一系列操作完毕后需要销毁顺序表来释放对应的内存空间，故我们再来定义一个销毁函数来完成这部分功能。
void Destroy(SL* ps) {
if(ps->arr)//等价于 (ps->arr != NULL)
free(ps->arr);
ps->arr = NULL;//将释放的空间置为空，避免野指针造成错误访问
ps->size = ps->capacity = 0;
}
在上面的销毁操作中，最值得注意的就是在释放了顺序表内的空间后，原有空间部分的首地址指针要置为空，避免生成野指针造成错误访问。
通过上面两个自定义函数我们可以观察到，我们在传参部分使用的是传址调用而不是传值调用。若使用传值调用，函数内操作的部分是原数据的一份临时拷贝，出栈帧即会销毁。实参部分不会得到真实改变，所以在此处传参我们要使用指针来接收要操作部分的地址，实现传址调用来改变实参部分。
在操作数据前我们应首先考虑申请空间的大小，即一次申请多大的空间，使用哪一个内存函数。我们知道 C 语言中内存函数有 malloc、calloc、realloc。
由于我们是需要对数组进行扩容，所以我们选择 realloc。原因如下：
malloc 分配新的内存，然后丢弃旧的，会频繁引起内存碎片，并可能导致大量小块内存无法再利用，效率低下。realloc 可以合并相邻的小内存块，减少碎片。realloc 能够保持原有数据的连续性，这对于性能优化特别重要，特别是对于需要快速访问元素的数据结构（如链表和数组）。realloc 在现有内存基础上进行扩展，相比于多次 malloc 和 free 操作，它减少了系统调用次数，提高了程序响应速度。确定使用的内存函数后，每次扩容应扩大多少？扩容通常来说是成倍数的增加，一般来说是 2 倍或 3 倍（由数学推理得出的最佳值）
void SLcheckcapacity(SL* ps) {
if (ps->capacity == ps->size) {
int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;//三目表达式
SLDataType* tmp = (SLDataType*)realloc(ps->arr, newcapacity * sizeof(SLDataType));//我们之所以用 newcapacity 和 tmp 来过渡是为了保证即使扩容失败原有数据也不会丢失
if (tmp == NULL)//之所以在此判断是为了确定扩容成功
{
perror("扩容失败");
exit(1);
}
ps->capacity = newcapacity;//扩容成功，将过渡变量的值赋值给 arr 和 capacity
ps->arr = tmp;
}
}
void SLPushBack(SL* ps, SLDataType x) {
//判断 ps 是否为空
//温柔的解决方式
/*if (ps == NULL) {
return;
}*/
//暴力判断 ps 是否为空
assert(ps);//等价于 assert(ps != NULL)
//对空间大小判断
SLcheckcapacity(ps);
ps->arr[ps->size] = x;
++ps->size;
//更加巧妙地尾插代码
//ps->arr[ps->size++] = x; 使用后置++使得数据插入后 size 才会发生++ 操作
}
对数组进行尾插操作就找到数组已有数据后面一位再插入数据，由此我们需要将结构体的地址和要插入的数据传递给尾插函数。
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++;//顺序表内元素个数加一（下标）
}
头插操作中最关键的一步就是对已有数据的挪动，一定是从最后往后移，否则会造成原有数据丢失。
void SLPopBack(SL* ps) {
assert(ps);
assert(ps->size);
//上面判断顺序表不为空
--ps->size;
//我们将顺序表有效数值个数减一后，最后一位元素就无法访问了，即被我们从顺序表中删除
}
尾删的关键在于把顺序表中数组的最后一位下标减一，如此最后一位元素就无法访问了，即被我们删除。
void SLPopfront(SL* ps) {
assert(ps);
SLcheckcapacity(ps);
//顺序表判空并同时检查空间
//数据整体往前挪动一位
for (int i = 0; i < ps->size - 1; i++)
{
ps->arr[i] = ps->arr[i + 1];
}
--ps->size;//顺序表中有效数据个数减一
}
头删操作和头插操作逻辑类似，关键都在于对于数据的挪动，只是头删时我们需要把数据整体往前挪动一位。
如上图所示，顺序表中原有的有效数据个数对应到顺序表元素下标时，其会在最后一个元素后面一位（即留有一处可操作的为空的空间），我们想要在指定位置（此处指定位置我们定义为 pos）插入元素时，便需要将 pos 之后的元素全部后移一位，而 arr[size] 这一块空间就为我们移动数据做了准备。
同时，我们还要考虑一个问题就是指定的位置 pos 是否在顺序表有效的空间之内，pos 能否等于 0，-1，10000 呢？要解决上面问题 j 就需要我们对 pos 的大小进行判断。第一，pos 最小是多少？显而易见，pos 最小时为 0，也就是头插。第二，pos 最大是多少？由上类推可知 pos 最大是 pos == size 的时候，也就是尾插。
void SLInsert(SL* ps, int pos, SLDataType x) {
//判断传过来的结构体地址不为空
assert(ps);
//判断指定的位置 pos 是否在现有情况之下
assert(pos >= 0 && pos <= ps->size);
//判断空间大小够不够
SLcheckcapacity(ps);
//将 pos 及其之后的数据统一往后移动一位
for (int i = ps->size; i > pos; i--) //既然是后移，循环的初始化部分就是顺序表中可操作空间的最后，即 i == size
//循环判断部分可以使用极限情况推导得出，见下面注释
{
ps->arr[i] = ps->arr[i - 1];//最后一次循环情况 arr[pos+1] = arr[pos]
}
ps->arr[pos] = x;
++ps->size;//顺序表中有效数据个数 +1
}
如上图所示，在指定位置删除数据需要将 pos 后面的数据整体向前移动一位，从而让 pos+1 处的数据将 pos 处的数据覆盖以实现删除效果。
void SLErase(SL* ps, int pos) {
//判断传来的结构体地址不为空
assert(ps);
//判断指定的位置 pos 是否合理
assert(pos >= 0 && pos <= ps->size);
for (int i = pos; i < ps->size - 1; i++) //因为是要在指定位置删除数据，故 i == pos
//循环判断部分可以使用极限情况推导得出，见下面注释
{
ps->arr[i] = ps->arr[i + 1];//最后一次循环时情况 arr[size-2] = arr[size-1]
}
--ps->size;//删除数据后，顺序表中有效数据个数 -1
}
void SLFind(SL* ps, SLDataType x) {
assert(ps);
for (int i = 0; i < ps->size; i++)
{
if (ps->arr[i] == x)
{
printf("找到啦");
return i;
}
}
printf("没有找到");
return -1;
}
#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLDataType;
typedef struct SeqList {
SLDataType* arr;
int size;
int capacity;
}SL;
void SLInit(SL* ps);
void SLDestroy(SL* ps);
void SLPrint(SL s);
void SLcheckcapacity(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);
void SLErase(SL* ps, int pos);
void SLFind(SL* ps, SLDataType x);
#include"SeqList.h"
void SLInit(SL* ps) {
ps->arr = NULL;
ps->size = 0;
ps->capacity = 0;
}
void SLDestroy(SL* ps) {
free(ps->arr);
ps->arr = NULL;
ps->size = ps->capacity = 0;
}
void SLPrint(SL s) {
int i = 0;
for (i = 0; i < s.size; i++)
{
printf("%d", s.arr[i]);
}
printf("\n");
}
void SLcheckcapacity(SL* ps) {
if (ps->capacity == ps->size) {
int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
SLDataType* tmp = (SLDataType*)realloc(ps->arr, newcapacity * sizeof(SLDataType));//我们之所以用 newcapacity 和 tmp 来过渡是为了保证即使扩容失败原有数据也不会丢失
if (tmp == NULL)//之所以在此判断是为了确定扩容成功
{
perror("扩容失败");
exit(1);
}
ps->capacity = newcapacity;//扩容成功，将过渡变量的值赋值给 arr 和 capacity
ps->arr = tmp;
}
}
void SLPushBack(SL* ps, SLDataType x) {
//判断 ps 是否为空
//温柔的解决方式
/*if (ps == NULL) {
return;
}*/
//暴力判断 ps 是否为空
assert(ps);//等价于 assert(ps != NULL)
//对空间大小判断
SLcheckcapacity(ps);
ps->arr[ps->size] = x;
++ps->size;
//更加巧妙地尾插插入
//ps->arr[ps->size++] = x; 使用后置++使得数据插入后 size 才会发生++ 操作
}
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++;//顺序表内有效数值个数加一（下标）
}
void SLPopBack(SL* ps) {
assert(ps);
assert(ps->size);
//上面判断顺序表不为空
--ps->size;
//我们将顺序表有效数值个数减一后，最后一位元素就无法访问了，即被我们从顺序表中删除
}
void SLPopfront(SL* ps) {
assert(ps);
SLcheckcapacity(ps);
//顺序表判空并同时检查空间
//数据整体往前挪动一位
for (int i = 0; i < ps->size - 1; i++)
{
ps->arr[i] = ps->arr[i + 1];
}
--ps->size;//顺序表中有效数据个数减一
}
//在指定位置 pos 插入数据
void SLInsert(SL* ps, int pos, SLDataType x) {
//判断传过来的结构体地址不为空
assert(ps);
//判断指定的位置 pos 是否合理
assert(pos >= 0 && pos <= ps->size);
//判断空间大小够不够
SLcheckcapacity(ps);
//将 pos 及其之后的数据统一往后移动一位
for (int i = ps->size; i > pos; i--) //既然是后移，循环的初始化部分就是顺序表中可操作空间的最后，即 i == size
//循环判断部分可以使用极限情况推导得出，见下面注释
{
ps->arr[i] = ps->arr[i - 1];//最后一次循环情况 arr[pos+1] = arr[pos]
}
ps->arr[pos] = x;
++ps->size;//顺序表中有效数据个数 +1
}
//在指定位置删除数据
void SLErase(SL* ps, int pos) {
//判断传来的结构体地址不为空
assert(ps);
//判断指定的位置 pos 是否合理
assert(pos >= 0 && pos <= ps->size);
for (int i = pos; i < ps->size - 1; i++) //因为是要在指定位置删除数据，故 i == pos
//循环判断部分可以使用极限情况推导得出，见下面注释
{
ps->arr[i] = ps->arr[i + 1];//最后一次循环时情况 arr[size-2] = arr[size-1]
}
--ps->size;//删除数据后，顺序表中有效数据个数 -1
}
//查找
void SLFind(SL* ps, SLDataType x) {
assert(ps);
for (int i = 0; i < ps->size; i++)
{
if (ps->arr[i] == x)
{
printf("找到啦");
return i;
}
}
printf("没有找到");
return -1;
}
#include"SeqList.h"
void SLtest_1() {
SL sl;
SLInit(&sl);
//增删查改操作
//测试尾插
SLPushBack(&sl, 1);
SLPushBack(&sl, 2);
SLPushBack(&sl, 3);
SLPushBack(&sl, 4);
SLPrint(sl);//1 2 3 4
//SLPushFront(&sl, 5); //SLPushFront(&sl, 6);
//测试尾删
SLPopBack(&sl);
SLPrint(sl);//1 2 3
SLPopBack(&sl);
SLPrint(sl);//1 2
SLPopBack(&sl);
SLPrint(sl);//1
//SLPopBack(&sl); //SLPrint(sl);//空
//...........
SLDestroy(&sl);
}
int main() {
SLtest_1();
return 0;
}
运行结果：
（此处省略图片展示）
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML 转 Markdown 互为补充。 在线工具，Markdown 转 HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML 转 Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online