1. 为什么第九篇我选了动态数组设计思路与代码结构C语言学到第九篇指针、结构体、内存管理基本都见过了但很多初学者仍然卡在一个瓶颈上单独看每个知识点都懂一写综合点的代码就不知道从哪下手。这一篇我特意选了“手写一个动态数组”作为实战案例就是因为它能把指针、结构体、堆内存、函数传参这几块硬骨头全部揉在一起而且做完后你会得到一个能真正用在项目里的工具不是那种跑完就删的练习题。动态数组是什么一句话解释一个能够自动扩容的数组。普通数组长度写死int arr[10]就是 10 个格子多了装不下少了浪费内存。动态数组底层其实也是连续内存但它会在空间不够时申请一块更大的新内存把老数据搬过去然后把旧的还回去。用这个思路去理解它你会瞬间看透 C 语言里数组和指针之间的本质关系——数组名不是指针但数组在函数间传递、在堆上申请时几乎处处都在通过指针操作。我见过不少人在学习时只关注语法本身比如“二重指针是什么意思”“realloc怎么用”但一旦要把它们组合起来就懵了。这个现象很正常C 语言的知识点不是孤立的你不把它们串成一个整体去实践就永远感觉是在学碎片。这第九篇的定位就是把前面零散的知识串起一条线来。你可能想问为什么不是链表链表在插入删除上确实灵活但它每个节点单独分配内存节点之间用指针相连对你理解“连续内存”帮助不大。而动态数组的核心价值有两个底层是连续内存缓存命中率高随机访问是 O(1)扩容逻辑逼着你处理realloc、指针失效、内存释放这些真正折磨人的问题换句话说动态数组是练“内存布局”意识的最好载体。链表练的是“指针指向”动态数组练的是“一块内存怎么长大”。整个设计的最终目标也很朴素写一个Vector支持初始化、释放、追加、弹出、按下标读写、按位置插删还要有容量自动扩展。真正难的不是功能本身而是你在每一个细节上做出的取舍比如容量因子选多少、缩容策略要不要做、结构体里为什么放两个字段而不放三个。下面一个一个小节拆开讲。1.1 动态数组比普通数组好在哪内存布局与扩容逻辑先理解一个问题为什么动态数组能“动态”关键在于它把数组的控制权从编译器手里夺了回来。普通数组声明出来内存大小在编译期就固定了如果你想根据用户输入来决定数组长度标准 C 里你是做不到的——C99 之后虽然有了变长数组但它分配的往往是栈内存一来不能太大二来生命周期很受限。动态数组的做法完全不同一开始在堆上分配一小块内存比如能放 4 个元素然后每次写满时重新分配一块更大的内存。这里的“重新分配”有两种实现方式一般初学者会搞混先malloc新内存再memcpy旧数据再free旧内存。逻辑清晰但代码啰嗦。直接用realloc。它内部会帮你处理“原地扩展”和“搬到新家”两种情况如果后面有空闲空间就原地扩大指针范围如果不够就重新找一块内存自动拷贝旧数据并释放旧块。大多数情况下用realloc就够了但有个铁律必须记住永远不要把realloc的返回值直接赋给原来的指针。因为一旦分配失败realloc会返回NULL如果你直接p realloc(p, new_size)原来的p就丢了不仅数据全丢而且旧内存没人释放等于一手造成泄漏和崩溃。正确写法是先拿一个临时指针接返回值判断成功后再覆盖。int *new_ptr realloc(arr-data, new_capacity * sizeof(int)); if (new_ptr NULL) { // 处理失败但 arr-data 还在还能安全继续用 return -1; } arr-data new_ptr; arr-capacity new_capacity;这一步就是整个动态数组的灵魂。可以说你如果把这个realloc的细节琢磨透了以后写任何涉及扩容的代码都不会在内存上翻车。1.2 结构体里为什么要存 size 和 capacity 两个字段size表示当前实际存了多少个元素capacity表示当前底层数组最多能存多少个。这俩看着像但作用完全是两码事。size是给使用者看的逻辑长度capacity是给内存管理用的物理容量。好比一个书包装了多少本书是size书包设计能装多少本是capacity你每次把书装满就得换个大书包。很多初学者嫌麻烦只记一个长度然后用完了就扩容。短期看好像够用一旦你想把动态数组当成通用容器用比如要支持中间插入、删除、随机访问没有capacity你根本不知道自己还有没有余量去放新元素。每次push_back都判断当前下标是否等于数组长度长度加 1 就扩容这种写法有两个毛病你在插入时不知道底层容量还剩多少需要额外定义容量变量或者自己推算结构体里不存容量函数之间传参时你就得多带一个参数接口设计一下就变得很难看不统一所以我在设计时结构体固定放三个字段typedef struct { int *data; // 指向堆区连续内存的指针 size_t size; // 当前元素个数 size_t capacity; // 当前分配的内存能容纳的元素个数 } Vector;这里有个隐藏问题值得细说。size和capacity到底用int还是size_t我在项目里统一用size_t。原因很简单C 标准里malloc、realloc、数组下标这些操作天然无符号sizeof返回的也是size_t。如果你用int混用的时候编译器会报警告稍微复杂一点的运算还可能溢出。唯一麻烦的是size_t是非负的写循环判断时要注意不要写成for (int i size - 1; i 0; i--)这种蠢代码直接用while (size 0)或size_t i size; i 0; i--。这个坑我在带新人的时候几乎每次都能见到大家都不太注意无符号类型绕回的特性。2. 指针没吃透先搞定这 4 个关键细节动态数组的核心离不开指针操作。如果这一篇只给代码不讲指针那就等于让你背答案换个题目照样懵。所以我把整个实现里最关键的指针问题拆成四个细节单独说清楚每个都是曾经让我和身边同事踩过坑的地方。2.1 结构体指针传参与修改为什么经常要传二级指针很多初学者写初始化函数时会这么干void init(Vector vec) { vec.data NULL; vec.size 0; vec.capacity 0; }看起来逻辑很合理实际运行一点效果都没有。原因在于 C 语言里函数参数是值传递vec传入函数后会生成一份拷贝你在函数内部修改的只是那份拷贝外面原始的Vector变量纹丝未动。解决思路有两个方案一传指针修改指针指向的内容void init(Vector *vec) { vec-data NULL; vec-size 0; vec-capacity 0; }调用的时候init(arr)vec指向外界的真正的arr所有vec-xxx的修改都会真实落回去。这个方案适用于“结构体已经存在只需要初始化”的场景。方案二返回新结构体Vector init(void) { Vector vec {0}; return vec; }调用时Vector arr init();。因为结构体可以整体赋值直接把返回值拷给arr也不用。两种方案各有优劣。方案一适合像realloc这种需要修改底层数据的场景方案二写起来更简洁但在后续扩展中如果函数改完还想返回新的容量、长度之类的信息就显得捉襟见肘。我个人习惯是统一用指针版本因为动态数组后续还要写插入、删除、清空等操作这些函数往往需要修改size甚至data传指针是唯一省事的写法。2.2 数组名和指针的关系下标访问到底是怎么工作的C 语言里arr[i]本质上是*(arr i)的语法糖。这一点是理解数组、指针、下标三者关系的钥匙。动态数组里arr-data[i]就是先拿到连续内存的起始地址再做一次指针偏移和解引用。正因为如此你才能用一个int *的data字段同时表示“底层的数组”、以及“通过下标访问数组”这两件事在 C 语言中是同一回事。有一个细节容易让新手怀疑人生如果你拿到的是一个指向Vector的指针比如Vector *vec那么vec-data[i]里面data本身就是一个指针data[i]和*(data i)完全等价。这个写法嵌套了两个指针层次但逻辑上是清楚分层的第一层是结构体指针vec指向结构体第二层是结构体里的data指针指向数组首元素。建议你在纸上画一下内存图真的会通很多。2.3 为什么free之后指针还要置空写destroy函数时最容易被忽略的一步是free完之后没有把data置为NULL。举个例子void destroy(Vector *vec) { free(vec-data); }如果调用两次destroy(arr)第二次free的是一块已经被释放的内存。这不是一定崩溃但是是未定义行为轻则啥事没有重则堆结构被破坏程序跑着跑着莫名崩溃特别难排查。所以标准的做法是void destroy(Vector *vec) { free(vec-data); vec-data NULL; vec-size 0; vec-capacity 0; }free(NULL)是安全的C 标准明确规定对空指针free不做任何事。所以把指针置空后哪怕有人不小心再次调用destroy也没法造成破坏。这条经验我在项目里已经养成肌肉记忆了只要是释放内存的接口我都会顺手把指针置空。看起来只是多一行代码省掉的问题是成倍的。2.4realloc失败时不要裸奔安全扩容的标准动作前面提到临时指针接返回值这里再补充两个细节。很多人把扩容逻辑简化成arr-data realloc(arr-data, new_capacity * sizeof(int)); arr-capacity new_capacity;这段代码十次有九次能用唯一一次不能用就是内存不足时realloc返回NULL然后你干了两件蠢事一是把NULL赋给了原来好端端的data旧内存从此找不回来二是又把capacity更新成了一个新容量但data实际上什么都存不了。后续一写入就段错误而且你根本找不到是谁干的。正确的扩容逻辑请直接抄下面的模式int vector_reserve(Vector *vec, size_t new_capacity) { if (new_capacity vec-capacity) { return 0; } int *new_data realloc(vec-data, new_capacity * sizeof(int)); if (new_data NULL) { return -1; // 失败时保持原 vec 完全不变 } vec-data new_data; vec-capacity new_capacity; return 0; }这里我想多讲一层new_capacity * sizeof(int)这个乘法也有风险。如果new_capacity是外界传进来的你没法保证它乘完不溢出。真正严谨的库会检查溢出但初学者阶段我觉得意识到这个问题就够了不要为了过度防御把代码搞得很难读。3. 手把手写出可复用的动态数组完整实现与测试讲完原理和易踩的坑现在进入实操环节。这一节我会把完整代码贴出来然后逐段解释每个函数的设计意图并且给出一份能直接跑起来的测试用例。你不需要照着抄一遍而是要知道每个函数为什么要这么写这样到你自己改造成其他类型时才能有底气。3.1 整体头文件设计接口清晰比什么都重要动态数组虽然不是库但写它的过程中你就该养成“接口设计”的习惯。我把声明全部放在一个头文件里然后实现放.c文件主测试文件放另一个.c。这样哪怕你现在只是自己练手也能立刻感受到模块化带来的好处。// vector.h #ifndef VECTOR_H #define VECTOR_H #include stddef.h typedef struct { int *data; size_t size; size_t capacity; } Vector; void vector_init(Vector *vec); void vector_destroy(Vector *vec); int vector_push_back(Vector *vec, int value); int vector_pop_back(Vector *vec); int vector_insert(Vector *vec, size_t index, int value); int vector_erase(Vector *vec, size_t index); int vector_get(const Vector *vec, size_t index); void vector_set(Vector *vec, size_t index, int value); size_t vector_size(const Vector *vec); int vector_empty(const Vector *vec); #endif为什么返回值统一用int成功返回 0失败返回 -1因为这是 C 语言里最通用的做法不解释你也能看懂。我比较想说的是vector_get里的const Vector *vec这个意思是“我这个函数只读不改”编译器会帮你检查。培养这个习惯越早越好不然读代码的时候你永远没法从函数签名判断它是否会偷偷改你的数据。3.2 核心函数实现init、destroy、push、pop、insert、erase// vector.c #include vector.h #include stdlib.h #include string.h void vector_init(Vector *vec) { vec-data NULL; vec-size 0; vec-capacity 0; } void vector_destroy(Vector *vec) { free(vec-data); vec-data NULL; vec-size 0; vec-capacity 0; }init的NULL指针是有讲究的。你可能会想为什么不一开始就malloc4 个元素的空间我的答案是零初始化是最安全的状态。你可以无脑地对一个零初始化的结构体调用destroy没有任何副作用NULL也能被安全的freesize0是逻辑上的空数组。如果一开始就分配内存你又得考虑分配失败怎么办、何时释放、会不会泄漏平白增加复杂度。真正需要空间是第一次push_back的时候那时候再分配也不迟。static int vector_grow(Vector *vec) { size_t new_capacity (vec-capacity 0) ? 4 : vec-capacity * 2; int *new_data realloc(vec-data, new_capacity * sizeof(int)); if (new_data NULL) { return -1; } vec-data new_data; vec-capacity new_capacity; return 0; } static int vector_shrink(Vector *vec) { if (vec-size vec-capacity / 2) { return 0; } int *new_data realloc(vec-data, vec-size * sizeof(int)); if (new_data NULL) { return -1; } vec-data new_data; vec-capacity vec-size; return 0; }vector_grow里的static关键字表示这个函数只在当前.c文件里可见对外不暴露这是一种封装手法。扩容倍数我选了 2 倍这背后有两个考量。第一均摊复杂度是 O(1)每次扩容把容量翻倍意味着下一次扩容之前我能插入好多个元素分摊下来每个插入的成本极低。第二吞吐和内存的平衡如果每次只扩容 1 个元素插入 1000 次就要realloc1000 次白白把 O(1) 的操作变成 O(n)如果扩容 3 倍、4 倍浪费的内存又太多。2 倍是经典折中很多语言的动态数组也都这么干。vector_shrink不是必须的甚至有些教材刻意不提缩容。我在实际项目里的体会是缩容要保守不要一砍就砍到size。因为如果用户反复“插一个删一个”每次操作都会触发一次扩容加一次缩容性能会急剧抖动。我这里的策略是当size降到capacity / 2以下时才缩回size大小这样留出了一半余量。int vector_push_back(Vector *vec, int value) { if (vec-size vec-capacity) { if (vector_grow(vec) ! 0) { return -1; } } vec-data[vec-size] value; return 0; } int vector_pop_back(Vector *vec) { if (vec-size 0) { return -1; } vec-size--; vector_shrink(vec); return 0; }push_back的逻辑就是“先检查容量不够就扩容然后写进去”。这里有个细节为什么先vec-size再存我用的是vec-data[vec-size] value因为后置递增会先取当前下标再自增正好符合“用旧下标存值下一次 size 已变”的顺序。你写 位置时一定要想清楚语义写反了就是越界写一个元素。int vector_insert(Vector *vec, size_t index, int value) { if (index vec-size) { return -1; } if (vec-size vec-capacity) { if (vector_grow(vec) ! 0) { return -1; } } // 从后往前搬移避免覆盖 for (size_t i vec-size; i index; i--) { vec-data[i] vec-data[i - 1]; } vec-data[index] value; vec-size; return 0; } int vector_erase(Vector *vec, size_t index) { if (index vec-size) { return -1; } // 从前往后搬移覆盖被删元素 for (size_t i index; i 1 vec-size; i) { vec-data[i] vec-data[i 1]; } vec-size--; vector_shrink(vec); return 0; }插和删的核心是搬移元素。插入时要从尾部开始往后搬不然前面的覆盖后面的删除时要从开头往前搬不然后面的没法依次补上。这个“方向”问题我第一次写反过结果插入后整个数组变成了僵尸局拿调试器看半天才发现是方向反了。你一定要理解循环里i index和i 1 vec-size这两个边界条件的来源以后才能灵活应变。3.3 测试代码自己写测试比自己猜结果更有用// main.c #include stdio.h #include vector.h int main(void) { Vector arr; vector_init(arr); for (int i 0; i 100; i) { if (vector_push_back(arr, i * 10) ! 0) { fprintf(stderr, push_back failed at %d\n, i); break; } } printf(size %zu, capacity %zu\n, vector_size(arr), arr.capacity); for (size_t i 0; i vector_size(arr); i) { printf(%d , vector_get(arr, i)); if ((i 1) % 10 0) putchar(\n); } putchar(\n); vector_insert(arr, 3, 999); printf(after insert, arr[3] %d\n, vector_get(arr, 3)); vector_erase(arr, 3); printf(after erase, arr[3] %d\n, vector_get(arr, 3)); vector_destroy(arr); return 0; }编译的时候我建议养成加警告选项的习惯gcc -Wall -Wextra -g main.c vector.c -o demo-Wall -Wextra会把可疑的代码亮黄牌-g则让你能用 gdb 调试。跑起来你就能看到容量从 4 一路涨到 128 的过程由于我是先扩容再输出第一次push_back后capacity就已经是 4 了第二次到第四次仍然是 4到第五次才跳到 8。这些数字看起来平淡无奇但它们背后就是动态数组在真实世界里干的事。3.4 参数与边界条件瞬间自查下标、空表和容量写完代码我建议你养成一个习惯在insert、erase、get这种带下标参数的函数里第一时间确认边界条件。函数合法的下标范围越界行为空表行为vector_get0 index size未定义行为需要调用者保证必然越界vector_set同上同上同上vector_insert0 index size返回 -1index0时等价于插头部vector_erase0 index size返回 -1返回 -1vector_pop_back无下标不合法返回 -1为什么insert允许index size因为往尾部插入本质就是push_back这是非常自然的语义。而erase不允许index size因为size这个位置本就没有元素。这个边界意识是写容器类代码的基本功。4. 编译通过不算完段错误与内存泄漏排查实录代码写完了程序能跑不代表万事大吉。我自己带项目时最常遇到学生说“我代码编译过了但是跑起来崩了”然后一脸迷茫。这一节我专门把动态数组高频出现的几类问题整理出来每个都附带排查思路这些都是我在真实环境里调试过的东西。4.1 最容易翻车的 5 个运行时错误第一个是忘记初始化就使用。声明Vector arr;后就直接push_back。这时候data是随机值size和capacity也完全没谱push_back一进来就判断size capacity然后往一个不知道指向哪的data里写值。轻则段错误重则悄悄改坏别的变量程序到后面才崩排查起来极其痛苦。解决就一句话vector_init(arr);不能省。第二个是结构体整体赋值引起的二次释放。看这个操作Vector a; vector_init(a); vector_push_back(a, 1); Vector b a; vector_destroy(a); vector_destroy(b); // 这里 double free结构体整体赋值会把data指针也复制过去于是a和b都指向同一块堆内存释放两次必定出问题。这个坑在初学者里特别常见因为其他编程语言里对象赋值会自动拷贝元素而 C 语言里你必须自己区分“深度拷贝”和“浅拷贝”。第三个是下标越界。比如vector_get(arr, 100)但size只有 5。我在实现里没做防御性检查这是故意的——因为标准动态数组的特性就是随机访问不检查边界越界属于调用者的责任。但如果你让调用者来判断调用者又得时刻记住size用起来实在麻烦。折中方案是实现一个vector_at带检查的版本去替代vector_get给新手用而把vector_get留给对性能敏感的生产代码。第四个是指针悬挂。你写了一句int *p vector_get(arr, 0); // 假设返回的是引用我们这里简化成 arr.data[0] vector_push_back(arr, 999); // 可能触发扩容 // 此时 p 指向的旧内存可能已经被 free 了一旦发生扩容底层data会换到别的地方旧的地址已经被释放。你手里那个p还指着老地方访问它就等于访问纪念品。这就是为什么我不建议在持有内部指针的情况下继续往数组里写数据要么先用下标取要么保证后续操作不扩容。第五个是只扩容不缩容导致内存无限增长。比如用户先插入 1 万个数再删除到只剩 1 个。如果没有缩容逻辑底层数组还是拿了能存 8192 个元素的空间白白占着内存。我这版实现里特意加了vector_shrink就是为了处理这种“先膨胀后收缩”的场景但从策略上讲也不该过于激进前面已经提到过。4.2 用 Valgrind 验证你的内存管理我推荐每个学 C 的人都把 Valgrind 当作标配工具尤其是写这种手动管理内存的容器。用法非常简单valgrind --leak-checkfull ./demo输出里会有两行值得关注definitely lost和invalid write/invalid read。前者表示有内存块没释放后者表示你访问了不该访问的地址。我每次写完容器类的代码都会跑一遍 Valgrind不是因为它能解决所有问题而是它能帮你把“内存泄漏”和“越界访问”这类看不见的病提前暴露出来。在 Windows 上没有 Valgrind 可用的话可以用 Visual Studio 的诊断工具或者编写时自带的 CRT 堆检查但思路都是一样的先跑工具再定位再改再重新跑。我见过很多人写代码时自信满满一跑 Valgrind 就沉默了——那些红色警告比任何理论都更能教会你尊重内存。4.3 调试定位技巧从 print 到 gdb 的思路遇到崩溃时最忌讳的是在代码里到处乱加printf然后凭感觉找问题。我的做法是先用gdb跑一遍看崩溃在哪个函数、哪一行。比如gdb ./demo run btbt能打出调用栈一眼就能看到崩溃现场在哪里。如果是越界写通常栈上能看到一个奇怪的下标值或者某个变量已经被写成了莫名其妙的内容。C 语言的调试非常依赖工具你越早学 gdb越少走弯路。实战里还有个土办法也很好用在崩溃点附近写一个printf(index%zu size%zu capacity%zu\n, i, arr.size, arr.capacity);跑一轮看日志往往就能发现下标已经比size大了或者capacity是 0 却往里面写。这种打印式调试对初学者来说比 gdb 门槛低先跑通、再深入工具链也是一条正常路线。5. 下一步扩展泛型和栈应用的改造方向写完了IntArray你是不是觉得这个动态数组太单一了实际业务里你需要存double、存结构体甚至存指针。那要怎么办呢这里我给出两条路一条是改造成工具库时用的“残废但可行”的思路一条是以后可以学的正统做法。5.1 用 void* 实现泛型的思路存储任意数据类型最直接的思路是让data变成void *然后在结构体里额外记录每个元素的大小elem_size。realloc的时候需要乘上元素大小赋值的时候需要用到memcpy。比如typedef struct { void *data; size_t size; size_t capacity; size_t elem_size; } Vector;好处是任意类型都能装进去坏处是类型安全消失了。你在get的时候需要自己把它强转回具体类型的指针int *val (int *)vector_get(v, 0);所有的拷贝工作都是按字节进行的memcpy派上大用场。这种设计接近标准库里一些轻量容器实现的方式适合做底层公共组件。但如果你只是自己练手我建议等我把int版本的彻底吃透了再动这个不然会被绕晕。5.2 用宏实现轻量泛型C 语言里的“模板”思路还有一种在纯 C 里常见的“模板”思路是用宏定义来生成代码。核心做法是把类型名作为宏参数拼出一整套函数和结构体名#define DEFINE_VECTOR(type, name) \ typedef struct { type *data; size_t size; size_t capacity; } name##_Vector; \ /* 下面继续用宏拼接函数名 */这个方向挺好的但入门阶段我不建议深入毕竟宏调试起来实在痛苦。宁可老老实实写一份int版本后面真正需要在项目里用了再抽出时间去做泛型化。5.3 把它改造成一个栈一个扩展方向实例动态数组最常见的应用之一是实现栈。你只需要把已有的接口限制一下入栈vector_push_back出栈vector_pop_back取栈顶vec-data[vec-size - 1]因为栈的两个核心操作都在数组尾部进行动态数组天然适配。你可以用这套小工具去写进制转换、括号匹配、表达式求值等经典练手项目。我在教学时经常让人先写动态数组再去写栈因为栈的实现会反过来加深你对动态数组接口设计的理解——一个好用的容器应该能让使用者几乎感觉不到底层扩容的存在。我个人在实际操作中的体会是这种小容器的价值远不止于“能存数”。它逼着你一遍遍思考“内存是谁的”“谁负责释放”“指针什么时候会失效”这些问题才是 C 语言能力的真正分水岭。每次写完松一口气之后记得跑一把 Valgrind然后故意改坏一两个索引位置把错误重新炸出来亲手修一遍。这个过程比看十遍书都有用。 
长河君 · 2026/10/13 23:43:58 · 阅读 1.2k C语言手写动态数组：从指针到内存管理的完整实战
1. 为什么第九篇我选了动态数组设计思路与代码结构C语言学到第九篇指针、结构体、内存管理基本都见过了但很多初学者仍然卡在一个瓶颈上单独看每个知识点都懂一写综合点的代码就不知道从哪下手。这一篇我特意选了“手写一个动态数组”作为实战案例就是因为它能把指针、结构体、堆内存、函数传参这几块硬骨头全部揉在一起而且做完后你会得到一个能真正用在项目里的工具不是那种跑完就删的练习题。动态数组是什么一句话解释一个能够自动扩容的数组。普通数组长度写死int arr[10]就是 10 个格子多了装不下少了浪费内存。动态数组底层其实也是连续内存但它会在空间不够时申请一块更大的新内存把老数据搬过去然后把旧的还回去。用这个思路去理解它你会瞬间看透 C 语言里数组和指针之间的本质关系——数组名不是指针但数组在函数间传递、在堆上申请时几乎处处都在通过指针操作。我见过不少人在学习时只关注语法本身比如“二重指针是什么意思”“realloc怎么用”但一旦要把它们组合起来就懵了。这个现象很正常C 语言的知识点不是孤立的你不把它们串成一个整体去实践就永远感觉是在学碎片。这第九篇的定位就是把前面零散的知识串起一条线来。你可能想问为什么不是链表链表在插入删除上确实灵活但它每个节点单独分配内存节点之间用指针相连对你理解“连续内存”帮助不大。而动态数组的核心价值有两个底层是连续内存缓存命中率高随机访问是 O(1)扩容逻辑逼着你处理realloc、指针失效、内存释放这些真正折磨人的问题换句话说动态数组是练“内存布局”意识的最好载体。链表练的是“指针指向”动态数组练的是“一块内存怎么长大”。整个设计的最终目标也很朴素写一个Vector支持初始化、释放、追加、弹出、按下标读写、按位置插删还要有容量自动扩展。真正难的不是功能本身而是你在每一个细节上做出的取舍比如容量因子选多少、缩容策略要不要做、结构体里为什么放两个字段而不放三个。下面一个一个小节拆开讲。1.1 动态数组比普通数组好在哪内存布局与扩容逻辑先理解一个问题为什么动态数组能“动态”关键在于它把数组的控制权从编译器手里夺了回来。普通数组声明出来内存大小在编译期就固定了如果你想根据用户输入来决定数组长度标准 C 里你是做不到的——C99 之后虽然有了变长数组但它分配的往往是栈内存一来不能太大二来生命周期很受限。动态数组的做法完全不同一开始在堆上分配一小块内存比如能放 4 个元素然后每次写满时重新分配一块更大的内存。这里的“重新分配”有两种实现方式一般初学者会搞混先malloc新内存再memcpy旧数据再free旧内存。逻辑清晰但代码啰嗦。直接用realloc。它内部会帮你处理“原地扩展”和“搬到新家”两种情况如果后面有空闲空间就原地扩大指针范围如果不够就重新找一块内存自动拷贝旧数据并释放旧块。大多数情况下用realloc就够了但有个铁律必须记住永远不要把realloc的返回值直接赋给原来的指针。因为一旦分配失败realloc会返回NULL如果你直接p realloc(p, new_size)原来的p就丢了不仅数据全丢而且旧内存没人释放等于一手造成泄漏和崩溃。正确写法是先拿一个临时指针接返回值判断成功后再覆盖。int *new_ptr realloc(arr-data, new_capacity * sizeof(int)); if (new_ptr NULL) { // 处理失败但 arr-data 还在还能安全继续用 return -1; } arr-data new_ptr; arr-capacity new_capacity;这一步就是整个动态数组的灵魂。可以说你如果把这个realloc的细节琢磨透了以后写任何涉及扩容的代码都不会在内存上翻车。1.2 结构体里为什么要存 size 和 capacity 两个字段size表示当前实际存了多少个元素capacity表示当前底层数组最多能存多少个。这俩看着像但作用完全是两码事。size是给使用者看的逻辑长度capacity是给内存管理用的物理容量。好比一个书包装了多少本书是size书包设计能装多少本是capacity你每次把书装满就得换个大书包。很多初学者嫌麻烦只记一个长度然后用完了就扩容。短期看好像够用一旦你想把动态数组当成通用容器用比如要支持中间插入、删除、随机访问没有capacity你根本不知道自己还有没有余量去放新元素。每次push_back都判断当前下标是否等于数组长度长度加 1 就扩容这种写法有两个毛病你在插入时不知道底层容量还剩多少需要额外定义容量变量或者自己推算结构体里不存容量函数之间传参时你就得多带一个参数接口设计一下就变得很难看不统一所以我在设计时结构体固定放三个字段typedef struct { int *data; // 指向堆区连续内存的指针 size_t size; // 当前元素个数 size_t capacity; // 当前分配的内存能容纳的元素个数 } Vector;这里有个隐藏问题值得细说。size和capacity到底用int还是size_t我在项目里统一用size_t。原因很简单C 标准里malloc、realloc、数组下标这些操作天然无符号sizeof返回的也是size_t。如果你用int混用的时候编译器会报警告稍微复杂一点的运算还可能溢出。唯一麻烦的是size_t是非负的写循环判断时要注意不要写成for (int i size - 1; i 0; i--)这种蠢代码直接用while (size 0)或size_t i size; i 0; i--。这个坑我在带新人的时候几乎每次都能见到大家都不太注意无符号类型绕回的特性。2. 指针没吃透先搞定这 4 个关键细节动态数组的核心离不开指针操作。如果这一篇只给代码不讲指针那就等于让你背答案换个题目照样懵。所以我把整个实现里最关键的指针问题拆成四个细节单独说清楚每个都是曾经让我和身边同事踩过坑的地方。2.1 结构体指针传参与修改为什么经常要传二级指针很多初学者写初始化函数时会这么干void init(Vector vec) { vec.data NULL; vec.size 0; vec.capacity 0; }看起来逻辑很合理实际运行一点效果都没有。原因在于 C 语言里函数参数是值传递vec传入函数后会生成一份拷贝你在函数内部修改的只是那份拷贝外面原始的Vector变量纹丝未动。解决思路有两个方案一传指针修改指针指向的内容void init(Vector *vec) { vec-data NULL; vec-size 0; vec-capacity 0; }调用的时候init(arr)vec指向外界的真正的arr所有vec-xxx的修改都会真实落回去。这个方案适用于“结构体已经存在只需要初始化”的场景。方案二返回新结构体Vector init(void) { Vector vec {0}; return vec; }调用时Vector arr init();。因为结构体可以整体赋值直接把返回值拷给arr也不用。两种方案各有优劣。方案一适合像realloc这种需要修改底层数据的场景方案二写起来更简洁但在后续扩展中如果函数改完还想返回新的容量、长度之类的信息就显得捉襟见肘。我个人习惯是统一用指针版本因为动态数组后续还要写插入、删除、清空等操作这些函数往往需要修改size甚至data传指针是唯一省事的写法。2.2 数组名和指针的关系下标访问到底是怎么工作的C 语言里arr[i]本质上是*(arr i)的语法糖。这一点是理解数组、指针、下标三者关系的钥匙。动态数组里arr-data[i]就是先拿到连续内存的起始地址再做一次指针偏移和解引用。正因为如此你才能用一个int *的data字段同时表示“底层的数组”、以及“通过下标访问数组”这两件事在 C 语言中是同一回事。有一个细节容易让新手怀疑人生如果你拿到的是一个指向Vector的指针比如Vector *vec那么vec-data[i]里面data本身就是一个指针data[i]和*(data i)完全等价。这个写法嵌套了两个指针层次但逻辑上是清楚分层的第一层是结构体指针vec指向结构体第二层是结构体里的data指针指向数组首元素。建议你在纸上画一下内存图真的会通很多。2.3 为什么free之后指针还要置空写destroy函数时最容易被忽略的一步是free完之后没有把data置为NULL。举个例子void destroy(Vector *vec) { free(vec-data); }如果调用两次destroy(arr)第二次free的是一块已经被释放的内存。这不是一定崩溃但是是未定义行为轻则啥事没有重则堆结构被破坏程序跑着跑着莫名崩溃特别难排查。所以标准的做法是void destroy(Vector *vec) { free(vec-data); vec-data NULL; vec-size 0; vec-capacity 0; }free(NULL)是安全的C 标准明确规定对空指针free不做任何事。所以把指针置空后哪怕有人不小心再次调用destroy也没法造成破坏。这条经验我在项目里已经养成肌肉记忆了只要是释放内存的接口我都会顺手把指针置空。看起来只是多一行代码省掉的问题是成倍的。2.4realloc失败时不要裸奔安全扩容的标准动作前面提到临时指针接返回值这里再补充两个细节。很多人把扩容逻辑简化成arr-data realloc(arr-data, new_capacity * sizeof(int)); arr-capacity new_capacity;这段代码十次有九次能用唯一一次不能用就是内存不足时realloc返回NULL然后你干了两件蠢事一是把NULL赋给了原来好端端的data旧内存从此找不回来二是又把capacity更新成了一个新容量但data实际上什么都存不了。后续一写入就段错误而且你根本找不到是谁干的。正确的扩容逻辑请直接抄下面的模式int vector_reserve(Vector *vec, size_t new_capacity) { if (new_capacity vec-capacity) { return 0; } int *new_data realloc(vec-data, new_capacity * sizeof(int)); if (new_data NULL) { return -1; // 失败时保持原 vec 完全不变 } vec-data new_data; vec-capacity new_capacity; return 0; }这里我想多讲一层new_capacity * sizeof(int)这个乘法也有风险。如果new_capacity是外界传进来的你没法保证它乘完不溢出。真正严谨的库会检查溢出但初学者阶段我觉得意识到这个问题就够了不要为了过度防御把代码搞得很难读。3. 手把手写出可复用的动态数组完整实现与测试讲完原理和易踩的坑现在进入实操环节。这一节我会把完整代码贴出来然后逐段解释每个函数的设计意图并且给出一份能直接跑起来的测试用例。你不需要照着抄一遍而是要知道每个函数为什么要这么写这样到你自己改造成其他类型时才能有底气。3.1 整体头文件设计接口清晰比什么都重要动态数组虽然不是库但写它的过程中你就该养成“接口设计”的习惯。我把声明全部放在一个头文件里然后实现放.c文件主测试文件放另一个.c。这样哪怕你现在只是自己练手也能立刻感受到模块化带来的好处。// vector.h #ifndef VECTOR_H #define VECTOR_H #include stddef.h typedef struct { int *data; size_t size; size_t capacity; } Vector; void vector_init(Vector *vec); void vector_destroy(Vector *vec); int vector_push_back(Vector *vec, int value); int vector_pop_back(Vector *vec); int vector_insert(Vector *vec, size_t index, int value); int vector_erase(Vector *vec, size_t index); int vector_get(const Vector *vec, size_t index); void vector_set(Vector *vec, size_t index, int value); size_t vector_size(const Vector *vec); int vector_empty(const Vector *vec); #endif为什么返回值统一用int成功返回 0失败返回 -1因为这是 C 语言里最通用的做法不解释你也能看懂。我比较想说的是vector_get里的const Vector *vec这个意思是“我这个函数只读不改”编译器会帮你检查。培养这个习惯越早越好不然读代码的时候你永远没法从函数签名判断它是否会偷偷改你的数据。3.2 核心函数实现init、destroy、push、pop、insert、erase// vector.c #include vector.h #include stdlib.h #include string.h void vector_init(Vector *vec) { vec-data NULL; vec-size 0; vec-capacity 0; } void vector_destroy(Vector *vec) { free(vec-data); vec-data NULL; vec-size 0; vec-capacity 0; }init的NULL指针是有讲究的。你可能会想为什么不一开始就malloc4 个元素的空间我的答案是零初始化是最安全的状态。你可以无脑地对一个零初始化的结构体调用destroy没有任何副作用NULL也能被安全的freesize0是逻辑上的空数组。如果一开始就分配内存你又得考虑分配失败怎么办、何时释放、会不会泄漏平白增加复杂度。真正需要空间是第一次push_back的时候那时候再分配也不迟。static int vector_grow(Vector *vec) { size_t new_capacity (vec-capacity 0) ? 4 : vec-capacity * 2; int *new_data realloc(vec-data, new_capacity * sizeof(int)); if (new_data NULL) { return -1; } vec-data new_data; vec-capacity new_capacity; return 0; } static int vector_shrink(Vector *vec) { if (vec-size vec-capacity / 2) { return 0; } int *new_data realloc(vec-data, vec-size * sizeof(int)); if (new_data NULL) { return -1; } vec-data new_data; vec-capacity vec-size; return 0; }vector_grow里的static关键字表示这个函数只在当前.c文件里可见对外不暴露这是一种封装手法。扩容倍数我选了 2 倍这背后有两个考量。第一均摊复杂度是 O(1)每次扩容把容量翻倍意味着下一次扩容之前我能插入好多个元素分摊下来每个插入的成本极低。第二吞吐和内存的平衡如果每次只扩容 1 个元素插入 1000 次就要realloc1000 次白白把 O(1) 的操作变成 O(n)如果扩容 3 倍、4 倍浪费的内存又太多。2 倍是经典折中很多语言的动态数组也都这么干。vector_shrink不是必须的甚至有些教材刻意不提缩容。我在实际项目里的体会是缩容要保守不要一砍就砍到size。因为如果用户反复“插一个删一个”每次操作都会触发一次扩容加一次缩容性能会急剧抖动。我这里的策略是当size降到capacity / 2以下时才缩回size大小这样留出了一半余量。int vector_push_back(Vector *vec, int value) { if (vec-size vec-capacity) { if (vector_grow(vec) ! 0) { return -1; } } vec-data[vec-size] value; return 0; } int vector_pop_back(Vector *vec) { if (vec-size 0) { return -1; } vec-size--; vector_shrink(vec); return 0; }push_back的逻辑就是“先检查容量不够就扩容然后写进去”。这里有个细节为什么先vec-size再存我用的是vec-data[vec-size] value因为后置递增会先取当前下标再自增正好符合“用旧下标存值下一次 size 已变”的顺序。你写 位置时一定要想清楚语义写反了就是越界写一个元素。int vector_insert(Vector *vec, size_t index, int value) { if (index vec-size) { return -1; } if (vec-size vec-capacity) { if (vector_grow(vec) ! 0) { return -1; } } // 从后往前搬移避免覆盖 for (size_t i vec-size; i index; i--) { vec-data[i] vec-data[i - 1]; } vec-data[index] value; vec-size; return 0; } int vector_erase(Vector *vec, size_t index) { if (index vec-size) { return -1; } // 从前往后搬移覆盖被删元素 for (size_t i index; i 1 vec-size; i) { vec-data[i] vec-data[i 1]; } vec-size--; vector_shrink(vec); return 0; }插和删的核心是搬移元素。插入时要从尾部开始往后搬不然前面的覆盖后面的删除时要从开头往前搬不然后面的没法依次补上。这个“方向”问题我第一次写反过结果插入后整个数组变成了僵尸局拿调试器看半天才发现是方向反了。你一定要理解循环里i index和i 1 vec-size这两个边界条件的来源以后才能灵活应变。3.3 测试代码自己写测试比自己猜结果更有用// main.c #include stdio.h #include vector.h int main(void) { Vector arr; vector_init(arr); for (int i 0; i 100; i) { if (vector_push_back(arr, i * 10) ! 0) { fprintf(stderr, push_back failed at %d\n, i); break; } } printf(size %zu, capacity %zu\n, vector_size(arr), arr.capacity); for (size_t i 0; i vector_size(arr); i) { printf(%d , vector_get(arr, i)); if ((i 1) % 10 0) putchar(\n); } putchar(\n); vector_insert(arr, 3, 999); printf(after insert, arr[3] %d\n, vector_get(arr, 3)); vector_erase(arr, 3); printf(after erase, arr[3] %d\n, vector_get(arr, 3)); vector_destroy(arr); return 0; }编译的时候我建议养成加警告选项的习惯gcc -Wall -Wextra -g main.c vector.c -o demo-Wall -Wextra会把可疑的代码亮黄牌-g则让你能用 gdb 调试。跑起来你就能看到容量从 4 一路涨到 128 的过程由于我是先扩容再输出第一次push_back后capacity就已经是 4 了第二次到第四次仍然是 4到第五次才跳到 8。这些数字看起来平淡无奇但它们背后就是动态数组在真实世界里干的事。3.4 参数与边界条件瞬间自查下标、空表和容量写完代码我建议你养成一个习惯在insert、erase、get这种带下标参数的函数里第一时间确认边界条件。函数合法的下标范围越界行为空表行为vector_get0 index size未定义行为需要调用者保证必然越界vector_set同上同上同上vector_insert0 index size返回 -1index0时等价于插头部vector_erase0 index size返回 -1返回 -1vector_pop_back无下标不合法返回 -1为什么insert允许index size因为往尾部插入本质就是push_back这是非常自然的语义。而erase不允许index size因为size这个位置本就没有元素。这个边界意识是写容器类代码的基本功。4. 编译通过不算完段错误与内存泄漏排查实录代码写完了程序能跑不代表万事大吉。我自己带项目时最常遇到学生说“我代码编译过了但是跑起来崩了”然后一脸迷茫。这一节我专门把动态数组高频出现的几类问题整理出来每个都附带排查思路这些都是我在真实环境里调试过的东西。4.1 最容易翻车的 5 个运行时错误第一个是忘记初始化就使用。声明Vector arr;后就直接push_back。这时候data是随机值size和capacity也完全没谱push_back一进来就判断size capacity然后往一个不知道指向哪的data里写值。轻则段错误重则悄悄改坏别的变量程序到后面才崩排查起来极其痛苦。解决就一句话vector_init(arr);不能省。第二个是结构体整体赋值引起的二次释放。看这个操作Vector a; vector_init(a); vector_push_back(a, 1); Vector b a; vector_destroy(a); vector_destroy(b); // 这里 double free结构体整体赋值会把data指针也复制过去于是a和b都指向同一块堆内存释放两次必定出问题。这个坑在初学者里特别常见因为其他编程语言里对象赋值会自动拷贝元素而 C 语言里你必须自己区分“深度拷贝”和“浅拷贝”。第三个是下标越界。比如vector_get(arr, 100)但size只有 5。我在实现里没做防御性检查这是故意的——因为标准动态数组的特性就是随机访问不检查边界越界属于调用者的责任。但如果你让调用者来判断调用者又得时刻记住size用起来实在麻烦。折中方案是实现一个vector_at带检查的版本去替代vector_get给新手用而把vector_get留给对性能敏感的生产代码。第四个是指针悬挂。你写了一句int *p vector_get(arr, 0); // 假设返回的是引用我们这里简化成 arr.data[0] vector_push_back(arr, 999); // 可能触发扩容 // 此时 p 指向的旧内存可能已经被 free 了一旦发生扩容底层data会换到别的地方旧的地址已经被释放。你手里那个p还指着老地方访问它就等于访问纪念品。这就是为什么我不建议在持有内部指针的情况下继续往数组里写数据要么先用下标取要么保证后续操作不扩容。第五个是只扩容不缩容导致内存无限增长。比如用户先插入 1 万个数再删除到只剩 1 个。如果没有缩容逻辑底层数组还是拿了能存 8192 个元素的空间白白占着内存。我这版实现里特意加了vector_shrink就是为了处理这种“先膨胀后收缩”的场景但从策略上讲也不该过于激进前面已经提到过。4.2 用 Valgrind 验证你的内存管理我推荐每个学 C 的人都把 Valgrind 当作标配工具尤其是写这种手动管理内存的容器。用法非常简单valgrind --leak-checkfull ./demo输出里会有两行值得关注definitely lost和invalid write/invalid read。前者表示有内存块没释放后者表示你访问了不该访问的地址。我每次写完容器类的代码都会跑一遍 Valgrind不是因为它能解决所有问题而是它能帮你把“内存泄漏”和“越界访问”这类看不见的病提前暴露出来。在 Windows 上没有 Valgrind 可用的话可以用 Visual Studio 的诊断工具或者编写时自带的 CRT 堆检查但思路都是一样的先跑工具再定位再改再重新跑。我见过很多人写代码时自信满满一跑 Valgrind 就沉默了——那些红色警告比任何理论都更能教会你尊重内存。4.3 调试定位技巧从 print 到 gdb 的思路遇到崩溃时最忌讳的是在代码里到处乱加printf然后凭感觉找问题。我的做法是先用gdb跑一遍看崩溃在哪个函数、哪一行。比如gdb ./demo run btbt能打出调用栈一眼就能看到崩溃现场在哪里。如果是越界写通常栈上能看到一个奇怪的下标值或者某个变量已经被写成了莫名其妙的内容。C 语言的调试非常依赖工具你越早学 gdb越少走弯路。实战里还有个土办法也很好用在崩溃点附近写一个printf(index%zu size%zu capacity%zu\n, i, arr.size, arr.capacity);跑一轮看日志往往就能发现下标已经比size大了或者capacity是 0 却往里面写。这种打印式调试对初学者来说比 gdb 门槛低先跑通、再深入工具链也是一条正常路线。5. 下一步扩展泛型和栈应用的改造方向写完了IntArray你是不是觉得这个动态数组太单一了实际业务里你需要存double、存结构体甚至存指针。那要怎么办呢这里我给出两条路一条是改造成工具库时用的“残废但可行”的思路一条是以后可以学的正统做法。5.1 用 void* 实现泛型的思路存储任意数据类型最直接的思路是让data变成void *然后在结构体里额外记录每个元素的大小elem_size。realloc的时候需要乘上元素大小赋值的时候需要用到memcpy。比如typedef struct { void *data; size_t size; size_t capacity; size_t elem_size; } Vector;好处是任意类型都能装进去坏处是类型安全消失了。你在get的时候需要自己把它强转回具体类型的指针int *val (int *)vector_get(v, 0);所有的拷贝工作都是按字节进行的memcpy派上大用场。这种设计接近标准库里一些轻量容器实现的方式适合做底层公共组件。但如果你只是自己练手我建议等我把int版本的彻底吃透了再动这个不然会被绕晕。5.2 用宏实现轻量泛型C 语言里的“模板”思路还有一种在纯 C 里常见的“模板”思路是用宏定义来生成代码。核心做法是把类型名作为宏参数拼出一整套函数和结构体名#define DEFINE_VECTOR(type, name) \ typedef struct { type *data; size_t size; size_t capacity; } name##_Vector; \ /* 下面继续用宏拼接函数名 */这个方向挺好的但入门阶段我不建议深入毕竟宏调试起来实在痛苦。宁可老老实实写一份int版本后面真正需要在项目里用了再抽出时间去做泛型化。5.3 把它改造成一个栈一个扩展方向实例动态数组最常见的应用之一是实现栈。你只需要把已有的接口限制一下入栈vector_push_back出栈vector_pop_back取栈顶vec-data[vec-size - 1]因为栈的两个核心操作都在数组尾部进行动态数组天然适配。你可以用这套小工具去写进制转换、括号匹配、表达式求值等经典练手项目。我在教学时经常让人先写动态数组再去写栈因为栈的实现会反过来加深你对动态数组接口设计的理解——一个好用的容器应该能让使用者几乎感觉不到底层扩容的存在。我个人在实际操作中的体会是这种小容器的价值远不止于“能存数”。它逼着你一遍遍思考“内存是谁的”“谁负责释放”“指针什么时候会失效”这些问题才是 C 语言能力的真正分水岭。每次写完松一口气之后记得跑一把 Valgrind然后故意改坏一两个索引位置把错误重新炸出来亲手修一遍。这个过程比看十遍书都有用。