手撕数据结构：C语言实现顺序表（附完整源码）

一、前言：为什么要手写顺序表？

“问渠那得清如许？为有源头活水来。” —— 朱熹《观书有感》

在数据结构的学习道路上，顺序表（Sequence List）往往是大多数人敲下的第一行"高级"代码。很多同学可能会有疑问：“C++ 里有 vector，Java 里有 ArrayList，Python 里的 list 更是开箱即用，为什么我们还要回到 C 语言里去手动管理内存、手写扩容？”

在 C++ 里，vector 本质上就是工程级、工业封装好的"动态顺序表"。
在 Java 生态中，ArrayList 就是顺序表的代名词。
Python 的 list 是一个"存储对象引用的动态数组（Dynamic Array）"。
C 语言顺序表（原理） → C++ vector（系统级封装） → Java ArrayList（应用级封装） → Python list（脚本级封装）

这个问题的答案，正是本文存在的意义。正如朱熹所言，要理解"清如许"的高级数据结构，必须追溯其"源头活水"——底层原理。

1.1 顺序表在数据结构中的地位

顺序表不仅仅是"会用的数组"，它是线性表的物理基石。如果把数据结构比作一座大厦，那么顺序表就是地基。它用一段连续的物理内存模拟了逻辑上的线性结构。

• 承上启下：理解了顺序表，你才能真正理解链表为什么"碎"、哈希表为什么需要"负载因子"。
• 底层逻辑：所有的动态数组（vector、ArrayList）底层都是顺序表。不懂顺序表，你永远只是在调用 API，而不是在掌握原理。
• 内存视角：它是你第一次直面堆（Heap）内存管理、地址连续性和缓存命中率的地方。

1.2 面试/考研必考点

无论是大厂后台开发面试，还是 408 考研，顺序表都是高频考点（稍不注意就挂）：

场景 | 常考问题
面试 | vector 的扩容机制是什么？为什么是 1.5 倍或 2 倍？
面试 | 顺序表和链表的区别？什么时候用谁？
考研 | 在长度为 n 的顺序表中插入一个元素，平均移动次数是多少？
考研 | 简述顺序表的存储结构特点。

划重点：面试官不问你怎么用，而是问为什么这么设计。手写顺序表，就是为了应对这些"为什么"。

1.3 本文你能学到什么

“纸上得来终觉浅，绝知此事要躬行。” —— 陆游《冬夜读书示子聿》

这不是一篇简单的代码堆砌博客，读完本文，你将收获：

二、顺序表核心概念回顾

2.1 什么是顺序表？

顺序表（Sequence List）是用一段物理地址连续的存储单元依次存储数据元素的线性结构。

2.2 静态顺序表 vs 动态顺序表

静态顺序表（代码）

#define ElemType int // 目前支持的类型（任意类型）

// 顺序表管理结构体
typedef struct SeqList {
ElemType arr[MAX]; // int arr[100] 400byte
size_t cursize; // 统计目前空间中元素的个数
size_t capacity; // 统计当前空间最大容量
} SeqList;

动态顺序表（代码）

#define MAX 100 // 当前顺序表的容量
typedef int datatype;
typedef struct seqlist {
datatype* data; // 存储管理–动态内存分配
int size; // 访问管理
int capacity; // 容量管理
} seqlist;

生活类比

静态顺序表

适用场景：

• 嵌入式系统（内存极小且固定）
• 数据规模绝对已知的场景

动态顺序表

📌 适用场景：

• 99% 的工程项目
• 数据量不确定
• 需要高性能增删改查

2.3 时间复杂度分析（O(1) vs O(n)）

三、工程级顺序表设计

3.1 设计目标（健壮性、可扩展性）

在工程实践中，一个合格的顺序表必须满足以下三个核心指标：
✅ 1. 健壮性（Robustness）

• 防崩：对空指针、NULL 传入进行拦截。
• 防越界：访问下标时严格检查边界。
• 防泄漏：申请的内存必须能释放。

✅ 2. 可扩展性（Scalability）

• 容量自适应：空间不够自动扩容，不需要人工干预。
• 类型无关：通过 typedef 支持任意数据类型（int、struct 等）。
• 接口清晰：增删查改函数命名规范，易于复用。

✅ 3. 高效性（Efficiency）

• 均摊 O(1)：尾插操作尽可能快。
• 缓存友好：利用连续内存提高 CPU Cache 命中率。

Cache 小知识

1）先建一个画面：一个写字的人，一张桌子，和一个远处的仓库
CPU（中央处理器） 👉 相当于正在写方案的你（干活的那个人）
寄存器（Register） 👉 就是你握在手里的笔尖 / 指尖刚写出来的字（离脑子最近、最快，但放不了几样东西）
CPU Cache（L1/L2/L3） 👉 就是你面前这张书桌的桌面（不大，但就在手边，拿东西只要一伸胳膊）
内存 RAM 👉 就是房间尽头那个大档案柜 / 仓库（东西巨多，但走过去、拉开抽屉、找位置，很慢很慢）
2）为什么要有 Cache？——“走一趟太亏了”
你写到一半，需要查一个数据：

