1. 翻出2015年的培训班笔记本第四章为什么今天还要重读上周整理书架从一摞旧书里翻出来一个软皮笔记本封面磨得发白书脊处贴着透明胶带。翻开一看是2015年夏天参加C语言培训班时留下的课堂笔记。那时候我还是个连数组两个字都觉得像天书的小白如今再翻这页纸字迹潦草错别字一堆但第四章数组与字符串的内容却让我越看越觉得有必要重新整理一遍。为什么因为这些年我陆续写过Java、Python、JavaScript、Go但凡是碰到排序、字符串处理、二维数组遍历这类基础问题脑子里自动浮现的还是当年那套C语言的底层逻辑。数组和字符串是几乎所有编程语言共有的基础结构但C语言把它们逼到了最原始的形态——你就直接站在内存面前没有包装、没有封装、没有任何帮你兜底的东西。这种裸奔式的学习经历反而是打牢基础的最佳途径。这一章笔记的内容其实不算难从数组的定义与初始化开始讲一维和二维数组的遍历然后进入字符串的字符数组本质与常用操作最后落到排序算法冒泡、选择和一点简单的算法思想。今天这篇博文就是把这章笔记重新誊写一遍加上我个人这些年实际工作中踩过的坑和补齐的理解希望能帮到正在啃C语言基础的朋友也当作给当年那个在笔记本上抄代码的自己一个交代。适合谁看如果你正在学C语言数组和字符串学过但总觉得会了又没完全会这篇可以帮你把概念夯实如果你已经在用其他语言写业务代码也可以借这篇回看一下底层的内存与指针思维处理复杂数据问题时会更有底气。2. 数组定义与初始化当年反复被敲黑板的初始化陷阱2.1 一维数组的几种写法差别比想象中大笔记第一页老师用红笔圈了五行代码int a[5]; /* 建议不要这样声明完直接用 */ int a[5] {0}; /* 全部元素初始化为0 */ int a[5] {1, 2, 3}; /* 前三个有值后两个自动补0 */ int a[] {1, 2, 3, 4, 5}; /* 由初始化列表推导长度 */ static int a[5]; /* 静态存储期自动清零 */当年我只会机械地把五行抄进笔记本心想不就是定义个数组嘛有啥区别。后来才知道这五行之间差别大了去了。int a[5];如果声明在函数内部属于自动存储期不初始化就直接用里面装的是栈上残留的随机值。当年培训班后期调试程序经常遇到数组里莫名其妙出现一个天文数字的诡异问题十次里有八次是没初始化。int a[5] {0};是最稳妥的写法C标准保证只要初始化列表里出现了至少一个值其余未列出的元素一律自动补0。所以想清空数组直接写这一个0就够了不用费劲写一长串0。int a[] {1,2,3,4,5};由编译器帮你算长度省事但只适合初始化时就确定好全部值的场景。一旦数组长度需要由运行时数据决定就得走后面第6节要讲的动态内存那条路了。static int a[5];连初始化都不用写静态存储期的变量默认就是0。这个特性在写全局数组或者需要长期保存状态的场景里很好用但要注意静态数组不随函数返回而销毁内存占用也一直在。2.2 memset与sizeof初始化习惯影响了我后来的职业生涯笔记后面补了一段memset的用法这也是后来我在真实项目里使用频率最高的函数之一#include string.h int buf[1024]; memset(buf, 0, sizeof(buf));memset按字节填充内存把buf指向的sizeof(buf)个字节全部填成0。关键点在于sizeof(buf)返回的是整个数组的字节数不需要手算元素个数这样最安全。我在这个函数上踩过一个特别典型的坑。有一年维护一段网络通信模块别人写的代码是memset(buf, 0, 1024); /* 看起来没问题 */问题在于当时buf已经被改成了char buf[2048]但memset第三参数还停留在1024。编译不报错运行也不一定立刻崩溃但缓冲区后半部分1024字节的旧数据会被当成用户内容拿去解析导致偶发性的协议解析错乱。这种bug非常磨人日志看不到规律重启又恢复正常后来一行行代码排查才定位到是memset长度没跟上数组定义。从那以后我给自己定了一条死规矩凡是memset和数组出现在一起一律写sizeof(buf)禁止写硬编码数字。这个习惯的源头就是2015年那章笔记里初始化必须认真六个字。跟我的学员讲这个例子他们总觉得我小题大做直到自己碰上一次才会心一笑。3. 遍历与二维数组血泪换来的边界意识3.1 一维遍历起始下标与结束条件要对着看笔记里遍历的例题很朴素求数组最大值、求和、逆序输出。典型代码如下int arr[] {9, 5, 2, 7, 3}; int n sizeof(arr) / sizeof(arr[0]); int max arr[0]; for (int i 1; i n; i) { if (arr[i] max) { max arr[i]; } }最值得背下来的不是循环本身而是sizeof(arr) / sizeof(arr[0])这个计算元素个数的惯用法。当年老师让我们把它当公式记牢说是防止把数组长度写死。我一开始不以为然数组长度明明写在定义里了费这个劲干啥直到工作后接手一个老项目里面全是硬编码的数组长度比如for (int i 0; i 10; i)而数组定义早就从10个元素改成了20个尾巴上10个元素永远遍历不到。那是个库存统计分析程序有个汇总功能时不时少算一批数据查了两天才定位到是循环边界没跟着数组定义走。从那时起才理解sizeof(arr)/sizeof(arr[0])这句看似多余的废话其实是C语言里性价比最高的防御式编程。还有一个细节遍历的起始下标和结束条件必须对照着检查。for (int i 0; i n; i)是标准写法但新手很容易写顺手写成i n这就是典型的越界访问。C语言数组越界不报错你读到的是相邻内存位置的垃圾值——这是C语言最坑人的地方也是最锻炼人的地方。当年培训班老师在黑板上画了一排格子下标标成0到n-1反复强调最后一个元素的下标永远是n-1这个印象我一直保留到现在。3.2 二维数组与鞍点问题理解行列不对称笔记里二维数组的实战题是经典的5*5鞍点问题在一个5行5列的矩阵中找某个元素它既是所在行的最大值又是所在列的最小值。这道题我至今还记得解法结构#include stdio.h #include limits.h int main(void) { int matrix[5][5] { {11, 3, 5, 6, 9}, {12, 4, 7, 8, 10}, {10, 5, 6, 9, 11}, { 8, 6, 4, 7, 2}, {15, 10, 11, 20, 25} }; int i, j, k; int found 0; int saddle_row -1, saddle_col -1, saddle_val 0; for (i 0; i 5; i) { /* 第1步找出第i行的最大值并记住它所在的列号 */ int row_max INT_MIN; int col_of_max 0; for (j 0; j 5; j) { if (matrix[i][j] row_max) { row_max matrix[i][j]; col_of_max j; } } /* 第2步检查这个元素在它那一列中是不是最小值 */ int col_min matrix[0][col_of_max]; for (k 1; k 5; k) { if (matrix[k][col_of_max] col_min) { col_min matrix[k][col_of_max]; } } if (row_max col_min) { found 1; saddle_row i; saddle_col col_of_max; saddle_val row_max; break; } } if (found) { printf(鞍点位于 matrix[%d][%d]值为 %d\n, saddle_row, saddle_col, saddle_val); } else { printf(矩阵中不存在鞍点\n); } return 0; }这段代码的核心逻辑是两步走先在当前行里找最大值并记录列号再到这一列里验证该值是否也是最小值。INT_MIN来自limits.h用来初始化当前最大值保证第一个元素就能被纳进比较——这是当年培训班特意用到的头文件考点。为什么这道题值得反复做因为它强迫你理解二维数组的两个维度是不对称的。按行遍历时外层循环固定行号i、内层循环变动列号j按列遍历时就要固定列号、变动行号。这个行优先和列优先的思维转换是二维数组最重要的基本功。我后来处理地图数据、邻接矩阵、图像像素全都建立在这个认知上。3.3 九九乘法表嵌套循环最好的试炼场培训班还留了一道课后题打印九九乘法表。看起来简单其实是检验嵌套循环理解程度的经典题目#include stdio.h int main(void) { for (int i 1; i 9; i) { for (int j 1; j i; j) { printf(%d*%d%-2d , j, i, i * j); } printf(\n); } return 0; }关键在于内层循环的结束条件是j i这样打印出来的是一个左下三角。%-2d表示左对齐、最少占2位保证输出对齐美观。这道题再怎么强调不过分因为嵌套循环的控制逻辑——外层管行数、内层管每行内容——和咱们处理二维数组时一模一样。能把九九乘法表闭着眼写对的人二维数组遍历基本不会出大问题。我面试新人时也喜欢拿它当热身题不光是考语法更是看对方有没有真正理解循环变量之间的关系。4. 字符串不是普通数组探清本质再动手4.1 字符数组与字符串就差一个\0笔记有一页专门画了内存示意图char s[] hello;在内存里实际占6个字节最后一个是字符串结束标志\0。当年老师反复强调C语言字符串本质上就是以\0结尾的字符数组。这句话听着简单实际使用中埋的雷特别多char s[5] hello; /* 错误5个字节装不下 hello\0需要6个字节 */ char s[6] hello; /* 正确 */ char s[] hello; /* 正确编译器自动分配6个字节 */s[5]这种错误非常隐蔽编译器通常只给个警告甚至完全放行但\0已经写到了数组外面。字符串看起来是对的一旦调用strlen、strcpy这类函数就会沿着内存继续读下去。我在培训班写一个学生信息管理程序时就栽过一回定义了char name[8]想存一个8字节英文名结果name后面紧跟着学号变量strlen(name)返回了13整个学生信息打印出来乱七八糟。最后才明白是\0无处安放把旁边变量的内存污染了。这类问题的坑点在于它不直接崩溃而是静默地破坏相邻数据排查难度很高。4.2 sizeof(s)与strlen(s)为什么算出来不一样笔记里有个对比我一直沿用到今天给新人讲课写法结果含义char s[] hello; sizeof(s)6整个字符数组占用的字节数含\0char s[] hello; strlen(s)5有效字符个数不含\0char *p hello; sizeof(p)864位系统指针本身的字节数与字符串长度无关char *p hello; strlen(p)5指针指向的字符串的有效长度sizeof是编译期算子计算的是变量在内存中占的空间strlen是运行时函数沿着指针一个个数字符直到碰到\0为止。这个对比是理解数组和指针区别的第一道分水岭。当年笔记上用红笔写得明白sizeof测的是盒子的大小strlen测的是盒子里装的货的长度。话说得糙但特别好用。4.3 字符串逆序笔试面试里经久不衰的题笔记后面有一道练习到现在面试别人我还常出字符串逆序输出。输入hello输出olleh。培训班的标准解法是两个下标一前一后往中间走交换字符#include stdio.h #include string.h void reverse_str(char s[]) { int left 0; int right strlen(s) - 1; while (left right) { char tmp s[left]; s[left] s[right]; s[right] tmp; left; right--; } } int main(void) { char s[] hello; reverse_str(s); printf(%s\n, s); return 0; }这道题考三个点第一能不能想到用strlen拿右边界第二交换两个字符时知不知道要引入临时变量tmp第三循环条件为什么是left right而不是left ! right。第三个点是很多人栽过跟头的细节。当字符串长度是偶数时两个指针会刚好在中间错过去。如果条件是left ! right它们会把已经交换过的部分再交换一遍字符串最终回到原样。只有用才能保证在中间停下。还有一个更容易踩的坑不能写成char *p hello;然后拿p去reverse_str修改。因为字符串字面量存储在只读数据段修改它会段错误。正确做法就是示例里用字符数组char s[] hello;。这个区分在当年的笔记里没被强调是我后来自己运行崩溃了才补在空白处的。4.4 字符串按空格分割strtok的副作用要心里有数另一道作业是把一个字符串按空格分割成若干子串。培训班提供了两种思路一是自己遍历字符、遇到空格就把当前位置之前的字符当一段二是直接使用strtok函数。#include stdio.h #include string.h int main(void) { char line[] hello world from c training class; char *token strtok(line, ); while (token ! NULL) { printf(%s\n, token); token strtok(NULL, ); } return 0; }用strtok时有个必须知道的副作用它会修改原始字符串把分隔符位置替换成\0。如果你后续还要用到原始的整体字符串就得先把内容复制一份。我在实际项目里就犯过这个错——用strtok切完字符串之后原变量变得千疮百孔再打印出来是一段一段的当时还以为是并发问题排查了半天才明白是strtok把源串改了。现在用strtok_sWindows或strtok_rLinux可以支持多线程安全但理解分割会破坏原串这个底层事实无论用哪个版本都一样重要。5. 排序算法实战从冒泡到归并的成长路径5.1 冒泡排序先写对再谈优化笔记里排序部分从冒泡排序开始2015年版是最原始的写法void bubble_sort(int arr[], int n) { for (int i 0; i n - 1; i) { for (int j 0; j n - 1 - i; j) { if (arr[j] arr[j 1]) { int tmp arr[j]; arr[j] arr[j 1]; arr[j 1] tmp; } } } }内层循环的j n - 1 - i是精髓每完成一轮外循环最大的元素就冒泡到了最后一位下一轮没有必要再比较它所以内层范围可以随i的增长而缩小。冒泡排序时间复杂度是 O(n²)数据量大时确实慢但教学价值无可替代——它把两两比较、交换位置这两个排序的核心动作直观地摆在面前。后来我学快排、归并、堆排序发现不管多高级的排序算法本质都是在不同策略下重复这两件事。笔试常考一个小改进加一个标志位如果某一轮内层循环完全没有发生交换说明数组已有序直接跳出void bubble_sort(int arr[], int n) { for (int i 0; i n - 1; i) { int swapped 0; for (int j 0; j n - 1 - i; j) { if (arr[j] arr[j 1]) { int tmp arr[j]; arr[j] arr[j 1]; arr[j 1] tmp; swapped 1; } } if (!swapped) { break; } } }这个优化在近有序数组上能把实际耗时拉回接近 O(n)。面试时主动写出这个版本通常是个加分项。5.2 选择排序最符合直觉的排序方式选择排序的思路是每一轮从未排序部分里挑出最小的元素放到已排序部分的末尾。void selection_sort(int arr[], int n) { for (int i 0; i n - 1; i) { int min_idx i; for (int j i 1; j n; j) { if (arr[j] arr[min_idx]) { min_idx j; } } if (min_idx ! i) { int tmp arr[i]; arr[i] arr[min_idx]; arr[min_idx] tmp; } } }选择排序和冒泡排序代表了两种完全不同的直观冒泡是相邻交换选择是先锁定目标再交换。选择排序的交换次数更少每轮最多1次但比较次数依然接近 O(n²)。培训班把这两个排序成对出现是有深意的就是让学员体会同一个问题看的角度不同算法路径就不同。5.3 归并排序第一次接触分治思想笔记后面有一节加粗标题归并排序——分治思想的入门课。归并排序的核心是分而治之把数组从中间切开分别排序再把两个有序子数组合并成一个。void merge(int arr[], int left, int mid, int right) { int n1 mid - left 1; int n2 right - mid; int L[n1], R[n2]; for (int i 0; i n1; i) L[i] arr[left i]; for (int j 0; j n2; j) R[j] arr[mid 1 j]; int i 0, j 0, k left; while (i n1 j n2) { if (L[i] R[j]) { arr[k] L[i]; } else { arr[k] R[j]; } } while (i n1) arr[k] L[i]; while (j n2) arr[k] R[j]; } void merge_sort(int arr[], int left, int right) { if (left right) { int mid left (right - left) / 2; merge_sort(arr, left, mid); merge_sort(arr, mid 1, right); merge(arr, left, mid, right); } }归并排序的时间复杂度是稳定的 O(n log n)无论原数据是正序、逆序还是随机表现都一致。它不像冒泡、选择那么直观但逻辑极其清晰先递归到一个元素这个天然有序的最小规模再一层层合并回去。为什么一定要学归并排序不只是因为它是常见考点更重要的原因是合并思想是很多高级算法的底座。比如求逆序对数量、外排序、数据库处理超大数据集排序核心思路都和归并一致。学归并排序等于提前学会了如何把子问题的解拼成大问题的解这套系统化思维。当年我在培训班第一次看归并排序代码半天没绕明白递归是怎么展开又收回的。后来自己在纸上手动模拟了merge_sort([3,1,2,4], 0, 3)的完整调用过程先切到 [3]、[1]、[2]、[4]然后两两合并成 [1,3] 和 [2,4]最后合并成 [1,2,3,4]。手写一遍这个路径比盯着代码看十遍都有用。这个手动模拟递归的学习方法我建议所有初学者都试一次胜过死记代码。6. 指针数组与动态数组培训班里的分水岭6.1 指针数组记住数组里存的是指针笔记在中间用加粗写了三个字劝退点。说的就是指针数组。指针数组的定义其实不复杂——它就是个数组只不过每个元素是指针。char *courses[3] {C语言, 数据结构, 操作系统};courses[0]指向字符串C语言的首地址courses[1]指向数据结构的首地址以此类推。遍历打印课程名for (int i 0; i 3; i) { printf(%s\n, courses[i]); }这里courses[i]是char*类型printf的%s正好需要char*所以能打印整个字符串。指针数组和二维字符数组的区别是我工作之后才真正理解透的。二维字符数组char courses[3][20]是3行20列的格子每个名字不管长短都占用20字节指针数组char *courses[3]只为字符串本身分配空间每个元素只占一个指针64位系统下8字节字符串字面量存放在只读数据段。前者适合需要修改每个字符串内容、且长度可控的场景后者适合字符串内容不变、数量多、长度差异大的场景。用sizeof一量就特别清楚char a[3][20]; char *b[3]; printf(%zu\n, sizeof(a)); /* 60 3 * 20 */ printf(%zu\n, sizeof(b)); /* 24 3 * 8 */这一页笔记让我明白一个重要道理选数据结构的核心不是哪个更高级而是哪个更匹配数据特点和操作需求。这个认知在后来设计解析器、命令表、配置项时反复用到。6.2 动态数组用malloc和realloc突破定长限制培训班后半段讲了动态数组。C语言数组声明时长度必须是编译期常量但很多时候只有运行期才知道用户要存多少数据。解决办法就是malloc和realloc#include stdio.h #include stdlib.h int main(void) { int n; scanf(%d, n); int *arr (int *)malloc(n * sizeof(int)); if (arr NULL) { fprintf(stderr, 内存分配失败\n); return 1; } for (int i 0; i n; i) { arr[i] i * i; } free(arr); return 0; }几个细节值得注意。第一malloc(n * sizeof(int))里的sizeof(int)不能省因为malloc的参数是字节数不是元素个数写成malloc(n)就真的只分配了n个字节。第二返回值必须检查是否为NULL内存分配失败在真实项目里会导致空指针崩溃处理方式可以简单但不处理不行。第三用完必须free否则内存泄漏。培训班老师讲到这里时举了个例子一个需要连续运行一周的服务程序如果每个请求泄漏100字节一周后内存就被吃光了。当时我没当回事后来维护一个MFC程序因为字符串处理反复分配不释放内存占用一路飙升到几百MB才真正体会到泄漏两个字的重量。realloc是动态扩容arr (int *)realloc(arr, new_size * sizeof(int));用realloc有个关键注意点如果扩容失败它会返回NULL但原来的内存并不会被释放。所以更安全的写法是先用临时指针接住结果确认不是NULL再赋给原指针否则原指针丢失内存泄漏和数据丢失一起来int *new_arr (int *)realloc(arr, new_size * sizeof(int)); if (new_arr ! NULL) { arr new_arr; } else { /* 扩容失败arr仍然有效需要自行决定如何处理 */ }这个坑我在2015年之后的第三个项目里真踩过。当时写一个动态增长的消息队列直接arr realloc(...)没做保护某次内存紧张时realloc返回NULL整个队列的指针当场丢失之前的消息数据全没了排查代码时冷汗都下来了。7. 从数组走向算法更高级问题的敲门砖7.1 KMP与字符串匹配数组和指针的高级配合章末有一节讲字符串匹配。最先是朴素匹配就是一个位置一个位置试主串长度n、模式串长度m最坏情况复杂度 O(n*m)。培训班只要求了解但笔记里贴了KMP算法核心思想的摘要旁边写着要想完全看懂得先吃透前缀表。KMP的核心在于匹配失败时不让主串指针回退只让模式串指针回退到合适位置。这个合适位置由模式串自身的next数组前缀函数表决定。KMP代码网上到处都是这里不重复贴了重点是它和数组的关系。KMP 的next数组解决的是模式串内部哪些位置可以安全复用的问题。没有建立数组思维KMP的代码就是天书有了数组思维再看它不过是一个借助预计算数组指导回退的匹配算法。这就是为什么C语言数组基础不牢后面学什么算法都像在沙地上盖楼。7.2 树状数组把直线排列的数组玩出维度笔记最后几页有个提纲挈领的总结提到了树状数组Fenwick树。它利用数组下标二进制上的特性让单点更新区间求和两个操作都能做到 O(log n)。一个经典模板#define MAXN 100005 int tree[MAXN]; int lowbit(int x) { return x (-x); } void add(int idx, int delta) { while (idx MAXN) { tree[idx] delta; idx lowbit(idx); } } int prefix_sum(int idx) { int res 0; while (idx 0) { res tree[idx]; idx - lowbit(idx); } return res; }lowbit(x)返回x的二进制中最低位的1所代表的值。比如lowbit(6) lowbit(0b110) 2。add更新时从当前下标往右上方跳prefix_sum查询时往左上方跳。树状数组不是培训班要求掌握的内容笔记上只有老师随口提的一句你们以后搞算法竞赛或者处理海量数据的前缀和、频次统计会碰到这个结构。后来我做数据统计模块时真用上了频繁更新某个类目的计数、频繁查询前N类目的总数如果用普通数组更新 O(1) 但查询 O(n)数据量一上去就顶不住。树状数组把两边都压到 O(log n)算是普通数组的魔法升级版。7.3 暴力枚举简单但不可耻的算法思路还有一个小节讲暴力枚举。老师反复强调很多新手一上来就追求巧妙算法但实际工程里数据规模小的时候暴力枚举往往是最不容易出错、最容易维护的方案。暴力枚举的核心是穷举所有可能性然后检查。比如在一个数组里找和为指定值的两个数最简单的做法就是双重循环枚举所有数对。数据规模在几百以内O(n²)根本没压力何必费劲写哈希表这个道理我在真实项目里反复验证一个运行在嵌入式设备上的数据校验程序数据量从不超过几百条用暴力枚举又稳又直观强行上复杂算法反而增加排查问题的难度。培训班同学里有个很有意思的现象写得快、跑得通的往往不是那些最早学了一堆高级算法的人而是能老老实实用暴力枚举先解决问题、再用高级手段做优化的人。这个习惯我一直保持到现在。几个放在最后的实际操作体会把2015年的笔记本翻完我最大的感受是技术会演进语言会迭代但数组、字符串、排序、遍历这些最基础的能力永远是程序员的看家本领。现在写Go写Javaslice和ArrayList用得很顺手但正是因为当年在C里被\0、越界、内存分配这些问题反复折磨过我才真正理解高级语言替我们做了什么也才更清楚什么时候该信任抽象、什么时候该打破抽象看细节。最后分享一个我后来一直沿用的学习习惯任何新学到的算法或数据结构都先用C语言或者任何偏底层的语言手动实现一遍不依赖现成库函数然后再用其他语言的高级特性去写业务代码。为什么因为当你只能用最原始的工具把逻辑跑通说明你真的理解了它反过来直接用现成的Arrays.sort()或者list.sort()很容易停留在调调接口的层面。这个习惯帮我在几次技术栈切换中保持了底层嗅觉建议处在基础阶段的朋友也试一试。