1. 为什么顺序表是数据结构的第一道坎1.1 从一次课堂翻车说起我带过几届数据结构实验课几乎每届都有学生在顺序表这个实验上栽跟头。印象最深的是一个学生代码写完了编译也过了运行起来插入几个元素看着也正常结果一到删除操作就出问题——删完最后一个元素再打印一遍末尾莫名其妙多出一个旧值。他盯着屏幕看了半小时最后发现是删除时只把后面的元素往前挪了忘了把有效长度减一末尾那个幽灵元素其实早就该被逻辑丢弃了。这个场景特别典型。顺序表看起来简单无非就是数组加一个长度变量但真正动手写的时候边界条件、下标越界、长度维护、内存管理每一个细节都能让人翻车。它之所以被安排成实验一不是因为简单而是因为它把数据结构最核心的几个思维习惯一次性全塞给你了逻辑结构和存储结构的对应关系、操作的时间复杂度意识、边界条件的严谨处理、以及用代码精确表达算法的能力。这篇文章我会把顺序表实验从设计思路到代码实现、从踩坑记录到调试技巧完整地拆一遍。不管你是正在做这个实验的学生还是想重新夯实基础的自学者都能直接拿去参考。我会尽量把每个为什么这么做讲透而不是只丢一段代码让你抄。1.2 顺序表到底在解决什么问题先说清楚顺序表是什么。顺序表是用一段地址连续的内存单元依次存储线性表的数据元素。说白了就是用一个数组存数据再用一个变量记录当前存了多少个元素。它的逻辑结构是线性的——每个元素有唯一的前驱和后继除了首尾而它的存储结构也是线性的——元素在内存里一个挨着一个。为什么要有顺序表因为很多场景下我们需要按位置快速访问的能力。比如你要做一个学生成绩管理系统想直接查第 5 个学生的成绩顺序表能做到 O(1) 的时间复杂度因为下标一算就定位到了。这是链表做不到的链表你得从头一个个数过去。但顺序表也有它的代价。插入和删除的时候为了保持元素的连续性往往需要移动大量元素平均时间复杂度是 O(n)。所以顺序表适合查多改少的场景比如成绩表、配置项列表、固定大小的缓冲区。理解这个取舍是理解整个线性表体系的第一步。1.3 这个实验适合谁、能学到什么这个实验的定位是入门级但它的知识密度不低。适合的人群包括正在上数据结构课的学生、准备考研复试要手写代码的同学、以及工作后想补基础的程序员。你不需要多深的编程功底会基本的 C 或 C 语法就够了但你需要有耐心去抠每一个边界条件。学完这个实验你应该能掌握几件事第一能用代码定义一个顺序表结构体并说清楚每个成员变量的作用第二能实现初始化、插入、删除、查找、遍历这几个基本操作并分析它们的时间复杂度第三能处理各种边界情况比如空表删除、表满插入、位置非法等第四能把这些操作组合起来解决一个实际问题比如两个有序表的合并。这些能力看起来基础但它们是后面学链表、栈、队列、树、图的地基。地基没打牢后面全是空中楼阁。2. 实验整体设计与思路拆解2.1 用数组还是动态分配存储方案的选择顺序表的实现有两种常见路线。一种是静态分配直接定义一个固定大小的数组比如int data[100]再配一个length记录当前元素个数。另一种是动态分配用指针加malloc在运行时申请内存容量不够时可以扩容。静态分配写起来简单适合实验课上快速验证算法逻辑。但它的缺点很明显容量写死了存满了就没法再加。动态分配更灵活也更接近真实工程里的用法但要多处理内存申请失败、扩容、释放这些事对初学者来说容易出错。我的建议是实验一先用静态分配把逻辑跑通理解清楚每个操作的原理然后再用动态分配重写一遍。这样你能对比两种方式的差异也能体会到存储结构的选择会影响代码复杂度这件事。很多同学一上来就写动态分配结果指针操作出错连基本的插入都没调通反而耽误时间。如果你用 C还可以用vector或者自己封装一个类把data和length藏起来只暴露操作接口。这就是**抽象数据类型ADT**的思想——使用者不需要知道内部怎么存的只需要知道能做什么操作。这个思想贯穿整个数据结构课程早点建立起来有好处。2.2 结构体怎么定义才合理不管静态还是动态顺序表的核心信息就两样存数据的容器和当前元素个数。用结构体把它们绑在一起是最自然的做法。静态版本大概长这样#define MAXSIZE 100 typedef struct { int data[MAXSIZE]; int length; } SeqList;这里MAXSIZE是最大容量length是当前实际元素个数。注意区分这两个概念容量是最多能装多少长度是现在装了多少。很多 bug 就出在把这两个搞混了比如判断表满的时候用错了变量。动态版本则是typedef struct { int *data; int length; int capacity; } SeqList;多了一个capacity记录当前申请的容量。初始化时先申请一块内存插入时如果length capacity就扩容。扩容一般按 1.5 倍或 2 倍增长这样均摊下来插入操作还是 O(1) 的。为什么是 1.5 或 2 倍而不是每次加 1因为每次加 1 会导致频繁申请和拷贝总代价变成 O(n²)而按倍数增长能让总代价摊薄到 O(n)。提示结构体里的成员顺序会影响内存对齐但对这个实验来说影响可以忽略不用纠结。真正要纠结的是length的语义——它既是元素个数也是下一个可插入位置的下标这个双重身份要时刻记牢。2.3 操作接口的设计原则一个完整的顺序表应该提供哪些操作至少包括初始化、判空、判满、按位置插入、按位置删除、按值查找、按位置取值、遍历输出、求长度、清空。如果做应用扩展还要加上合并、去重、逆置这些。设计接口的时候有个原则每个函数只做一件事并且把边界检查放在函数内部。比如插入函数进来先判断位置是否合法、表是否已满不合法就返回错误码合法才执行插入。这样调用者就不用每次都自己检查代码更干净也更不容易出错。返回值的设计也有讲究。C 语言里没有异常机制所以通常用返回值表示成功或失败比如返回 1 表示成功、0 表示失败或者用枚举类型定义一组错误码。取值操作则通过指针参数把结果带出来。这种返回值表状态、指针参数带结果的模式在数据结构代码里非常常见要习惯它。3. 核心操作的原理与实操要点3.1 插入操作为什么从后往前挪插入是顺序表里第一个需要移动元素的操作。假设表里有n个元素要在第i个位置下标从 0 开始算的话就是下标i插入一个新元素那么从下标i到n-1的所有元素都要往后挪一位腾出位置。关键在于移动的方向。必须从最后一个元素开始依次往后挪也就是从data[n-1]挪到data[n]data[n-2]挪到data[n-1]一直到data[i]挪到data[i1]。如果反过来从前往后挪data[i]会先覆盖掉data[i1]后面的数据就全丢了。int listInsert(SeqList *L, int pos, int value) { if (pos 0 || pos L-length) return 0; // 位置非法 if (L-length MAXSIZE) return 0; // 表已满 for (int j L-length; j pos; j--) { L-data[j] L-data[j - 1]; } L-data[pos] value; L-length; return 1; }注意pos的合法范围是0到length不是0到length-1。因为你可以插在最后一个元素的后面也就是插到表尾。这个多一个位置的细节是初学者最容易搞错的地方之一。时间复杂度方面最好情况是插在表尾不用移动O(1)最坏情况是插在表头要移动全部 n 个元素O(n)平均移动 n/2 个元素所以平均时间复杂度是 O(n)。3.2 删除操作别忘了把长度减一删除和插入是镜像操作。删除第i个位置的元素需要把下标i1到n-1的元素全部往前挪一位覆盖掉被删的元素。这次移动方向是从前往后因为前面的位置空出来了后面的元素往前填。int listDelete(SeqList *L, int pos, int *e) { if (pos 0 || pos L-length) return 0; // 位置非法 *e L-data[pos]; // 把被删的值带出去 for (int j pos; j L-length - 1; j) { L-data[j] L-data[j 1]; } L-length--; // 长度减一 return 1; }这里pos的合法范围是0到length-1因为你要删的元素必须存在。和插入不同删除没有多一个位置的说法。我前面提到的那个学生就是漏了L-length--这一行。长度不减程序就认为末尾还有一个有效元素但那个位置的数据其实已经被逻辑丢弃了打印出来就是脏数据。这个 bug 不会导致崩溃但会让结果错误比崩溃更难查。3.3 查找与取值按位置和按值的区别查找分两种。按位置查找也叫取值是给定下标直接返回data[pos]时间复杂度 O(1)这是顺序表最大的优势。按值查找是给定一个值从头遍历找到第一个匹配的元素返回它的下标时间复杂度 O(n)。int getElem(SeqList L, int pos, int *e) { if (pos 0 || pos L.length) return 0; *e L.data[pos]; return 1; } int locateElem(SeqList L, int value) { for (int i 0; i L.length; i) { if (L.data[i] value) return i; } return -1; // 没找到 }按值查找返回 -1 表示没找到这是一个约定。但要注意如果表里存的值本身可能是负数用 -1 表示没找到就有歧义了。更严谨的做法是返回一个布尔值表示是否找到下标通过指针参数带出来。这种细节在工程里很重要实验里可以先简单处理但心里要有数。3.4 遍历与打印调试的好帮手遍历就是从头到尾访问每个元素。它本身很简单但在调试阶段极其重要。每次做完插入或删除都打印一遍整个表能立刻看出结果对不对。void printList(SeqList L) { printf(List (length%d): , L.length); for (int i 0; i L.length; i) { printf(%d , L.data[i]); } printf(\n); }打印的时候把length也带上这样你能同时看到逻辑长度和实际数据。如果发现打印出来的元素个数和length对不上那基本就是长度维护出了问题。注意调试时不要只打印data数组的前几个元素一定要按length来打印。因为数组里超出length的部分是无效数据打印出来只会干扰判断。4. 完整实操流程与代码实现4.1 从零搭建文件结构与编译我习惯把顺序表的代码分成三个文件seqlist.h放结构体定义和函数声明seqlist.c放函数实现main.c放测试代码。这样结构清晰也方便后面复用。如果你用的是集成开发环境直接建一个工程把三个文件加进去就行如果用的是命令行编译命令大概是这样gcc main.c seqlist.c -o seqlist_test ./seqlist_test分文件的好处是头文件里只暴露接口实现细节藏在.c文件里。别人用你的顺序表只需要#include seqlist.h不需要关心内部怎么实现的。这就是封装。4.2 初始化与基础操作实现初始化就是把length置为 0。静态分配的话数组本身已经存在了不需要额外申请内存。void initList(SeqList *L) { L-length 0; }判空和判满也很简单int isEmpty(SeqList L) { return L.length 0; } int isFull(SeqList L) { return L.length MAXSIZE; }这几个函数虽然简单但它们是其他操作的基础。插入前要判满删除前要判空养成操作前先检查状态的习惯能避免大量边界 bug。4.3 应用一两个有序顺序表的合并基本操作跑通之后就该做应用了。最经典的应用是合并两个有序顺序表。给定两个非递减排列的顺序表 A 和 B要求合并成一个新的非递减顺序表 C。思路是用两个指针分别指向 A 和 B 的当前元素比较大小小的先放进 C然后对应指针后移。当一个表走完了把另一个表剩下的元素全部追加到 C 后面。void mergeList(SeqList A, SeqList B, SeqList *C) { int i 0, j 0, k 0; while (i A.length j B.length) { if (A.data[i] B.data[j]) { C-data[k] A.data[i]; } else { C-data[k] B.data[j]; } } while (i A.length) C-data[k] A.data[i]; while (j B.length) C-data[k] B.data[j]; C-length k; }这个算法的时间复杂度是 O(mn)其中 m 和 n 分别是两个表的长度。因为每个元素只被访问一次。空间复杂度是 O(mn)因为要开一个新表存结果。如果要求原地合并把 B 合并进 A那就复杂一些需要从后往前处理避免覆盖未处理的元素。4.4 应用二就地逆置与去重就地逆置是把表里的元素顺序反过来要求空间复杂度 O(1)。做法是用两个指针一个指向头一个指向尾交换它们的值然后向中间靠拢直到相遇。void reverseList(SeqList *L) { int i 0, j L-length - 1; while (i j) { int temp L-data[i]; L-data[i] L-data[j]; L-data[j] temp; i; j--; } }去重是删除表中重复的元素只保留第一个出现的。如果表是有序的可以用双指针法一个指针记录当前保留的最后一个元素的位置另一个指针遍历。如果表是无序的通常用双重循环时间复杂度 O(n²)。void removeDuplicates(SeqList *L) { int k 0; // k 是当前保留的最后一个元素的下标 for (int i 1; i L-length; i) { if (L-data[i] ! L-data[k]) { k; L-data[k] L-data[i]; } } L-length k 1; }这个去重算法要求表是有序的。它的巧妙之处在于k始终指向已经处理好的部分的最后一个元素i负责扫描。遇到和data[k]不同的元素就把它接到k后面。整个过程只遍历一次时间复杂度 O(n)。4.5 测试用例怎么设计才全面写完代码只是第一步测试才是保证正确性的关键。我建议至少覆盖这几类用例测试场景输入预期结果空表插入空表位置 0值 5成功表变为 [5]表尾插入[1,2,3]位置 3值 4成功表变为 [1,2,3,4]表头插入[1,2,3]位置 0值 0成功表变为 [0,1,2,3]非法位置插入[1,2,3]位置 5值 9失败表不变表满插入满表任意位置失败表不变空表删除空表位置 0失败表不变删除表尾[1,2,3]位置 2成功表变为 [1,2]删除表头[1,2,3]位置 0成功表变为 [2,3]非法位置删除[1,2,3]位置 3失败表不变查找存在的值[1,2,3]查找 2返回下标 1查找不存在的值[1,2,3]查找 9返回 -1把这些用例都跑一遍基本能覆盖 90% 的边界情况。剩下的就是组合操作比如连续插入删除、合并后再去重等等。5. 常见问题与排查技巧实录5.1 段错误与下标越界段错误是顺序表实验里最常见的崩溃原因几乎都是下标越界导致的。比如插入时pos传了个负数或者删除时pos等于length都会访问到非法内存。排查方法在插入和删除函数的开头加上位置检查并且用printf把pos和length打出来看看是不是超出了预期范围。另外循环的边界也要仔细检查比如插入的循环for (j length; j pos; j--)如果写成j pos就会多挪一次把data[pos-1]也覆盖掉。提示C 语言不会帮你检查数组越界越界访问可能不崩溃但结果错误也可能直接崩溃。所以每次写涉及下标的代码都要在脑子里过一遍边界值。5.2 长度维护错误的连锁反应length是顺序表的灵魂变量它错了后面全错。常见的错误有三种插入后忘了加一、删除后忘了减一、清空时忘了置零。这些错误不会立刻崩溃但会让后续操作基于错误的状态进行最终结果面目全非。排查方法每次操作后都打印length和整个表对比预期。如果发现打印出来的元素个数和length不一致或者length和实际数据对不上那就是长度维护出了问题。养成操作后立即验证的习惯能第一时间发现这类 bug。5.3 移动方向搞反导致的数据覆盖插入要从后往前挪删除要从前往后挪这两个方向搞反了数据就会被覆盖。这个错误很隐蔽因为程序不会崩溃只是结果不对。排查方法拿一个小例子手动模拟。比如表是 [1,2,3]要在位置 1 插入 9。正确过程是先把 3 挪到位置 3再把 2 挪到位置 2然后位置 1 放 9结果是 [1,9,2,3]。如果你从前往后挪先把 1 挪到位置 1覆盖了 2再把 2 挪到位置 2覆盖了 3结果就乱了。手动模拟一遍方向对不对立刻就清楚了。5.4 动态分配版本的内存问题如果你写的是动态分配版本还要额外注意内存问题。初始化时malloc失败没检查、扩容后旧指针没释放、程序结束时没free这些都是常见问题。int initList(SeqList *L, int initCapacity) { L-data (int *)malloc(sizeof(int) * initCapacity); if (L-data NULL) return 0; // 申请失败 L-length 0; L-capacity initCapacity; return 1; } void destroyList(SeqList *L) { free(L-data); L-data NULL; L-length 0; L-capacity 0; }扩容的时候先申请一块更大的内存把旧数据拷过去再释放旧内存最后更新指针和容量。顺序不能错否则要么内存泄漏要么访问已释放的内存。5.5 常见问题速查表现象可能原因排查方向程序崩溃段错误下标越界、空指针解引用检查 pos 范围、指针是否为空结果末尾多出脏数据删除后未减 length检查删除函数的 length--插入后数据错乱移动方向反了检查循环是从后往前还是从前往后表满判断失效用了 length 和 MAXSIZE 比较但写反了检查 isFull 的返回值动态版本崩溃扩容后指针未更新、内存泄漏检查 malloc/free 配对查找总是返回 -1循环边界写错、比较用错检查循环条件和比较运算符6. 从实验一到后续学习的衔接顺序表这个实验做完你手里就有了一套完整的线性表操作代码。别急着丢掉后面学链表的时候把同样的操作在链表上实现一遍对比两者的差异你会对存储结构决定操作效率这件事有更深的体会。比如按位置查找顺序表 O(1)链表 O(n)插入删除顺序表 O(n)链表 O(1)前提是已经定位到位置。再往后学栈和队列你会发现它们都可以基于顺序表或链表实现。顺序栈就是限制了插入删除位置的顺序表顺序队列就是加了队头队尾指针的顺序表。所以顺序表是很多数据结构的基础把它吃透后面会轻松很多。我个人在做这个实验的时候最大的收获不是写出了能跑的代码而是养成了先想清楚边界再动手写的习惯。每次写一个操作先问自己空表怎么办满表怎么办位置在头、在尾、在中间分别怎么处理把这些想清楚了代码自然就对了。这个习惯后来帮我省了无数调试时间。最后分享一个小技巧如果你觉得某个操作逻辑绕就拿一张纸画几个格子代表数组手动模拟一遍。比如插入操作画 5 个格子标上 1 到 5然后一步步挪把每一步的下标变化写下来。模拟一遍之后循环怎么写就一目了然了。这个方法看起来笨但对理解算法特别有效尤其是后面学树和图的遍历时画图模拟几乎是必备技能。
1. 为什么顺序表是数据结构的第一道坎1.1 从一次课堂翻车说起我带过几届数据结构实验课几乎每届都有学生在顺序表这个实验上栽跟头。印象最深的是一个学生代码写完了编译也过了运行起来插入几个元素看着也正常结果一到删除操作就出问题——删完最后一个元素再打印一遍末尾莫名其妙多出一个旧值。他盯着屏幕看了半小时最后发现是删除时只把后面的元素往前挪了忘了把有效长度减一末尾那个幽灵元素其实早就该被逻辑丢弃了。这个场景特别典型。顺序表看起来简单无非就是数组加一个长度变量但真正动手写的时候边界条件、下标越界、长度维护、内存管理每一个细节都能让人翻车。它之所以被安排成实验一不是因为简单而是因为它把数据结构最核心的几个思维习惯一次性全塞给你了逻辑结构和存储结构的对应关系、操作的时间复杂度意识、边界条件的严谨处理、以及用代码精确表达算法的能力。这篇文章我会把顺序表实验从设计思路到代码实现、从踩坑记录到调试技巧完整地拆一遍。不管你是正在做这个实验的学生还是想重新夯实基础的自学者都能直接拿去参考。我会尽量把每个为什么这么做讲透而不是只丢一段代码让你抄。1.2 顺序表到底在解决什么问题先说清楚顺序表是什么。顺序表是用一段地址连续的内存单元依次存储线性表的数据元素。说白了就是用一个数组存数据再用一个变量记录当前存了多少个元素。它的逻辑结构是线性的——每个元素有唯一的前驱和后继除了首尾而它的存储结构也是线性的——元素在内存里一个挨着一个。为什么要有顺序表因为很多场景下我们需要按位置快速访问的能力。比如你要做一个学生成绩管理系统想直接查第 5 个学生的成绩顺序表能做到 O(1) 的时间复杂度因为下标一算就定位到了。这是链表做不到的链表你得从头一个个数过去。但顺序表也有它的代价。插入和删除的时候为了保持元素的连续性往往需要移动大量元素平均时间复杂度是 O(n)。所以顺序表适合查多改少的场景比如成绩表、配置项列表、固定大小的缓冲区。理解这个取舍是理解整个线性表体系的第一步。1.3 这个实验适合谁、能学到什么这个实验的定位是入门级但它的知识密度不低。适合的人群包括正在上数据结构课的学生、准备考研复试要手写代码的同学、以及工作后想补基础的程序员。你不需要多深的编程功底会基本的 C 或 C 语法就够了但你需要有耐心去抠每一个边界条件。学完这个实验你应该能掌握几件事第一能用代码定义一个顺序表结构体并说清楚每个成员变量的作用第二能实现初始化、插入、删除、查找、遍历这几个基本操作并分析它们的时间复杂度第三能处理各种边界情况比如空表删除、表满插入、位置非法等第四能把这些操作组合起来解决一个实际问题比如两个有序表的合并。这些能力看起来基础但它们是后面学链表、栈、队列、树、图的地基。地基没打牢后面全是空中楼阁。2. 实验整体设计与思路拆解2.1 用数组还是动态分配存储方案的选择顺序表的实现有两种常见路线。一种是静态分配直接定义一个固定大小的数组比如int data[100]再配一个length记录当前元素个数。另一种是动态分配用指针加malloc在运行时申请内存容量不够时可以扩容。静态分配写起来简单适合实验课上快速验证算法逻辑。但它的缺点很明显容量写死了存满了就没法再加。动态分配更灵活也更接近真实工程里的用法但要多处理内存申请失败、扩容、释放这些事对初学者来说容易出错。我的建议是实验一先用静态分配把逻辑跑通理解清楚每个操作的原理然后再用动态分配重写一遍。这样你能对比两种方式的差异也能体会到存储结构的选择会影响代码复杂度这件事。很多同学一上来就写动态分配结果指针操作出错连基本的插入都没调通反而耽误时间。如果你用 C还可以用vector或者自己封装一个类把data和length藏起来只暴露操作接口。这就是**抽象数据类型ADT**的思想——使用者不需要知道内部怎么存的只需要知道能做什么操作。这个思想贯穿整个数据结构课程早点建立起来有好处。2.2 结构体怎么定义才合理不管静态还是动态顺序表的核心信息就两样存数据的容器和当前元素个数。用结构体把它们绑在一起是最自然的做法。静态版本大概长这样#define MAXSIZE 100 typedef struct { int data[MAXSIZE]; int length; } SeqList;这里MAXSIZE是最大容量length是当前实际元素个数。注意区分这两个概念容量是最多能装多少长度是现在装了多少。很多 bug 就出在把这两个搞混了比如判断表满的时候用错了变量。动态版本则是typedef struct { int *data; int length; int capacity; } SeqList;多了一个capacity记录当前申请的容量。初始化时先申请一块内存插入时如果length capacity就扩容。扩容一般按 1.5 倍或 2 倍增长这样均摊下来插入操作还是 O(1) 的。为什么是 1.5 或 2 倍而不是每次加 1因为每次加 1 会导致频繁申请和拷贝总代价变成 O(n²)而按倍数增长能让总代价摊薄到 O(n)。提示结构体里的成员顺序会影响内存对齐但对这个实验来说影响可以忽略不用纠结。真正要纠结的是length的语义——它既是元素个数也是下一个可插入位置的下标这个双重身份要时刻记牢。2.3 操作接口的设计原则一个完整的顺序表应该提供哪些操作至少包括初始化、判空、判满、按位置插入、按位置删除、按值查找、按位置取值、遍历输出、求长度、清空。如果做应用扩展还要加上合并、去重、逆置这些。设计接口的时候有个原则每个函数只做一件事并且把边界检查放在函数内部。比如插入函数进来先判断位置是否合法、表是否已满不合法就返回错误码合法才执行插入。这样调用者就不用每次都自己检查代码更干净也更不容易出错。返回值的设计也有讲究。C 语言里没有异常机制所以通常用返回值表示成功或失败比如返回 1 表示成功、0 表示失败或者用枚举类型定义一组错误码。取值操作则通过指针参数把结果带出来。这种返回值表状态、指针参数带结果的模式在数据结构代码里非常常见要习惯它。3. 核心操作的原理与实操要点3.1 插入操作为什么从后往前挪插入是顺序表里第一个需要移动元素的操作。假设表里有n个元素要在第i个位置下标从 0 开始算的话就是下标i插入一个新元素那么从下标i到n-1的所有元素都要往后挪一位腾出位置。关键在于移动的方向。必须从最后一个元素开始依次往后挪也就是从data[n-1]挪到data[n]data[n-2]挪到data[n-1]一直到data[i]挪到data[i1]。如果反过来从前往后挪data[i]会先覆盖掉data[i1]后面的数据就全丢了。int listInsert(SeqList *L, int pos, int value) { if (pos 0 || pos L-length) return 0; // 位置非法 if (L-length MAXSIZE) return 0; // 表已满 for (int j L-length; j pos; j--) { L-data[j] L-data[j - 1]; } L-data[pos] value; L-length; return 1; }注意pos的合法范围是0到length不是0到length-1。因为你可以插在最后一个元素的后面也就是插到表尾。这个多一个位置的细节是初学者最容易搞错的地方之一。时间复杂度方面最好情况是插在表尾不用移动O(1)最坏情况是插在表头要移动全部 n 个元素O(n)平均移动 n/2 个元素所以平均时间复杂度是 O(n)。3.2 删除操作别忘了把长度减一删除和插入是镜像操作。删除第i个位置的元素需要把下标i1到n-1的元素全部往前挪一位覆盖掉被删的元素。这次移动方向是从前往后因为前面的位置空出来了后面的元素往前填。int listDelete(SeqList *L, int pos, int *e) { if (pos 0 || pos L-length) return 0; // 位置非法 *e L-data[pos]; // 把被删的值带出去 for (int j pos; j L-length - 1; j) { L-data[j] L-data[j 1]; } L-length--; // 长度减一 return 1; }这里pos的合法范围是0到length-1因为你要删的元素必须存在。和插入不同删除没有多一个位置的说法。我前面提到的那个学生就是漏了L-length--这一行。长度不减程序就认为末尾还有一个有效元素但那个位置的数据其实已经被逻辑丢弃了打印出来就是脏数据。这个 bug 不会导致崩溃但会让结果错误比崩溃更难查。3.3 查找与取值按位置和按值的区别查找分两种。按位置查找也叫取值是给定下标直接返回data[pos]时间复杂度 O(1)这是顺序表最大的优势。按值查找是给定一个值从头遍历找到第一个匹配的元素返回它的下标时间复杂度 O(n)。int getElem(SeqList L, int pos, int *e) { if (pos 0 || pos L.length) return 0; *e L.data[pos]; return 1; } int locateElem(SeqList L, int value) { for (int i 0; i L.length; i) { if (L.data[i] value) return i; } return -1; // 没找到 }按值查找返回 -1 表示没找到这是一个约定。但要注意如果表里存的值本身可能是负数用 -1 表示没找到就有歧义了。更严谨的做法是返回一个布尔值表示是否找到下标通过指针参数带出来。这种细节在工程里很重要实验里可以先简单处理但心里要有数。3.4 遍历与打印调试的好帮手遍历就是从头到尾访问每个元素。它本身很简单但在调试阶段极其重要。每次做完插入或删除都打印一遍整个表能立刻看出结果对不对。void printList(SeqList L) { printf(List (length%d): , L.length); for (int i 0; i L.length; i) { printf(%d , L.data[i]); } printf(\n); }打印的时候把length也带上这样你能同时看到逻辑长度和实际数据。如果发现打印出来的元素个数和length对不上那基本就是长度维护出了问题。注意调试时不要只打印data数组的前几个元素一定要按length来打印。因为数组里超出length的部分是无效数据打印出来只会干扰判断。4. 完整实操流程与代码实现4.1 从零搭建文件结构与编译我习惯把顺序表的代码分成三个文件seqlist.h放结构体定义和函数声明seqlist.c放函数实现main.c放测试代码。这样结构清晰也方便后面复用。如果你用的是集成开发环境直接建一个工程把三个文件加进去就行如果用的是命令行编译命令大概是这样gcc main.c seqlist.c -o seqlist_test ./seqlist_test分文件的好处是头文件里只暴露接口实现细节藏在.c文件里。别人用你的顺序表只需要#include seqlist.h不需要关心内部怎么实现的。这就是封装。4.2 初始化与基础操作实现初始化就是把length置为 0。静态分配的话数组本身已经存在了不需要额外申请内存。void initList(SeqList *L) { L-length 0; }判空和判满也很简单int isEmpty(SeqList L) { return L.length 0; } int isFull(SeqList L) { return L.length MAXSIZE; }这几个函数虽然简单但它们是其他操作的基础。插入前要判满删除前要判空养成操作前先检查状态的习惯能避免大量边界 bug。4.3 应用一两个有序顺序表的合并基本操作跑通之后就该做应用了。最经典的应用是合并两个有序顺序表。给定两个非递减排列的顺序表 A 和 B要求合并成一个新的非递减顺序表 C。思路是用两个指针分别指向 A 和 B 的当前元素比较大小小的先放进 C然后对应指针后移。当一个表走完了把另一个表剩下的元素全部追加到 C 后面。void mergeList(SeqList A, SeqList B, SeqList *C) { int i 0, j 0, k 0; while (i A.length j B.length) { if (A.data[i] B.data[j]) { C-data[k] A.data[i]; } else { C-data[k] B.data[j]; } } while (i A.length) C-data[k] A.data[i]; while (j B.length) C-data[k] B.data[j]; C-length k; }这个算法的时间复杂度是 O(mn)其中 m 和 n 分别是两个表的长度。因为每个元素只被访问一次。空间复杂度是 O(mn)因为要开一个新表存结果。如果要求原地合并把 B 合并进 A那就复杂一些需要从后往前处理避免覆盖未处理的元素。4.4 应用二就地逆置与去重就地逆置是把表里的元素顺序反过来要求空间复杂度 O(1)。做法是用两个指针一个指向头一个指向尾交换它们的值然后向中间靠拢直到相遇。void reverseList(SeqList *L) { int i 0, j L-length - 1; while (i j) { int temp L-data[i]; L-data[i] L-data[j]; L-data[j] temp; i; j--; } }去重是删除表中重复的元素只保留第一个出现的。如果表是有序的可以用双指针法一个指针记录当前保留的最后一个元素的位置另一个指针遍历。如果表是无序的通常用双重循环时间复杂度 O(n²)。void removeDuplicates(SeqList *L) { int k 0; // k 是当前保留的最后一个元素的下标 for (int i 1; i L-length; i) { if (L-data[i] ! L-data[k]) { k; L-data[k] L-data[i]; } } L-length k 1; }这个去重算法要求表是有序的。它的巧妙之处在于k始终指向已经处理好的部分的最后一个元素i负责扫描。遇到和data[k]不同的元素就把它接到k后面。整个过程只遍历一次时间复杂度 O(n)。4.5 测试用例怎么设计才全面写完代码只是第一步测试才是保证正确性的关键。我建议至少覆盖这几类用例测试场景输入预期结果空表插入空表位置 0值 5成功表变为 [5]表尾插入[1,2,3]位置 3值 4成功表变为 [1,2,3,4]表头插入[1,2,3]位置 0值 0成功表变为 [0,1,2,3]非法位置插入[1,2,3]位置 5值 9失败表不变表满插入满表任意位置失败表不变空表删除空表位置 0失败表不变删除表尾[1,2,3]位置 2成功表变为 [1,2]删除表头[1,2,3]位置 0成功表变为 [2,3]非法位置删除[1,2,3]位置 3失败表不变查找存在的值[1,2,3]查找 2返回下标 1查找不存在的值[1,2,3]查找 9返回 -1把这些用例都跑一遍基本能覆盖 90% 的边界情况。剩下的就是组合操作比如连续插入删除、合并后再去重等等。5. 常见问题与排查技巧实录5.1 段错误与下标越界段错误是顺序表实验里最常见的崩溃原因几乎都是下标越界导致的。比如插入时pos传了个负数或者删除时pos等于length都会访问到非法内存。排查方法在插入和删除函数的开头加上位置检查并且用printf把pos和length打出来看看是不是超出了预期范围。另外循环的边界也要仔细检查比如插入的循环for (j length; j pos; j--)如果写成j pos就会多挪一次把data[pos-1]也覆盖掉。提示C 语言不会帮你检查数组越界越界访问可能不崩溃但结果错误也可能直接崩溃。所以每次写涉及下标的代码都要在脑子里过一遍边界值。5.2 长度维护错误的连锁反应length是顺序表的灵魂变量它错了后面全错。常见的错误有三种插入后忘了加一、删除后忘了减一、清空时忘了置零。这些错误不会立刻崩溃但会让后续操作基于错误的状态进行最终结果面目全非。排查方法每次操作后都打印length和整个表对比预期。如果发现打印出来的元素个数和length不一致或者length和实际数据对不上那就是长度维护出了问题。养成操作后立即验证的习惯能第一时间发现这类 bug。5.3 移动方向搞反导致的数据覆盖插入要从后往前挪删除要从前往后挪这两个方向搞反了数据就会被覆盖。这个错误很隐蔽因为程序不会崩溃只是结果不对。排查方法拿一个小例子手动模拟。比如表是 [1,2,3]要在位置 1 插入 9。正确过程是先把 3 挪到位置 3再把 2 挪到位置 2然后位置 1 放 9结果是 [1,9,2,3]。如果你从前往后挪先把 1 挪到位置 1覆盖了 2再把 2 挪到位置 2覆盖了 3结果就乱了。手动模拟一遍方向对不对立刻就清楚了。5.4 动态分配版本的内存问题如果你写的是动态分配版本还要额外注意内存问题。初始化时malloc失败没检查、扩容后旧指针没释放、程序结束时没free这些都是常见问题。int initList(SeqList *L, int initCapacity) { L-data (int *)malloc(sizeof(int) * initCapacity); if (L-data NULL) return 0; // 申请失败 L-length 0; L-capacity initCapacity; return 1; } void destroyList(SeqList *L) { free(L-data); L-data NULL; L-length 0; L-capacity 0; }扩容的时候先申请一块更大的内存把旧数据拷过去再释放旧内存最后更新指针和容量。顺序不能错否则要么内存泄漏要么访问已释放的内存。5.5 常见问题速查表现象可能原因排查方向程序崩溃段错误下标越界、空指针解引用检查 pos 范围、指针是否为空结果末尾多出脏数据删除后未减 length检查删除函数的 length--插入后数据错乱移动方向反了检查循环是从后往前还是从前往后表满判断失效用了 length 和 MAXSIZE 比较但写反了检查 isFull 的返回值动态版本崩溃扩容后指针未更新、内存泄漏检查 malloc/free 配对查找总是返回 -1循环边界写错、比较用错检查循环条件和比较运算符6. 从实验一到后续学习的衔接顺序表这个实验做完你手里就有了一套完整的线性表操作代码。别急着丢掉后面学链表的时候把同样的操作在链表上实现一遍对比两者的差异你会对存储结构决定操作效率这件事有更深的体会。比如按位置查找顺序表 O(1)链表 O(n)插入删除顺序表 O(n)链表 O(1)前提是已经定位到位置。再往后学栈和队列你会发现它们都可以基于顺序表或链表实现。顺序栈就是限制了插入删除位置的顺序表顺序队列就是加了队头队尾指针的顺序表。所以顺序表是很多数据结构的基础把它吃透后面会轻松很多。我个人在做这个实验的时候最大的收获不是写出了能跑的代码而是养成了先想清楚边界再动手写的习惯。每次写一个操作先问自己空表怎么办满表怎么办位置在头、在尾、在中间分别怎么处理把这些想清楚了代码自然就对了。这个习惯后来帮我省了无数调试时间。最后分享一个小技巧如果你觉得某个操作逻辑绕就拿一张纸画几个格子代表数组手动模拟一遍。比如插入操作画 5 个格子标上 1 到 5然后一步步挪把每一步的下标变化写下来。模拟一遍之后循环怎么写就一目了然了。这个方法看起来笨但对理解算法特别有效尤其是后面学树和图的遍历时画图模拟几乎是必备技能。
平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测)