• 如果这个数据就在桌面（Cache 命中）：你顺手一抽，继续写，几乎不停顿。
• 如果桌面没有（Cache Miss）：你得站起来 👉 走到仓库 👉 拉开柜子 👉 找到文件 👉 走回来。
  这段"走路"的代价，比你写两行字的代价高几十上百倍。

3.2 结构体定义（为什么要分开 size 和 capacity）

很多初学者会问：“size 和 capacity 不都是表示数量吗？用一个不行吗？”
答案是：不行。这两个变量代表了逻辑世界和物理世界的分离。

生活类比：酒店房间

当你试图只用一个 size 就会发生逻辑混乱：

typedef struct {
int* data;
int size; // 既是数量，又代表容量？
} List;

如果 size = 5，到底是有 5 个空位，还是有 5 个数据？
你无法判断数组是否已满，也无法在不遍历的情况下知道哪里是数据的终点。
size 和 capacity 的分离，是为了让"逻辑"不再受限于"物理"。

3.3 类型重定义（ElemType 的重要性）

typedef struct {
int* data; // 只能存 int
int size;
int capacity;
} SeqList;

问题来了：
明天老板让你存 double、存 char*、存 struct Student，你是不是要把整个代码复制粘贴一遍，然后把 int 全部替换？
在这时候类型重定义的重要性就体现出来了。

有两种方法实现：
使用 #define 或 typedef 将"具体类型"抽象成"业务类型"。

写法一：宏定义（最常用，C语言风格）

#define ElemType int

写法二：typedef（更现代，推荐）

typedef int SLDataType;

ElemType 的抽象，是为了让"代码"不再受制于"类型"。
再遇到上述问题只需要修改一次即可。

四、核心接口实现（手撕源码）

函数声明

#pragma once
//头文件：用于声明我们将要实现的结构体和函数的功能
#include<stdio.h>//库里面自带的书用<>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
#include<string.h>
#define ElemType int //目前支持的类型（任意类型）
#define SXQ_INIT_SIZE 10//初始时需要申请的元素个数

#define SXQ_INCMEN_SIZE 2//当容量达到满了时每次扩容的倍数

typedef struct seqlist {
ElemType* arr;
size_t cursize;
size_t capacity;
}seqlist;

//1.初始化
void intseqlist(seqlist* s);//函数声明
//2.获取当前容量
int getcap(seqlist* s);
//3.获取当前个数
int getsize(seqlist* s);
//4.判空
bool isempty(seqlist* s);
//5.判满
bool isfull(seqlist* s);
//6.头插
bool push_front(seqlist* s, ElemType val);
//7.尾插
bool push_back(seqlist* s, ElemType val);
//8.打印
void PRINTF(seqlist* s);
//9.按位置插入元素
bool push_index(seqlist* s, int index, ElemType val);
//10.按下标插入元素
bool push_index(seqlist* s, int index, ElemType val);
//11.查询
int findvalue(seqlist* s, ElemType val);
//12.头删
bool pop_front(seqlist* s);
//13.尾删
bool pop_back(seqlist* s);
//14.按下标删
bool pop_index(seqlist* s, int index);
//15.按值删
bool removeelem(seqlist* s, ElemType val);
//16.获取首元素
bool getfront(seqlist* s, ElemType* val);
//17.获取尾元素
bool getback(seqlist* s, ElemType* val);
//18.获取index元素
bool getindex(seqlist* s, ElemType* val, int index);
//19.清空顺序表
void clearseqlist(seqlist* s);
//20.销毁顺序表
void destroyseqlist(seqlist* s);

4.1 初始化与销毁

//初始化
void intseqlist(seqlist* s) {//函数实现
assert(s != NULL);
//对每一个成员初始化
ElemType* p = (ElemType*)malloc(sizeof(ElemType) * SXQ_INIT_SIZE );
if (NULL == p) {
printf("初始化失败！当前顺序表无法创建成功！\\n");
return;
}
s->arr = p;
s->cursize = 0;
s->capacity = SXQ_INIT_SIZE;
}
//销毁顺序表
void destroyseqlist(seqlist* s) {
assert(s != NULL);
s->capacity = 0;
s->cursize = 0;
free(s->arr);
s->arr = NULL;
}

4.2 扩容机制（重点）

bool incmem(seqlist* s) {
assert(s != NULL);
int newcapacity = s->capacity * SXQ_INCMEN_SIZE;
ElemType* p = (ElemType*)realloc(s->arr, sizeof(ElemType) * newcapacity );
if (p == NULL)return false;
s->arr = p;
s->capacity = newcapacity;
return true;
}

