1. 从C语言到数据结构先搞清楚这门课到底在解决什么问题很多自学者都会经历这样一个时刻C语言的语法学得差不多了指针虽然绕但能用结构体也会写了文件操作、内存管理这些虽然不熟但至少知道是怎么回事。然后翻开数据结构教材看到第一章的顺序表——心里冒出的第一个念头往往是这不就是数组吗C语言不是早就会数组了吗为什么还要专门学一遍这个疑问非常正常也恰恰点中了数据结构这门课的核心价值。C语言教的是怎么写代码数据结构教的是怎么组织数据。同样是存一百个学生的成绩用普通数组能存用结构体数组也能存但当你要往里插入一条记录、删掉一条记录、按学号查找某个人的信息时数据摆放方式不同代码的复杂度和运行速度可能差出几个数量级。数据结构解决的就是这类问题的通用方案。它不关心你的数据是学生成绩还是商品价格只关心数据之间的逻辑关系和存储方式。顺序表是所有数据结构里最基础的一种因为它最贴近我们已有的认知——它就是在连续的内存空间里顺序存放一组数据元素。换句话说你学会C语言数组的那一刻其实已经掌握了顺序表的存储形态但离真正掌握顺序表还差一层把数组和它的操作封装成一套完整、可复用、边界安全的机制。所以我建议所有C语言学习者在学数据结构的时候把心态从我会不会写代码切换成我这套设计能不能经得起推敲。顺序表这个入门项目表面上代码量不大但它涵盖了数据结构的三种核心能力怎么定义结构、怎么设计操作、怎么分析效率。把这三件事理顺了后面的链表、栈、队列、树学起来都是顺水推舟的事。这篇文章会完整拆解顺序表的每一个核心操作从结构体定义到初始化、插入、删除、查找、销毁代码是完整的C语言实现每一步都会解释设计理由。也会把我在实际调试中遇到的崩溃现场、边界条件问题讲清楚这些是教材和很多教程里不会细写的东西。2. 顺序表的本质为什么数组加几个变量就能被称为一种数据结构2.1 从硬币收纳盒理解顺序表的三个核心字段如果我们把顺序表拆到不能再拆它其实就是一块连续的内存 记录已经存了几个元素的变量 记录这块内存能存几个元素的变量。这三样东西一个都不能少。打个比方。你有一个长条形的硬币收纳盒盒子有十个槽位——这十个槽位就是内存空间。你往里放了四个硬币——这个数量就是当前长度。收纳盒总共能装十个硬币——这个上限就是容量。少了当前长度这个变量你就不知道里面到底有几个硬币只能靠数少了容量这个变量你往里塞第十一个硬币的时候就不知道盒子已经满了。顺序表的设计就是把这个简单的物理模型抽象成C语言里的结构体。典型的结构体定义是这样的#define INIT_CAPACITY 8 // 初始容量 typedef struct { int *data; // 指向动态分配的内存空间 int length; // 当前元素个数 int capacity; // 当前分配的空间能容纳的元素个数 } SeqList;为什么要用int *data而不是直接定义一个定长数组int data[100]这个设计选择后面会展开讲核心原因是为了让顺序表的大小可以根据需要动态调整而不是一上来就锁死成某个固定值。术语上需要先统一一下。length在数据结构里叫表长就是当前实际存了多少个元素。capacity叫容量是最多能存多少个元素。很多初学会把这两个概念搞混写循环的时候用错了要么访问越界要么漏掉最后一个元素。这两个字段的含义和区别是顺序表所有操作的基础务必记牢。2.2 逻辑结构和物理结构顺序表为什么叫顺序表数据结构这门课里顺序这个词特指物理存储上的连续。也就是说第0个元素和第1个元素在内存里是紧挨着的第1个和第2个也是紧挨着的以此类推。这种一个挨一个的存储关系在C语言里天然对应数组。但这里要区分两个概念逻辑结构和物理结构。逻辑结构是指数据之间的抽象关系——在顺序表里元素之间有前驱和后继的关系比如第3个元素的前驱是第2个后继是第4个。物理结构是指数据在内存里的实际摆放方式——顺序表的物理摆放就是连续的数组。有的同学会问连续摆放有什么好处最大的好处是随机访问。你要访问第5个元素只要知道起始地址加上5乘每个元素的大小马上就能算出第5个元素的内存地址跳到那里取值。这个操作的时间消耗是固定的跟表里有多少个元素没关系。我们用大O记号表示就是O(1)复杂度。这个特性在后面的章节会反复用到。插入和删除为什么慢也是因为连续这个要求——往中间插一个元素后面的所有元素都得往后挪给新元素腾地方。要维持连续这个性质就必须付出挪动的代价。顺序表的快和慢本质上都来自连续这两个字。2.3 静态分配与动态分配数据结构教材里的路线分岔我见过很多教材和网课在顺序表这一节会给出两种实现方式一种是定长数组一种是动态分配内存。初学者往往觉得两种都行直接跳过了这个差别。实际上这背后是对数据结构应该具备什么能力的不同理解。静态分配版本是这样写的#define MAX_SIZE 100 typedef struct { int data[MAX_SIZE]; int length; } SeqList;问题在于MAX_SIZE定多少合适定小了往里插数据时满了怎么办没空间了程序要么报错要么只能忽略新数据。定大了比如定10000但实际只用了10个多余的空间白白占着浪费内存。静态分配最大的毛病就是不够灵活它把一个应该根据实际情况动态调整的需求提前锁死在了编译期。动态分配版本则允许我们运行时申请内存、空间不够了重新申请一块更大的、用完后释放。这更贴近真实项目的需要因为真实场景下你往往不知道数据量会涨到多大。我在写C语言项目时几乎不会为了存放数据而使用固定大小的数组动态分配是基本操作。既然要讲透顺序表那必须用动态分配版本。这也是从C语言存储期概念过渡到数据结构存储结构概念的一个自然衔接——C语言的内存管理能力在这里第一次有了明确的应用场景。3. 顺序表核心操作逐行拆解从初始化到销毁的完整实现3.1 初始化malloc之后一定要做的事情初始化是顺序表的第一道生命周期也是最容易出错的地方。很多同学的代码在初始化这一步就埋下了隐患malloc了内存但没检查是否成功分配完没给capacity赋值结果后面length明明可以增长但程序自己都不知道上限在哪。标准做法分三步分配内存、检查分配结果、设置初始状态。#include stdio.h #include stdlib.h #define INIT_CAPACITY 8 typedef struct { int *data; int length; int capacity; } SeqList; // 初始化顺序表 void SeqList_Init(SeqList *list) { list-data (int *)malloc(sizeof(int) * INIT_CAPACITY); if (list-data NULL) { printf(内存分配失败\n); exit(1); } list-length 0; list-capacity INIT_CAPACITY; }为什么把list设计成指针而不是直接传值因为C语言是值传递如果直接传一个SeqList list进去函数内部修改的是那份拷贝出了函数就丢了。所以这里必须传地址SeqList *list才能让初始化真正作用到外部的顺序表上。malloc返回的是void *我们在前面加了(int *)强制转换。在C语言里这个转换可以省略但写上更明确——省得读到代码时还要想一下这块内存是按什么类型来用的。检查返回值那个if是必须的malloc不是每次都能成功的内存不足时会返回NULL如果不检查直接往下用等于对空指针解引用运行时会直接崩溃。3.2 插入操作为什么必须从最后一个元素开始往后挪顺序表的插入是初学阶段理解挪动元素这个概念的第一个窗口。在位置pos我们约定用下标表示从0开始插入一个新元素val标准的操作序列是先判断参数是否合法、检查容量是否够、从最后一个元素开始逐个往后复制、腾出位置后放入新元素、更新长度。没有经验的代码往往会写成这样找到位置后直接从前向后挪结果把后面的元素都覆盖了。比如data[i1] data[i]第一次执行就把第i1位的值覆盖成了第i位的后面的数据全乱了。正确做法是从后往前挪先把最后一个往后移再把倒数第二个移到倒数第一个的位置——后移的过程中始终不会覆盖还没处理的值。// 在指定下标位置插入元素 val void SeqList_Insert(SeqList *list, int pos, int val) { // 1. 判断插入位置是否合法 if (pos 0 || pos list-length) { printf(插入位置非法\n); return; } // 2. 如果空间不够先扩容 if (list-length list-capacity) { SeqList_Expand(list); } // 3. 从后往前依次后移元素 for (int i list-length - 1; i pos; i--) { list-data[i 1] list-data[i]; } // 4. 放入新值更新长度 list-data[pos] val; list-length; }关于位置合法性的判断有一个细节值得多说两句。pos允许等于list-length吗允许。因为这意味着在表的末尾追加元素。所以合法范围是0到length是一个闭开区间。很多同学会把边界写错要么漏了pos length导致没办法用同一个函数在尾部追加要么写了pos list-length导致尾部追加直接报错。3.3 删除操作前移的覆盖逻辑与先用再减的陷阱删除操作和插入是镜像的。删除位置pos的元素需要把pos之后的元素全部往前移一位然后长度减一。这个逻辑看起来很简单但里面藏着初学者最容易犯错的一个点移动方向。插入要从后往前移删除要从前往后移。为什么因为删除是把后面的值往前覆盖你从pos开始执行data[i] data[i1]等于用后面一个值覆盖当前的值下一轮循环再用再后面的值覆盖刚才那个位置——这个链条是安全的不会丢数据。如果反过来从后往前移后面的值会先覆盖掉前面的数据丢失。完整代码// 删除指定下标的元素 void SeqList_Delete(SeqList *list, int pos) { // 1. 检查位置是否合法 if (pos 0 || pos list-length) { printf(删除位置非法\n); return; } // 2. 从前往后前移元素 for (int i pos; i list-length - 1; i) { list-data[i] list-data[i 1]; } // 3. 长度减一 list-length--; }我在初学的时候最喜欢在删除操作里犯的错是循环结束后没有list-length--。这会导致一个问题——逻辑上你删了一个元素但表里实际记录的还是原来的长度。后面遍历的时候最后一个元素会幽灵复现因为它的值还在内存里躺着长度又没减少所以会被打印出来。这种bug不算崩溃但数据完全不对排查起来也很费劲。这里还有一个值得养成的习惯删除末尾元素后data[length]这个位置的值其实还留在内存里但逻辑上它已经不属于这个表了。我们通过length来界定哪些位置有效凡是index length的位置都视为无效数据。这个思维方式在后面的栈、队列里会反复用到。3.4 按值查找与按位访问顺序表最引以为傲的O(1)能力顺序表有两种最常见的查询按下标访问以及按值查找。按下标访问很简单list-data[i]就是。因为数组是连续存储的地址计算是起始地址 i * sizeof(int)这个计算和i的大小无关所以无论表里有一万个元素还是一亿个元素随机访问某个元素的时间都是一样的也就是O(1)复杂度。这是顺序表相对于链表的绝对优势。按值查找就是给定一个值找到它第一次出现的位置// 查找第一个值为 val 的元素返回下标找不到返回 -1 int SeqList_Find(SeqList *list, int val) { for (int i 0; i list-length; i) { if (list-data[i] val) { return i; } } return -1; }这个代码很直白但有两个点值得注意。第一返回值设计。我用-1表示没有找到。为什么不用0因为0是合法下标第0个位置是可以存数据的如果用0表示没找到那么第0个位置恰好是目标值时你无法区分是找到了第0个还是没找到。所以负数作为失败标志是合理的选择。这个返回值设计要能区分成功与失败的思路在之后写栈、队列的Pop操作时会反复出现。第二这个操作的时间复杂度是O(n)。因为最坏情况下你要扫描完整个表才知道值存不存在。这也是顺序表这个名字的另一层含义的代价——顺序访问。你在写程序时要能判断出某段代码是被高频调用的如果在一个大表上频繁做按值查找O(n)的代价可能成为性能瓶颈那时候可能就需要考虑哈希表之类的方案了。3.5 扩容机制倍增法为什么是够用且不浪费的折中方案前面在插入操作里提到了SeqList_Expand这是动态内存管理最关键的部分需要单独展开讲。扩容的思路是当length capacity时说明当前内存已经满了此时重新申请一块更大的内存把旧数据搬过去然后释放旧内存并使用新内存。直接上代码void SeqList_Expand(SeqList *list) { // 容量翻倍 int new_capacity list-capacity * 2; int *new_data (int *)malloc(sizeof(int) * new_capacity); 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而不是每次加10个或者每次加100个这里有个摊还分析的思想——虽然单次扩容要拷贝全部元素、开销不小但如果每次都翻倍那么分摊到每一次插入上的平均成本非常低近似O(1)。反过来如果固定加10个容量那每插入10次就要扩容一次扩容时要把前面所有元素都拷贝一遍累积成本会越来越高整体插入复杂度会退化到O(n)。倍增法也有边界问题如果初始容量是1每次翻倍那么从1到2、到4、到8……一旦元素数量接近2的某次幂下一次扩容就是一次全部拷贝。但这个拷贝是有摊销的平均下来依然是可接受的。实际工程里很多动态数组也是采用类似的倍增策略只是倍率不同有的是1.5倍、有的是2倍。扩容的时候还有几个细节需要养成习惯realloc可以合并分配新内存、拷贝旧数据、释放旧内存三步但很多教材不用它原因是realloc在扩容失败时会返还NULL这个时候原本的内存可能已经被释放或者处于不可用状态处理起来要格外小心。用malloc 手动拷贝 free的方式虽然代码长一点但每一步都在掌控之中对初学者更友好。释放旧内存那行free(list-data)不要漏。经典的内存泄漏案例就是这样来的不断扩容但不释放旧的内存块程序跑着跑着内存越占越多最后被系统杀掉。写完扩容函数后配合调试器或者valgrind工具跑一遍确认没有泄漏这是一个很重要的习惯。3.6 遍历打印与销毁一个表完整的生命周期管理有了上面的基础操作打印和销毁就顺理成章了。打印函数的主要价值在于每次操作后打印一下能肉眼确认数据是否符合预期这是初学阶段最直观的调试手段。// 打印顺序表所有元素 void SeqList_Print(SeqList *list) { printf([); for (int i 0; i list-length; i) { printf(%d, list-data[i]); if (i list-length - 1) { printf(, ); } } printf(]\n); } // 销毁顺序表 void SeqList_Destroy(SeqList *list) { free(list-data); list-data NULL; list-length 0; list-capacity 0; }销毁函数的价值容易被忽略。初学写小程序时确实无所谓程序退出后操作系统会回收所有内存。但一旦进入真实项目和后续的课程设计长生命周期程序里反复创建、销毁数据结构不写销毁函数的后果就是内存泄漏。free之后把指针置为NULL也是一个重要习惯——防止后续代码误用一个已经释放的指针也就是悬空指针问题。这里顺带提一下data指针在free后置NULL的另一个好处如果后面不小心再次free(list-data)对NULL指针执行free是安全的程序不会崩。但如果你忘记置NULL又碰巧再次freeC标准说是未定义行为实际运行中往往会在内存管理环节崩溃而且崩溃的位置和原因相隔很远排错非常痛苦。4. 教科书不会明说的崩溃现场这些坑我都替你踩过了4.1 那个让我调试了两个小时的非法地址访问顺序表入门阶段遇到最多的运行时错误就是在终端里蹦出来一句Segmentation fault或者Process returned -1073741819Windows上常见前者是段错误后者在Windows下通常对应0xC0000005访问冲突。两个都指向同一类问题访问了不属于你的内存。最常见的场景是初始化顺序表之后没有调用SeqList_Init直接调用SeqList_Insert。这时候list-data是一个未初始化的垃圾值——可能指向某个随机的内存地址也可能为NULL。程序毫不知情地往这个地址写入数据于是直接崩溃。很多同学第一次遇到时会懵反复检查插入代码逻辑却忘了问题出在更早的初始化步骤。排查这类问题的思路应该是由近及远先看崩溃发生在哪个函数再逐层追溯谁调用了它。如果你用的IDE有调试器在调用栈里能看到main函数里哪一行调用了SeqList_Insert顺着步骤检查——那个list的data字段有没有被正确初始化。4.2 插入位置判定出错边界条件是数据结构最重要的细节还有一个特别容易犯的错更隐蔽插入时判断合法位置用的是if (pos 0 || pos list-length)但有人在写的时候把写成了。测试的时候如果只插到中间某个位置看不出问题一旦在尾部追加元素程序就报插入位置非法。这种bug是典型的边界条件问题平时跑正常用例一切正常一到边界情况就露馅。数据结构的学习很大一部分就是训练边界敏感性。写插入操作的时候把pos的合法区间画出来最小是0最大是length尾部追加。把所有可能取值逐个在脑海里过一遍确认合法区间。删除操作的合法区间则是0到length-1注意这里和插入不一样——删除位置不能等于length因为那个位置根本没有元素。4.3 移动方向错误的连锁反应为什么会复制出一堆重复元素移动方向错误引起的现象也很有意思。插入时如果从前往后挪结果不是崩溃而是数据错乱——某个元素值被重复了一遍另一个元素值消失了。比如数组是[1,2,3,4,5]往下标2的位置插入99如果从前往后执行data[i1]data[i]会得到[1,2,2,2,2,5]这种乱七八糟的结果。这类逻辑错误不会崩溃但输出的结果是完全错误的——而这恰恰是新手觉得最难排查的程序能跑但结果不对。排查手段就是打印输出每一个中间态。我给自己的建议是学数据结构的时候别嫌慢每一步操作后都把整个表打印一遍盯着看数据是怎么流动的。几次下来对从后往前和从前往后的理解就不再是死记硬背而是真的知道为什么了。4.4 内存泄漏与重复释放动态内存管理必须养成的三个习惯用malloc系列函数的时候有三个习惯越早养成越好。第一谁分配谁释放——在哪个函数里malloc的就要负责在合适的时机free。第二free之后把指针置NULL防止重复释放和悬空指针。第三所有动态分配的地方都要检查返回值也就是判断是否为NULL。重复释放的例子很常见第一个循环里删除了某个节点顺便free了第二个循环里又用了这个节点结果就double free程序崩溃。再比如你按值删除了一个元素但这个值对应的内存已经被别的地方释放了你没有同步置NULL后面又free了一次。C语言不会帮你检测这类错误跑起来时崩溃的位置和崩溃原因经常隔了十万八千里。valgrind --leak-checkfull ./your_program这个工具在Linux环境里是排查内存问题的神器能定位出具体的泄漏位置和非法访问行号。Windows上也可以用Visual Studio的调试模式配合CRT内存泄漏检测。我推荐初学者从第一份数据结构作业开始就养成跑内存检测的习惯这会帮你避开无数后面的痛苦。5. 为什么顺序表是快慢兼备的结构时间复杂度的真实含义5.1 O(1)与O(n)随机访问和插入删除的天然差异顺序表最核心的复杂度特征就两句话按下标访问是O(1)插入删除是O(n)。这两句话如果只当作结论背下来过两天就忘了如果理解了背后连续存储这个根本原因就永远不会忘。访问是O(1)是因为地址计算只需要一次加法和一次乘法跟表有多大无关。你要取第50万个元素和取第5个元素计算的时间是相同的。插入删除是O(n)是因为连续这个性质要求你必须给新元素腾出连续的空间或者填补删除后留下的空洞。平均来看你要移动一半的元素。如果表里有10万个元素插入一次就要移动5万个这个代价是肉眼可见的。这也是面试中经常遇到的题目为什么数组比链表更适合随机访问但链表更适合频繁插入删除答案的根源就在连续和非连续的存储方式上。顺序表用连续存储换来了O(1)的随机访问代价是插入删除要挪元素链表用指针连接换来了O(1)的插入删除假设已经定位到位置代价是随机访问必须从头遍历。5.2 存储密度顺序表为什么比链表更省内存还有一个经常被忽略但面试常提的概念是存储密度。存储密度 数据本身占用的空间 / 结点总共占用的空间。顺序表每个位置都只存元素本身没有额外的指针开销所以存储密度接近1。而链表每个节点除了存数据还要存一个指向下一个节点的指针如果数据是int4字节指针在64位系统下是8字节那存储密度就只有4/(48)≈33%——三分之二的内存花在了指路上。这个差异在实际项目中是有意义的。如果你处理的是上百万条记录每条记录是一个结构体顺序表比链表省下的内存可能就非常可观。当然链表也有它不可替代的场景比如频繁在中间插入删除、或者数据块大小不固定的时候。但从入门第一课的角度看顺序表让你先理解数据密度连续存储这些基础概念后面学链表的时候再对比理解链路就顺了。5.3 扩容的摊还分析倍增法告诉你平均时间是怎么回事前面提到的扩容采用倍增法这里把背后的摊还分析说透。假设初始容量为1要连续插入n个元素。在插入第1个时扩容到2拷贝1个元素插入第2个时扩容到4拷贝2个插入第4个时扩容到8拷贝4个。依此类推扩容的总拷贝次数是1248...n/2等比数列求和约等于n。这意味着插入n个元素的总开销大约是n次拷贝加上n次直接插入平摊下来每次插入的开销是一个常数也就是摊还O(1)。反过来如果每次都只增加固定数量的容量比如一次加10个那么每插入10次就要扩容一次每次扩容要拷贝之前所有元素总开销是1112131...是O(n²)级别的。这在数据量大了以后会非常明显地卡顿。所以倍增不是一个随意的选择它保证了动态数组在随机插到尾部时平均性能依然接近O(1)。这一点在理解vector、ArrayList这类语言内置动态数组的实现原理时同样适用。虽然这篇文章用的是C语言但很多语言里都有类似的数据结构原理是通的。6. 把顺序表用起来两个综合练习和一个面试常考题6.1 综合分析顺序表实现去重操作学完基本操作我强烈建议做两个综合练习这两个练习能检验自己对顺序表操作的掌握程度。第一个是去重给定一个顺序表把重复的元素删掉只保留第一次出现的那个。思路并不复杂遍历所有元素对每个元素看它前面的部分是否已经出现过这个值。如果没有保留如果有删掉它。由于删除操作本身会导致后面的元素前移所以用倒着遍历的方式删除会更方便——从后往前检查删除某个元素不影响前面还没检查到的元素的下标。void SeqList_RemoveDuplicates(SeqList *list) { for (int i 0; i list-length; i) { int val list-data[i]; // 从 i1 开始找删除所有等于 val 的元素 for (int j i 1; j list-length; ) { if (list-data[j] val) { SeqList_Delete(list, j); // 删除后 j 不增加因为后面的元素补上来了 } else { j; } } } }代码里有一个关键点删除后j不能自增因为原来的j1位置的元素已经移到j位置了如果不检查就会漏掉这个新移到当前位置的元素。这类细节就是边界思维和移动思维的实际应用多做几道题就能形成肌肉记忆。6.2 递增有序表的合并双指针法的启蒙第二个练习是合并两个递增有序的顺序表输出一个新的递增有序顺序表。这个问题是很多算法题的原型也是双指针技巧的启蒙。思路是用两个下标分别指向两个表的起始位置每次比较两个当前元素把较小的那个放入新表相应下标前进一位。任何一个表遍历完把另一个表的剩余部分全部追加到新表尾部。void SeqList_Merge(SeqList *a, SeqList *b, SeqList *result) { int i 0, j 0, k 0; while (i a-length j b-length) { if (a-data[i] b-data[j]) { result-data[k] a-data[i]; } else { result-data[k] b-data[j]; } result-length k; } // 处理剩余部分 while (i a-length) { result-data[k] a-data[i]; result-length k; } while (j b-length) { result-data[k] b-data[j]; result-length k; } }这个合并操作的时间复杂度是O(mn)也就是只扫描一遍两个表就完成了合并。这个双指针思路在后续的归并排序、链表合并、字符串处理里会反复出现。从顺序表开始接触它性价比非常高。6.3 C语言指针的再认识顺序表是理解指针最好的实战场景有个容易忽略但特别重要的副产品学会顺序表之后你对C语言指针的理解会上一个台阶。因为顺序表的所有操作都绕不开结构体指针、通过指针访问成员、动态内存分配这些概念。之前学C语言时觉得抽象的指针在这里变成了你每天都在用的工具。比如list-length这个写法list是指向SeqList结构体的指针-是解引用并取成员的语法糖。你写了无数次之后对指针指向某个结构体通过指针操作结构体成员这些事情就有了实感。再回头看C语言教材里的指针章节会比原来清晰得多。这也是我经常对初学者说的一句话先学C语言再用数据结构这门课来复习C语言效果比单纯刷C语言题好得多。7. 学习路线建议与常见问题答疑7.1 一道经典面试题两个递增顺序表求交集每次我辅导新手学到这里都会给他们加一道经典题给定两个递增有序的顺序表求它们的交集公共元素。思路同样用双指针但因为两个表都是有序的所以不需要暴力双重循环。具体做法是两个下标同时走谁小谁往前走相等记录这个值同时两个下标一起走。因为有序所以这个策略不会漏掉任何公共元素。时间复杂度是O(mn)比O(m*n)的暴力解法高效很多。void SeqList_Intersection(SeqList *a, SeqList *b, SeqList *result) { int i 0, j 0, k 0; while (i a-length j b-length) { if (a-data[i] b-data[j]) { i; } else if (a-data[i] b-data[j]) { j; } else { // 相等 result-data[k] a-data[i]; result-length k; i; j; } } }这道题在面试中出现频率很高核心考点不是代码量而是你有没有意识到利用有序性来减少比较次数。刷题的时候多做几道这种题对算法思维的形成很有帮助。7.2 一个经常被问到的困惑顺序表初始容量设多大很多同学会纠结INIT_CAPACITY这个值到底该取8、16还是100。答案是没有标准答案取决于你的应用场景。如果数据量通常很小8或16就够了如果可能很大设一个更大的初始值可以减少扩容次数。真实的项目中这个值往往是基于历史数据统计来定的。重点不是初始值而是扩容机制要正确。即使初始值设错了只要扩容逻辑没问题表最终也能正常工作只是效率上会有微小的差别。所以初学阶段设8还是16都可以不用过度纠结。7.3 学习顺序表的正确姿势动手路线图最后梳理一下我觉得最有效的学习路线。第一步手写一遍完整的顺序表代码包括初始化、插入、删除、查找、扩容、销毁一个都不能少不能只抄书上的要自己敲出来。第二步想办法弄坏它试着插入越界位置、在空表上删除、连续插入触发多次扩容观察会发生什么为什么会这样。第三步做几道综合练习就是前面提到的去重、合并、求交集这类题。第四步找一个数据结构可视化的网站把顺序表的插入删除过程放慢看一遍把从后往前挪变成脑子里的一幅画面。整个过程下来你对顺序表就不仅仅是知道而是会用、会调、能说清楚。这也是数据结构这门课第一个内容该有的掌握程度。这一步踩实了后面的链表、栈、队列就是水到渠成的事了。
