Appearance
第 21 讲：数据结构——顺序表
⏱️ 本讲 L1 内容建议分 3 次 学习：第 1 次理解概念与结构，第 2 次吃透增删接口，第 3 次动手实现通讯录。顺序表是你系统接触数据结构的第一站，务必把每个接口的下标变化在纸上画一遍。📘 与末尾 🔬 拓展可按需跳过。
🎯 学完本讲，你将能够
- 解释什么是数据结构、线性表，以及顺序表与数组的关系
- 说清静态顺序表与动态顺序表的区别，以及动态扩容为什么要用
realloc+ 临时指针 - 独立实现顺序表的初始化、销毁、头/尾插删、任意位置插删、查找共 9 个接口
- 分析头插/中间插入为什么是 O(N)、尾插为什么是 O(1)
- 用顺序表作为底层容器，实现一个带文件持久化的通讯录项目
🔗 先修知识
数组（第 5 讲）、结构体（第 14 讲）、malloc/realloc/free（第 15 讲）、文件读写（第 16 讲）、assert（第 18 讲）。
自检三问：
realloc失败时返回什么？原来的内存还在不在？- 为什么
realloc的返回值要先存到临时指针，而不是直接写p = realloc(p, n)？ - 结构体数组
arr[i]和arr + i有什么关系？
一、为什么要学数据结构
从这一讲起，我们不再纠结语法细节，而是学习如何组织和管理数据。学完顺序表和链表，就能动手做通讯录这样的实用项目。
1.1 什么是数据结构
"数据结构"由"数据"和"结构"合成：
- 数据：数值、用户信息（姓名/年龄/电话）、网页里的文字图片……都是数据。
- 结构：把大量同类型数据按某种关系组织起来的方式。想从草原上找一只叫"咩咩"的羊很难，但从羊圈里找"1 号羊"很容易——羊圈就是一种结构。
定义：数据结构是计算机存储、组织数据的方式，是相互之间存在特定关系的数据元素的集合。好的数据结构要同时满足两点：① 能存下数据；② 存下的数据方便查找和操作。
1.2 有了数组，为什么还要别的数据结构
数组能存数据，但直接用它做增删很麻烦：
- 插入前要判断"满了没有"，数组不会自动扩容；
- 频繁求"有效元素个数"在数据量大时拖慢效率；
- 头/中间插入要手动搬移大量元素。
结论：基础数组提供的能力不足以支撑复杂操作，我们需要在它之上封装出更顺手的工具——这就是顺序表。
二、线性表与顺序表
2.1 线性表
线性表是 n 个具有相同特性的数据元素的有限序列。常见的线性表：顺序表、链表、栈、队列、字符串。它在逻辑上是一条连续的线，但物理存储上不一定连续——可以用数组（连续）存，也可以用链式结构（分散）存。
2.2 顺序表 = 数组 + 常用接口
顺序表底层就是数组，我们在数组之上封装好增删改查接口，用起来更省心。分两类：
| 类型 | 存储方式 | 缺陷 |
|---|---|---|
| 静态顺序表 | 定长数组 | 开小了不够用，开大了浪费 |
| 动态顺序表 | malloc/realloc 按需扩容 | 扩容要申请新空间、拷贝、释放旧空间 |
本讲重点实现动态顺序表。
三、动态顺序表的结构
c
typedef int SLDataType; // 元素类型，将来可换成结构体
typedef struct SeqList
{
SLDataType* a; // 指向动态数组
int size; // 有效元素个数
int capacity; // 当前已分配容量
} SL;size 记录"实际存了几个"，capacity 记录"能装几个"，size == capacity 时再插入就要扩容。把元素类型抽成 SLDataType，日后换成结构体（如通讯录的 PersonInfo）只需改这一行——这是通讯录项目复用同一套顺序表的关键。
四、九个接口逐一实现
下面把结构和全部接口写进一个文件，方便你复制即跑：
📄 01_seqlist_full.c · ✅ 完整程序（可直接复制编译）
c
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
typedef int SLDataType;
typedef struct SeqList
{
SLDataType* a;
int size;
int capacity;
} SL;
void SLInit(SL* ps)
{
assert(ps);
ps->a = NULL;
ps->size = ps->capacity = 0;
}
void SLDestroy(SL* ps)
{
assert(ps);
if (ps->a != NULL)
{
free(ps->a);
ps->a = NULL;
}
ps->size = ps->capacity = 0;
}
void SLPrint(SL* ps)
{
assert(ps);
for (int i = 0; i < ps->size; i++)
printf("%d ", ps->a[i]);
printf("\n");
}
void SLCheckCapacity(SL* ps)
{
assert(ps);
if (ps->size == ps->capacity)
{
int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
SLDataType* tmp = (SLDataType*)realloc(ps->a,
newCapacity * sizeof(SLDataType));
if (tmp == NULL)
{
perror("realloc fail");
exit(EXIT_FAILURE);
}
ps->a = tmp;
ps->capacity = newCapacity;
}
}
void SLPushBack(SL* ps, SLDataType x)
{
assert(ps);
SLCheckCapacity(ps);
ps->a[ps->size++] = x;
}
void SLPopBack(SL* ps)
{
assert(ps);
assert(ps->size > 0);
ps->size--;
}
void SLPushFront(SL* ps, SLDataType x)
{
assert(ps);
SLCheckCapacity(ps);
for (int i = ps->size; i > 0; i--) /* 从后往前整体后移 */
ps->a[i] = ps->a[i - 1];
ps->a[0] = x;
ps->size++;
}
void SLPopFront(SL* ps)
{
assert(ps);
assert(ps->size > 0);
for (int i = 0; i < ps->size - 1; i++) /* 从前往后整体前移 */
ps->a[i] = ps->a[i + 1];
ps->size--;
}
void SLInsert(SL* ps, int pos, SLDataType x)
{
assert(ps);
assert(pos >= 0 && pos <= ps->size); /* 允许在末尾插，即尾插 */
SLCheckCapacity(ps);
for (int i = ps->size; i > pos; i--)
ps->a[i] = ps->a[i - 1];
ps->a[pos] = x;
ps->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->a[i] = ps->a[i + 1];
ps->size--;
}
int SLFind(SL* ps, SLDataType x)
{
assert(ps);
for (int i = 0; i < ps->size; i++)
if (ps->a[i] == x)
return i;
return -1;
}
int main(void)
{
SL s;
SLInit(&s);
for (int i = 1; i <= 5; i++) SLPushBack(&s, i);
printf("尾插1-5: "); SLPrint(&s);
SLPushFront(&s, 0);
printf("头插0: "); SLPrint(&s);
SLInsert(&s, 3, 99);
printf("下标3前插99: "); SLPrint(&s);
SLErase(&s, 0);
printf("删下标0: "); SLPrint(&s);
SLPopBack(&s); SLPopFront(&s);
printf("头尾各删: "); SLPrint(&s);
printf("查找99下标: %d\n", SLFind(&s, 99));
printf("查找100下标: %d\n", SLFind(&s, 100));
SLDestroy(&s);
printf("销毁后 size=%d capacity=%d\n", s.size, s.capacity);
return 0;
}实测输出：
text
尾插1-5: 1 2 3 4 5
头插0: 0 1 2 3 4 5
下标3前插99: 0 1 2 99 3 4 5
删下标0: 1 2 99 3 4 5
头尾各删: 2 99 3 4
查找99下标: 1
查找100下标: -1
销毁后 size=0 capacity=04.1 扩容：为什么必须用临时指针
SLCheckCapacity 里最关键的一行是 tmp = realloc(...)。C11 §7.22.3.5 规定：realloc 失败返回空指针，且原内存保持不变。如果写成 ps->a = realloc(ps->a, ...)，一旦失败，ps->a 被覆盖成 NULL，原来那块有效数据就彻底丢失（内存泄漏 + 悬空）。所以必须先用 tmp 接住，判空成功后再赋回 ps->a。
扩容策略是"满了才翻倍，初始给 4"，把平均插入成本摊到 O(1)。
📜 标准卡（L2 选读）：realloc 与 assert
realloc(ptr, size)：C11 §7.22.3.5。成功返回新指针（可能搬家），失败返回 NULL 且原块不变；ptr为 NULL 时等价于malloc；size为 0 为实现定义 🟡。assert：C11 §7.2.1.1。定义NDEBUG后所有断言被编译掉，故断言里不能放有副作用的表达式。- gcc/MSVC：二者
realloc行为一致，遵循 C 标准。
4.2 头插 vs 尾插：O(N) 与 O(1) 的分水岭
- 尾插
SLPushBack：直接在a[size]放元素、size++，不动任何已有元素，O(1)（不算偶发扩容）。 - 头插
SLPushFront：必须先把所有元素后移一格，腾出a[0]，搬移量与size成正比，O(N)。
注意头插的循环方向：for (i = size; i > 0; i--) a[i] = a[i-1]，从后往前。若从前往后（a[i]=a[i-1] 从 i=1 递增），前面的值会先覆盖后面的、导致全表变成 a[0]。删除同理，前移要从前往后。
五、顺序表的应用：通讯录项目
用顺序表当容器，元素类型换成 PersonInfo 结构体，就得到一个通讯录。这是本课程第一个像样的多文件项目：
| 文件 | 作用 |
|---|---|
contact.h | PeoInfo 结构体 + 通讯录接口声明 |
SeqList.h / SeqList.c | 动态顺序表（元素类型 = PeoInfo） |
test.c | 菜单与 main |
⚠️ 命名一致性提醒：原课件讲顺序表用
SL/SLPushBack，讲通讯录又换成SLT/SeqListPushBack，两套命名混用会导致头文件与实现对不上、编译失败。本讲统一为一套：类型SL、函数SLXxx。
5.1 contact.h
🧩 contact.h（多文件源文件片段） · 需与其余文件同目录一起编译
c
#pragma once
#include <stdio.h>
#define NAME_MAX 100
#define SEX_MAX 5
#define TEL_MAX 12
#define ADDR_MAX 100
struct SeqList; /* 前置声明，contact.h 不必包含 SeqList.h */
typedef struct PersonInfo
{
char name[NAME_MAX];
char sex[SEX_MAX];
int age;
char tel[TEL_MAX];
char addr[ADDR_MAX];
} PeoInfo;
void InitContact(struct SeqList* con);
void AddContact(struct SeqList* con);
void DelContact(struct SeqList* con);
void ShowContact(struct SeqList* con);
void FindContact(struct SeqList* con);
void ModifyContact(struct SeqList* con);
void DestroyContact(struct SeqList* con);5.2 SeqList.h（通讯录版）
🧩 SeqList.h（多文件源文件片段） · 元素类型改为 PeoInfo
c
#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include "contact.h"
typedef PeoInfo SLDataType; /* 唯一改动：元素类型换成结构体 */
typedef struct SeqList
{
SLDataType* a;
int size;
int capacity;
} SL;
void SLInit(SL* ps);
void SLDestroy(SL* ps);
void SLCheckCapacity(SL* ps);
void SLPushBack(SL* ps, SLDataType x);
void SLErase(SL* ps, int pos);SeqList.c 的实现与第四节完全相同（realloc 大小自动按 sizeof(PeoInfo) 计算），此处省略。
5.3 contact.c（核心节选）
🧩 contact.c（多文件源文件片段） · 展示增删查改与文件持久化
c
#define _CRT_SECURE_NO_WARNINGS
#include "contact.h"
#include "SeqList.h"
#include <string.h>
static void LoadContact(SL* con)
{
FILE* pf = fopen("contact.dat", "rb");
if (pf == NULL) return; /* 首次运行没有文件，正常 */
PeoInfo info;
while (fread(&info, sizeof(PeoInfo), 1, pf) == 1)
SLPushBack(con, info);
fclose(pf);
printf("历史数据导入成功！\n");
}
void InitContact(SL* con) { SLInit(con); LoadContact(con); }
void AddContact(SL* con)
{
PeoInfo info;
memset(&info, 0, sizeof(info));
printf("请输入姓名："); scanf("%s", info.name); /* 数组名即地址，不加 & */
printf("请输入性别："); scanf("%s", info.sex);
printf("请输入年龄："); scanf("%d", &info.age);
printf("请输入电话："); scanf("%s", info.tel);
printf("请输入地址："); scanf("%s", info.addr);
SLPushBack(con, info);
printf("插入成功！\n");
}
static int FindByName(SL* con, const char* name)
{
for (int i = 0; i < con->size; i++)
if (strcmp(con->a[i].name, name) == 0)
return i;
return -1;
}
void DelContact(SL* con)
{
char name[NAME_MAX];
printf("请输入要删除的姓名："); scanf("%s", name);
int pos = FindByName(con, name);
if (pos < 0) { printf("用户不存在！\n"); return; }
SLErase(con, pos);
printf("删除成功！\n");
}
static void SaveContact(SL* con)
{
FILE* pf = fopen("contact.dat", "wb");
if (pf == NULL) { perror("fopen error"); return; }
for (int i = 0; i < con->size; i++)
fwrite(con->a + i, sizeof(PeoInfo), 1, pf); /* 二进制整块写 */
fclose(pf);
printf("通讯录保存成功！\n");
}
void DestroyContact(SL* con) { SaveContact(con); SLDestroy(con); }📘 提高（L2）：原课件通讯录代码的两处 bug（本讲已修正）
scanf("%s", &info.name)：info.name是数组，数组名本身就是首元素地址，再加&得到的是"整个数组"的地址，类型是char (*)[100]，与%s要求的char*不匹配。虽然数值上恰好指向同一位置、多数平台能跑，但属于类型错误，-Wall会警告。正确写法去掉&：scanf("%s", info.name)。- 命名不统一导致无法编译：见本节开头。统一为
SL/SLXxx后，四个文件可正常链接。
5.4 编译运行
四个文件放同一目录：
bash
gcc -Wall -Wextra -std=c11 test.c contact.c SeqList.c -o contact
./contact实测（添加两人→展示→查找→退出，再重启验证持久化）：
text
插入成功！
插入成功！
姓名 性别 年龄 电话 地址
张三 男 20 13800000001 北京
李四 女 22 13900000002 上海
查找成功！
张三 男 20 13800000001 北京
通讯录保存成功！
（重启后）
历史数据导入成功！六、顺序表的问题与思考
- 中间/头部插入删除 O(N)：要搬移大量元素；
- 增容要申请新空间、拷贝、释放旧空间，有额外消耗；
- 2 倍增长可能浪费空间（容量 100 满后增到 200，只多用 5 个则浪费 95）。
这些正是链表的用武之地——链表用非连续的节点 + 指针，插入删除不搬移数据，也不预先浪费空间。下一讲见。
⚠️ 常见坑与报错表
| 现象 | 原因 | 对策 |
|---|---|---|
realloc 后数据丢失/崩溃 | 直接写 p = realloc(p, n)，失败时 p 变 NULL | 用临时指针 tmp 接，判空后再赋回 |
| 头插后全表变成同一个值 | 搬移方向反了（从前往后覆盖） | 插入从后往前移，删除从前往后移 |
SLInsert 越界断言失败 | pos 允许范围是 [0, size]，写成 < size 或漏判 | 插入 pos<=size，删除 pos<size |
| 换元素类型后编译报错 | 只改了 typedef，函数签名里写死了 int | 全程用 SLDataType，改一处即可 |
| 通讯录两套文件命名对不上 | SL/SLT、SLPushBack/SeqListPushBack 混用 | 全项目统一命名 |
scanf("%s", &info.name) 警告 | 数组名再加 & 类型不符 | 去掉 & |
| 退出后数据没了 | 忘记在销毁前 SaveContact 写文件 | DestroyContact 里先存再释放 |
🛠️ 动手练习
📊 本讲网页练习进度0 / 8（0%）
进度自动保存在本浏览器；编程题不计数，请在编辑器中完成。
第 1 题（知识点：数据结构概念 · 难度：⭐）
下列关于"数据结构"的说法，最准确的是？
第 2 题（知识点：扩容安全 · 难度：⭐⭐）
SLCheckCapacity 里为什么用 tmp = realloc(...) 而不是 ps->a = realloc(...)？
第 3 题（知识点：时间复杂度 · 难度：⭐⭐）
顺序表在尾部插入是 O(1)，在头部插入是 O(N)，根本原因是？
第 4 题（知识点：搬移方向 · 难度：⭐⭐）
头插时把元素后移的循环必须"从后往前"（i 从 size 递减），若改成"从前往后"会怎样？
第 5 题（知识点：顺序表缺陷 · 难度：⭐⭐）
下列哪些是顺序表的固有缺点？
第 6 题（知识点：接口设计 · 难度：⭐⭐）
通讯录项目能直接复用讲原理时那套顺序表代码，靠的是把元素类型抽成别名 SLDataType。原理版写的是 typedef int SLDataType;，通讯录版只需把这一行的 int 换成 ______（填结构体名）。
空①
第 7 题（知识点：按值删除 · 难度：⭐⭐⭐）
🛠 动手编程题 · 请在 VS2026（或你的编辑器）中完成
给顺序表实现 SLRemoveAll(SL* ps, SLDataType x)：删除所有等于 x 的元素，剩余元素相对顺序不变。
✅ 过关标准：只用一次遍历（读写双下标），时间 O(N)；连续多个 x、x 在头/尾、全是 x、没有 x 等情况都正确；size 更新准确。
网页内无法练习写代码，亲手敲、亲手编译才能真正学会。下方按顺序展开 思路 → 步骤 → 答案。
💡 思路（卡住再点开）
用两个下标：write 指向"下一个该放的位置"，read 从头扫到尾。遇到 a[read] != x 就把它抄到 a[write] 并 write++；等于 x 就跳过。最后 size = write。这就是 LeetCode 27 移除元素的双指针法。
🔑 点击查看参考答案
c
void SLRemoveAll(SL* ps, SLDataType x)
{
assert(ps);
int write = 0;
for (int read = 0; read < ps->size; read++)
{
if (ps->a[read] != x)
ps->a[write++] = ps->a[read];
}
ps->size = write;
}实测：1 3 2 3 3 4 删除 3 → 1 2 4，size=3，一次遍历完成。
第 8 题（知识点：原地去重（有序表）· 难度：⭐⭐⭐）
🛠 动手编程题 · 请在 VS2026（或你的编辑器）中完成
假设顺序表已升序排序，实现 SLUnique(SL* ps)：删除重复元素，每个值只保留一个，返回去重后的元素个数。
✅ 过关标准：一次遍历 O(N)、原地完成；空表、单元素、全部相同、无重复等边界均正确；不额外申请数组。
网页内无法练习写代码，亲手敲、亲手编译才能真正学会。下方按顺序展开 思路 → 步骤 → 答案。
💡 思路（卡住再点开）
有序时重复值一定相邻。同样用读写双下标：write 记录去重区末尾，read 从下标 1 开始，只要 a[read] != a[write] 就说明遇到新值，++write 后把 a[read] 放进去。最后长度是 write+1。这就是 LeetCode 26。
🔑 点击查看参考答案
c
int SLUnique(SL* ps)
{
assert(ps);
if (ps->size == 0)
return 0;
int write = 0;
for (int read = 1; read < ps->size; read++)
{
if (ps->a[read] != ps->a[write])
ps->a[++write] = ps->a[read];
}
ps->size = write + 1;
return ps->size;
}实测：1 1 2 2 2 3 5 去重 → 1 2 3 5，返回 4。
📝 小结与自测
本讲脉络：
- 数据结构=存储+组织数据的方式；线性表是逻辑连续的一类结构，顺序表是其数组实现。
- 动态顺序表用
a/size/capacity三件套，满了realloc翻倍，必须用临时指针接返回值。 - 尾插尾删 O(1)，头插头删/中间插删 O(N)；搬移方向：插入从后往前、删除从前往后。
- 元素类型抽象成
SLDataType，一套代码可装 int 也可装结构体，通讯录即由此复用。 - 顺序表缺点（搬移、拷贝、浪费空间）引出下一讲链表。
自测三问：
- 为什么
realloc不能直接写回原指针？ - 头插的搬移循环为什么必须从后往前？
- 通讯录项目要新增/删除一个联系人，分别调用了顺序表的哪个接口？
🔑 自测答案
realloc失败返回 NULL 且原内存不变；直接p=realloc(p,..)会在失败时把 p 覆盖为 NULL，原块地址丢失→泄漏且无法访问。用 tmp 接住判空后再赋回。- 从前往后会让
a[i]=a[i-1]读到刚被覆盖的值，连锁污染成同一个值；从后往前能保证每个a[i-1]还是原始值。 - 新增用
SLPushBack（追加到末尾）；删除先FindByName定位下标，再SLErase(con, pos)。
🔬 选学拓展（L3）
WARNING
以下为进阶内容，供学有余力的同学选学。
拓展 1：静态顺序表版本
把 a 从指针改成定长数组，就不需要 realloc 了：
c
#define N 100
typedef struct StaticSeqList
{
int a[N];
int size;
} SSL;优点：无动态内存、无扩容、结构简单；缺点：容量写死，小了不够、大了浪费。适合数据规模确定的场景。
拓展 2：经典 OJ——合并两个有序数组（LeetCode 88）
两个升序数组，把第二个合并进第一个（第一个有足够尾部空间）。关键：从后往前填，避免覆盖未处理元素：
c
void merge(int* nums1, int m, int* nums2, int n)
{
int i = m - 1, j = n - 1, k = m + n - 1;
while (j >= 0)
{
if (i >= 0 && nums1[i] > nums2[j])
nums1[k--] = nums1[i--];
else
nums1[k--] = nums2[j--];
}
}从后往前是顺序表"搬移方向"思想的又一次应用。
拓展 3：通用化——用 void* 和函数指针
上面的 SLDataType 换类型要重编译。C 里可用 void* 存任意类型 + 传入比较/打印函数指针，做出"一次编译、多类型使用"的通用容器。代价是指针类型不安全、代码复杂。C++ 的模板能更好地解决此问题，这也是工程上很多团队从 C 转向 C++/Rust 做数据结构的原因之一。
📜 标准卡（L2 选读）：本讲依据
- 动态内存：C11 §7.22.3（malloc/calloc/realloc/free）；
realloc语义见 §7.22.3.5。 - 断言：C11 §7.2.1.1。
- 二进制文件读写：C11 §7.21.3（fread/fwrite），结构体整块写入的可移植性依赖同一实现（不同编译器对齐可能不同 🟡）。