在数据结构这门课里顺序表往往是第一道要认真啃的坎。很多同学一开始觉得它“不就是个数组嘛”可真到写代码的时候才发现插入一个元素要想着从哪边开始挪删除一个元素又得琢磨下标会不会越界更别提什么时候扩容、什么时候释放内存这些细节。我当年写顺序表调试到半夜最后发现只是把i pos写成了i pos那种感觉至今记得。这篇“顺序表专题1”就是想把这些坑一次性讲透。我会从顺序表的设计思路讲起把C语言实现的核心操作初始化、插入、删除、查找、扩容逐一拆开再用教材里最常见的“图书信息管理”场景串一遍最后也聊聊Java的ArrayList和C的vector底层是怎么干这件事的。适合刚学数据结构的学生、正在准备面试的求职者以及所有想把线性表基础打牢的人。内容以C语言为主但思路对任何语言都通用。1. 顺序表到底在解决什么问题1.1 从“教室座位”说起线性关系怎么存想象一个教室里的座位一排连着一排每个座位有固定编号学生按编号坐好。如果老师想找第15号座位上的同学直接看座位号走过去就行不需要从头数。如果想让一个新同学插到第8个位置那第8个位置原来的同学和后面所有同学都得往后挪一个位置。这就是顺序表最直观的模型。顺序表解决的核心问题是把具有“前后关系”的一组数据按照逻辑上的线性顺序存放在一块连续的内存区域里。逻辑上每个元素有唯一的前驱和唯一的后继头元素无前驱尾元素无后继物理上它们在内存中是一个挨着一个的地址连续空间。这种“逻辑结构”和“存储结构”的对应关系是理解后面所有操作的基础。之所以叫“顺序表”而不是直接叫“数组”是因为它比裸数组多了一层抽象——我们维护了当前元素个数的信息并封装了插入、删除、查找等操作。数组只是存储工具顺序表是建立在数组之上的数据结构。1.2 连续内存带来的优势和代价顺序表最大的优势是随机访问。因为元素地址连续第i个元素的地址可以靠公式直接算出来地址 起始地址 i × 单个元素大小。所以按下标访问任意元素的时间复杂度是O(1)这是链表做不到的。编程里常用的“按下标查值”“按位置改值”顺序表几乎是零成本。还有一个很多人忽略的优势CPU缓存友好。连续的内存和顺序的遍历方式能让CPU预取缓存命中率很高。在数据量不算特别夸张的时候顺序表遍历的速度往往比链表快很多因为链表节点分散在内存各处每访问一个节点大概率都要重新从主存拉数据。代价也很明显插入和删除需要批量移动元素平均时间复杂度是O(n)而且连续空间要求一次性分配一块足够大的内存不够灵活。如果频繁在头部插入顺序表会很吃亏这时候链表更合适。两者之间的关系不是“谁取代谁”而是看使用场景。1.3 静态数组 vs 动态顺序表教材里经常先讲静态顺序表——用固定大小的数组存储比如int data[100]。缺点是容量写死数据多了放不下数据少了浪费空间。实际工程里很少用静态的更通用的是动态顺序表用一个指针指向堆上分配的内存容量不够时自动扩容。这就引出两个核心概念length当前元素个数和capacity当前容量。length表示表里实际有多少元素capacity表示当前分配的内存最多能装多少。只要length capacity就可以继续往里加元素一旦length capacity就要先扩容再插入。这两个字段的区别特别重要下面所有操作都离不开它们。2. C语言版顺序表结构体设计背后的门道2.1 三个字段撑起一张能长大的表C语言没有类没有模板最正统的做法是用结构体把顺序表“封装”起来typedef struct { int *data; // 指向堆上连续内存的指针 int length; // 当前元素个数 int capacity; // 当前容量 } SeqList;data指向用malloc申请来的一块连续内存length和capacity分别记录逻辑长度和物理容量。为什么非要用结构体而不是直接定义全局数组因为结构体把数据和控制信息打包在一起各种函数只需要传一个SeqList*指针就能操作整张表代码可读性、可维护性都更高也方便同时创建多张独立的表。2.2 初始化把表“唤醒”成一个空表初始化要做的三件事给data申请初始容量大小的内存、把length设为0、把capacity设为初始容量。void initSeqList(SeqList *list, int initCapacity) { list-data (int *)malloc(sizeof(int) * initCapacity); if (list-data NULL) { printf(内存分配失败\n); exit(1); } list-length 0; list-capacity initCapacity; }注意判断malloc返回值是否为NULL这步千万别省。教材里经常为了排版省略判空但实际工程中内存分配失败是真实存在的。养成判空的习惯能避免很多难以排查的崩溃。初始化容量取多少我习惯取一个接近实际需要的预估值。比如知道大概要存几百个数据就直接初始化成200完全没概念可以初始化成4或8让扩容机制去兜底。初始化得太大浪费太小频繁扩容有性能损耗。这不是玄学是权衡。2.3 销毁让内存“有借有还”申请到堆上的内存用完必须释放否则就是内存泄漏。销毁顺序表很简单void destroySeqList(SeqList *list) { if (list-data ! NULL) { free(list-data); list-data NULL; // 置空防止出现野指针 } list-length 0; list-capacity 0; }free之后把data置为NULL这一步非常关键。如果不置空data就成了一个悬空指针后续如果不小心再次free会导致“重复释放”错误或者在其他地方误访问这块已回收的内存产生难以定位的bug。很多老手在代码审查时看到free后面不置NULL都会直接打回。3. 基本操作实现插入删除才是顺序表的分水岭3.1 插入操作的三步走顺序表里最核心、最容易写错的就是插入。做一个插入操作逻辑上分三步检查插入位置是否合法pos必须在0到length之间包括等于length表示在表尾追加。检查容量是否足够不够则先扩容。从最后一个元素开始把元素依次往后挪一个位置腾出下标为pos的空位然后写入新元素length。对应代码int insertElem(SeqList *list, int pos, int val) { // 位置校验 if (pos 0 || pos list-length) { printf(插入位置非法\n); return 0; } // 容量校验满了先扩容 if (list-length list-capacity) { expandSeqList(list); } // 从后往前挪直到把 data[pos] 空出来 for (int i list-length; i pos; i--) { list-data[i] list-data[i - 1]; } list-data[pos] val; list-length; return 1; }为什么要从后往前挪想象一排人站在格子线上现在要在第3格插入一个人。如果从前往后挪第3格的人先挪到第4格结果第4格原本的人还没动就把他覆盖了。正确的做法是从最后一个人开始先往后挪一步腾出空位再往前一个重复操作直到第3格原来的元素也被挪走。这个“从后往前”是插入操作的灵魂写反了数据就乱了。位置校验为什么是pos list-length而不是pos list-capacity因为插入位置是逻辑位置只要不超过当前元素个数元素之间就能容得下新元素。如果pos length意味着插到末尾这是合法的如果pos length中间空着若干下标逻辑上就破坏了线性表的“连续无空位”性质所以是非法的。3.2 删除操作反方向的移动删除操作是把后面的元素依次往前挪覆盖掉被删除元素的位置。方向与插入正好相反——从前往后挪。int deleteElem(SeqList *list, int pos) { if (pos 0 || pos list-length) { printf(删除位置非法\n); return 0; } for (int i pos; i list-length - 1; i) { list-data[i] list-data[i 1]; } list-length--; return 1; }注意循环边界是i list-length - 1因为最后一个元素不需要再往后面挪了直接把length--就算“删除”了。被挪走元素的旧位置里的值成了“垃圾数据”下次插入新元素时会被覆盖没关系。细心的同学可能会说删除后容量没缩小浪费空间怎么办两全其美的办法是先只length--当length远小于capacity时再缩容。缩容的时机和阈值要根据场景定不建议删除一个元素就缩一次频繁malloc/free的代价远比那点内存空间贵。3.3 查找按位置和按值是两回事按下标查找很简单判断下标合法后直接返回data[pos]时间复杂度O(1)。按值查找要遍历。找到第一个值匹配的元素返回它的下标找不到返回-1。int findElem(SeqList *list, int val) { for (int i 0; i list-length; i) { if (list-data[i] val) { return i; } } return -1; }按值查找的时间复杂度是O(n)因为最坏情况要全部看一遍。顺序表这里有个小优化空间如果数据有规律比如有序可以用二分查找把复杂度降到O(log n)。但要注意二分查找的前提是数据有序如果插入删除很频繁维护有序性的成本可能比查找省下来的时间还多。3.4 扩容动态顺序表的“第二次生命”expandSeqList是整个动态顺序表的引擎。最经典的做法是容量翻倍void expandSeqList(SeqList *list) { int newCapacity list-capacity * 2; int *newData (int *)malloc(sizeof(int) * newCapacity); if (newData NULL) { printf(扩容失败\n); exit(1); } // 把旧数据拷贝到新内存 for (int i 0; i list-length; i) { newData[i] list-data[i]; } free(list-data); list-data newData; list-capacity newCapacity; }为什么扩容要翻倍而不是只加一假设要从容量N扩到N1每插入一个元素都触发一次扩容每次扩容都要把旧数据全部拷贝一遍总代价是O(n²)级别的。翻倍扩容时扩容操作发生的频率越来越低分摊下来每个插入操作的均摊代价是O(1)。在C里还可以用realloc简化操作有些情况下realloc可以在原地扩展省去数据拷贝的开销但注意realloc也可能失败返回NULL时原来的指针不会被释放直接赋值会丢掉原指针导致内存泄漏。稳妥的写法是先存到临时变量判断成功后再赋值。扩容倍数也不是越大越好。翻倍是最常见的做法Java的ArrayList扩容约1.5倍C的vector在GCC和MSVC下也是2倍。倍数太大会浪费内存倍数太小扩容过于频繁。2倍是一个工程上验证过合理的选择。4. 图书信息顺序表把理论塞进一个场景4.1 为什么教材都爱拿“图书信息”当案例“图书信息顺序表”几乎是每个学校C语言/数据结构课程的标配实验题。原因很简单图书信息天然适合线性表建模。每本书有编号ISBN、书名、作者、价格多个字段但整体是一个一个排好序的列表插入一本新书、删除下架的书、按编号查书、遍历显示在馆图书对应顺序表的插入、删除、查询、遍历操作。用一个贴近生活的场景比“int数组”更容易理解这些操作的实际用途。4.2 完整示例图书表的增删改查先定义一个图书结构体再定义一个“图书顺序表”结构体#include stdio.h #include stdlib.h #include string.h typedef struct { char isbn[20]; char title[100]; char author[50]; float price; } Book; typedef struct { Book *data; // 注意这里不再是 int *而是 Book * int length; int capacity; } BookSeqList;初始化、扩容、销毁的逻辑和int版本完全一样只是数据类型从int换成Book。这也体现出用结构体封装的好处数据类型变了控制逻辑不需要重写。插入一本新书按位置插入int insertBook(BookSeqList *list, int pos, Book book) { if (pos 0 || pos list-length) return 0; if (list-length list-capacity) { expandBookSeqList(list); } for (int i list-length; i pos; i--) { list-data[i] list-data[i - 1]; // 结构体整体赋值 } list-data[pos] book; list-length; return 1; }删除下架一本书int deleteBookByIsbn(BookSeqList *list, const char *isbn) { for (int i 0; i list-length; i) { if (strcmp(list-data[i].isbn, isbn) 0) { // 从 i 开始向前挪 for (int j i; j list-length - 1; j) { list-data[j] list-data[j 1]; } list-length--; return 1; } } return 0; }按位置修改一本图书的信息int updateBook(BookSeqList *list, int pos, Book newInfo) { if (pos 0 || pos list-length) return 0; list-data[pos] newInfo; return 1; }这里有个细节值得注意结构体可以直接整体赋值。list-data[i] list-data[i - 1]这一行实际上是把一本书的所有字段isbn、title、author、price整体复制到了相邻位置。C语言里结构体的赋值是逐成员拷贝的这对我们自己写的简单结构体完全够用。但如果结构体里有指针字段比如将来改成动态分配的书名字符串那浅拷贝就会出问题——两个元素会指向同一块内存释放时出现双重释放。改代码的时候要特别小心这个点。4.3 把眼光放宽Java ArrayList 和 C vector 也在做同一件事学C语言的顺序表不只是为了交实验报告。当你切到Java写ArrayList或者切到C用vector本质上都在操作同一个东西——动态数组。ArrayList底层就是一个Object[]数组也有size和容量概念满了自动扩容扩容系数大约是1.5倍旧版本是int newCapacity oldCapacity (oldCapacity 1)。vector则通过std::allocator管理内存GCC下的实践是容量不够时翻倍增长。有时间的话可以去看一眼ArrayList的add(int index, E element)源码你会发现它做的也是“System.arraycopy 后移元素 赋值 size”和C语言版的思路一模一样。理解了这个底层逻辑面试官问你“ArrayList为什么插入慢、查询快”的时候你就知道该往连续内存和批量移动上回答了。顺带提一个热词里的误区“C运算符优先级顺序表”其实跟数据结构里的顺序表不是同一个东西。前者是编译原理/表达式求值里用来表示运算符优先级级别的对照表比如*优先级高于、高于||这些规则而数据结构里的顺序表是一种存储结构。两个词碰巧都带“顺序表”容易在搜索引擎里混在一起。写代码的时候如果看到“顺序表”三个字先分清是在说数据结构还是在说运算符优先级不然容易一头雾水。5. 写顺序表最容易翻车的5个位置5.1 数组越界插入位置等于容量不是等于长度最容易翻车的细节是混淆length和capacity。比如插入时判断条件写成if (list-length list-capacity)没问题但如果写成了if (list-length 100)这种硬编码容量一变就会出问题。更隐蔽的是插入位置校验写成pos list-capacity看起来“多留了点空间”实际在pos length但pos capacity时合法pos length时会出现空洞破坏了顺序表“连续存满”的不变量。排查数组越界有个土办法在每次插入、删除操作前后打一个断言检查length是否满足0 length capacity。一旦出现length capacity说明某次扩容或删除时逻辑没跟上。5.2 移动方向错乱一步错步步错插入时从前往后挪会把后面的元素覆盖删除时从后往前挪会把前面的元素覆盖。我见过很多同学把这两个方向搞反最典型的症状是插入后输出发现插入点后面的数据全变成了同一个值。记住一个简单的记忆方法插入要“先动尾巴”删除要“先动头”。插入是从最后一个元素开始依次后移删除是从被删元素的下一个开始依次前移。5.3 传参结构体是传值还是传指针C语言里函数传结构体有两种方式传值和传指针。如果写void deleteElem(SeqList list, int pos)在函数里改list.length--改的只是形参的副本不会作用到原结构体上。这就是为什么所有会修改表结构的函数都得传SeqList *list。只读操作比如按值查找、遍历打印传值勉强可以但会多一次结构体拷贝的开销所以统一传指针是最省心的做法。提示如果传指针进去还会导致函数通不过编译多半是结构体类型定义写错了。先检查typedef struct {...} SeqList;后面有没有分号再检查函数声明和定义是否一致。这是C语言新手最容易犯的语法错误没有之一。5.4 扩容后忘记更新容量字段扩容函数里如果只换了data指针而忘了list-capacity newCapacity后果很隐蔽表现在“插入几次后又莫名其妙满了”或者length已经大于capacity但程序没察觉继续插入直到真正越界才崩溃。每次写完扩容函数检查三件事data是否指向新内存、旧内存是否释放、capacity是否更新。这三件套缺一个都不行。5.5 释放时机拎不清早释放和晚释放都出事使用动态顺序表时用完就要destroySeqList释放。但要注意释放的时机比如在一个循环里反复创建和释放顺序表释放后一定要把指针置NULL或者把代码逻辑隔离在独立函数里。否则下一轮循环如果复用了同一个变量名判断“是否已初始化”时可能拿到一个悬空指针访问list-length直接段错误。这类问题排查起来特别恶心因为崩溃位置往往离真正出错的代码很远。5.6 常见问题速查表现象可能原因排查重点插入后数据错乱、有重复值插入移动方向错误从前往后挪检查循环起点是不是length删除后末尾元素没消失删除循环边界写错少挪了最后一个检查i length - 1的边界插入到一半程序崩溃未扩容或length与capacity判断错误检查扩容条件和capacity更新查找永远找不到目标遍历边界写了capacity导致访问垃圾数据检查遍历范围是lengthfree(): invalid pointer释放了栈上数组或重复释放检查data是否来自malloc释放后是否置NULL结构体内容被修改但外部没变化函数传的是结构体值而不是指针检查形参是否为SeqList *写顺序表后的几个体会从写第一版到处是bug的顺序表到后来能在很短时间内写出基本无错的版本我的体会是顺序表的价值不只是“能交作业”而已它逼着你把内存连续、逻辑位置、物理位置、边界条件这些最基础但最关键的概念想清楚。插入为什么从后往前挪、删除为什么要检查边界、扩容为什么要翻倍、为什么动态分配的内存必须释放——这些问题全部搞懂之后后面学链表、栈、队列都会轻松很多。还有一个小技巧分享给大家写完顺序表之后拿几组特殊数据测一下比如空表插入、表尾插入、表头删除、重复扩容到很大容量把这些边界case跑一遍比什么检查都管用。我自己排查过的大部分顺序表bug八成出在边界位置上。把这个习惯带到以后所有数据结构的编写中你会省下大量调试时间。下一篇文章我打算写顺序表在查找场景里更进阶的玩法有序表的二分查找、以及为什么有序表插入成本那么高顺便聊聊怎么用顺序表去实现栈这种受限的线性结构。顺序表这个专题一篇一篇往下啃基础就扎实了。