顺序表可能是C语言数据结构里第一个让人有“原来如此”感觉的内容。很多人学完数组之后都会问：数组不是已经能存数据了吗？为什么还要搞一个顺序表？这个问题我在刚接触数据结构时也想过，直到自己动手用顺序表做了一个简易通讯录，才真正明白数组和顺序表之间的区别，不只是“多了一个变量”那么简单。
这篇文章我会把顺序表的核心设计、动态扩容、插入删除的细节全部拆开讲，再贴出一套可以直接编译运行的简易通讯录项目全源码。无论你是正在准备C语言期末复习、要写数据结构实验报告，还是单纯想把考研基础打牢，这套代码和思路都能直接拿过去用。
1. 为什么顺序表值得亲手实现一遍
1.1 顺序表到底是什么
顺序表本质上就是“有管理员的数组”。普通数组是一个固定大小的连续内存块，程序员自己记着里面存了多少个有效元素，取数据全靠下标编号。顺序表则在这个数组外面包了一层结构体，把“当前有效元素个数”和“底层容量大小”一起管理起来，对外提供初始化、插入、删除、查找、修改这些标准接口。
如果你写过课程作业里的成绩管理系统，一定遇到过这种尴尬：明明只录入了30条记录，却要定义一个500大小的数组。这时候普通数组的短板就暴露了——它不知道哪些位置有数据，也不知道还剩多少空间。顺序表通过一个变量记录size，也就是逻辑长度，把“实际用了多少”和“最多能存多少”分离，这才是一个数据结构该有的样子。
底层存储连续是顺序表最核心的特征。这意味着访问第i个元素只需要执行一次地址计算：data + i * sizeof(元素)，时间开销恒定的O(1)。这个特性让顺序表非常适合“按下标随机访问”的场景，比如通讯录里按下标修改某条记录，速度极快。
1.2 从静态数组到动态顺序表，到底改变了什么
静态数组的问题不只是空间浪费。你永远无法预判运行时的真实需求：分配小了，程序可能直接越界崩溃；分配大了，内存白白占着。很多C语言新手会把数组下标写越界，因为编译器不检查，运行时才会出问题，这种错误排查起来相当痛苦。
动态顺序表的思路很简单：先分配一个初始容量，比如4个或8个元素的存储空间，当size逼近capacity时，自动申请一块更大的内存，把旧数据整体搬过去。这个操作就叫扩容，也叫realloc。通讯录项目为什么特别适合演示这个特性？因为联系人的数量完全不可控，今天录入3个，明天可能录入30个。用动态顺序表，内存按需增长，数据不会丢，程序也不怕撑爆固定数组。
从学习角度说，动态扩容是你理解“内存管理”的第一课。malloc负责申请，realloc负责调整，free负责释放，三者配合好了，程序才稳定。很多面试题和期末考试都喜欢考“扩容失败怎么处理”“原指针被覆盖了怎么办”，这些坑在后面章节我会专门展开。
1.3 顺序表血统纯正，但为什么不适合所有场景
有的同学一上来就想学链表，觉得链表高级。但数据结构的选型和场景强相关。链表的优势在于头部插入和删除的时间复杂度O(1)，劣势在于按位置访问必须从头遍历，而且每个节点都要额外存储一个指针，内存开销更大。
通讯录这个场景，用户最频繁的操作是什么？显示全部联系人、按下标修改联系人、按姓名查找联系人。前两个操作恰恰是顺序表的强项：遍历和随机访问都是O(1)，链表反而要一个个跳节点。至于按姓名删除，顺序表和链表都需要先做一次O(n)的查找，找完之后顺序表搬移元素，链表修改指针，差距并不明显。
所以新手练习项目选顺序表是明智的。它实现简单、逻辑直观、调试方便，先搞清楚“连续存储 + 元素搬移”这套思维，再去看链表会轻松很多。数据结构不是比谁的指针绕得更花，而是比谁更贴合需求。
2. 顺序表的核心设计与关键实现
2.1 结构体怎么设计才规范
设计和实现顺序表时，我建议先定义结构体，把容量和长度放在一起管理。下面是这个通讯录项目的核心结构：
#define INIT_CAP 4 typedef struct { char name[32]; char phone[20]; char email[32]; } Contact; typedef struct { Contact *data; // 指向堆上连续内存 int size; // 当前有效元素个数 int capacity; // 当前最大容量 } SeqList;Contact是通讯录里的一条联系人记录，SeqList是顺序表本身。很多教材喜欢直接写int data[100]，然后配一个length变量，这种做法在考试里没问题，但在实际项目中太僵硬了。把数组改成指针Contact *data，我们才能在初始化时用malloc按需分配，在扩容时用realloc动态调整。
size和capacity这两个变量必须分清楚：size是逻辑长度，表示当前有几条有效联系人；capacity是物理容量，表示底层申请了多少个元素的空间。这个区分是面试高频考点，很多bug都出在“把数组长度当成了容量”或“把容量当成了长度”。
2.2 初始化、销毁与判空操作
初始化要做的事情很明确：申请初始容量的内存，把size置0，capacity设置成初始值。注意malloc之后一定要判空，内存不足时程序应该给出明确提示并退出，而不是继续往下跑。
void initList(SeqList *list) { list->data = (Contact *)malloc(sizeof(Contact) * INIT_CAP); if (list->data == NULL) { printf("内存分配失败\n"); exit(1); } list->size = 0; list->capacity = INIT_CAP; } void destroyList(SeqList *list) { if (list->data != NULL) { free(list->data); list->data = NULL; } list->size = 0; list->capacity = 0; }销毁操作容易被人忽略，但它和malloc同样重要。程序退出前不free，短时间看没影响，放在长时间运行的服务里就是内存泄漏。free之后把data置空，是为了防止“悬空指针”。这个习惯一定要养成：谁申请，谁释放；释放完，指针归零。
2.3 动态扩容：为什么翻倍而不是加一个固定值
当size == capacity时再插入新元素，就必须扩容。最安全的扩容写法不是直接把realloc的结果赋给原指针，而是先用一个临时变量接住返回值。因为realloc有可能失败，失败时返回NULL，原内存仍然有效。如果直接list->data = realloc(list->data, ...)，一旦失败，原指针就丢了，数据就彻底没了。
int expand(SeqList *list) { int newCap = list->capacity * 2; Contact *tmp = (Contact *)realloc(list->data, sizeof(Contact) * newCap); if (tmp == NULL) { printf("扩容失败，当前数据未受影响\n"); return 0; } list->data = tmp; list->capacity = newCap; return 1; }为什么容量翻倍而不是每次多分配几个位置？这里有个摊销分析。假设每次追加一个元素，如果容量每次只加1，那么插入第n个元素时需要搬移大约n次，总代价是O(n²)。如果容量翻倍，扩容次数只有O(logn)，每次扩容搬移现有元素，平摊到每次插入上，代价近似O(1)。这是很多算法题里“动态数组均摊O(1)”说法的由来。
初始容量我设成4，是因为通讯录演示场景通常不会一上来就录很多人，4个够用。如果你想改成8、16，完全没问题。唯一要注意的是初始容量不能为0，否则第一次判断size == capacity恒成立，会直接陷入扩容逻辑，逻辑容易混乱。
2.4 插入操作：元素搬移的方向为什么是从后往前
插入是顺序表的核心操作，也是最容易写错的地方。插入位置pos的合法范围是0 <= pos <= size。当pos等于size时，其实就是尾部追加；当pos小于0或大于size时，直接拒绝。
int insertAt(SeqList *list, int pos, Contact c) { if (pos < 0 || pos > list->size) { printf("插入位置不合法\n"); return 0; } if (list->size == list->capacity) { if (!expand(list)) { return 0; } } for (int i = list->size; i > pos; i--) { list->data[i] = list->data[i - 1]; } list->data[pos] = c; list->size++; return 1; }这段代码里最关键的循环是for (int i = list->size; i > pos; i--)。为什么要从最后一个元素开始，一个一个往后搬？因为插入点及后面的元素都要向后移动一位，如果从前往后搬，后面的元素会被前面的覆盖掉。
我举个直观例子：数组内容是{A, B, C}，size是3，要在pos=1处插入X。如果从前往后搬，data[2] = data[1]，先把B复制到C的位置，但接下来data[1] = data[0]执行后，原始B已经被覆盖，B就丢了。从后往前搬，先data[3] = data[2]把C挪走，再data[2] = data[1]把B挪到原来C的位置，最后data[1] = X，所有数据完整保留。这个方向性问题是期末机考最喜欢埋的坑。
2.5 删除操作：方向反过来的原因
删除操作和插入正好相反。删除pos处的元素时，需要把pos后面的元素整体往前覆盖，所以循环方向是从前往后。
int deleteAt(SeqList *list, int pos) { if (pos < 0 || pos >= list->size) { printf("删除位置不合法\n"); return 0; } for (int i = pos; i < list->size - 1; i++) { list->data[i] = list->data[i + 1]; } list->size--; return 1; }很多初学者会问：删除为什么不需要free？因为顺序表删掉的只是“逻辑上”的一个元素，底层数组的内存空间还在，capacity不变。我们只是把size减1，让这个位置变成无效状态，下次插入新元素时直接覆盖它就行。这在操作系统中叫“逻辑删除”，概念可以类比文件系统里删除文件时先标记、不立刻擦除。
删除后末尾的残留数据要不要清掉？严格来说不是必须。如果通信录的data里存了字符串，残留数据不会影响任何逻辑判断，因为size已经限定了有效范围。但如果元素是指针类型，需要手动释放指针指向的内存，再考虑清空，否则会内存泄漏。
3. 把顺序表变成简易通讯录：完整项目全源码
3.1 需求分析与菜单设计
通讯录项目是我用来讲顺序表最常见的案例，因为它能覆盖顺序表几乎全部核心操作。这个简易版本需要支持添加联系人、按姓名删除联系人、按姓名查找联系人、按下标修改联系人、显示全部联系人、退出并释放内存。
添加用的是尾插法，也就是把pos设为list.size，这样每次新联系人追加到末尾，顺序自然保持录入顺序。删除和查找共用findByName函数，先找到下标，再调用删除。修改则要求用户输入下标，直接替换该位置的Contact结构体。
菜单设计成控制台循环，用switch分支。我在前面已经说过，C语言里case内不定义变量，所有临时变量都在main开头声明，这样能避免“crosses initialization”这种编译错误。菜单读取数字之后，一定要把缓冲区里残留的换行符清掉，否则下一个读取字符串的scanf会直接吞掉换行符。
3.2 完整源码
下面是一份可直接保存为contacts.c的完整项目源码，单文件就能编译运行，适合作为实验报告或课程设计基础版：
#include <stdio.h> #include <stdlib.h> #include <string.h> #define INIT_CAP 4 typedef struct { char name[32]; char phone[20]; char email[32]; } Contact; typedef struct { Contact *data; int size; int capacity; } SeqList; void initList(SeqList *list) { list->data = (Contact *)malloc(sizeof(Contact) * INIT_CAP); if (list->data == NULL) { printf("内存分配失败\n"); exit(1); } list->size = 0; list->capacity = INIT_CAP; } void destroyList(SeqList *list) { if (list->data != NULL) { free(list->data); list->data = NULL; } list->size = 0; list->capacity = 0; } int expand(SeqList *list) { int newCap = list->capacity * 2; Contact *tmp = (Contact *)realloc(list->data, sizeof(Contact) * newCap); if (tmp == NULL) { printf("扩容失败，当前数据未受影响\n"); return 0; } list->data = tmp; list->capacity = newCap; return 1; } int insertAt(SeqList *list, int pos, Contact c) { if (pos < 0 || pos > list->size) { printf("插入位置不合法\n"); return 0; } if (list->size == list->capacity) { if (!expand(list)) { return 0; } } for (int i = list->size; i > pos; i--) { list->data[i] = list->data[i - 1]; } list->data[pos] = c; list->size++; return 1; } int deleteAt(SeqList *list, int pos) { if (pos < 0 || pos >= list->size) { printf("删除位置不合法\n"); return 0; } for (int i = pos; i < list->size - 1; i++) { list->data[i] = list->data[i + 1]; } list->size--; return 1; } int findByName(SeqList *list, const char *name) { for (int i = 0; i < list->size; i++) { if (strcmp(list->data[i].name, name) == 0) { return i; } } return -1; } void modifyAt(SeqList *list, int pos, Contact c) { if (pos < 0 || pos >= list->size) { return; } list->data[pos] = c; } void printList(SeqList *list) { if (list->size == 0) { printf("通讯录是空的\n"); return; } printf("\n%-16s%-20s%-32s\n", "姓名", "电话", "邮箱"); for (int i = 0; i < list->size; i++) { printf("%-16s%-20s%-32s\n", list->data[i].name, list->data[i].phone, list->data[i].email); } printf("当前共 %d 人\n", list->size); } int main(void) { SeqList list; initList(&list); Contact c; char name[32]; int pos; int choice; int ch; while (1) { printf("\n===== 简易通讯录 =====\n"); printf("1. 添加联系人\n"); printf("2. 按姓名删除联系人\n"); printf("3. 按姓名查找联系人\n"); printf("4. 按下标修改联系人\n"); printf("5. 显示全部联系人\n"); printf("6. 退出并释放内存\n"); printf("请选择: "); scanf("%d", &choice); while ((ch = getchar()) != '\n' && ch != EOF) { } switch (choice) { case 1: printf("姓名: "); scanf("%s", c.name); printf("电话: "); scanf("%s", c.phone); printf("邮箱: "); scanf("%s", c.email); if (insertAt(&list, list.size, c)) { printf("添加成功\n"); } break; case 2: printf("输入要删除的姓名: "); scanf("%s", name); pos = findByName(&list, name); if (pos == -1) { printf("找不到该联系人\n"); } else { deleteAt(&list, pos); printf("删除成功\n"); } break; case 3: printf("输入要查找的姓名: "); scanf("%s", name); pos = findByName(&list, name); if (pos == -1) { printf("找不到该联系人\n"); } else { printf("联系人下标: %d\n", pos); printf("%-16s%-20s%-32s\n", "姓名", "电话", "邮箱"); printf("%-16s%-20s%-32s\n", list.data[pos].name, list.data[pos].phone, list.data[pos].email); } break; case 4: printf("输入要修改的下标: "); scanf("%d", &pos); if (pos < 0 || pos >= list.size) { printf("下标越界\n"); } else { printf("新的姓名: "); scanf("%s", c.name); printf("新的电话: "); scanf("%s", c.phone); printf("新的邮箱: "); scanf("%s", c.email); modifyAt(&list, pos, c); printf("修改成功\n"); } break; case 5: printList(&list); break; case 6: destroyList(&list); printf("已释放内存，再见\n"); return 0; default: printf("无效选项，请重新输入\n"); } } }这段代码我故意把逻辑整理得比较“教学化”，每个函数只做一件事，命名也尽量直白。insertAt和deleteAt返回int，是为了让调用处能知道操作是否成功。findByName返回-1表示找不到，这也是C语言项目里的常用约定。
3.3 编译运行与实际效果演示
在Linux或Windows的gcc环境里，编译只要一行命令：
gcc contacts.c -o contacts ./contacts如果是Windows下用VS或者Dev-C++，直接新建C语言控制台项目，把代码粘进去运行即可。程序启动后会看到菜单，输入1添加联系人，输入5显示全部。连续录入六个联系人之后，程序会出现一次自动扩容，因为初始容量只有4，第四个插满之后，第五个插入触发扩容。这个扩容过程是自动的，用户感知不到，但内存确实被扩展了。
我用实际输入测试过：依次录入张三、李四、王五、赵六、钱七五个联系人，程序正常显示5人；按姓名删除张三后，显示4人；按下标2修改联系人，修改后打印验证，数据完全正确。这套流程足够覆盖课程设计的基本要求。
4. 我在实现过程中踩过的坑与排查技巧
4.1 realloc的指针陷阱：少写一个临时变量就翻车
网上很多教程会写p = realloc(p, newSize)，这种写法在realloc成功时没问题，但如果内存不足导致realloc返回NULL，原本的p就被覆盖成了NULL，旧内存的地址找不回来了。轻则数据全丢，重则程序崩溃。
正确写法是先用临时变量接住返回结果，判断非NULL后再赋值给原指针。我在扩容函数里专门用了Contact *tmp来承接，这个习惯值得所有C语言新手记住。很多数据结构的作答题不是考你realloc怎么用，而是考你“如何保证realloc失败后数据不丢”。
另外，realloc之后的指针地址可能和原来完全不同，千万不要在扩容前把旧地址存到另一个变量里，然后在扩容后继续用旧地址访问数据。地址已经变了，旧地址指向的内存可能已经被系统回收。
4.2 插入删除的边界条件：pos取等还是不取等
写顺序表最容易翻车的就是下标边界。插入位置合法范围是[0, size]，因为size位置可以视为尾部追加；删除位置合法范围是[0, size-1]，因为删除的元素必须真实存在。这两个范围一个闭区间一个半开区间，经常被搞混。
我在代码里通过insertAt的pos < 0 || pos > list->size和deleteAt的pos < 0 || pos >= list->size做了双重校验。很多考试题会故意让你写“在第i个位置插入”或“删除第i个元素”，这里的i如果从1开始计数，转换成数组下标还要减1。建议统一把位置参数定义为数组下标，逻辑更简单。
4.3 scanf残留换行符导致菜单“神经错乱”
这个坑几乎每个C语言项目都会遇到。用户在菜单处输入数字6之后按下回车，缓冲区里会留着一个换行符。下一次代码执行到scanf("%s", c.name)时，这个换行符并不会被自动跳过，而是可能被当成输入结束处理，让你少读一次数据。
解决方案是在每次读完菜单数字后，用一个循环把缓冲区里剩余的字符吞掉。我在源码里写的while ((ch = getchar()) != '\n' && ch != EOF)就是这个作用。这个习惯同样适用于读取字符、读取数字后再读取字符串的场景，是C语言交互式程序的重要基本功。
4.4 字符串处理：strcpy和strcmp的细节
通讯录的姓名、电话、邮箱都用char数组存储。添加联系人时，scanf("%s", c.name)会把输入的字符串和结尾的'\0'一起写到数组里。这里有个隐藏风险：如果用户输入的字符串超过31个字符，数组会溢出，覆盖相邻内存。演示项目可以接受这个限制，但在真实项目里建议用fgets并限制长度。
strcmp比较字符串是用来判断两个名字是否相等的，不能直接写list->data[i].name == name，因为数组名会退化成指针，比较的是地址而不是内容。这个错误在初学者代码里出现频率极高，我用strcmp(list->data[i].name, name) == 0来判断相等。注意strcmp相等返回0，不是返回1，这一点很容易搞反。
4.5 中文输出对齐的小问题
printf("%-16s", "姓名")在英文环境下非常好用，但遇到中文时，一个汉字在终端里占2个或3个英文字符宽度，%-16s无法完美对齐。我在打印通讯录时直接用了固定宽度，效果勉强能看，但如果你追求表格线严格对齐，建议用宽字符处理函数，或者直接接受不对齐的现实。
这个细节不算bug，但实验报告截图里很显眼。如果你想让输出更整齐，可以把姓名、电话、邮箱的列宽加大，或者在中文和数字混合时手动填充空格。当然，更优雅的做法是使用wprintf配合宽字符库，只是对初学者难度偏高，我选择了最直观的printf方案。
5. 复杂度表现、实验报告素材与扩展方向
5.1 顺序表操作的时间复杂度速查
整理一张复杂度表能帮你快速应对期末复习和面试：
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 按下标访问 | O(1) | 底层连续存储，直接算地址 |
| 尾部插入/删除 | O(1)均摊 | 尾部插入偶尔触发扩容 |
| 中间插入 | O(n) | 需要搬移后面所有元素 |
| 中间删除 | O(n) | 需要搬移后面所有元素 |
| 按值查找 | O(n) | 线性扫描，无序表没有优化空间 |
| 扩容 | O(n) | 拷贝旧数据到新空间，但均摊后O(1) |
很多同学不理解“均摊O(1)”是什么意思。这么说吧：每次插入的代价并不完全一样，偶尔一次扩容会把前面所有元素搬一遍，代价高，但这次高代价被前面多次低代价的插入分摊了。就像你每个月正常开销不大，但每年交一次保险费时开销很高，把保险费摊到每个月看，就是一笔稳定的小支出。
5.2 实验报告和期末考怎么用这些素材
如果你在写数据结构实验报告，可以把“动态扩容机制”“插入删除元素搬移方向”“realloc失败处理”作为重点分析内容写进去。实验目的不用写得天花乱坠，就写清楚两点：一是掌握顺序表的存储结构，二是理解动态内存分配和边界条件处理。程序运行截图、输入输出结果、时间复杂度和空间复杂度分析，这三样是实验报告的核心。
期末机考和笔试经常出现这几类变形题：用顺序表删除所有值等于x的元素、把顺序表原地逆置、合并两个有序顺序表。这类题本质都是在考察元素搬移的方向和下标边界。你把本文的insertAt和deleteAt彻底看懂，再做题时会发现套路非常固定。
5.3 这个通讯录后续还能怎么扩展
这份简易通讯录只是一个最小可运行版本，扩展空间很大。第一个方向是排序，可以在显示前按姓名做字典序排序，或者按下标、按姓氏分类。第二个方向是文件持久化，程序退出前把联系人写入文件，下次启动再读回来，这需要增加save和load两个函数，会用到fopen、fwrite、fprintf等文件操作API。
第三个方向是查找优化。如果把联系人按姓名排好序，查找就可以用二分查找，时间复杂度从O(n)降到O(logn)。第四个方向是把顺序表改造成泛型版本，用void*存储任意类型的数据，这样通讯录只是顺序表的一种应用，你还能拿它做一个学生成绩表、商品库存表。这个思路已经接近C语言高级项目的设计方法了。
我个人在实际操作中的体会是，顺序表最值得反复练习的并不是代码能跑通，而是“边界条件”和“内存生命周期”这两个词。插入时想清楚要不要扩容，删除时想清楚下标能不能取等号，销毁时想清楚内存是不是真的释放了。每次写之前先画一张小图，把数组元素一个个画出来，模拟搬移过程，比盲目刷十道题都管用。这份通讯录源码你拿去之后，可以先原样编译运行，再用gdb或者VSCode断点观察容量变化，最后试着加上文件保存功能，在这个基础上折腾，你会比只看不练的人收获多得多。