为什么按 2 倍扩容？

因为可以减少扩容次数和数据搬移次数，使 n 次插入的均摊时间复杂度为 O(1)，并在时间和空间之间取得平衡。（ 为了在“时间效率”和“空间浪费”之间取得最佳平衡，并保证插入操作的均摊时间复杂度为 O(1) ）

realloc 的陷阱

易错写法

s->arr=(ElemType*)realloc(s->arr,newcapacity*sizeof(ElemType) );

致命问题
如果 realloc失败 → 返回 NULL
原指针丢失
内存泄漏

4.3 尾插法与尾删法

//尾插
bool push_back(seqlist* s, ElemType val) {
assert(s != NULL);
if (isfull(s)) {
if (incmem(s) == false)return false;
}
s->arr[s->cursize++] = val;
return true;
}

//尾删
bool pop_back(seqlist* s) {
assert(s != NULL);
if (isempty(s))return false;
s->cursize—;
return true;
}

Q：尾删时需要移动元素吗？
不需要，只需要将 size 减 1。
Q：尾删时为什么要判空？
防止对空表进行操作，避免出现非法内存访问。

4.4 头插法与头删法

//头插
bool push_front(seqlist* s, ElemType val) {
assert(s != NULL);
if (isfull(s)) {
if (incmem(s) == false)return false;
}
memmove(s->arr + 1, s->arr, sizeof(ElemType) * s->cursize++);
s->arr[0] = val;
return true;
}

//头删
bool pop_front(seqlist* s) {
assert(s != NULL);
if (isempty(s))return false;
memmove(s->arr, s->arr + 1, sizeof(ElemType) * s->cursize— – 1);
return true;
}

Q：头插和头删的时间复杂度是多少？
头插和头删都需要整体搬移元素，时间复杂度为 O(n)。
Q：为什么用 memmove 而不用 memcpy？
因为源地址和目标地址存在内存重叠，memcpy 行为是未定义的，memmove 可以安全处理。

4.5 任意位置插入与删除

任意位置插入和删除需要移动大量元素，时间复杂度为 O(n)；必须严格检查位置合法性，并正确处理循环终止条件，避免越界访问。

bool pop_index(seqlist* s, int index) {
assert(s != NULL);
if (isempty(s))return false;//
if (index<0 || index>s->cursize – 1)return false;
memmove(s->arr + index, s->arr + index + 1, sizeof(ElemType) * (—s->cursize – index));
return true;
}

边界条件判断

数据搬移

方法一

// 数据搬移（从后往前）
for (int i = s->size; i > cursize; —i) {
s->arr[i] = s->arr[i – 1];
}

方法二

memmove(s->arr + index, s->arr + index – 1, sizeof(ElemType) * (++s->cursize – index));

4.6 查找

按值查找

//查询(按值查下标)
int findvalue(seqlist* s, ElemType val) {
assert(s != NULL);
if (isempty(s))return –1;
for (int i = 0; i < s->cursize; i++) {
if (val == s->arr[i])return i;
}
return –1;
}

按位查找

//18.获取index元素
bool getindex(seqlist* s, ElemType* val, int index) {
assert(s != NULL);
if (isempty(s) || index<0 || index>s->cursize – 1)return false;
*val = s->arr[index];
return true;
}

五、完整可运行源码

