C++顺序表从零手写：核心操作与边界处理详解

很多朋友第一次接触数据结构第一个动手实现的就是顺序表也有不少人问过我C 里std::vector都现成了为什么还要自己写顺序表这个问题的答案恰恰是顺序表值得认真实现一遍的理由。作为最基础、最直观的线性表顺序表能让你看清“数组”和“表”之间的那层抽象也能让你在面试、考试和竞赛里碰到越界、扩容、元素移位这类问题时心里有底。这篇文章我会从零开始手写一份基于 C 的顺序表把创建、输入、输出、插入、删除、取值这六个操作逐一拆开讲透再落到一道真实题目上验证它能不能打。文章不追求高深只求把每一步为什么这么做说清楚。1. 顺序表不是过时的玩具它是一切“高效访问”的底层地基1.1 数组内存连续性带来的访存优势顺序表本质就是一段连续的内存区域数据一个挨一个存放。很多人觉得这个定义太简单简单到不值得学。但恰恰是“连续”二字决定了它一系列性能特征。第一随机访问任意位置都是常数时间。因为元素地址可以直接通过起始地址 下标 × 元素大小算出来不需要从头遍历。第二连续存储对 CPU 缓存非常友好。程序遍历顺序表时内存地址在物理上也接近CPU 载入缓存行之后能连续命中遍历速度非常可观。第三内存布局简单调试时用监视窗口看数组内容一目了然。记着这个底层性质你才能理解后面所有操作的移动逻辑。为什么插入要在中间位置把元素往后搬为什么删除要往前搬归根到底都是因为“连续内存”要求数据必须紧凑排列中间不能有空洞。如果这个性质被破坏顺序表就不再是顺序表随机访问的优势也就丢了。1.2 从顺序表到 STL vector差距只剩封装很多人对std::vector有误解以为它是什么高深容器。其实把vector拆开看内部就是一个动态数组它保存着指向连续内存的指针、有效元素个数size和容量capacity。插入元素时满了就重新分配一块更大的内存把旧数据搬过去再继续用。这个流程跟我下面要手写的顺序表完全同构。那为什么平时用vector感觉不到这些细节因为标准库把这些操作用类封装好了还会在适当时候自动触发扩容。封装带来了便利代价是很多同学直到迭代器失效也没想明白到底发生了什么。手写一遍顺序表相当于把这层黑盒打开你才能真正理解什么时候扩容、为什么尾插均摊是 O(1)、为什么vector的迭代器可能在push_back之后失效。这些知识点如果只靠背诵转头就忘亲手写过之后就成了条件反射。2. 手写顺序表前先把数据结构和接口设计想清楚2.1 核心字段存储区、有效长度、容量写代码前我先定义顺序表的成员变量。这里没必要一步到位模仿vector的花哨接口但三个核心字段一个都不能少存储区指针、有效元素个数、容量大小。class SeqList { private: int* data; // 指向动态数组的指针 int size; // 当前有效元素个数 int capacity; // 当前容量 public: SeqList(int cap 10); ~SeqList(); void input(int n); void output() const; int get(int pos) const; bool insert(int pos, int val); bool remove(int pos); private: bool resize(int newCap); };为什么需要三个字段而不是两个因为有效元素个数和容量是两个概念。数组里实际上能放capacity个元素但目前只用了size个。只有知道了容量才能在size capacity的时候判断“满了”进而决定要不要扩容。如果只维护一个计数器你永远不知道这次插入是否越界。2.2 接口设计几个容易被忽略的关键决策设计接口时我做了几个决策每个都踩过坑第一insert和remove的返回值用bool不是void。因为插入和删除都可能失败位置越界、容量不足且扩容失败。返回bool能让调用方明确知晓操作是否成功。很多人数组写得久默认下标合法结果程序在边界处崩得莫名其妙根本原因就是把“假设”当成了“契约”。第二位置参数全部采用0起始下标。在线性表教材里很多写法用“第 1 个元素到第 n 个元素”这种逻辑位置做题时还得在调用处减一。我的选择是容器内部统一用0起始下标调用层自己决定怎么转换。这样更符合 C 数组习惯也能避免容器内部出现“减一忘记写”的 bug。第三get返回int但越界时不能随便返回-1糊弄过去因为-1本身可能是合法数据。我选择抛出std::out_of_range异常让调用方知道位置不合法。当然在竞赛场景里异常会有少量性能开销所以我在题目实战部分也会给一个“先保证下标合法再调用”的写法。3. 创建、输入、输出、取值热身操作也要写好边界3.1 创建与初始化malloc 还是 new顺序表的“创建”一般由构造函数完成。存的是 C 代码动态内存分配我会统一用new而不是malloc。原因有三new会调用构造函数类型安全更自然失败时默认抛异常而不是返回空指针配套delete使用逻辑上更符合 C 的 RAII 习惯。SeqList::SeqList(int cap) : size(0), capacity(cap 0 ? cap : 10) { data new int[capacity]; } SeqList::~SeqList() { delete[] data; }注意析构函数里必须写delete[] data中括号不能省。我见过很多初学者在这里写成delete data表面看程序没崩其实已经属于未定义行为等到数据量大或换了编译器就会莫名崩溃。new[]和delete[]必须配对就像malloc和free必须配对一样。3.2 输入与输出长度驱动不要踩到 capacity 之外输入操作在竞赛里很常见先读一个 n再把 n 个整数放进顺序表。我的建议是input不负责读 n直接把 n 作为参数传入让调用方控制读取流程容器只负责把数据存好。void SeqList::input(int n) { if (n capacity !resize(n)) { return; } for (int i 0; i n; i) { std::cin data[i]; } size n; }为什么这里要检查容量因为循环里使用的是data[i]如果 n 超过初始 capacity写进data[i]就是越界写。越界写不一定会立刻 crash但可能悄悄改坏堆上的其他数据导致后面printf输出乱码、指针失效等“灵异现象”。判断一次n capacity成本极低收益却是避免一场大排查。输出函数的关键是只用size控制循环而不是capacity。如果你把容量也打出来会输出一堆未初始化的垃圾值。格式上我习惯元素之间用空格分隔最后补换行void SeqList::output() const { for (int i 0; i size; i) { if (i 0) std::cout ; std::cout data[i]; } std::cout \n; }3.3 取值O(1) 操作中隐藏的检查点get是最简单的操作但因为简单反而容易被轻视。int SeqList::get(int pos) const { if (pos 0 || pos size) { throw std::out_of_range(SeqList::get: index out of range); } return data[pos]; }也许你会问取值明明是 O(1)为什么还要加检查因为下标越界是 C/C 里最隐蔽的问题之一。一次比较的成本微乎其微却能帮你避免大量不必要的数据错乱。有些核心计算场景会刻意去掉这个检查来榨取性能但如果你写的是通用工具保留检查明显更稳妥。调用方如果不想要异常可以提前保证pos在[0, size)范围内。4. 插入与删除顺序表真正的主战场4.1 插入从后往前移动元素的根本原因插入操作是顺序表的核心也是考试和面试最喜欢问的部分。代码本身不长bool SeqList::insert(int pos, int val) { if (pos 0 || pos size) return false; if (size capacity !resize(capacity * 2)) return false; for (int i size; i pos; --i) { data[i] data[i - 1]; } data[pos] val; size; return true; }最关键的细节是移动方向必须从最后一个有效元素开始从后往前搬。原因很直白如果从前往后搬data[i 1] data[i]会把后面还没搬的元素覆盖掉产生连锁错位。从后往前搬时目标位置的元素一定是空出来的源位置的元素还没被改所以安全。边界条件也要逐条想清楚。pos的合法范围是[0, size]当pos size时表示尾插是最常用的场景pos 0是头插代价最大因为所有元素都要后移。当size capacity时必须先扩容再移动否则第一步就会越界。整个插入的最坏时间复杂度是 O(n)平均也是 O(n)因为大约要移动一半元素。4.2 删除为什么这次要从前王后移动删除操作和插入正好相反移动方向要从前往后。我的实现bool SeqList::remove(int pos) { if (pos 0 || pos size) return false; for (int i pos; i size - 1; i) { data[i] data[i 1]; } --size; return true; }你可能也有过困惑删除后要不要把最后一个格子清零我的建议是不需要。只要size减一那个位置在逻辑上就不再属于有效数据了之后插入新元素或扩容拷贝时都会覆盖它。当然如果顺序表存的是指针或带资源管理的对象删除时还要额外处理资源释放不能只移动元素就完事。删除的时间复杂度同样是 O(n)因为被删元素后面的所有元素都要往前挪。如果频繁需要在头部删除顺序表并不合适这时候应该考虑链表。这个判断在学习阶段就要建立顺序表适合“读多写少、随机访问多”的场景不适合高频头插头删。4.3 扩容倍增容量背后的均摊复杂度扩容是顺序表从“固定数组”升级为“动态数组”的关键一步。我的做法是倍增而不是每次加固定大小。bool SeqList::resize(int newCap) { int* newData new (std::nothrow) int[newCap]; if (!newData) return false; for (int i 0; i size; i) { newData[i] data[i]; } delete[] data; data newData; capacity newCap; return true; }有人会问为什么扩容要翻倍而不是每次多申请 5 个、10 个这里有一个“均摊复杂度”的概念。假设初始容量是 1连续插入 n 个元素。使用倍增策略扩容时拷贝的元素总数大约是 1 2 4 … n ≈ 2n均摊到每次插入只有 O(1) 次拷贝如果每次扩容只增加固定大小 k那么 n 次插入总共要拷贝大约 k 2k 3k …成本是 O(n²)均摊到每次就是 O(n)。数据量一旦上来性能差距极其明显。这也是std::vector普遍采用倍增容量的底层原因。扩容代码里我用了new (std::nothrow)再检查空指针是防止内存分配失败时直接抛异常导致data指针悬空。实际工程里可能更倾向于让异常抛出去但在教学代码中防御式检查能帮助你养成“每次分配都考虑失败”的习惯。5. 验证顺序表从普通测试到洛谷 P31565.1 测试用例设计先把边界全打出来写完了类不能直接扔到题库里就完事。我的习惯是先在本地把所有操作各过一遍尤其要主动测试那些“一看就容易出事”的边界场景。int main() { SeqList list; list.input(5); list.output(); list.insert(2, 99); list.output(); list.remove(0); list.output(); try { std::cout list.get(3) \n; } catch (const std::out_of_range e) { std::cout 越界: e.what() \n; } return 0; }更细致的测试我会逐个验证向空表插入位置 0删除位置 0连续插入直到超过初始容量删除到空表后再取值capacity 扩到很大后有没有数据错乱。顺序表最容易出问题的地方全在边界光靠脑子想很难把所有组合覆盖完。本地环境不需要多复杂VSCode 配好 C/C 编译调试环境就够用关键是跑起来、打断点、盯着data数组看每一步的变化。5.2 实战解析P3156 询问学号洛谷的 P3156【深基15.例1】询问学号是一道很适合用来验证顺序表的题目。题目会给出按顺序排列的学号序列然后有一系列询问每个询问要求输出指定位置的学号。按顺序表的思路存下序列后每次询问直接按下标取值回答复杂度就是 O(1)。用我们刚写的顺序表代码结构大概是这样的#include iostream #include SeqList.h int main() { int n, m; std::cin n m; SeqList list(n); list.input(n); while (m--) { int k; std::cin k; std::cout list.get(k - 1) \n; } return 0; }这里最需要注意的就是“第 k 个”和“下标 k-1”的转换。题目问的是逻辑位置容器内部用的是从 0 开始的数组下标少一个多一个都会全盘出错。我个人的习惯是容器内部坚持 0 起始所有转换放到业务层做这样顺序表这个工具本身更通用不会被特定题目绑架。6. 顺序表 vs 链表 vs vector什么时候该手写6.1 典型操作的直观对比学习顺序表的过程中我经常拿它和链表、std::vector对比着看。一张小表就能把核心差异说清楚典型操作顺序表链表std::vector随机访问O(1)O(n)O(1)头部插入O(n)O(1)O(n)尾部插入O(1) 均摊O(1)O(1) 均摊中间插入O(n)O(n)O(n)缓存友好性高低高额外内存开销少量容量冗余每节点额外指针少量容量冗余这张表给我的启发是没有绝对的好坏只有适不适合。顺序表和vector的优势在于随机访问和缓存友好链表的优势在于已知位置插入删除时不需要搬动大量元素vector则是顺序表的工业级封装把容量管理、异常安全、迭代器这些都补全了。6.2 实际工程里我的选择经验坦白讲在实际项目中我几乎不会拿手写顺序表替代std::vector。标准库的vector经过了多年优化异常安全、内存管理、迭代器支持都远比我手写的类完善。那手写顺序表的意义在哪意义在于理解当你亲手实现过一次resize你就再也不会问“为什么push_back之后迭代器会失效”当你亲手处理过一次插入边界你再写业务代码时就会自然而然地检查下标和容量。我见过很多人一上手就背八股把“顺序表插入平均 O(n)”背得滚瓜烂熟可一旦遇到vector扩容后指针失效依然一脸茫然。原因就是他没有在底层真正走过一遍。所以我建议你带着目的去写写完六步操作后去刷几道关于线性表的题把这次手写变成真正的肌肉记忆而不是交完作业就删掉。最后再分享一个我自己的小习惯我会在调试时把size和capacity一起打印出来观察每次扩容发生的时机。亲手感受一次“容量翻倍”“数据搬迁”“指针重新指向”的全过程你写工程代码时对数据结构和内存开销会敏感得多。这也是手写顺序表带给我的最大收获。