数据结构这门课很多人碰到的第一道坎不是指针也不是递归而是顺序表。可能有人会觉得顺序表不就是数组吗有什么好讲的。我以前也这么想直到自己动手写了个图书信息管理的小系统数组越界后整个程序的数据稀里糊涂“变脏”排查了一整个晚上才定位到问题——根子就在我没有真正搞懂顺序表的 length、capacity 和存储空间三者的关系。顺序表之所以值得单独拆出来消化是因为后面你要学的查找、排序、KMP 算法、归并排序底层几乎都依赖一个逻辑清晰、操作正确的线性结构来装数据顺序表就是这个结构的起点。这篇文章我打算把顺序表掰开揉碎地讲一遍从它和普通数组的差别到初始化、扩容、插入、删除、按值查找这些基本操作再到复杂度分析里很多人栽跟头的 O、Ω、θ 符号最后用一个图书信息顺序表管理的完整 C 语言示例收尾。内容适合刚上数据结构课的同学、准备 408 统考的考研党以及那些平时写业务代码但没系统补过数据结构的非科班朋友。1. 先把顺序表这张图在脑子里画清楚1.1 从数组到顺序表多出来的两个字段到底在管什么数组是编程语言天然自带的容器声明完 int a[100]编译器就给你划一块连续内存下标访问简单粗暴。但数组有个天生的毛病它不知道数组里到底有几个元素是“有效”的。你塞了 3 个数据进去和塞了 80 个数据进去a 这个数组本身不会给你任何提示只有你自己心里清楚。顺序表在数组之上做了一层封装它把“数组容量”和“当前有效元素个数”分离成两个字段。用 C 语言来定义通常长这样#define INIT_CAPACITY 10 typedef struct { int *data; // 指向连续内存的指针 int length; // 当前已存储的元素个数 int capacity; // 当前内存最多能容纳的元素个数 } SeqList;这里最关键的一句话数组大小是物理容量顺序表的 length 是逻辑长度。capacity 告诉你这片内存最多装多少length 告诉你现在实际装了多少。为什么非要多一个 capacity因为顺序表的精髓在于“动态”它不能像 int a[100] 一样把容量焊死在代码里。你预先不知道用户会往里塞多少数据所以需要 capacity 来跟踪当前分配的内存大小当 length 逼近 capacity 时就知道该扩容了。用个生活类比这就像电影院的一排座位。座位总数是 capacity已经入座的人数是 length。座位数和人数必须分开记否则你数人头的时候根本不知道这一排还空着几个座也不知道下一批观众进场时要不要加开一排。1.2 为什么顺序表这么重要而不被链表替代你可能会问同样能存一组数据链表不是也能做到吗为什么排序算法、KMP 算法背后的存储结构默认都是顺序表而不是链表答案就四个字随机存取。顺序表的内存是连续的data[i] 的访问直接通过“基地址 i × 元素大小”计算偏移时间复杂度是 O(1)。这个能力太要命了。二分查找要在每一步直接跳到中位元素快速排序要频繁交换任意两个位置的元素KMP 算法要按 next 数组回溯到指定下标——这些算法如果放在链表上访问第 i 个节点得先从头指针走 i 步一趟 O(n)算法复杂度直接整体上一个台阶很多优美性质全没了。顺序表还有一个常被忽略的优势缓存局部性好。连续内存的元素被 CPU 加载进高速缓存时是一块一块拉进来的。你遍历前几个元素的时候后续元素大概率已经躺在缓存里了。链表节点散落在堆里每次访问都大概率要重新命中缓存数据量一大性能差距非常明显。当然顺序表不是万能的。它在头部或中间插入、删除时为了保持元素的连续性必须整体搬移一批元素这是它最大的软肋。所以实用的建议是游戏排行榜这类“查得多、改得少、偶尔在尾部追加”的场景首选顺序表文本编辑器这类需要在任意位置频繁插入删除的场景顺序表就非常痛苦得考虑链表或者其他结构。这俩不是谁取代谁是互补关系你心里得有这张图。2. 顺序表核心操作一行行拆给你看2.1 结构体定义、初始化和销毁先给出一个基本的初始化函数。注意一个原则只要函数内部会修改顺序表的状态就必须传指向 SeqList 的指针否则你在函数里改了 length外面完全感知不到。传值操作只能“望梅止渴”。void init_seqlist(SeqList *list) { list-data (int *)malloc(INIT_CAPACITY * sizeof(int)); if (list-data NULL) { printf(初始化失败内存分配失败\n); exit(1); } list-length 0; list-capacity INIT_CAPACITY; }malloc 返回的指针必须判空这是很多新手容易忽略的事。嵌入式和物联网场景里内存本来就紧张分配失败是常态不判空直接往 NULL 里写数据轻则崩溃重则静默污染内存。初始化完 length 置 0capacity 置 10这两个谁写反了后面所有操作全乱。对应的销毁函数也要养成配套写的习惯。C 语言里 malloc 和 free 是一对写一个带 malloc 的结构体就一定要写一个对应的 free 入口void destroy_seqlist(SeqList *list) { if (list-data ! NULL) { free(list-data); list-data NULL; } list-length 0; list-capacity 0; }2.2 扩容你最不希望触发、但必须先写对的函数扩容是顺序表里最容易写错、也最考验功底的一个环节。触发条件很简单当 length 快要等于 capacity 时再插入新元素就没地方放了。扩容的策略是重新分配一块更大的内存把旧数据搬过去再释放旧内存。void ensure_capacity(SeqList *list, int extra) { // extra 表示接下来至少要新增加几个元素 if (list-length extra list-capacity) { return; } int new_capacity list-capacity 0 ? 1 : list-capacity * 2; while (new_capacity list-length extra) { new_capacity * 2; } int *new_data (int *)malloc(new_capacity * sizeof(int)); if (new_data NULL) { printf(扩容失败\n); exit(1); } // 把旧数据逐个复制过去 for (int i 0; i list-length; i) { new_data[i] list-data[i]; } free(list-data); list-data new_data; list-capacity new_capacity; }为什么要选择乘 2 扩容而不是每次多申请一个位置这是一个均摊分析的问题。如果一趟插入一个位置连续插入 n 次每次都要搬运已有的全部数据总复杂度是 1 2 3 ... n O(n²)数据量大一点直接卡死。而扩容成 2 倍容量到 n 时需要扩容的次数是 log₂n 级别每轮扩容的总搬运量加起来才 2n 左右均摊到每次插入是 O(1)。这就是数据结构里经典“均摊复杂度”的实战意义。有一点必须提醒你扩容之后list-data 指向的是全新的内存地址。如果你在别处偷偷保存了旧的 data 指针继续用那拿到的全是已经释放的野内存这是最常见的内存 bug 来源之一。正确做法是永远通过 list-data 去访问元素不要另存副本。2.3 三个插入函数的边界条件插入是顺序表里最需要细心的地方。我给出一套完整实现把尾插、中间插、头插统一到一个函数里。// 在逻辑位序 pos 处插入元素 valpos 从 0 开始 int insert_seqlist(SeqList *list, int pos, int val) { if (pos 0 || pos list-length) { printf(插入位置非法\n); return 0; } ensure_capacity(list, 1); // 从后往前搬迁给 pos 腾出位置 for (int i list-length; i pos; i--) { list-data[i] list-data[i - 1]; } list-data[pos] val; list-length; return 1; } // 尾部插入 int append_seqlist(SeqList *list, int val) { return insert_seqlist(list, list-length, val); } // 头部插入 int push_front_seqlist(SeqList *list, int val) { return insert_seqlist(list, 0, val); }位置校验这里非常容易出错。很多人会把判断写成 pos list-length这其实是错的。在逻辑位序 pos 处插入意味着新元素可以插到当前最后一个元素的后面也就是 pos length 的位置所以合法范围是 0 到 length 闭区间。元素后移的方向必须从后往前。你要是写成从前往后第一次搬迁就把后面元素覆盖了整个数组直接丢数据。边界上还有一个细节如果原来的长度是 length插入后最大的下标是 length所以扩容必须保证 capacity 至少是 length 1ensure_capacity 的参数传 1 就是这个道理。2.4 删除、按值查找、修改删除是插入的逆操作但方向反过来了要从前往后搬。删除第 pos 个元素后后面的元素要统一往前移动一位最后一个有效位置变成“废弃值”但逻辑上已经被移出表了。int delete_seqlist(SeqList *list, int pos) { if (pos 0 || pos list-length) { printf(删除位置非法\n); return 0; } int deleted list-data[pos]; for (int i pos; i list-length - 1; i) { list-data[i] list-data[i 1]; } list-length--; return deleted; } // 按下标查找 int get_seqlist(SeqList *list, int pos) { if (pos 0 || pos list-length) { printf(访问越界\n); return -1; } return list-data[pos]; } // 按值查找返回第一个匹配元素的下标 int find_seqlist(SeqList *list, int val) { for (int i 0; i list-length; i) { if (list-data[i] val) { return i; } } return -1; }删除时我有一个个人习惯把被删元素的值作为返回值返回出来。这样调用者既能确认删除是否成功又能拿到被删的数据比如排行榜上一个玩家下线了系统总要记录他的积分再移除。如果返回值只有 0 和 1被删的数据就白白在内存里丢了。另外注意删除元素后我没有立刻缩容。容量大一点并不是坏事因为之后再插入数据就免去了扩容开销。除非你的顺序表长时间处于长尾低占用状态否则不建议写 shrink 逻辑。频繁缩容又扩容会造成内存抖动反而比留着空间更伤性能。3. 复杂度分析O 和 θ 到底什么时候用3.1 三种渐进符号的差别学习数据结构一定会碰到复杂度符号很多人在这里被卡住“明明题目里写的是 O(n²)为什么老师又说这个算法实际上是 Θ(n²)”其实这三个符号的区别非常直观O(f(n))表示算法的运行时间不会超过 f(n) 的某个常数倍相当于给出时间上界。最坏情况的复杂度用 O 表达最合适。Ω(f(n))表示算法的运行时间至少是 f(n) 的某个常数倍相当于给出时间下界。最好情况或最优输入的分析适合用 Ω。Θ(f(n))表示运行时间既不超过也不低于 f(n) 的常数倍上下界重合在一起这是最精确的描述。举个例子在顺序表里做顺序查找从第一个元素开始逐个比对。最好情况第一个元素就是要找的目标只比较 1 次所以是 Ω(1)。最坏情况目标在最后一个位置或不存在要比较 n 次所以是 O(n)。平均情况假设每个位置被查找的概率相同成功查找的平均比较次数约等于 (n1)/2也就是线性级别此时可以说这个操作是 Θ(n) 的。如果你只说“顺序查找的时间复杂度是 O(n)”这没有错但它丢掉了“平均也是线性”这个更精确的信息如果你直接用 Θ(n)意思是无论最好、平均还是最坏它都会退化到线性级复杂度这个说法其实更贴切。那什么时候写 O、什么时候写 Θ我自己的经验是三条在课程作业和考试里如果没有特殊说明默认考察“最坏情况”就用 O这是最普遍的表达习惯。如果算法的最好情况和最坏情况复杂度相同比如普通嵌套双循环的冒泡排序无论什么输入比较次数都是 n(n-1)/2直接写 Θ(n²) 更准确。分析均摊复杂度时比如刚才讲的顺序表动态扩容可以写成“单次操作均摊 O(1)”这里强调的是整体表现上界。3.2 顺序表各操作的复杂度速查顺序表各基本操作的用时是这样分布的操作最好情况平均情况最坏情况说明按下标访问 data[i]O(1)O(1)O(1)随机存取不依赖表长按值查找O(1)O(n)O(n)最好第一个就是目标尾部插入O(1)O(1) 均摊O(n)遇到扩容时需整表复制头部/中间插入O(1)O(n)O(n)后移元素是开销来源头部/中间删除O(1)O(n)O(n)前移元素是开销来源这张表里最值得玩味的是尾部插入。如果只说“尾部插入 O(1)”实际遇到扩容时它单次开销是 O(n) 级的扩容一次搬运 n 个数据。所以严格说法是“均摊 O(1)”。考试里如果题目问“动态扩容表尾插入的平均时间复杂度是多少”答案通常就是均摊 O(1)。这也是为什么很多排序算法归并排序、快速排序在实现时临时数组和数据交换都优先选用顺序表——排序过程中的“随机访问某一位置”和“从尾部追加临时结果”这两个操作顺序表的表现都是最优级别。如果你把排序对象换成链表虽然比较次数不变但访问代价从 O(1) 变成 O(n)整体性能天差地别。4. 完整案例图书信息顺序表管理程序说到这儿理论基础已经够用了。热词里反复出现“图书信息顺序表 c 语言”这基本是数据结构实验报告的经典命题。我用一个完整可运行的 C 程序把顺序表实战一遍存图书信息支持添加、按 ISBN 删除、按书名查找、遍历展示。设计思路图书信息本身不是 int而是一个结构体 Book。顺序表的元素类型要从 int 抽象成“任何你想存的东西”这里就体现出了定义结构体时用指针 元素大小计算的好处——扩容时只需要把 sizeof(int) 改成 sizeof(Book)整体结构不用大改。4.1 数据定义与初始化#include stdio.h #include stdlib.h #include string.h #define INIT_CAP 8 typedef struct { char isbn[20]; // 国际标准书号 char name[64]; // 书名 float price; // 定价 } Book; typedef struct { Book *items; // 存储图书的连续内存 int length; // 馆藏图书数量 int capacity; // 当前存储容量 } BookList; void init_booklist(BookList *list) { list-items (Book *)malloc(INIT_CAP * sizeof(Book)); if (list-items NULL) { printf(初始化失败\n); exit(1); } list-length 0; list-capacity INIT_CAP; } void destroy_booklist(BookList *list) { free(list-items); list-items NULL; list-length 0; list-capacity 0; }注意看这个结构几乎和 int 版顺序表一模一样只是把 int *data 换成了 Book *items。扩容函数里的 sizeof(int) 也必须同步替换成 sizeof(Book)这是新手最容易漏的事后面我会单独展开讲。4.2 核心操作函数// 扩容新容量按 2 倍增长 void ensure_capacity(BookList *list, int extra) { if (list-length extra list-capacity) { return; } int new_cap list-capacity * 2; while (new_cap list-length extra) { new_cap * 2; } Book *new_items (Book *)malloc(new_cap * sizeof(Book)); if (new_items NULL) { printf(扩容失败\n); exit(1); } // 逐个元素拷贝 for (int i 0; i list-length; i) { new_items[i] list-items[i]; } free(list-items); list-items new_items; list-capacity new_cap; } // 尾部添加一本图书 int append_book(BookList *list, Book book) { ensure_capacity(list, 1); list-items[list-length] book; list-length; return 1; } // 按 ISBN 号删除图书 int delete_by_isbn(BookList *list, const char *isbn) { for (int i 0; i list-length; i) { if (strcmp(list-items[i].isbn, isbn) 0) { // 前移覆盖 for (int j i; j list-length - 1; j) { list-items[j] list-items[j 1]; } list-length--; return 1; } } return 0; } // 按书名模糊查找打印所有匹配项 void find_by_name(BookList *list, const char *keyword) { int found 0; for (int i 0; i list-length; i) { if (strstr(list-items[i].name, keyword) ! NULL) { printf(找到图书ISBN%s书名%s价格%.2f\n, list-items[i].isbn, list-items[i].name, list-items[i].price); found 1; } } if (found 0) { printf(没有找到包含%s的书\n, keyword); } } // 展示全部图书 void print_all(BookList *list) { printf(当前馆藏共 %d 本\n, list-length); for (int i 0; i list-length; i) { printf( [%d] %s | %s | %.2f元\n, i, list-items[i].isbn, list-items[i].name, list-items[i].price); } }这里我把删除设计成“按 ISBN 先查再删”实际就是在顺序表里做一次线性查找找到后执行前移覆盖。按书名查找用的 strstr 是子串匹配里面隐含的查找方式和 KMP 算法同一类思路只不过标准库函数更多考虑的是通用性。4.3 主程序实测效果int main() { BookList library; init_booklist(library); append_book(library, (Book){978-7-111-54742-8, 数据结构C语言版, 49.0}); append_book(library, (Book){978-7-121-32790-6, 算法导论, 128.0}); append_book(library, (Book){978-7-115-43651-9, 深入理解计算机系统, 139.0}); append_book(library, (Book){978-7-302-54276-5, 计算机网络自顶向下方法, 89.0}); print_all(library); printf(\n尝试删除 ISBN978-7-121-32790-6 的书\n); delete_by_isbn(library, 978-7-121-32790-6); print_all(library); printf(\n搜索书名包含“数据结构”的图书\n); find_by_name(library, 数据结构); destroy_booklist(library); return 0; }运行结果大致是先把四本书全部打印出来然后删除 ISBN 为 978-7-121-32790-6 的《算法导论》剩下三本最后按书名关键词“数据结构”只能匹配到《数据结构C语言版》。这个 100 来行的程序就是很多学校“图书信息管理系统”实验的雏形。你把这个框架跑通之后往上加“按价格区间筛选”“按书名排序输出”都是很自然的扩展。排序时你用顺序表存数据随便你写冒泡排序还是快速排序直接操作 items[i] 和 items[j] 交换即可不用像链表那样去处理一大堆指针。5. 顺序表使用中的高频翻车现场5.1 七类常见问题与排查思路这些年看下来顺序表写崩的情况几乎都集中在下面几个点上现象可能原因排查思路插入后打印顺序表发现有的元素“凭空消失”元素后移的方向写成从前往后覆盖了还没搬走的元素检查插入循环是不是i length; i pos; i--程序偶尔崩溃但报错位置不在顺序表代码插入前忘记扩容数组越界写坏了相邻内存检查 insert 函数里有没有先调 ensure_capacitylength 一直不对越插越乱插入成功后忘了 length或初始化时把 length 和 capacity 赋反打印 length 和 capacity 中间值逐点核对访问 data[pos] 得到垃圾值pos 超出 length 范围访问了 NULL 或已释放内存访问前先做 pos 合法性检查程序退出时报“munmap_chunk(): invalid pointer”扩容后重复释放旧指针或 free 了非 malloc 地址检查扩容里 free 的只能是旧 data 指针逻辑完全正确但大数据量下特别慢扩容策略写成了每次 1 个元素均摊复杂度接近 O(n²)改成倍增扩容同时观察扩容次数是否爆增从 int 顺序表改存结构体后数据错乱扩容、复制、释放时还在用 sizeof(int)没有换成 sizeof(Book)搜索代码里所有 sizeof 的调用逐一替换前面几条比较常见我想详细说最后一条这是我在实际项目里踩过最隐蔽的坑。当时我写了一个通用的顺序表里面全是 int 操作。后来系统要存一组坐标点我顺手把int *data改成了Point *data但扩容函数里 malloc 的地方没改还是sizeof(int)。结果就是逻辑上我申请了 capacity 个 int 大小的空间实际我却往里塞 Point 结构体每个 Point 占的空间比 int 大capacity 才存到一半就已经写穿边界了。这种 bug 非常难查因为它在小数据量下恰好不崩要等数据量变大才爆。排查技巧是直接在扩容函数入口处打印 sizeof(元素类型) 和 malloc 的总字节数再对比最终分配的 capacity 是否匹配。字节数不匹配九成就是这个类型魔法的锅。写代码的时候把malloc(new_cap * sizeof(类型))里的 sizeof 当成一个不可跳过的“强制检查点”每次改类型必查。5.2 关于位置约定写代码前先定好“下标还是位序”还有一个反复出现的问题是关于位置的说法。很多参考书喜欢说“在第 i 个位置插入”这里的 i 是逻辑位序从 1 开始而 C 语言数组下标从 0 开始。这俩一旦混用程序写出来错得莫名其妙。我写顺序表代码时的统一约定是所有函数的 pos 参数都表示从 0 开始的下标。逻辑位序和数组下标的关系是“逻辑位序 下标 1”。函数注释里必须写清楚“pos 从 0 开始”调用时也保持同一个口径。这样虽然要多写一行注释但至少不会在接盘别人代码时对不上号。如果考试或实验报告里老师用的是位序我建议在函数内部加一步转换或者干脆在说明文档里明确写“本程序所有位置参数均为数组下标”。先定约定再动手写代码比写完再痛苦地排查哪个位置差了 1 要舒服得多。6. 我的个人体会顺序表这块内容说难不难但想真正写稳需要你把每个函数的边界条件都想清楚。我个人的学习路径是第一遍照着示例代码敲跑通就行第二遍合上书本在空白编辑器里自己从结构体定义开始写到完整操作跑出同样结果第三遍把它从 int 扩展到 Book 这种自定义结构体再扩展到支持扩容后不泄漏内存。三遍下来后面学链表和栈队列会顺畅非常多。你要是想再往下扩展可以把顺序表改成循环队列的底层结构或者给图书信息程序加上按书名排序的功能排序算法用快速排序感受一下“随机存取”在排序里的威力。这些实验做完你对顺序表价值的理解就不再停留在“数组的包装”这个层面了。 
长河君 · 2026/9/28 13:08:25 · 阅读 1.2k 顺序表完全指南：底层原理、核心操作与C语言实现
数据结构这门课很多人碰到的第一道坎不是指针也不是递归而是顺序表。可能有人会觉得顺序表不就是数组吗有什么好讲的。我以前也这么想直到自己动手写了个图书信息管理的小系统数组越界后整个程序的数据稀里糊涂“变脏”排查了一整个晚上才定位到问题——根子就在我没有真正搞懂顺序表的 length、capacity 和存储空间三者的关系。顺序表之所以值得单独拆出来消化是因为后面你要学的查找、排序、KMP 算法、归并排序底层几乎都依赖一个逻辑清晰、操作正确的线性结构来装数据顺序表就是这个结构的起点。这篇文章我打算把顺序表掰开揉碎地讲一遍从它和普通数组的差别到初始化、扩容、插入、删除、按值查找这些基本操作再到复杂度分析里很多人栽跟头的 O、Ω、θ 符号最后用一个图书信息顺序表管理的完整 C 语言示例收尾。内容适合刚上数据结构课的同学、准备 408 统考的考研党以及那些平时写业务代码但没系统补过数据结构的非科班朋友。1. 先把顺序表这张图在脑子里画清楚1.1 从数组到顺序表多出来的两个字段到底在管什么数组是编程语言天然自带的容器声明完 int a[100]编译器就给你划一块连续内存下标访问简单粗暴。但数组有个天生的毛病它不知道数组里到底有几个元素是“有效”的。你塞了 3 个数据进去和塞了 80 个数据进去a 这个数组本身不会给你任何提示只有你自己心里清楚。顺序表在数组之上做了一层封装它把“数组容量”和“当前有效元素个数”分离成两个字段。用 C 语言来定义通常长这样#define INIT_CAPACITY 10 typedef struct { int *data; // 指向连续内存的指针 int length; // 当前已存储的元素个数 int capacity; // 当前内存最多能容纳的元素个数 } SeqList;这里最关键的一句话数组大小是物理容量顺序表的 length 是逻辑长度。capacity 告诉你这片内存最多装多少length 告诉你现在实际装了多少。为什么非要多一个 capacity因为顺序表的精髓在于“动态”它不能像 int a[100] 一样把容量焊死在代码里。你预先不知道用户会往里塞多少数据所以需要 capacity 来跟踪当前分配的内存大小当 length 逼近 capacity 时就知道该扩容了。用个生活类比这就像电影院的一排座位。座位总数是 capacity已经入座的人数是 length。座位数和人数必须分开记否则你数人头的时候根本不知道这一排还空着几个座也不知道下一批观众进场时要不要加开一排。1.2 为什么顺序表这么重要而不被链表替代你可能会问同样能存一组数据链表不是也能做到吗为什么排序算法、KMP 算法背后的存储结构默认都是顺序表而不是链表答案就四个字随机存取。顺序表的内存是连续的data[i] 的访问直接通过“基地址 i × 元素大小”计算偏移时间复杂度是 O(1)。这个能力太要命了。二分查找要在每一步直接跳到中位元素快速排序要频繁交换任意两个位置的元素KMP 算法要按 next 数组回溯到指定下标——这些算法如果放在链表上访问第 i 个节点得先从头指针走 i 步一趟 O(n)算法复杂度直接整体上一个台阶很多优美性质全没了。顺序表还有一个常被忽略的优势缓存局部性好。连续内存的元素被 CPU 加载进高速缓存时是一块一块拉进来的。你遍历前几个元素的时候后续元素大概率已经躺在缓存里了。链表节点散落在堆里每次访问都大概率要重新命中缓存数据量一大性能差距非常明显。当然顺序表不是万能的。它在头部或中间插入、删除时为了保持元素的连续性必须整体搬移一批元素这是它最大的软肋。所以实用的建议是游戏排行榜这类“查得多、改得少、偶尔在尾部追加”的场景首选顺序表文本编辑器这类需要在任意位置频繁插入删除的场景顺序表就非常痛苦得考虑链表或者其他结构。这俩不是谁取代谁是互补关系你心里得有这张图。2. 顺序表核心操作一行行拆给你看2.1 结构体定义、初始化和销毁先给出一个基本的初始化函数。注意一个原则只要函数内部会修改顺序表的状态就必须传指向 SeqList 的指针否则你在函数里改了 length外面完全感知不到。传值操作只能“望梅止渴”。void init_seqlist(SeqList *list) { list-data (int *)malloc(INIT_CAPACITY * sizeof(int)); if (list-data NULL) { printf(初始化失败内存分配失败\n); exit(1); } list-length 0; list-capacity INIT_CAPACITY; }malloc 返回的指针必须判空这是很多新手容易忽略的事。嵌入式和物联网场景里内存本来就紧张分配失败是常态不判空直接往 NULL 里写数据轻则崩溃重则静默污染内存。初始化完 length 置 0capacity 置 10这两个谁写反了后面所有操作全乱。对应的销毁函数也要养成配套写的习惯。C 语言里 malloc 和 free 是一对写一个带 malloc 的结构体就一定要写一个对应的 free 入口void destroy_seqlist(SeqList *list) { if (list-data ! NULL) { free(list-data); list-data NULL; } list-length 0; list-capacity 0; }2.2 扩容你最不希望触发、但必须先写对的函数扩容是顺序表里最容易写错、也最考验功底的一个环节。触发条件很简单当 length 快要等于 capacity 时再插入新元素就没地方放了。扩容的策略是重新分配一块更大的内存把旧数据搬过去再释放旧内存。void ensure_capacity(SeqList *list, int extra) { // extra 表示接下来至少要新增加几个元素 if (list-length extra list-capacity) { return; } int new_capacity list-capacity 0 ? 1 : list-capacity * 2; while (new_capacity list-length extra) { new_capacity * 2; } int *new_data (int *)malloc(new_capacity * sizeof(int)); if (new_data NULL) { printf(扩容失败\n); exit(1); } // 把旧数据逐个复制过去 for (int i 0; i list-length; i) { new_data[i] list-data[i]; } free(list-data); list-data new_data; list-capacity new_capacity; }为什么要选择乘 2 扩容而不是每次多申请一个位置这是一个均摊分析的问题。如果一趟插入一个位置连续插入 n 次每次都要搬运已有的全部数据总复杂度是 1 2 3 ... n O(n²)数据量大一点直接卡死。而扩容成 2 倍容量到 n 时需要扩容的次数是 log₂n 级别每轮扩容的总搬运量加起来才 2n 左右均摊到每次插入是 O(1)。这就是数据结构里经典“均摊复杂度”的实战意义。有一点必须提醒你扩容之后list-data 指向的是全新的内存地址。如果你在别处偷偷保存了旧的 data 指针继续用那拿到的全是已经释放的野内存这是最常见的内存 bug 来源之一。正确做法是永远通过 list-data 去访问元素不要另存副本。2.3 三个插入函数的边界条件插入是顺序表里最需要细心的地方。我给出一套完整实现把尾插、中间插、头插统一到一个函数里。// 在逻辑位序 pos 处插入元素 valpos 从 0 开始 int insert_seqlist(SeqList *list, int pos, int val) { if (pos 0 || pos list-length) { printf(插入位置非法\n); return 0; } ensure_capacity(list, 1); // 从后往前搬迁给 pos 腾出位置 for (int i list-length; i pos; i--) { list-data[i] list-data[i - 1]; } list-data[pos] val; list-length; return 1; } // 尾部插入 int append_seqlist(SeqList *list, int val) { return insert_seqlist(list, list-length, val); } // 头部插入 int push_front_seqlist(SeqList *list, int val) { return insert_seqlist(list, 0, val); }位置校验这里非常容易出错。很多人会把判断写成 pos list-length这其实是错的。在逻辑位序 pos 处插入意味着新元素可以插到当前最后一个元素的后面也就是 pos length 的位置所以合法范围是 0 到 length 闭区间。元素后移的方向必须从后往前。你要是写成从前往后第一次搬迁就把后面元素覆盖了整个数组直接丢数据。边界上还有一个细节如果原来的长度是 length插入后最大的下标是 length所以扩容必须保证 capacity 至少是 length 1ensure_capacity 的参数传 1 就是这个道理。2.4 删除、按值查找、修改删除是插入的逆操作但方向反过来了要从前往后搬。删除第 pos 个元素后后面的元素要统一往前移动一位最后一个有效位置变成“废弃值”但逻辑上已经被移出表了。int delete_seqlist(SeqList *list, int pos) { if (pos 0 || pos list-length) { printf(删除位置非法\n); return 0; } int deleted list-data[pos]; for (int i pos; i list-length - 1; i) { list-data[i] list-data[i 1]; } list-length--; return deleted; } // 按下标查找 int get_seqlist(SeqList *list, int pos) { if (pos 0 || pos list-length) { printf(访问越界\n); return -1; } return list-data[pos]; } // 按值查找返回第一个匹配元素的下标 int find_seqlist(SeqList *list, int val) { for (int i 0; i list-length; i) { if (list-data[i] val) { return i; } } return -1; }删除时我有一个个人习惯把被删元素的值作为返回值返回出来。这样调用者既能确认删除是否成功又能拿到被删的数据比如排行榜上一个玩家下线了系统总要记录他的积分再移除。如果返回值只有 0 和 1被删的数据就白白在内存里丢了。另外注意删除元素后我没有立刻缩容。容量大一点并不是坏事因为之后再插入数据就免去了扩容开销。除非你的顺序表长时间处于长尾低占用状态否则不建议写 shrink 逻辑。频繁缩容又扩容会造成内存抖动反而比留着空间更伤性能。3. 复杂度分析O 和 θ 到底什么时候用3.1 三种渐进符号的差别学习数据结构一定会碰到复杂度符号很多人在这里被卡住“明明题目里写的是 O(n²)为什么老师又说这个算法实际上是 Θ(n²)”其实这三个符号的区别非常直观O(f(n))表示算法的运行时间不会超过 f(n) 的某个常数倍相当于给出时间上界。最坏情况的复杂度用 O 表达最合适。Ω(f(n))表示算法的运行时间至少是 f(n) 的某个常数倍相当于给出时间下界。最好情况或最优输入的分析适合用 Ω。Θ(f(n))表示运行时间既不超过也不低于 f(n) 的常数倍上下界重合在一起这是最精确的描述。举个例子在顺序表里做顺序查找从第一个元素开始逐个比对。最好情况第一个元素就是要找的目标只比较 1 次所以是 Ω(1)。最坏情况目标在最后一个位置或不存在要比较 n 次所以是 O(n)。平均情况假设每个位置被查找的概率相同成功查找的平均比较次数约等于 (n1)/2也就是线性级别此时可以说这个操作是 Θ(n) 的。如果你只说“顺序查找的时间复杂度是 O(n)”这没有错但它丢掉了“平均也是线性”这个更精确的信息如果你直接用 Θ(n)意思是无论最好、平均还是最坏它都会退化到线性级复杂度这个说法其实更贴切。那什么时候写 O、什么时候写 Θ我自己的经验是三条在课程作业和考试里如果没有特殊说明默认考察“最坏情况”就用 O这是最普遍的表达习惯。如果算法的最好情况和最坏情况复杂度相同比如普通嵌套双循环的冒泡排序无论什么输入比较次数都是 n(n-1)/2直接写 Θ(n²) 更准确。分析均摊复杂度时比如刚才讲的顺序表动态扩容可以写成“单次操作均摊 O(1)”这里强调的是整体表现上界。3.2 顺序表各操作的复杂度速查顺序表各基本操作的用时是这样分布的操作最好情况平均情况最坏情况说明按下标访问 data[i]O(1)O(1)O(1)随机存取不依赖表长按值查找O(1)O(n)O(n)最好第一个就是目标尾部插入O(1)O(1) 均摊O(n)遇到扩容时需整表复制头部/中间插入O(1)O(n)O(n)后移元素是开销来源头部/中间删除O(1)O(n)O(n)前移元素是开销来源这张表里最值得玩味的是尾部插入。如果只说“尾部插入 O(1)”实际遇到扩容时它单次开销是 O(n) 级的扩容一次搬运 n 个数据。所以严格说法是“均摊 O(1)”。考试里如果题目问“动态扩容表尾插入的平均时间复杂度是多少”答案通常就是均摊 O(1)。这也是为什么很多排序算法归并排序、快速排序在实现时临时数组和数据交换都优先选用顺序表——排序过程中的“随机访问某一位置”和“从尾部追加临时结果”这两个操作顺序表的表现都是最优级别。如果你把排序对象换成链表虽然比较次数不变但访问代价从 O(1) 变成 O(n)整体性能天差地别。4. 完整案例图书信息顺序表管理程序说到这儿理论基础已经够用了。热词里反复出现“图书信息顺序表 c 语言”这基本是数据结构实验报告的经典命题。我用一个完整可运行的 C 程序把顺序表实战一遍存图书信息支持添加、按 ISBN 删除、按书名查找、遍历展示。设计思路图书信息本身不是 int而是一个结构体 Book。顺序表的元素类型要从 int 抽象成“任何你想存的东西”这里就体现出了定义结构体时用指针 元素大小计算的好处——扩容时只需要把 sizeof(int) 改成 sizeof(Book)整体结构不用大改。4.1 数据定义与初始化#include stdio.h #include stdlib.h #include string.h #define INIT_CAP 8 typedef struct { char isbn[20]; // 国际标准书号 char name[64]; // 书名 float price; // 定价 } Book; typedef struct { Book *items; // 存储图书的连续内存 int length; // 馆藏图书数量 int capacity; // 当前存储容量 } BookList; void init_booklist(BookList *list) { list-items (Book *)malloc(INIT_CAP * sizeof(Book)); if (list-items NULL) { printf(初始化失败\n); exit(1); } list-length 0; list-capacity INIT_CAP; } void destroy_booklist(BookList *list) { free(list-items); list-items NULL; list-length 0; list-capacity 0; }注意看这个结构几乎和 int 版顺序表一模一样只是把 int *data 换成了 Book *items。扩容函数里的 sizeof(int) 也必须同步替换成 sizeof(Book)这是新手最容易漏的事后面我会单独展开讲。4.2 核心操作函数// 扩容新容量按 2 倍增长 void ensure_capacity(BookList *list, int extra) { if (list-length extra list-capacity) { return; } int new_cap list-capacity * 2; while (new_cap list-length extra) { new_cap * 2; } Book *new_items (Book *)malloc(new_cap * sizeof(Book)); if (new_items NULL) { printf(扩容失败\n); exit(1); } // 逐个元素拷贝 for (int i 0; i list-length; i) { new_items[i] list-items[i]; } free(list-items); list-items new_items; list-capacity new_cap; } // 尾部添加一本图书 int append_book(BookList *list, Book book) { ensure_capacity(list, 1); list-items[list-length] book; list-length; return 1; } // 按 ISBN 号删除图书 int delete_by_isbn(BookList *list, const char *isbn) { for (int i 0; i list-length; i) { if (strcmp(list-items[i].isbn, isbn) 0) { // 前移覆盖 for (int j i; j list-length - 1; j) { list-items[j] list-items[j 1]; } list-length--; return 1; } } return 0; } // 按书名模糊查找打印所有匹配项 void find_by_name(BookList *list, const char *keyword) { int found 0; for (int i 0; i list-length; i) { if (strstr(list-items[i].name, keyword) ! NULL) { printf(找到图书ISBN%s书名%s价格%.2f\n, list-items[i].isbn, list-items[i].name, list-items[i].price); found 1; } } if (found 0) { printf(没有找到包含%s的书\n, keyword); } } // 展示全部图书 void print_all(BookList *list) { printf(当前馆藏共 %d 本\n, list-length); for (int i 0; i list-length; i) { printf( [%d] %s | %s | %.2f元\n, i, list-items[i].isbn, list-items[i].name, list-items[i].price); } }这里我把删除设计成“按 ISBN 先查再删”实际就是在顺序表里做一次线性查找找到后执行前移覆盖。按书名查找用的 strstr 是子串匹配里面隐含的查找方式和 KMP 算法同一类思路只不过标准库函数更多考虑的是通用性。4.3 主程序实测效果int main() { BookList library; init_booklist(library); append_book(library, (Book){978-7-111-54742-8, 数据结构C语言版, 49.0}); append_book(library, (Book){978-7-121-32790-6, 算法导论, 128.0}); append_book(library, (Book){978-7-115-43651-9, 深入理解计算机系统, 139.0}); append_book(library, (Book){978-7-302-54276-5, 计算机网络自顶向下方法, 89.0}); print_all(library); printf(\n尝试删除 ISBN978-7-121-32790-6 的书\n); delete_by_isbn(library, 978-7-121-32790-6); print_all(library); printf(\n搜索书名包含“数据结构”的图书\n); find_by_name(library, 数据结构); destroy_booklist(library); return 0; }运行结果大致是先把四本书全部打印出来然后删除 ISBN 为 978-7-121-32790-6 的《算法导论》剩下三本最后按书名关键词“数据结构”只能匹配到《数据结构C语言版》。这个 100 来行的程序就是很多学校“图书信息管理系统”实验的雏形。你把这个框架跑通之后往上加“按价格区间筛选”“按书名排序输出”都是很自然的扩展。排序时你用顺序表存数据随便你写冒泡排序还是快速排序直接操作 items[i] 和 items[j] 交换即可不用像链表那样去处理一大堆指针。5. 顺序表使用中的高频翻车现场5.1 七类常见问题与排查思路这些年看下来顺序表写崩的情况几乎都集中在下面几个点上现象可能原因排查思路插入后打印顺序表发现有的元素“凭空消失”元素后移的方向写成从前往后覆盖了还没搬走的元素检查插入循环是不是i length; i pos; i--程序偶尔崩溃但报错位置不在顺序表代码插入前忘记扩容数组越界写坏了相邻内存检查 insert 函数里有没有先调 ensure_capacitylength 一直不对越插越乱插入成功后忘了 length或初始化时把 length 和 capacity 赋反打印 length 和 capacity 中间值逐点核对访问 data[pos] 得到垃圾值pos 超出 length 范围访问了 NULL 或已释放内存访问前先做 pos 合法性检查程序退出时报“munmap_chunk(): invalid pointer”扩容后重复释放旧指针或 free 了非 malloc 地址检查扩容里 free 的只能是旧 data 指针逻辑完全正确但大数据量下特别慢扩容策略写成了每次 1 个元素均摊复杂度接近 O(n²)改成倍增扩容同时观察扩容次数是否爆增从 int 顺序表改存结构体后数据错乱扩容、复制、释放时还在用 sizeof(int)没有换成 sizeof(Book)搜索代码里所有 sizeof 的调用逐一替换前面几条比较常见我想详细说最后一条这是我在实际项目里踩过最隐蔽的坑。当时我写了一个通用的顺序表里面全是 int 操作。后来系统要存一组坐标点我顺手把int *data改成了Point *data但扩容函数里 malloc 的地方没改还是sizeof(int)。结果就是逻辑上我申请了 capacity 个 int 大小的空间实际我却往里塞 Point 结构体每个 Point 占的空间比 int 大capacity 才存到一半就已经写穿边界了。这种 bug 非常难查因为它在小数据量下恰好不崩要等数据量变大才爆。排查技巧是直接在扩容函数入口处打印 sizeof(元素类型) 和 malloc 的总字节数再对比最终分配的 capacity 是否匹配。字节数不匹配九成就是这个类型魔法的锅。写代码的时候把malloc(new_cap * sizeof(类型))里的 sizeof 当成一个不可跳过的“强制检查点”每次改类型必查。5.2 关于位置约定写代码前先定好“下标还是位序”还有一个反复出现的问题是关于位置的说法。很多参考书喜欢说“在第 i 个位置插入”这里的 i 是逻辑位序从 1 开始而 C 语言数组下标从 0 开始。这俩一旦混用程序写出来错得莫名其妙。我写顺序表代码时的统一约定是所有函数的 pos 参数都表示从 0 开始的下标。逻辑位序和数组下标的关系是“逻辑位序 下标 1”。函数注释里必须写清楚“pos 从 0 开始”调用时也保持同一个口径。这样虽然要多写一行注释但至少不会在接盘别人代码时对不上号。如果考试或实验报告里老师用的是位序我建议在函数内部加一步转换或者干脆在说明文档里明确写“本程序所有位置参数均为数组下标”。先定约定再动手写代码比写完再痛苦地排查哪个位置差了 1 要舒服得多。6. 我的个人体会顺序表这块内容说难不难但想真正写稳需要你把每个函数的边界条件都想清楚。我个人的学习路径是第一遍照着示例代码敲跑通就行第二遍合上书本在空白编辑器里自己从结构体定义开始写到完整操作跑出同样结果第三遍把它从 int 扩展到 Book 这种自定义结构体再扩展到支持扩容后不泄漏内存。三遍下来后面学链表和栈队列会顺畅非常多。你要是想再往下扩展可以把顺序表改成循环队列的底层结构或者给图书信息程序加上按书名排序的功能排序算法用快速排序感受一下“随机存取”在排序里的威力。这些实验做完你对顺序表价值的理解就不再停留在“数组的包装”这个层面了。