学《数据结构》这门课的时候最容易被低估的一个概念就是线性表的顺序存储结构也就是大家常说的顺序表。很多同学觉得这不就是数组吗上课一听就懂作业一写就废等到期末考试或者面试的时候才发现连“在指定位置插入一个元素”都写不完整。别急这篇文章我就用做项目、带新人的视角把顺序表这件事从头到尾掰开揉碎从Why到How从原理到代码从典型坑到怎么写实验报告一次讲清楚。这篇文章适合三类人看正在学《数据结构》但卡在第一个知识点的同学准备考研或者期末复习想快速梳理重点的人以及马上要面试、想把手写顺序表练成肌肉记忆的求职者。它解决的问题很具体为什么顺序表能成为“数据结构第一课”它的三个核心成员分别管什么插入、删除、查找到底怎么实现才不算错把这些问题弄明白你后面学链表、栈、队列都会顺很多。1. 为什么入门数据结构先要啃下顺序表这块硬骨头1.1 顺序表不是单纯数组它是线性表的一种物理实现先理清两个容易混的概念线性表是一种逻辑结构描述的是“数据元素之间是一对一的线性关系”也就是每个元素都有唯一的前驱和唯一的后继而顺序表是线性表的一种存储结构它用一段地址连续的存储单元依次存放线性表中的数据元素。换句话说线性表是“抽象的样子”顺序表是“落地的方案”。很多同学看到“顺序表就是数组”这句话就会产生一个误解我学了那么久 C 语言数组早用明白了还学什么但你要注意数组只是底层载体顺序表的关键在于“对数组的封装”。传统数组要么是固定长度、要么只管读写而顺序表要负责的事情包括当前到底存了多少个有效元素、什么时候该扩容、插入一个元素时要不要先腾位置、删除之后长度要不要更新。这些“数组本身不做、使用者自己容易忘”的逻辑才是顺序表真正的核心。严蔚敏老师的《数据结构C语言版》第2版里第一张图就把逻辑结构、存储结构、运算举例列清楚顺序表就是这个框架的起点。很多考研题、期末常考题也专挑这种概念区分来出比如“线性表的顺序存储和链式存储哪个支持随机访问”本质就是在考你有没有把逻辑和物理这两层分开。1.2 顺序表能锻炼的三个核心素养作为“数据结构第一课”顺序表真正的价值不是让你背代码而是帮你建立三个基本素养。第一逻辑结构和存储结构分离的意识。同样的线性表可以用顺序存储也可以用链式存储。顺序表学完以后你再看栈和队列就会发现栈和队列也是逻辑结构底层照样可以用数组实现原理完全一致。第二算法复杂度的直觉。插一个元素为什么要移动后面的元素平均移动多少个这个问题看上去简单但它是你日后分析排序算法、树操作、哈希冲突的基础。顺序表把“移动元素”这个代价放到了你眼前让你第一次直观感受到“不同操作的成本不一样”。第三模块化的接口设计习惯。一个标准顺序表应该暴露哪些操作初始化、插入、删除、按值查找、按位查找、打印、销毁。这种“把数据和方法封装在一起”的思维放到工程里就是结构体加函数的设计模式。很多新手写着写着就把length变成全局变量、把data数组直接暴露给外部乱改这就是没有接口意识。所以顺序表不是“简单的数组”而是一个完整的、可以用来训练算法思维的微型系统。把它吃透比囫囵吞枣地背十个代码模板有用得多。2. 顺序表的设计与三个关键成员2.1 静态分配和动态分配怎么选顺序表的存储方案有两种静态分配和动态分配。静态分配是提前定义一个足够大的数组比如#define MAXSIZE 100然后直接在结构体里放ElemType data[MAXSIZE]。这种方式的优点是实现简单、代码好懂很多教材在讲原理的时候都用这种方式但缺点是容量一旦定死满了以后就只能报错无法继续插入。动态分配则是结构体里只存一个指向数组首地址的指针初始化的时候用malloc申请一块空间满了以后用realloc扩容。这种方式更接近工程实践也是我推荐你重点掌握的方式。原因很简单你现在写的代码是要跑在特定输入上的谁也没法预设数据规模能扩容的顺序表才真正算一个可复用的容器。不过动态分配也有代价就是你必须处理好内存分配失败的情况还要记得销毁时free。很多同学学完链表再回头写顺序表总忘记释放内存这个习惯到了工程里就是内存泄漏的隐患。2.2 三个成员data、capacity、length一个标准顺序表的结构体核心就是下面三样东西#include stdio.h #include stdlib.h #include stdbool.h #define InitSize 10 typedef int ElemType; // 用别名方便以后换成其他类型 typedef struct { ElemType *data; // 指向动态数组的指针 int capacity; // 当前容量 int length; // 当前有效元素个数 } SqList;data是真正的数据存储区你可以在堆上申请一块连续空间然后用data[0]、data[1]去访问。capacity表示这块空间最多能装多少个元素。length表示当前已经用了多少个元素。为什么有了数组下标还要单独存length这是新手最容易犯糊涂的地方。你看一个普通数组int arr[10]它确实有 10 个格子但你在代码里写循环遍历的时候往往还要再维护一个变量记录“实际存了几个数”。C 语言的数组本身不记录有效元素个数所以顺序表必须把这个信息收进结构体里管理否则你根本不知道哪一段空间是有数据的哪一段是空闲的。注意capacity和length的区别capacity是“能装多少”length是“装了多少”。当length capacity时再插入就要扩容当length 0时再删除就要报错或返回失败。这两个边界条件在后面的所有操作里都会反复出现。2.3 初始化与扩容的正确姿势初始化的逻辑很简单申请初始大小的空间把length置 0。void InitList(SqList *L) { L-data (ElemType *)malloc(InitSize * sizeof(ElemType)); if (L-data NULL) { printf(内存分配失败\n); exit(1); } L-capacity InitSize; L-length 0; }这里有个细节初始化时最好判断一下malloc的返回值。虽然考试时一般不写但实际工程里内存分配失败是真实存在的写上去不是为了炫技是为了养成习惯。扩容的时候常规做法是用realloc一次性扩展一段空间比如每次增加 10 个元素的大小bool IncreaseSize(SqList *L, int add) { if (L NULL || L-data NULL || add 0) { return false; } ElemType *newData (ElemType *)realloc(L-data, (L-capacity add) * sizeof(ElemType)); if (newData NULL) { printf(扩容失败\n); return false; } L-data newData; L-capacity add; return true; }我用realloc而不是先malloc再free是因为realloc会在原空间后面能找到更大连续空间时就地扩容找不到时才重新分配并拷贝旧数据如果中途失败原空间不会被释放更安全。实际做项目时还可以选择“倍增扩容”比如新容量 旧容量 × 2减少扩容次数但要注意空间浪费教材里一般不会深入这一点你面试的时候可以提一下两种扩容策略的区别。3. 三大核心操作插入、删除、查找的完整实现3.1 插入操作位置校验和移动方向最关键顺序表的插入操作完整动作有四步检查位置、检查容量、移动元素、更新长度。很多人写错就错在“移动方向”上。先看标准实现bool ListInsert(SqList *L, int i, ElemType e) { if (L NULL) { return false; } // 位置不合法i 从 1 开始最多插到 length 1 if (i 1 || i L-length 1) { printf(插入位置非法\n); return false; } // 满了就扩容 if (L-length L-capacity) { if (!IncreaseSize(L, 10)) { return false; } } // 从最后一个元素开始依次向后移动 for (int j L-length; j i; j--) { L-data[j] L-data[j - 1]; } L-data[i - 1] e; L-length; return true; }这里我默认了表内元素的下标从 0 开始但用户传入的位序 i 从 1 开始。比如用户说“在第 1 个位置插入”对应数组下标是 0用户说“在第length1个位置插入”意思就是在表尾追加。为什么要从后往前移动你可以把顺序表想成一排椅子最后面有一个空位。新来的人要坐到第 3 个位置那原来的第 3 个人到最后一个人都要往后挪一个位置。如果从前往后挪第 3 个人先把位置占了第 4 个人就把第 3 个人原来的值覆盖了数据就丢了。所以必须从最后一位开始先挪最后一个人再挪倒数第二个人一路挪到第 i 个位置。位置校验这里还要注意i L-length 1才是不合法也就是说允许在表尾插入。很多人会写成i L-length结果死活插不进去最后一个位置这是很典型的边界错误。3.2 删除操作和插入相反但坑不一样删除操作是把第 i 个元素删掉后面的元素依次往前移动最后把length减 1。bool ListDelete(SqList *L, int i, ElemType *e) { if (L NULL || e NULL) { return false; } // 空表无法删除位置也不能越界 if (L-length 0 || i 1 || i L-length) { printf(删除位置非法\n); return false; } // 用 e 把被删元素带出来 *e L-data[i - 1]; // 从第 i1 个元素开始依次向前移动 for (int j i; j L-length; j) { L-data[j - 1] L-data[j]; } L-length--; return true; }删除操作最容易犯的错有三个。第一个忘记判空。空表删除length 0此时再看i 1 || i L-length任何 i 都不满足合法条件所以判空其实可以合并进去但很多新手会在length 0时继续执行循环访问data[-1]整个程序直接崩掉。第二个移动方向写反。删除时要从前往后挪——先用后面的值覆盖前面的值顺序是从第 i1 个元素开始依次覆盖第 i 个、第 i1 个、第 i2 个……如果反过来从后往前挪你会把还没处理的元素覆盖掉同样丢数据。第三个删完之后没有及时把最后一个多余的位置清理掉。其实length--之后最后一个位置虽然还存着旧值但已经不属于“有效数据”了下次插入会直接覆盖所以不清理也没问题。但如果你实在担心调试时看见脏数据可以加一句L-data[L-length] 0这个纯粹是个人风格不是必须。删除接口里我用了ElemType *e这个输出参数目的是把被删元素的值传给调用者。为什么不用返回值因为函数返回的bool表示“删除是否成功”如果直接把元素值作为返回值遇到值为-1这种特殊数据时就没法区分成功还是失败。这种“返回值用于状态、形参用于输出数据”的设计在工程里非常常见。3.3 查找按位访问和按值查找是两回事顺序表有两个“找”的操作一个简单一个稍复杂。按位查找给定位置 i返回该位置的元素。由于顺序表底层是数组内存连续且下标可以直接换算地址所以按位查找的时间复杂度是 O(1)这就是“随机存取”的含义。ElemType GetElem(SqList *L, int i) { if (L NULL || i 1 || i L-length) { printf(位置非法\n); return -1; } return L-data[i - 1]; }按值查找给定一个值 e找到它在表中的位置。遍历数组第一个匹配到的元素返回位序找不到返回 0 表示失败。int LocateElem(SqList *L, ElemType e) { if (L NULL) { return 0; } for (int i 0; i L-length; i) { if (L-data[i] e) { return i 1; // 返回位序 } } return 0; }按值查找的时间复杂度是 O(n)因为最坏情况下要比较完全部 n 个元素才发现没有这个值。很多人在练习题里会遇到“7-3 顺序表删除”“7-2 递增有序顺序表的插入”这类题目它们本质上就是这三段代码的组合变形要么先查找再删除要么先查找位置再插入。把查找操作和插入删除串起来你已经能解决大部分基础实验题了。4. 时间复杂度分析从一道高频面试题说起4.1 插入和删除平均移动 n/2 是怎么算出来的面试和期末考试都很爱问一个问题在顺序表中插入一个元素平均需要移动多少个元素先假设表长为 n。插入一个元素时你能插的位置有 n1 种第 1 个位置、第 2 个位置、……、第 n1 个位置表尾。在第 i 个位置插入需要移动的元素个数是n - i 1个。插到第 1 个位置移动 n 个元素插到第 2 个位置移动 n-1 个元素插到第 n1 个位置表尾移动 0 个元素。如果每种位置出现的概率相同那么平均移动次数就是[ \frac{1}{n1}\sum_{i1}^{n1} (n - i 1) \frac{n}{2} ]也就是说在等概率情况下插入一个元素平均要移动一半的元素。删除操作同理总共有 n 个可删位置删第 i 个位置要移动n - i个元素求平均得到(n-1)/2。这个结果的价值在于它解释了为什么顺序表的插入删除是 O(n) 量级。n 变大时移动次数线性增长性能自然不行。这也是你在工程中选型时判断该不该用顺序表的核心依据。4.2 各操作复杂度速查表我整理了一张常见的复杂度对照表方便你复习或者面试前快速过一遍操作最好情况平均情况最坏情况原因按位访问O(1)O(1)O(1)数组下标直接计算地址按值查找O(1)O(n)O(n)需要遍历比较表尾插入/删除O(1)O(1)O(1)不涉及元素移动表头插入/删除O(n)O(n)O(n)所有元素都要移动任意位置插入O(1)O(n)O(n)平均移动 n/2 个元素任意位置删除O(1)O(n)O(n)平均移动 (n-1)/2 个元素这里有两点值得注意。第一很多人以为“插入删除是 O(n)”但这个说法太粗糙。准确表达应当是在表尾操作时 O(1)在表头或中间操作时 O(n)。面试官问复杂度如果你能分情况回答他会觉得你理解得足够细致。第二按位访问的 O(1) 是顺序表相对链表最大的王牌。链表按位访问要不断走 next 指针最坏 O(n)顺序表只需要一次地址换算速度差异在大数据量下非常明显。这也是为什么很多底层容器比如动态数组、消息队列的环形缓冲区宁可花代价做内存拷贝也要保证随机访问的高性能。5. 顺序表 vs 链表选型逻辑和典型应用场景5.1 一张表看清楚顺序表的优缺点把顺序表放到整个数据结构体系里看它最常被拿来跟链表对比。我直接给结论对比维度顺序表链表存储空间连续地址相邻离散靠指针串联空间利用率扩容可能浪费预留空间按需分配但每个节点多存一个指针随机访问O(1)优势极大O(n)只能从头开始走插入删除表尾 O(1)中间 O(n)已知节点位置时 O(1)查找仍需 O(n)缓存友好性高局部性好低节点散落内存各处内存分配一次性申请、偶尔扩容频繁申请和释放易产生碎片实现难度简单下标好理解指针操作多容易丢链从这张表能得出一个结论顺序表适合“读多写少”和“数据量可预估”的场景链表适合“频繁在中间插入删除”的场景。很多同学背不住这个结论但只要碰到具体需求对比一下这张表就能选出来。举个例子。一个班级的成绩管理系统需要按学号快速查询某个学生的成绩插入和删除很少发生——这种场景明显选顺序表。反过来一个文本编辑器的撤销记录用户会频繁在历史记录中间插入、删除新的记录而且记录条数未知——这种场景就该用链表或者至少用链表风格的容器。5.2 顺序表的高频考点逆置、合并、去重真正考验你顺序表有没有学会的不是背三个接口而是能不能用它们组合出更复杂的操作。这里我挑三个高频题型也是热词里出现过的方向简单说一下思路。顺序表逆置把数组中元素前后颠倒。最经典的双指针做法左指针i0右指针jlength-1交换data[i]和data[j]然后i、j--直到相遇。这个操作的时间复杂度是 O(n)空间复杂度是 O(1)面试官很喜欢让你现场写。递增有序顺序表的插入假设表内元素已经按非递减排列现在要插入一个新值并保持有序。思路是先找到第一个比新值大的位置然后调用插入函数。如果不允许用现成接口就自己写一个循环从最后一个元素开始把比新值大的元素依次后移。这个题就是“插入操作”和“查找位置”的结合练好这个题你就深刻理解了移动方向的重要性。两个有序顺序表合并给你两个已经排好序的顺序表合并成一个新的有序表。经典三指针做法从头开始比较两个表的元素谁小谁先进新表等其中一个表遍历完把另一个表的剩余部分直接接到后面。时间复杂度 O(mn)。这个模式在归并排序里也会出现算是必须掌握的基本功。这三类题目每次考的都长得很相似核心原因只有一个顺序表的所有操作都建立在“连续存储 元素移动”这两个特性上你只要理解了这两个特性哪怕换一套马甲也能认出来。6. 实操踩坑记录与实验报告/面试输出要点6.1 新手最常踩的四个坑我在带新人写代码和批改实验报告时见到的错误几乎都集中在下面这四个地方你也可以拿着这个清单自检。第一个坑不判满、不判空。插入前不看length和capacity删除前不看length是否为 0。代码在小数据下可能恰好能跑一旦数据量上去要么越界写坏内存要么访问到无意义的值。正确的习惯是每次操作前把合法性校验收口。第二个坑移动方向写反。插入要从后往前移动删除要从前往后移动。这个方向问题我在前面反复强调因为它太容易错了。你可以记住一个口诀“插入往后挪先挪最后面的删除往前挪先搬最前面的。”第三个坑位序和下标混用。用户传入的 i 从 1 开始数组下标从 0 开始很多人写着写着就把data[i]当成第 i 个元素结果差一位。我的建议是在所有函数入口处都显式写int idx i - 1;然后再用data[idx]这样一眼就能看清哪里在做换算。第四个坑忘记更新 length或者更新时机不对。插入后length删除后length--忘记更新的后果比你想的严重插入时会把数据写进data[length]但length没变遍历时你怎么都看不到新元素删除时length没减少旧值还遍历得到逻辑全乱。还有一个和内存相关的坑用realloc扩容时不要把返回结果直接赋给L-data。因为如果realloc失败它会返回NULL但原来的空间并没有释放你要是直接把L-data覆盖成NULL原来的内存地址就丢了连恢复的机会都没有。必须先用临时变量保存返回值判空后再赋值。6.2 实验报告和面试怎么把顺序表讲出彩最后聊一聊“输出”的问题因为很多同学代码写得没问题但一到实验报告或面试表达就不知道怎么组织语言了。实验报告老师要看的不只是代码能跑更是你的思路。结构上建议按四段式来写一是需求分析这段题目要干什么输入输出是什么二是算法设计用自然语言描述核心思路配上图示展示插入或删除过程中数据的变化过程三是代码实现贴关键代码不要全贴四是测试与分析设计几组测试用例包括正常情况、表空、表满、边界位置并记录运行结果最后附上时间复杂度和空间复杂度的分析。特别提醒一点很多同学只写“程序运行成功”就糊弄过去了这样拿不到高分。你至少要说明你测了哪些边界场景比如在空表里插入在表头删除插到length 1的位置删除最后一个元素等等。一套完善的测试用例比你写一千字“我觉得”更能证明你理解了顺序表。面试手撕顺序表代码的时候我建议你在一开始就把结构体、初始化、扩容、插入、删除这几个函数的骨架先默写出来然后再补细节。面试官真正想看的是你面对边界情况时的反应而不是你背代码背得多熟。我当年面试的时候就遇到过这种问题“如果realloc扩容失败你的插入函数怎么处理”如果你没有提前想过现场很容易愣住。我的经验是平时写题时把所有if分支都补全面试时就能很自然地讲先返回false由调用方决定是报错还是继续用旧数组。这种回答透露出的设计能力比代码本身更值钱。我自己带过好几轮实习生也批过不少课程设计项目算是在顺序表这个题目上踩过不少坑也看了别人踩坑。我的体会是顺序表这个内容代码量不大但它逼着你想清楚“数据怎么存、位置怎么算、边界怎么处理、代价是什么”这些底层问题一旦想透你后边学链表、学树、学图都会顺畅得多。最后再分享一个我自己觉得特别有用的练习方法把顺序表当成模板连续写十遍每一遍都假装是面试现场不查资料写错了就重新来。写到第五遍你会发现你已经不是在背代码了而是在凭直觉知道下一步该做什么。到第十遍的时候你闭着眼睛都能说出插入操作的四步流程移动方向永远是对的边界判断条件张口就来。这个阶段的你才算真正把顺序表这一关过了。 顺序表详解：从线性表存储结构到插入删除与时间复杂度分析
学《数据结构》这门课的时候最容易被低估的一个概念就是线性表的顺序存储结构也就是大家常说的顺序表。很多同学觉得这不就是数组吗上课一听就懂作业一写就废等到期末考试或者面试的时候才发现连“在指定位置插入一个元素”都写不完整。别急这篇文章我就用做项目、带新人的视角把顺序表这件事从头到尾掰开揉碎从Why到How从原理到代码从典型坑到怎么写实验报告一次讲清楚。这篇文章适合三类人看正在学《数据结构》但卡在第一个知识点的同学准备考研或者期末复习想快速梳理重点的人以及马上要面试、想把手写顺序表练成肌肉记忆的求职者。它解决的问题很具体为什么顺序表能成为“数据结构第一课”它的三个核心成员分别管什么插入、删除、查找到底怎么实现才不算错把这些问题弄明白你后面学链表、栈、队列都会顺很多。1. 为什么入门数据结构先要啃下顺序表这块硬骨头1.1 顺序表不是单纯数组它是线性表的一种物理实现先理清两个容易混的概念线性表是一种逻辑结构描述的是“数据元素之间是一对一的线性关系”也就是每个元素都有唯一的前驱和唯一的后继而顺序表是线性表的一种存储结构它用一段地址连续的存储单元依次存放线性表中的数据元素。换句话说线性表是“抽象的样子”顺序表是“落地的方案”。很多同学看到“顺序表就是数组”这句话就会产生一个误解我学了那么久 C 语言数组早用明白了还学什么但你要注意数组只是底层载体顺序表的关键在于“对数组的封装”。传统数组要么是固定长度、要么只管读写而顺序表要负责的事情包括当前到底存了多少个有效元素、什么时候该扩容、插入一个元素时要不要先腾位置、删除之后长度要不要更新。这些“数组本身不做、使用者自己容易忘”的逻辑才是顺序表真正的核心。严蔚敏老师的《数据结构C语言版》第2版里第一张图就把逻辑结构、存储结构、运算举例列清楚顺序表就是这个框架的起点。很多考研题、期末常考题也专挑这种概念区分来出比如“线性表的顺序存储和链式存储哪个支持随机访问”本质就是在考你有没有把逻辑和物理这两层分开。1.2 顺序表能锻炼的三个核心素养作为“数据结构第一课”顺序表真正的价值不是让你背代码而是帮你建立三个基本素养。第一逻辑结构和存储结构分离的意识。同样的线性表可以用顺序存储也可以用链式存储。顺序表学完以后你再看栈和队列就会发现栈和队列也是逻辑结构底层照样可以用数组实现原理完全一致。第二算法复杂度的直觉。插一个元素为什么要移动后面的元素平均移动多少个这个问题看上去简单但它是你日后分析排序算法、树操作、哈希冲突的基础。顺序表把“移动元素”这个代价放到了你眼前让你第一次直观感受到“不同操作的成本不一样”。第三模块化的接口设计习惯。一个标准顺序表应该暴露哪些操作初始化、插入、删除、按值查找、按位查找、打印、销毁。这种“把数据和方法封装在一起”的思维放到工程里就是结构体加函数的设计模式。很多新手写着写着就把length变成全局变量、把data数组直接暴露给外部乱改这就是没有接口意识。所以顺序表不是“简单的数组”而是一个完整的、可以用来训练算法思维的微型系统。把它吃透比囫囵吞枣地背十个代码模板有用得多。2. 顺序表的设计与三个关键成员2.1 静态分配和动态分配怎么选顺序表的存储方案有两种静态分配和动态分配。静态分配是提前定义一个足够大的数组比如#define MAXSIZE 100然后直接在结构体里放ElemType data[MAXSIZE]。这种方式的优点是实现简单、代码好懂很多教材在讲原理的时候都用这种方式但缺点是容量一旦定死满了以后就只能报错无法继续插入。动态分配则是结构体里只存一个指向数组首地址的指针初始化的时候用malloc申请一块空间满了以后用realloc扩容。这种方式更接近工程实践也是我推荐你重点掌握的方式。原因很简单你现在写的代码是要跑在特定输入上的谁也没法预设数据规模能扩容的顺序表才真正算一个可复用的容器。不过动态分配也有代价就是你必须处理好内存分配失败的情况还要记得销毁时free。很多同学学完链表再回头写顺序表总忘记释放内存这个习惯到了工程里就是内存泄漏的隐患。2.2 三个成员data、capacity、length一个标准顺序表的结构体核心就是下面三样东西#include stdio.h #include stdlib.h #include stdbool.h #define InitSize 10 typedef int ElemType; // 用别名方便以后换成其他类型 typedef struct { ElemType *data; // 指向动态数组的指针 int capacity; // 当前容量 int length; // 当前有效元素个数 } SqList;data是真正的数据存储区你可以在堆上申请一块连续空间然后用data[0]、data[1]去访问。capacity表示这块空间最多能装多少个元素。length表示当前已经用了多少个元素。为什么有了数组下标还要单独存length这是新手最容易犯糊涂的地方。你看一个普通数组int arr[10]它确实有 10 个格子但你在代码里写循环遍历的时候往往还要再维护一个变量记录“实际存了几个数”。C 语言的数组本身不记录有效元素个数所以顺序表必须把这个信息收进结构体里管理否则你根本不知道哪一段空间是有数据的哪一段是空闲的。注意capacity和length的区别capacity是“能装多少”length是“装了多少”。当length capacity时再插入就要扩容当length 0时再删除就要报错或返回失败。这两个边界条件在后面的所有操作里都会反复出现。2.3 初始化与扩容的正确姿势初始化的逻辑很简单申请初始大小的空间把length置 0。void InitList(SqList *L) { L-data (ElemType *)malloc(InitSize * sizeof(ElemType)); if (L-data NULL) { printf(内存分配失败\n); exit(1); } L-capacity InitSize; L-length 0; }这里有个细节初始化时最好判断一下malloc的返回值。虽然考试时一般不写但实际工程里内存分配失败是真实存在的写上去不是为了炫技是为了养成习惯。扩容的时候常规做法是用realloc一次性扩展一段空间比如每次增加 10 个元素的大小bool IncreaseSize(SqList *L, int add) { if (L NULL || L-data NULL || add 0) { return false; } ElemType *newData (ElemType *)realloc(L-data, (L-capacity add) * sizeof(ElemType)); if (newData NULL) { printf(扩容失败\n); return false; } L-data newData; L-capacity add; return true; }我用realloc而不是先malloc再free是因为realloc会在原空间后面能找到更大连续空间时就地扩容找不到时才重新分配并拷贝旧数据如果中途失败原空间不会被释放更安全。实际做项目时还可以选择“倍增扩容”比如新容量 旧容量 × 2减少扩容次数但要注意空间浪费教材里一般不会深入这一点你面试的时候可以提一下两种扩容策略的区别。3. 三大核心操作插入、删除、查找的完整实现3.1 插入操作位置校验和移动方向最关键顺序表的插入操作完整动作有四步检查位置、检查容量、移动元素、更新长度。很多人写错就错在“移动方向”上。先看标准实现bool ListInsert(SqList *L, int i, ElemType e) { if (L NULL) { return false; } // 位置不合法i 从 1 开始最多插到 length 1 if (i 1 || i L-length 1) { printf(插入位置非法\n); return false; } // 满了就扩容 if (L-length L-capacity) { if (!IncreaseSize(L, 10)) { return false; } } // 从最后一个元素开始依次向后移动 for (int j L-length; j i; j--) { L-data[j] L-data[j - 1]; } L-data[i - 1] e; L-length; return true; }这里我默认了表内元素的下标从 0 开始但用户传入的位序 i 从 1 开始。比如用户说“在第 1 个位置插入”对应数组下标是 0用户说“在第length1个位置插入”意思就是在表尾追加。为什么要从后往前移动你可以把顺序表想成一排椅子最后面有一个空位。新来的人要坐到第 3 个位置那原来的第 3 个人到最后一个人都要往后挪一个位置。如果从前往后挪第 3 个人先把位置占了第 4 个人就把第 3 个人原来的值覆盖了数据就丢了。所以必须从最后一位开始先挪最后一个人再挪倒数第二个人一路挪到第 i 个位置。位置校验这里还要注意i L-length 1才是不合法也就是说允许在表尾插入。很多人会写成i L-length结果死活插不进去最后一个位置这是很典型的边界错误。3.2 删除操作和插入相反但坑不一样删除操作是把第 i 个元素删掉后面的元素依次往前移动最后把length减 1。bool ListDelete(SqList *L, int i, ElemType *e) { if (L NULL || e NULL) { return false; } // 空表无法删除位置也不能越界 if (L-length 0 || i 1 || i L-length) { printf(删除位置非法\n); return false; } // 用 e 把被删元素带出来 *e L-data[i - 1]; // 从第 i1 个元素开始依次向前移动 for (int j i; j L-length; j) { L-data[j - 1] L-data[j]; } L-length--; return true; }删除操作最容易犯的错有三个。第一个忘记判空。空表删除length 0此时再看i 1 || i L-length任何 i 都不满足合法条件所以判空其实可以合并进去但很多新手会在length 0时继续执行循环访问data[-1]整个程序直接崩掉。第二个移动方向写反。删除时要从前往后挪——先用后面的值覆盖前面的值顺序是从第 i1 个元素开始依次覆盖第 i 个、第 i1 个、第 i2 个……如果反过来从后往前挪你会把还没处理的元素覆盖掉同样丢数据。第三个删完之后没有及时把最后一个多余的位置清理掉。其实length--之后最后一个位置虽然还存着旧值但已经不属于“有效数据”了下次插入会直接覆盖所以不清理也没问题。但如果你实在担心调试时看见脏数据可以加一句L-data[L-length] 0这个纯粹是个人风格不是必须。删除接口里我用了ElemType *e这个输出参数目的是把被删元素的值传给调用者。为什么不用返回值因为函数返回的bool表示“删除是否成功”如果直接把元素值作为返回值遇到值为-1这种特殊数据时就没法区分成功还是失败。这种“返回值用于状态、形参用于输出数据”的设计在工程里非常常见。3.3 查找按位访问和按值查找是两回事顺序表有两个“找”的操作一个简单一个稍复杂。按位查找给定位置 i返回该位置的元素。由于顺序表底层是数组内存连续且下标可以直接换算地址所以按位查找的时间复杂度是 O(1)这就是“随机存取”的含义。ElemType GetElem(SqList *L, int i) { if (L NULL || i 1 || i L-length) { printf(位置非法\n); return -1; } return L-data[i - 1]; }按值查找给定一个值 e找到它在表中的位置。遍历数组第一个匹配到的元素返回位序找不到返回 0 表示失败。int LocateElem(SqList *L, ElemType e) { if (L NULL) { return 0; } for (int i 0; i L-length; i) { if (L-data[i] e) { return i 1; // 返回位序 } } return 0; }按值查找的时间复杂度是 O(n)因为最坏情况下要比较完全部 n 个元素才发现没有这个值。很多人在练习题里会遇到“7-3 顺序表删除”“7-2 递增有序顺序表的插入”这类题目它们本质上就是这三段代码的组合变形要么先查找再删除要么先查找位置再插入。把查找操作和插入删除串起来你已经能解决大部分基础实验题了。4. 时间复杂度分析从一道高频面试题说起4.1 插入和删除平均移动 n/2 是怎么算出来的面试和期末考试都很爱问一个问题在顺序表中插入一个元素平均需要移动多少个元素先假设表长为 n。插入一个元素时你能插的位置有 n1 种第 1 个位置、第 2 个位置、……、第 n1 个位置表尾。在第 i 个位置插入需要移动的元素个数是n - i 1个。插到第 1 个位置移动 n 个元素插到第 2 个位置移动 n-1 个元素插到第 n1 个位置表尾移动 0 个元素。如果每种位置出现的概率相同那么平均移动次数就是[ \frac{1}{n1}\sum_{i1}^{n1} (n - i 1) \frac{n}{2} ]也就是说在等概率情况下插入一个元素平均要移动一半的元素。删除操作同理总共有 n 个可删位置删第 i 个位置要移动n - i个元素求平均得到(n-1)/2。这个结果的价值在于它解释了为什么顺序表的插入删除是 O(n) 量级。n 变大时移动次数线性增长性能自然不行。这也是你在工程中选型时判断该不该用顺序表的核心依据。4.2 各操作复杂度速查表我整理了一张常见的复杂度对照表方便你复习或者面试前快速过一遍操作最好情况平均情况最坏情况原因按位访问O(1)O(1)O(1)数组下标直接计算地址按值查找O(1)O(n)O(n)需要遍历比较表尾插入/删除O(1)O(1)O(1)不涉及元素移动表头插入/删除O(n)O(n)O(n)所有元素都要移动任意位置插入O(1)O(n)O(n)平均移动 n/2 个元素任意位置删除O(1)O(n)O(n)平均移动 (n-1)/2 个元素这里有两点值得注意。第一很多人以为“插入删除是 O(n)”但这个说法太粗糙。准确表达应当是在表尾操作时 O(1)在表头或中间操作时 O(n)。面试官问复杂度如果你能分情况回答他会觉得你理解得足够细致。第二按位访问的 O(1) 是顺序表相对链表最大的王牌。链表按位访问要不断走 next 指针最坏 O(n)顺序表只需要一次地址换算速度差异在大数据量下非常明显。这也是为什么很多底层容器比如动态数组、消息队列的环形缓冲区宁可花代价做内存拷贝也要保证随机访问的高性能。5. 顺序表 vs 链表选型逻辑和典型应用场景5.1 一张表看清楚顺序表的优缺点把顺序表放到整个数据结构体系里看它最常被拿来跟链表对比。我直接给结论对比维度顺序表链表存储空间连续地址相邻离散靠指针串联空间利用率扩容可能浪费预留空间按需分配但每个节点多存一个指针随机访问O(1)优势极大O(n)只能从头开始走插入删除表尾 O(1)中间 O(n)已知节点位置时 O(1)查找仍需 O(n)缓存友好性高局部性好低节点散落内存各处内存分配一次性申请、偶尔扩容频繁申请和释放易产生碎片实现难度简单下标好理解指针操作多容易丢链从这张表能得出一个结论顺序表适合“读多写少”和“数据量可预估”的场景链表适合“频繁在中间插入删除”的场景。很多同学背不住这个结论但只要碰到具体需求对比一下这张表就能选出来。举个例子。一个班级的成绩管理系统需要按学号快速查询某个学生的成绩插入和删除很少发生——这种场景明显选顺序表。反过来一个文本编辑器的撤销记录用户会频繁在历史记录中间插入、删除新的记录而且记录条数未知——这种场景就该用链表或者至少用链表风格的容器。5.2 顺序表的高频考点逆置、合并、去重真正考验你顺序表有没有学会的不是背三个接口而是能不能用它们组合出更复杂的操作。这里我挑三个高频题型也是热词里出现过的方向简单说一下思路。顺序表逆置把数组中元素前后颠倒。最经典的双指针做法左指针i0右指针jlength-1交换data[i]和data[j]然后i、j--直到相遇。这个操作的时间复杂度是 O(n)空间复杂度是 O(1)面试官很喜欢让你现场写。递增有序顺序表的插入假设表内元素已经按非递减排列现在要插入一个新值并保持有序。思路是先找到第一个比新值大的位置然后调用插入函数。如果不允许用现成接口就自己写一个循环从最后一个元素开始把比新值大的元素依次后移。这个题就是“插入操作”和“查找位置”的结合练好这个题你就深刻理解了移动方向的重要性。两个有序顺序表合并给你两个已经排好序的顺序表合并成一个新的有序表。经典三指针做法从头开始比较两个表的元素谁小谁先进新表等其中一个表遍历完把另一个表的剩余部分直接接到后面。时间复杂度 O(mn)。这个模式在归并排序里也会出现算是必须掌握的基本功。这三类题目每次考的都长得很相似核心原因只有一个顺序表的所有操作都建立在“连续存储 元素移动”这两个特性上你只要理解了这两个特性哪怕换一套马甲也能认出来。6. 实操踩坑记录与实验报告/面试输出要点6.1 新手最常踩的四个坑我在带新人写代码和批改实验报告时见到的错误几乎都集中在下面这四个地方你也可以拿着这个清单自检。第一个坑不判满、不判空。插入前不看length和capacity删除前不看length是否为 0。代码在小数据下可能恰好能跑一旦数据量上去要么越界写坏内存要么访问到无意义的值。正确的习惯是每次操作前把合法性校验收口。第二个坑移动方向写反。插入要从后往前移动删除要从前往后移动。这个方向问题我在前面反复强调因为它太容易错了。你可以记住一个口诀“插入往后挪先挪最后面的删除往前挪先搬最前面的。”第三个坑位序和下标混用。用户传入的 i 从 1 开始数组下标从 0 开始很多人写着写着就把data[i]当成第 i 个元素结果差一位。我的建议是在所有函数入口处都显式写int idx i - 1;然后再用data[idx]这样一眼就能看清哪里在做换算。第四个坑忘记更新 length或者更新时机不对。插入后length删除后length--忘记更新的后果比你想的严重插入时会把数据写进data[length]但length没变遍历时你怎么都看不到新元素删除时length没减少旧值还遍历得到逻辑全乱。还有一个和内存相关的坑用realloc扩容时不要把返回结果直接赋给L-data。因为如果realloc失败它会返回NULL但原来的空间并没有释放你要是直接把L-data覆盖成NULL原来的内存地址就丢了连恢复的机会都没有。必须先用临时变量保存返回值判空后再赋值。6.2 实验报告和面试怎么把顺序表讲出彩最后聊一聊“输出”的问题因为很多同学代码写得没问题但一到实验报告或面试表达就不知道怎么组织语言了。实验报告老师要看的不只是代码能跑更是你的思路。结构上建议按四段式来写一是需求分析这段题目要干什么输入输出是什么二是算法设计用自然语言描述核心思路配上图示展示插入或删除过程中数据的变化过程三是代码实现贴关键代码不要全贴四是测试与分析设计几组测试用例包括正常情况、表空、表满、边界位置并记录运行结果最后附上时间复杂度和空间复杂度的分析。特别提醒一点很多同学只写“程序运行成功”就糊弄过去了这样拿不到高分。你至少要说明你测了哪些边界场景比如在空表里插入在表头删除插到length 1的位置删除最后一个元素等等。一套完善的测试用例比你写一千字“我觉得”更能证明你理解了顺序表。面试手撕顺序表代码的时候我建议你在一开始就把结构体、初始化、扩容、插入、删除这几个函数的骨架先默写出来然后再补细节。面试官真正想看的是你面对边界情况时的反应而不是你背代码背得多熟。我当年面试的时候就遇到过这种问题“如果realloc扩容失败你的插入函数怎么处理”如果你没有提前想过现场很容易愣住。我的经验是平时写题时把所有if分支都补全面试时就能很自然地讲先返回false由调用方决定是报错还是继续用旧数组。这种回答透露出的设计能力比代码本身更值钱。我自己带过好几轮实习生也批过不少课程设计项目算是在顺序表这个题目上踩过不少坑也看了别人踩坑。我的体会是顺序表这个内容代码量不大但它逼着你想清楚“数据怎么存、位置怎么算、边界怎么处理、代价是什么”这些底层问题一旦想透你后边学链表、学树、学图都会顺畅得多。最后再分享一个我自己觉得特别有用的练习方法把顺序表当成模板连续写十遍每一遍都假装是面试现场不查资料写错了就重新来。写到第五遍你会发现你已经不是在背代码了而是在凭直觉知道下一步该做什么。到第十遍的时候你闭着眼睛都能说出插入操作的四步流程移动方向永远是对的边界判断条件张口就来。这个阶段的你才算真正把顺序表这一关过了。