//1.初始化
void intseqlist(seqlist* s) {//函数实现
assert(s != NULL);
//对每一个成员初始化
ElemType* p = (ElemType*)malloc(sizeof(ElemType) * SXQ_INIT_SIZE );
if (NULL == p) {
printf("初始化失败！当前顺序表无法创建成功！\\n");
return;
}
s->arr = p;
s->cursize = 0;
s->capacity = SXQ_INIT_SIZE;

}
//2.获取当前容量
int getcap(seqlist* s) {
assert(s != NULL);
return s->capacity;
}
//3.获取当前个数
int getsize(seqlist* s) {
assert(s != NULL);
return s->cursize;
}
//4.判空
bool isempty(seqlist* s) {
assert(s != NULL);
return 0==s->cursize;
}
//5.判满
bool isfull(seqlist* s) {
assert(s != NULL);
return s->capacity==s->cursize;
}
//6.头插
bool push_front(seqlist* s, ElemType val) {
assert(s != NULL);
if (isfull(s)) {
if (incmem(s) == false)return false;

}
memmove(s->arr + 1, s->arr, sizeof(ElemType) * s->cursize++);
s->arr[0] = val;
return true;
}
//7.尾插
bool push_back(seqlist* s, ElemType val) {
assert(s != NULL);
if (isfull(s)) {
if (incmem(s) == false)return false;

}
s->arr[s->cursize++] = val;
return true;
}
//8.打印
void PRINTF(seqlist* s) {
assert(s != NULL);
//if (isempty(s))return;
printf("当前顺序表中所有成员：");
for (int i = 0;i < s->cursize;i++) printf("%d ", s->arr[i]);printf("\\n");
}
//9.按位置插入元素
bool push_pos(seqlist* s, int index, ElemType val) {
assert(s != NULL);
if (isfull(s)) {
if (incmem(s) == false)return false;

}
if (index<=0 || index>s->cursize )return false;
memmove(s->arr + index, s->arr + index –1, sizeof(ElemType) * (++s->cursize – index));
s->arr[index – 1] = val;
return true;
}
//10.按下标插入元素
bool push_index(seqlist* s, int index, ElemType val) {
assert(s != NULL);
if (isfull(s)) {
if (incmem(s) == false)return false;

}
if (index<0 || index>s->cursize+1 )return false;
memmove(s->arr + index+1, s->arr + index , sizeof(ElemType) * (s->cursize++ – index ));
s->arr[index ] = val;
return true;
}
//11.查询(按值查下标)
int findvalue(seqlist* s, ElemType val){
assert(s != NULL);
if (isempty(s))return –1;
for (int i = 0;i < s->cursize;i++) {
if (val == s->arr[i])return i;
}
return –1;
}
//12.头删
bool pop_front(seqlist* s) {
assert(s != NULL);
if (isempty(s))return false;
memmove(s->arr, s->arr + 1, sizeof(ElemType) * s->cursize – 1);
s->cursize—;
return true;
}
//13.尾删
bool pop_back(seqlist* s) {
assert(s != NULL);
if (isempty(s))return false;
s->cursize—;
return true;
}
//14.按下标删
bool pop_index(seqlist* s, int index) {
assert(s != NULL);
if (isempty(s))return false;//1 2 3 4 5
if (index<0 || index>s->cursize – 1)return false;
memmove(s->arr + index, s->arr + index + 1, sizeof(ElemType) * (—s->cursize – index));
return true;
}
//15.按值删
bool removeelem(seqlist* s, ElemType val) {
assert(s != NULL);
if (isempty(s))return false;
int size = 0;
for (int i = 0;i < s->cursize;i++) {
if (val != s->arr[i])s->arr[size++] = s->arr[i];
}
if (size == s->cursize)return false;
s->cursize = size;
return true;
}
//16.获取首元素
bool getfront(seqlist* s, ElemType* val) {
assert(s != NULL);
if (isempty(s))return false;
*val = s->arr[0];
return true;
}
//17.获取尾元素
bool getback(seqlist* s, ElemType* val) {
assert(s != NULL);
if (isempty(s))return false;
*val = s->arr[s->cursize – 1];
return true;
}
//18.获取index元素
bool getindex(seqlist* s, ElemType* val, int index) {
assert(s != NULL);
if (isempty(s)||index<0||index>s->cursize–1)return false;

*val = s->arr[index];
return true;
}
//19.清空顺序表
void clearseqlist(seqlist* s) {
assert(s != NULL);
s->cursize = 0;

}
//20.销毁顺序表
void destroyseqlist(seqlist* s) {
assert(s != NULL);
s->capacity = 0;
s->cursize = 0;
if(s->arr!=NULL){
free(s->arr);
s->arr = NULL;
}
}

六、常见 Bug 与避坑指南

顺序表常见 Bug 主要包括野指针、内存泄漏、越界访问和 realloc 使用不当；必须通过严格的边界检查、正确的内存管理和防御式编程来避免。

在每一次写顺序表代码时，心里默念这 5 条：
✅ malloc / realloc 后一定判空
✅ realloc 一定用临时指针
✅ free 后一定置 NULL
✅ 所有下标一定检查边界
✅ size 和 capacity 永远保持一致

野指针问题

free(s->arr);

如果s->arr==NULL,

内存泄漏

1.

s->arr = realloc(s->arr, new_size);

这样写可能会
realloc 失败时返回 NULL
原指针丢失
原内存再也释放不了

2.重复定义也可能导致内存泄漏

intseqlist(&s);
intseqlist(&s);//重新分配内存，旧内存没释放​ → 内存泄漏

越界访问

//1.
s->arr[s->cursize] = val; // size 已经越界
//2.
for (int i = 0; i <= s->cursize; i++) // <= 错

realloc 失败处理

七、总结与进阶

一.顺序表的优缺点

📌 只要“查得多、改得少”，优先选顺序表

📌 头部操作频繁 → 不要用顺序表

二.与链表的对比

三.什么时候用谁？

“顺序表不难，难的是第一次认真把每一个 Bug 都想清楚。”

欢迎点赞、收藏、关注