★ FEATURED ARTICLE 1. 顺序表到底解决什么问题一个贯穿整个数据结构课程的基础模型顺序表这个词学计算机的应该都不陌生。它不是某个具体项目而是数据结构课程里最先展开讲解的线性表实现方式也是几乎所有后续内容——链表、栈、队列、树、图——的地基。我当年学的时候觉得它简单无非就是一个数组加几个操作函数但当我自己动手去实现一个可用、稳定、能处理边界情况的顺序表时才发现里面的门道远比教科书上写的那几行伪代码多得多。简单说顺序表就是“用一段连续的内存空间依次存放一组相同类型的数据”逻辑相邻的元素在物理存储上也相邻。它解决的第一个问题是如何让一组数据既能被快速访问又能被灵活增删。举个例子你维护一个班级成绩表需要按学号顺序查第几条记录顺序表直接通过下标算地址一步就到位这是它最核心的价值。它解决的第二个问题是帮你建立“内存管理意识”——连续空间从哪来、用完怎么释放、空间不够怎么扩容这些在后面的项目里几乎每天都要碰到。这个内容适合谁看一个是正在学数据结构的学生你需要把课本上的伪代码变成真正能跑的代码另一个是准备面试的开发者顺序表的基本操作和复杂度分析属于高频考点但只背结论远远不够。我下面会从设计思路开始把原理、代码、坑、选型全部拆一遍你说不定能从中找到一些课本之外的东西。2. 设计思路全拆解为什么顺序表是一副“连续扑克牌”2.1 顺序表的底层逻辑逻辑相邻 物理相邻线性表的数据元素之间存在一对一的线性关系顺序表就是在线性表的逻辑结构之上套了一层“连续内存”的物理实现。可以把它想成一副扑克牌按固定顺序码在桌面上两张相邻牌之间没有任何空隙你想拿从左边数第 5 张牌直接走过去拿就行不用一张一张数。这个“直接走过去”的能力对应到计算机就是随机访问而它成立的前提就是数组下标和内存地址之间存在一个确定的换算关系在 C 语言里数组data的首地址是base每个元素占sizeof(ElemType)个字节那么元素data[i]的地址就是address(data[i]) base i * sizeof(ElemType)这就是教科书上常说的“基址 偏移量”访问公式。因为地址可以直接计算得出所以无论表有多大访问任何一个元素的时间都是固定的也就是时间复杂度为 O(1)。这个特性后面你会反复遇到比如哈希表用数组做桶数组也是看中了这个 O(1) 的定位能力。教科书里经常用“逻辑相邻物理也相邻”这个表述来区分顺序表和链表链表允许逻辑上相邻的元素在物理内存里东一块西一块而顺序表不允许它必须整整齐齐排在一起。这既带来了优势也带来了限制下面我会展开说。2.2 和普通数组的区别顺序表是“自动扩容版数组”很多人会问顺序表和数组到底差在哪如果你只是定义一个int a[100]那它只是拿到了 100 个连续元素的空间但没有任何人替你管理“这个数组当前存了几个有效数据”。你的代码里可能自己约定int n来记录长度但增删、移动、越界检查这些事都得每次重新写。顺序表本质上就是把这些逻辑封装成一套标准操作接口InitList创建空表并分配初始内存ListInsert在指定位置插入元素ListDelete删除指定位置元素LocateElem按值查找元素GetElem按下标获取元素ListLength返回当前元素个数DestroyList释放内存。这套接口的背后是几个关键问题空间满了怎么办插入中间位置时大量元素怎么挪删除后要不要缩容这些决定不是一个普通数组能替你回答的但封装的顺序表可以。我见过不少新手在项目中直接裸用数组然后到处写for (int i pos; i n; i) arr[i] arr[i1];这样的挪动代码一旦逻辑散落在多个模块里边界条件特别容易出错。顺序表的价值就是把这种“公用操作”集中实现一次以后哪都能用。2.3 为什么数据结构课都从顺序表讲起顺序表是线性表的第一个实现因为它的思维负担最轻。数组是几乎所有编程语言内置的东西大家早已熟悉下标访问所以从顺序表切入可以把重点放在“数据结构的思维模式”上而不是被复杂的指针和节点操作劝退。等你能写出顺序表的增删查改理解了封装和内存管理这两个核心概念后面再学链表时就有了参照系链表到底改进了什么、引入了什么新问题一对比就很清楚。另一个原因是顺序表在工程中实在太常见。内存池里空闲块的管理、操作系统进程表的组织、数据库的页内记录存储底层都有顺序表的影子。把顺序表真正理解透后续学习很多系统级的代码都会有更强的代入感而不是看到一片连续的索引结构就发懵。3. 核心细节解析与实操要点连续性、扩容与挪移3.1 连续内存分配方式静态分配还是动态分配顺序表在内存中的空间有两种来源静态分配和动态分配。静态分配是直接在结构体里定死一个数组大小比如#define MAXSIZE 100 typedef struct { ElemType data[MAXSIZE]; int length; } SeqList;这种方式的优点是简单、不涉及堆内存管理、不担心内存泄漏缺点是表的最大容量写死一旦数据超过 MAXSIZE 就装不下若定义得太大又浪费内存。多数课程作业用这种方式演示算法逻辑完全没问题但和真实项目需求有些脱节。动态分配则是在初始化时根据参数向系统申请一块堆空间之后发现不够用再扩容typedef struct { ElemType *data; int capacity; // 当前容量 int length; // 当前长度 } SeqList;动态版本的data是一个指针指向堆内存中的某一段连续空间。程序运行期间可以根据数据量的增长调用realloc或“重新 malloc 拷贝”来扩大容量。我一般更推荐学习时直接上动态版本因为它是各种标准库容器实现的原型你迟早要接触不如现在就把它啃下来。实际开发中的“数组不够存了自动扩容”体验也只有动态版本能真正感受到。3.2 随机访问为什么快直接地址计算没有门槛顺序表最闪耀的优势就是GetElem一步到位。不管是第 1 个还是第 10000 个元素都是拿到下标按公式算地址然后直接取值ElemType GetElem(SeqList *L, int i) { if (i 1 || i L-length) { fprintf(stderr, 索引越界\n); exit(EXIT_FAILURE); } return L-data[i - 1]; }这里有三个细节要注意。第一逻辑位序和物理下标的转换。用户的视角中第 1 个元素的逻辑位序是 1但 C 语言数组下标从 0 开始所以访问时要i - 1。这是一个极易写错却又极少被解释清楚的地方。第二越界检查。教科书会强调“判断 i 是否合法”但实际使用中如果每次访问都判断性能会有损失所以很多标准库实现默认不做边界检查比如 C 语言的裸数组由调用方保证合法性但是封装良好的数据结构接口里强烈建议保留检查调试期能帮你节约大量时间。第三O(1)的时间复杂度不是形容词而是数学结论它不依赖表内元素个数 n。无论 n 是 10 还是 1000000地址都是直接算出来的这就是“随机访问”的含义。注意对比链表的访问必须要从头结点开始逐个移动指针那是 O(n)两者天差地别。3.3 动态扩容的两种策略增量扩容与倍增扩容顺序表的容量不可能永远够用这就引出了扩容策略。教科书里很少展开讨论但在工程中这是大量耗时的地方我把它单独拿出来讲。常见做法是当length capacity时重新开辟一块更大的内存把旧数据复制过去然后释放旧内存。关键问题是每次扩容应该增加多少第一种是固定增量扩容。比如每次多分配 10 个元素空间。优点是简单、可控但缺陷很明显如果插入频繁你可能在插入 10000 个元素时执行了 1000 次扩容操作每次都要做一次 O(n) 的搬家。整体来看插入 n 个元素的时间复杂度会退化到 O(n²)。我在一个老项目里见过类似实现插入几千条日志时界面卡顿严重排查到最后就是频繁扩容在作怪。第二种是倍增扩容乘性扩容。常见策略是翻倍即新容量 旧容量 × 2。它每次搬运的代价虽然也大但摊还到每一次插入上平均时间复杂度可以压到 O(1)。原因是扩容操作发生的次数大约只有 log n 次而总搬运量大约为 n所以总体上平摊到每个元素依旧只有常数级成本。这就是数据结构中著名的“摊还分析”队列、动态数组都离不开它。倍增系数不是越大越好。翻倍虽然让扩容次数更少但可能造成近一半的空间闲置某些标准库实现会选择 1.5 倍试图在空间利用率和扩容次数之间取得平衡。面试里如果被问到“为什么动态数组扩容用 2 倍或 1.5 倍”你要能说出来翻倍是为了摊还 O(1)但会牺牲空间定值增量空间友好但时间会退化。没有绝对正确只有场景取舍。3.4 插入和删除为什么是 O(n)挡路的人都要让一步顺序表用一组连续空间换取随机访问的便利代价就是插入和删除时的数据移动。往第 i 个位置插入元素时逻辑顺序第 i 到第 n 个元素都要往后挪一位从最后一个元素开始从后往前逐个后移删除第 i 个位置的元素时第 i1 到第 n 个元素都要往前挪一位从第 i1 个元素开始从前往后逐个前移。两种操作平均都要移动 n/2 个元素所以平均时间复杂度为 O(n)。这个代价有多大形象点说就像一条排好的队伍你非要插到中间后面所有人都得往后挪一步队越长挪的人越多。链表在这点上会优秀许多因为只需要改变相邻节点的指针不需要整队移动。但链表失去了随机访问的能力没有免费的午餐。还有两个实际优化经验值得记下在表尾插入或删除不需要移动任何元素时间复杂度是 O(1)这也是栈能用顺序表轻松实现的原因如果业务场景允许“删除即标记”也就是只把目标位置的元素做删除标记定期再统一整理可以把高频删除场景的均摊成本降下来这种“惰性删除”思路在不少系统的实现里都能看到。3.5 思考快慢表尾操作优于表头操作从上面可以推导出一个重要的实践结论凡是涉及频繁在头部或中间做插入删除的场景顺序表都不太合适凡是主要在尾部追加数据、头部较少改动的场景顺序表都很舒服。比如日志记录大部分数据都是按时间顺序往末尾追加查询时可能按下标取最近 N 条这种场景很适合顺序表。而文本编辑器里光标到处移动、随时在任意位置插入字符用顺序表就会频繁触发大范围数据移动这时候编辑器底层的 rope 结构一种带索引的树结构或者链表式设计会好很多。这里不是“谁比谁高级”而是选型时要先搞清楚自己的访问模式。4. 核心代码实现从零手写一个可用、可调试的顺序表4.1 结构体定义与初始化逻辑学习阶段我建议用动态版本并把一切可能导致内存问题的细节都摆在明面上。下面是完整的结构体定义和一些宏直接粘贴运行就可以看到结果#include stdio.h #include stdlib.h #include string.h typedef int ElemType; typedef struct { ElemType *data; int length; int capacity; } SeqList; #define INIT_CAPACITY 10 #define EXPAND_FACTOR 2初始化时注意三件事分配内存是否成功、长度归零、容量赋值。我见过不少同学忘了给capacity赋值之后扩容时连“空间满没满”都没法判断void InitSeqList(SeqList *L, int cap) { if (cap 0) cap INIT_CAPACITY; L-data (ElemType *)malloc(sizeof(ElemType) * cap); if (L-data NULL) { perror(malloc failed); exit(EXIT_FAILURE); } L-length 0; L-capacity cap; }这里传入cap而不是在函数内部写死是为了让调用方可以决定初始大小。如果你已知要存 1000 条记录却非要从 10 开始一次次扩容浪费的时间是可观的。先估算规模再初始化是一个很容易被忽略的性能习惯。4.2 扩容操作的两种写法realloc与手动搬家动态扩容是顺序表最容易翻车的地方我给出两种写法并说明区别。第一种是用realloc直接调整堆内存大小。realloc会尝试在原内存块上扩大空间如果后面的空间不够它会重新找一块更大的内存、自动复制旧数据并释放旧块。代码很简短void EnsureCapacity(SeqList *L, int need) { if (L-capacity need) return; int newCap L-capacity; while (newCap need) newCap * EXPAND_FACTOR; ElemType *newData (ElemType *)realloc(L-data, sizeof(ElemType) * newCap); if (newData NULL) { perror(realloc failed); exit(EXIT_FAILURE); } L-data newData; L-capacity newCap; }第二种是不用realloc自己走 “malloc memcpy free” 三件套。这样做的理由主要是为了暴露内存管理的完整流程让人看清扩容的本质void EnsureCapacity2(SeqList *L, int need) { if (L-capacity need) return; int newCap L-capacity; while (newCap need) newCap * EXPAND_FACTOR; ElemType *newData (ElemType *)malloc(sizeof(ElemType) * newCap); if (newData NULL) { perror(malloc failed); exit(EXIT_FAILURE); } memcpy(newData, L-data, sizeof(ElemType) * L-length); free(L-data); L-data newData; L-capacity newCap; }memcpy复制的是length个元素而不是capacity个因为旧空间里只有前length个位置是有意义的数据这点经常被写错。顺便提醒如果元素类型是结构体且内部含有指针memcpy浅拷贝会带来指针共享问题建议逐元素拷贝这个在更进阶的项目里值得警惕。这两种写法在实际效果上接近但realloc版本更依赖运行时的行为手动版本则把“必须释放旧空间”写在了明面上更适合学习阶段理解内存的来龙去脉。工程代码里我喜欢用realloc因为少一次拷贝的潜在机会教学和调试则用手动版本逻辑可控。4.3 插入从后往前挪动数据边界条件要细心void ListInsert(SeqList *L, int pos, ElemType e) { if (pos 1 || pos L-length 1) { printf(插入位置非法pos%d, length%d\n, pos, L-length); return; } EnsureCapacity(L, L-length 1); for (int j L-length; j pos; j--) { L-data[j] L-data[j - 1]; } L-data[pos - 1] e; L-length; }插入位置的合法性范围是1到length 1允许在表尾追加。数据的挪动是从最后一个元素开始所以循环的起点是length终点是pos有人在纸上推算半天每次都推错不如记住一条只有从后往前循环才不会发生“前面的值覆盖还没挪动的值”这种事。如果你在循环里写成了for (int j pos; j L-length; j) data[j 1] data[j];那这会从前往后覆盖结果就是整个数组后半部分变同一个数这就是典型的覆盖方向错误。我也踩过这个坑后来专门写了个小测试用例在插入位置 1、中间、尾部三个方向分别验证才彻底放心。4.4 删除从前往后挪动数据别忘了把游离值清掉void ListDelete(SeqList *L, int pos) { if (pos 1 || pos L-length) { printf(删除位置非法pos%d, length%d\n, pos, L-length); return; } for (int j pos - 1; j L-length - 1; j) { L-data[j] L-data[j 1]; } L-length--; // 可选的清理动作避免“残留值”给调试带来干扰 L-data[L-length] 0; }删除的挪动方向正好和插入相反必须从前往后循环。循环结束后把原来最后一个位置置 0这步不是为了正确性而是为了调试方便。如果没清掉你打印整个物理数组时会看到最后一个旧值还在里面容易造成“明明删除了却还在”的错觉。这个细节课本上不会写调试几次就懂了。删除时要不要缩容工业界的常见做法是“缩容要谨慎”。如果每次删除都触发容量减半而紧接着又有一次插入触发扩容就会陷入反复分配和释放的抖动里。所以容量只增不减、或者等空闲比例超过某阈值再缩容是更稳妥的设计。学习阶段可以先把缩容忽略重点吃透挪动逻辑。4.5 查找、打印与销毁收尾查找按值遍历找到返回逻辑位序从 1 开始找不到返回 -1int LocateElem(SeqList *L, ElemType e) { for (int i 0; i L-length; i) { if (L-data[i] e) return i 1; } return -1; }打印时只打印有效长度内的元素不要打印整个容量否则会把扩出来的闲置空间也无差别打出来void PrintList(SeqList *L) { printf(length%d, capacity%d, data[, L-length, L-capacity); for (int i 0; i L-length; i) { printf(%d, L-data[i]); if (i ! L-length - 1) printf(, ); } printf(]\n); }销毁时释放data指向的堆空间并把结构体里的字段清零防止重复释放void DestroySeqList(SeqList *L) { free(L-data); L-data NULL; L-length 0; L-capacity 0; }提醒一个实战中的好习惯每次free之后立刻把指针置为 NULL。虽然顺序表这个场景不太会重复free同一个指针但后面你写链表、树节点之间指针关系复杂悬空指针和双重释放都是很常见的段错误来源。把“释放即置空”变成肌肉记忆很有必要。4.6 一个完整的测试代码示例代码写完之后必须用测试代码验证这一步非常关键。我通常会准备一组覆盖主要边界情况的测试用例int main(void) { SeqList L; InitSeqList(L, 5); for (int i 0; i 10; i) { ListInsert(L, L.length 1, i 1); // 尾插 1 到 10 } PrintList(L); // 期望 1..10期间应发生一次扩容 ListInsert(L, 1, 100); // 头插 PrintList(L); // 期望 100, 1..10 ListInsert(L, L.length 1, 200); // 尾插 PrintList(L); // 期望 100, 1..10, 200 ListDelete(L, 1); // 删除头部 PrintList(L); int pos LocateElem(L, 5); printf(5 的位置是 %d\n, pos); DestroySeqList(L); return 0; }跑出来的结果应该是第一次尾插 10 个元素时初始容量 5在插入第 6 个时自动翻倍到 10插入 11 个时再次翻倍到 20。PrintList 里如果能看到 capacity 从 5 变 10 再变 20说明扩容逻辑工作正常。很多“代码能跑但结果不对”的情况多半是插入时的挪动方向或边界判断出了问题测试用例里多覆盖头、尾、中间三种插入位能帮你快速定位。5. 常见问题与排查技巧实录顺序表调试的七宗罪5.1 扩容之后数据丢失或脏数据现象插入一定数量后打印出来的数据出现随机值或者某些旧值丢失。排查方向先检查EnsureCapacity里是否真的把L-capacity更新了再去检查memcpy复制的字节数是不是sizeof(ElemType) * length而不是sizeof(ElemType) * capacity。还有一个隐蔽问题用realloc之后如果直接把返回值赋给L-data但realloc返回的是新地址而旧data里面没有任何需要保存的东西吗错旧数据已经被realloc自动搬走了所以这个写法是对的但如果你用malloc memcpy却忘了free旧空间就会内存泄漏长时间运行后内存涨到令人发指。5.2 插入位置合法判断写错现象向表中插入数据后顺序错乱或出现越界写入。排查方向判断pos 1 || pos L-length 1时很多人写成pos L-length那尾插就永远不合法逻辑上没问题但功能受限还有人写成pos capacity这就完全错了因为length和capacity是两个不同含义的变量——长度表示有效数据的个数容量表示空间大小插入合法性的上限是长度而非容量。分不清这两个变量是我见过最常见的初级错误。5.3 忘了“从后往前”还是“从前往后”现象插入后部分元素变成同样的值。排查方向前面提过插入必须从最后一个元素开始倒着移删除必须从第一个元素开始正着移。如果你写的移动方向反了覆盖顺序就乱了。我提供一个记忆办法插入的时候你要挪动的是“目标位置右边的元素”如果要保证右边的元素不被提前覆盖只能从右往左操作删除的时候要挪动的是“目标位置左边的元素”要从左往右操作。想不通的时候就拿一个小纸片写几个数字模拟一遍。5.4 打印表却把整个 capacity 打出来现象输出末尾带着很多 0 或乱码。排查方向打印循环用了capacity而不是length把扩容后尚未使用的空间也打出来了。如果扩容时用了malloc而不是calloc那些空间里是上一次的残留数据看起来就是乱码。这在学习阶段很容易让人误以为“数据被破坏了”实际上数据并没坏只是你把不该看的内存也看了而已。5.5 双重释放导致崩溃现象程序运行结束前执行DestroySeqList时崩溃或者执行两次销毁时崩溃。排查方向可能是你不仅在DestroySeqList里free在某些临时检查函数里也顺手free了一次。解决方法是统一销毁入口并且在释放后立即置 NULL。C 语言里对同一个指针调用两次free是未定义行为轻则崩溃重则悄悄破坏堆结构特别难查。一定要养成置空习惯。5.6 结构体传值还是传指针现象插入后PrintList显示长度没变。排查方向函数签名可能写成了void ListInsert(SeqList L, ...)传了一个结构体副本进去。在副本里改length改的是副本字段原结构体丝毫不受影响。所有需要修改结构体内部数据的函数都必须传SeqList *只有只读操作如PrintList可以传值或传指针传值会遇到整个结构体的栈复制有轻微性能开销传指针更务实。5.7 扩容后原有指针失效现象代码里提前把L-data存到了一个临时指针变量里之后继续用临时指针访问数据。排查方向扩容之后realloc可能把内存搬到了全新地址旧指针已经不指向有效内存了。任何指针都不能长期保存动态结构内部地址除非你非常确定该结构后续不会扩容。我见过一个比较隐蔽的场景先ElemType *p L-data;然后再插入几个元素触发扩容之后继续p[i]访问数据结果就是段错误。正确做法是每次都通过L-data重新获取。6. 应用场景与选型分析什么时候该用顺序表什么时候别用6.1 适合顺序表的典型场景根据前面的分析顺序表的优势集中在随机访问和尾端操作上所以适合它的场景很明确第一频繁按下标查询数据的场景。比如内存中维护一份固定字段的表用户通过索引翻页查看或者程序缓存一批事件记录随时要取第 N 条来复核。这些场景查询次数多、位置随机顺序表 O(1) 访问的价值被发挥得淋漓尽致。第二尾部追加为主、偶尔中间修改的场景。比如日志系统、监控事件收集器数据基本上是按时间顺序往末尾塞偶尔需要删除过期的头部数据。用顺序表实现“尾部写入 头部丢弃”的滑动窗口很自然就可以配合环形缓冲区使用。第三操作次数少、规模己知的场景。例如你明确知道要存储的元素最多 5000 个初始化时预分配 6000 个位置几乎不扩容顺序表非常轻量连链表式的结构开销都省了。第四作为栈的底层实现。栈的核心操作是压栈和弹栈都在栈顶发生对应顺序表的表尾插入和删除两个操作都是 O(1)。这也是“顺序栈比链栈更常用”的根本原因。6.2 不适合顺序表的典型场景不适合的场景也很典型。频繁在中间或头部插入删除是第一个红旗因为每次操作都要拉动大量元素数据量无法预估、且增长波动剧烈是第二个红旗扩容在极端情况下会带来明显卡顿元素本身很大比如几百字节的结构体而操作又频繁时数据移动的开销会变成瓶颈此时更适合用链表来避免整体搬运。我遇到过这样一个需求某模拟系统需要维护大量小任务任务间有先后依赖随时可能把一个新任务插到依赖链中间同时要按优先级不停调整顺序。这个场景用顺序表就非常难受后来换成链表结构才把插入耗时的痛点解决。选型不是比谁“高级”而是看数据的访问和修改模式更偏向哪一侧。6.3 顺序表 vs 链表的全面对比简单用一个表格总结两者的核心差异面试前也建议背熟对比维度顺序表链表内存布局连续离散随机访问O(1)O(n)头部插删O(n)O(1)尾部插删O(1)扩容时偶发O(n)O(1)需遍历找尾空间开销有闲置容量但无需指针域每个节点有指针域开销缓存友好度高连续访问局部性好低节点地址分散扩容方式批量搬移按需分配单节点不搬移适用场景查多改少、尾端操作为主频繁插入删除、无法预知规模特别提一下缓存友好度。现代 CPU 读内存时是一块一块地读进缓存顺序表相邻元素在连续地址上访问时大概率同一块缓存就能命中好几个元素所以遍历顺序表非常快链表节点分散在不同内存块每次跳转都可能发生缓存未命中。实际运行中链表遍历比想象中还要慢一倍以上这个也是我在压力测试里观察到的现象。6.4 现实世界哪些系统在用顺序表的内核顺序表的思想无处不在知道这些能帮你把课本概念和工程建立连接。常见的动态数组容器底层就是顺序表的通用化实现支持任意类型元素自动扩容扩容策略就是倍增或固定步长的改良版。操作系统里的进程表、文件描述符表底层很多也是密集索引结构逻辑类似顺序表可通过编号快速查找到对应表项插入和删除时用“空洞标记 整理”的手法来避免频繁移动。数据库的一页数据行在页内物理上也是连续排列通过页目录的偏移量实现随机访问本质上和顺序表的 “基址 偏移” 完全一样。我遇到过一位做存储引擎的工程师他提到即使是树形索引叶子节点内部仍然会用“连续数组”来存键值以利用顺序访问的速度。这说明顺序表不是数据结构课里淘汰的“基础章节”它在现代系统中依旧是极其重要的存储原语只是藏得更深了。7. 练手建议与后续扩展把顺序表从“会写”变成“会想”7.1 三个值得动手的练手任务如果把顺序表的基本操作写完就算完成那还差得远。我建议按难度递进做三个小任务做完你对这个章节的理解会完全不一样第一个实现带缩容策略的顺序表。设计规则当length不足capacity / 4时容量减半并确保缩容后capacity至少为初始值。这个任务会强迫你思考“什么时候缩容、会不会抖动、是否能和扩容共用一套内存调整逻辑”。第二个把顺序表改成环形缓冲区。用数组的“尾”位置指引下一次写入位置用“头”位置指引下一次读取位置绕过数组中点的限制。这个任务会锻炼你取模运算和边界判断也是日志收集和流处理里真实使用的数据结构。第三个实现一个“去重版顺序表”。插入前先LocateElem查一遍重复则拒绝插入不重复才插到尾部。任务看起来简单但加上“保持原有顺序”和“统计重复次数”两个变形需求就有实际的价值感了。7.2 进阶方向从顺序表走向更复杂的数据结构顺序表学完之后顺着两条线继续深入会很顺利。一条是线性结构的扩展链表、栈、队列、双端队列、循环队列另一条是数组的进阶矩阵压缩存储、树状数组、哈希表的开散列与闭散列。我个人最推荐先写一遍链表再回头看顺序表你会突然明白之前不少“约定俗成”的设计比如为什么插入允许length 1背后有多么具体的原因。再往后学树顺序表可以作为二叉树的存储方式——用数组下标表示父子关系这就是我一开始说“顺序表是地基”的原因。7.3 关键点总结学完顺序表你该带走什么我最后想强调的不是代码是三个思考习惯。第一任何数据结构在脑中都要同时有“逻辑结构”和“物理实现”两个层面顺序表是理解这对关系最好的入口第二分析复杂度时要关注最坏情况、平均情况和摊还情况扩容策略就是一个经典案例第三写代码时先想清边界条件插入、删除的位置合法性判断不是可有可无的防御代码它是正确性的第一道防线。说实话顺序表这部分我教过很多人、也陪很多人踩过坑。很多人一开始觉得无非一个数组不值得花太多时间但真到写链表、写树、写实际模块时却在内存操作和边界条件上反复翻车。我自己的体会是顺序表教会你的不是怎么用数组而是怎么站在“空间管理”和“数据移动成本”的角度审视一个结构。把这个内核想通后面的数据结构学起来会轻松不少。如果你正在学这块别急着把它翻过去多花点时间把揉代码、跑测试、观察扩容的内存变化这三件事做扎实了收益远比想象中大。
阅读完成 · 觉得有帮助？
