★ FEATURED ARTICLE 把数组讲透比刷十道模板题更有用。AcWing《语法基础课》第四讲就是围绕数组这一个核心数据结构展开的看似简单但一维、二维、字符数组、与指针的关系、初始化细节几乎决定了你后面学排序、学前缀和、学链表时能不能一次写对。这篇笔记我按自己刷课和实操的视角重写一遍把课堂上容易一笔带过、但实际做题时特别坑的细节全部补齐配合代码和踩坑记录适合正在跟课、或者学完想回头巩固的人看。1. 为什么数组是C入门的第一道坎1.1 数组在整个语法课中的定位AcWing的语法基础课把数组放在第四讲前面依次是变量、输入输出、表达式和语句后面紧跟着字符串、函数、结构体。这个顺序其实非常讲究。数组是你接触的第一个复合数据类型它把多个同类型变量用一个名字管理起来让循环有了真正的用武之地。没有数组你写10个数的平均值要声明10个变量有了数组for循环从0走到9问题瞬间变得规模化。可以说数组是从写小程序到写能解决问题的程序的转折点。我在带新手的时候经常说一句话数组这一讲如果没学透后面的排序、二分、前缀和、链表全都会在细节上翻车。原因很简单这些内容多少都依赖于连续内存下标访问边界控制这三个数组的基本特性。比如冒泡排序看起来只是两重循环加交换但内层循环的边界条件写错一位结果就是数组越界或者排序不完整这种问题在OJ上通常不会直接报错而是给出莫名其妙的错误答案难排查得很。1.2 从内存视角理解数组的本质数组在C里的本质是一段连续的内存空间里面按顺序存放着相同类型的元素。这句话一定要刻在脑子里。连续意味着什么意味着你知道首地址就能推算出任何一个元素的地址。假设有一个int数组a在常见的64位Linux系统下int占4字节那么a[0]的地址是0x1000的话a[1]的地址就是0x1004a[2]是0x1008以此类推。访问a[i]的时候编译器实际做的事情就是从a的起始地址偏移 i * sizeof(int) 个字节然后读取那4个字节作为int。这也是为什么数组下标从0开始而不是从1开始。如果从1开始那a[0]这个位置就空着每次访问都要做一次地址减一的偏移换算虽然不影响正确性但白白浪费一次运算。从0开始的话a[i]的地址直接就是 base i * element_size一步到位简洁高效。理解了这个底层逻辑你再看数组名是首地址、数组越界访问的是未知内存这些说法就不会觉得是死记硬背了。另外因为存储是连续的CPU访问数组时具备很好的局部性可以高效利用缓存这也是数组对比链表在多数场景下跑得更快的一个硬件层面的原因。2. 一维数组初始化、遍历与经典操作2.1 初始化方式对比与选择一维数组的初始化看似简单但在不同场景下选错方式会带来两种完全不同的行为。先看最常用的几种写法int a[5]; // 不初始化全局数组默认全是0局部数组是随机值 int b[5] {1, 2, 3}; // 只给了前3个剩下的自动补0 int c[5] {0}; // 所有元素都是0最常用的清零写法 int d[] {1, 2, 3, 4, 5}; // 不写大小编译器根据初始化列表自动推断为5 int e[5] {1, 2, 3, 4, 5, 6}; // 编译报错初始化列表太长这里最大的坑是第一种局部数组不初始化里面的值是随机的通常是一些残留的栈内存数据。新手最容易在这个地方翻车——写了个数组没赋初值就拿来累加或者比较结果每次运行结果还不一样十分诡异。我的习惯是只要数组后续要参与累加、计数、标记状态一律先初始化成0最稳妥的就是写 int a[N] {0}; 或者 int a[N] {};这两种写法效果一致都能把所有元素清零。还有一个小细节值得注意int a[N] 里如果N是变量在严格C标准下叫变长数组GCC编译器作为扩展支持但Visual C编译器不支持。AcWing的题目环境用的是GCC所以写 int n; cin n; int a[n]; 能通过编译但这个写法可移植性不好。更推荐的做法是先读取n再用动态内存或者vector或者干脆开一个足够大的定长数组比如 int a[100010]; 然后用其中的前n个位置。竞赛里开大数组是常规操作因为内存足够开大一点完全不浪费反而省掉了动态分配的麻烦。2.2 遍历与经典操作实战遍历是所有数组操作的基础一个标准的for循环从0到n-1是刻进肌肉记忆的写法。围绕遍历有几个经典操作刷题时反复出现这里逐个说清楚。反转数组。要求把数组元素顺序颠倒过来。最容易想到的写法是开一个新数组倒着拷贝但更好的做法是双指针从两端往中间走交换两个位置的值int i 0, j n - 1; while (i j) { swap(a[i], a[j]); i; j--; }这个写法的好处是O(1)额外空间而且在AcWing的题目里原地操作经常是硬性要求。双指针的思路后来还会在二分、滑动窗口里面反复出现算是第一套要掌握的思想模板。去重。给定一个有序数组要求去掉重复元素并返回新长度这是经典题。核心思路是维护一个已去重区间的末尾下标k然后遍历数组只要当前元素和a[k]不同就放到k1的位置int k 0; for (int i 1; i n; i) { if (a[i] ! a[k]) { a[k] a[i]; } } // 新长度为 k 1这个写法在原数组上操作后面的元素保持相对顺序不变是原地去重的最优解。注意前提是数组有序如果原数组无序就需要先排序或者用哈希表那就超纲到后面的章节了。求最大值和最小值。常规做法是遍历一遍维护两个变量但有个小技巧初始值不要随便设为0因为如果数组里全是负数初始值0会让最大值结果错误。正确做法是把初始值设为数组第一个元素然后从下标1开始遍历或者用 int maxv INT_MIN; 这种极值常量。这个细节在题目里遇到负数数据时特别容易中招。2.3 字符数组与字符串的边界问题字符数组是数组里特殊的一类它和字符串的关系让不少人迷糊。在C里字符串字面量 hello 本质上是一个const char数组末尾自动带了一个\0结束符。而字符数组可以逐字符赋值也可以整体用字符串初始化char s1[10] hello; // 实际占用6个字节最后一个是\0 char s2[] {h, e, l, l, o}; // 没有\0不是标准字符串 char s3[] {h, e, l, l, o, \0}; // 手动加结束符最大的坑在s2如果你把它传给strlen(s2)或者printf(%s, s2)函数会一直往后找\0直到在内存里撞到一个随机的0字节才停下来结果就是打印出hello后面跟着一堆乱码或者strlen输出一个很大的随机数。这类问题在OJ上表现为主机崩溃或者输出超长排查起来很头疼。所以我的建议非常明确字符数组初始化一律用字符串字面量或者手动显式加\0。如果用的是cin读取字符串到字符数组cin会自动在末尾补\0这一点倒是安全。另外遍历字符数组时判断结束不要写 for (int i 0; i strlen(s); i) 这种写法因为strlen每次循环都要从头数一遍长度O(n^2)复杂度数据稍大就超时。正确做法是 for (int i 0; s[i]; i)直接判断当前字符是不是\0也就是0效率高且写法简洁。3. 二维数组与指针数组内存布局与实战3.1 二维数组的本质是数组的数组二维数组 int a[3][4] 可以理解成一个3行4列的表格但在内存里它依然是连续的12个int排成一条线按行优先顺序存放先存第0行的4个再存第1行的4个依此类推。理解这个布局对后面学指针、学动态规划的状态转移都非常重要。遍历二维数组的写法看起来很自然两重循环for (int i 0; i 3; i) { for (int j 0; j 4; j) { a[i][j] i * 4 j; } }这里值得注意的一个点是循环顺序。因为二维数组在内存中是行优先的如果内存足够大按行遍历外层i内层j时访问的是相邻内存地址CPU缓存命中率极高反过来按列遍历外层j内层i每次访问都要跳4个int的距离缓存命中率差很多。在小数据量下感觉不到差异但数据量上来了性能差距可能达到数倍。这个知识点在后面学矩阵运算或者图像处理时会反复用到现在养成按行遍历的习惯不亏。二维数组的初始化也有一堆细节常见的如下int a[3][4] {0}; // 全0 int b[3][4] {{1, 2}, {3}}; // 第一行前两个为1,2其余全0 int c[][4] {{1, 2}, {3, 4}, {5, 6}}; // 省略行数编译器自动推断为3行省略行数是允许的但列数不能省略因为编译器需要知道每行多长才能正确计算偏移。比如 c[2][1] 的地址必须知道每行4个int才能算出来。这个规则对应到指针上就是指向二维数组的行指针必须带上列数否则无法做偏移。3.2 指针数组与数组指针的区别这是C语法课里公认的难点也是热搜词里频繁出现的关键词。先记结论指针数组是一个数组里面每个元素都是指针数组指针是一个指针指向整个数组。一行代码之差含义天差地别。int *p1[5]; // 指针数组5个int*每个元素都能指向一个int int (*p2)[5]; // 数组指针p2指向一个含有5个int的数组理解这个可以从优先级入手。[]的下标优先级高于*的解引用所以 intp1[5] 先结合[5]说明p1是数组元素类型是int。而 int (p2)[5] 用括号强行把和p2结合说明p2是指针指向的类型是int[5]。指针数组在实际中常用在字符串处理上。比如要存多行字符串可以定义一个字符指针数组const char *names[3] {Alice, Bob, Cathy}; for (int i 0; i 3; i) { cout names[i] endl; }这里每个names[i]都指向一个字符串常量这种写法比二维字符数组灵活因为每行的长度可以不同不会浪费空间。但要注意这些字符串是常量不能修改里面的字符如果需要修改还是建议用二维字符数组或者其他方式。数组指针在学到二维数组和函数传参时会用到。一个二维数组名实质上是指向第一行的数组指针所以如果你要写一个函数接收二维数组形参要么写成 int a[][4] 要么写成 int (*a)[4]两种写法完全等价。很多新手在这里卡住就是因为不明白为什么函数形参里必须写列数其实本质上是让编译器知道每行多长从而能算出 a[i][j] 的偏移量。3.3 二维数组的实战应用场景AcWing第四讲里二维数组常常用来解决矩阵类问题。比如方阵的旋转、回形遍历、对角线元素处理。这些题看起来绕但其实核心都是下标映射。我举一个入门必练的题——矩阵转置。给定n行m列的矩阵输出它的转置int a[110][110], b[110][110]; int n, m; cin n m; for (int i 0; i n; i) for (int j 0; j m; j) cin a[i][j]; for (int i 0; i m; i) { for (int j 0; j n; j) { b[i][j] a[j][i]; } } // 输出b它是m行n列这个代码本身不难但很能说明问题二维数组的每个操作本质上都是在问新位置和旧位置的下标有什么关系。做这类题的时候先别急着写代码拿笔在纸上画一个3乘2的矩阵手动推导一遍下标变化规律再动手写正确率会高很多。我见过太多学生循环写对了但转置后输出时的行列数搞反了导致全盘皆输。先在纸上标清楚输出时是几行几列这个问题就能提前规避。另一个常见的应用是二维前缀和后面第4节详述以及用二维数组模拟棋盘、地图为后面的搜索算法DFS、BFS打基础。AcWing第四讲虽然只要求掌握语法但这些二维数组的使用场景如果现在就能熟练后面学算法会顺很多。4. 数组进阶前缀和与差分思想4.1 前缀和一维的实现与解题思路严格来说前缀和是AcWing算法课里的内容但第四讲的数组作业里已经开始出现了这类题目的雏形而且很多同学在语法基础课阶段就会遇到类似题目。前缀和的核心思想是预处理把一个数组的区间和查询从每次O(n)的遍历降低到O(1)。定义前缀和数组ss[i]表示原数组前i个元素的和注意这里通常让s的下标从1开始。递推公式s[i] s[i - 1] a[i];有了s之后查询区间[l, r]的和就是 s[r] - s[l - 1]。这个式子要记牢出错几乎都出在边界上。为什么前缀和数组下标从1开始而不是0因为这样定义的话区间[1, r]的查询可以统一用 s[r] - s[0] 表示不需要特判l等于1的情况逻辑更干净。这个细节在写代码时能省掉一堆if判断是竞赛选手的常用技巧。存数据的时候让a[1]到a[n]存储实际数据a[0]留空或者存0问题不大。二维前缀和是这个思想在二维空间的推广后面的算法基础课会重点讲但这里可以先给一个直观感受。预处理公式s[i][j] s[i-1][j] s[i][j-1] - s[i-1][j-1] a[i][j];这个公式包含了一个重要的容斥思想加回左上角重叠减掉的部分。理解了后面query子矩阵和的公式s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] s[x1-1][y1-1]也就顺理成章了。数组这块如果能把前缀和的思想吃透等于提前接触了预处理换查询时间这个算法设计的核心思路。4.2 差分的应用场景差分是前缀和的逆运算。给定原数组a定义差分数组b使得a是b的前缀和。快速构造方法b[i] a[i] - a[i-1];差分有什么用它的核心能力是区间修改。你想给原数组区间[l, r]的所有元素都加上x朴素做法是遍历这个区间复杂度O(n)。但如果用差分数组只需要b[l] x; b[r 1] - x;两步操作就完成了。之后再对b数组做一遍前缀和就能得到修改后的原数组。这两个操作在竞赛题里非常常见比如给定m个操作每次把某个区间加一个数最后输出整个数组这类题差分是标准解法。虽然语法基础课不要求掌握差分但数组作为它的载体提前理解数组可以承载算法思想这一点对上后面课程的衔接很有帮助。实际上我在看AcWing讨论区的时候经常看到有人用第四讲的数组知识就写出来了差分模板说明这些思路并不算超纲反而是对数组理解的深化。4.3 树状数组等更复杂的数组结构热搜词里出现了树状数组模板和树状数组维护长度n16的序列查询前缀和sum(11)与单点修改add(3, x)分别这说明很多人在学完基础数组后会主动往数据结构方向探索。树状数组确实建立在数组之上但它的下标利用了lowbit运算逻辑上已经不是普通的下标即位置了。我不建议语法基础课阶段就深挖树状数组因为它的核心难点是二进制位运算和更新/查询路径这需要先把数组和位运算基础打得够扎实再上。否则很容易陷入代码能背但不懂原理的困境。如果确实有兴趣可以先把前缀和、差分练熟再往后学线段树、树状数组一步步来效果远好于拔苗助长。5. AcWing第四讲典型题解与踩坑实录5.1 常见错误速查表数组部分的错误翻来覆去其实就那么几类。我把它们整理成了一张速查表刷题报错时可以先对着排查一遍。错误现象大概率原因排查方法输出的结果全是随机大数数组未初始化就参与运算检查是否写成 int a[N] {0};程序在某些数据下崩溃数组越界访问了下标n或更大检查循环边界是不是 i n 而非 i n答案错但找不到逻辑问题数组开小了实际需要n1个位置检查题目数据范围多开10个位置保险字符串输出乱码字符数组没有\0结束符改用字符串字面量初始化本地正常OJ上RE递归栈溢出或数组越界触发段错误用assert或输出中间值定位缩小范围二维数组行列搞反输出时行的下标写成列的下标在纸上面画矩阵标明行列排查数组问题时我的第一反应永远是检查边界。很多报错的题解里别人一眼看出问题是for循环多循环了一位原因就是数组越界访问虽然不一定立刻崩溃但会读到相邻内存里的垃圾值让结果变得不可预测。特别是在OJ上同一个代码可能这组数据AC下组数据WA这种情况优先查越界。5.2 调试数组问题的几个实用技巧第一个技巧是利用打表观察中间状态。当你怀疑某个循环写错了最简单的方式不是用调试器而是在关键位置输出数组的内容。比如冒泡排序没排对就在每轮外层循环结束后把整个数组打印出来对比排序过程几秒钟就能看出是内层循环边界错了还是交换逻辑反了。printf大法虽然土但对付小规模数据是最高效的。第二个技巧是用assert检查下标。在关键位置写 assert(i 0 i n);如果越界会立即触发断言失败并打印出错位置比等着随机崩溃好定位得多。线上OJ做题时记得删掉这类断言因为有些OJ的编译环境在开启NDEBUG之后assert不生效可能影响逻辑。第三个技巧是处理输出格式类的错误。AcWing很多题目要求输出时行末不能有多余空格这是数组题里非常常见的WA原因。解决办法也很统一判断是不是最后一个元素不是的话才输出空格。养成这个习惯以后字符串处理题能少踩很多坑。第四个技巧是关于全局数组和局部数组的选择。全局数组自动初始化为0且分配在静态存储区不受栈大小限制这是我在OJ上几乎默认写全局数组的原因。局部大数组开在栈上一不小心就栈溢出程序直接崩溃这种崩溃在调试器里往往显示为访问冲突很难和数组越界区分开。所以我的编码习惯是数组一律定义在main外面做全局变量省心且安全。5.3 一个完整的小例子冒泡排序实现与边界分析冒泡排序作为最基础的排序算法每次讲解数组必提。这里贴一个标准实现配合边界分析说明为什么这么写#include iostream using namespace std; int main() { int a[100]; int n; cin n; for (int i 0; i n; i) cin a[i]; // 冒泡排序每一轮把最大的数冒到最后面 for (int i 0; i n - 1; i) { // 只要n-1轮就够了 for (int j 0; j n - 1 - i; j) { // 排好序的尾部不再参与比较 if (a[j] a[j 1]) { swap(a[j], a[j 1]); } } } for (int i 0; i n; i) { if (i) cout ; cout a[i]; } cout endl; return 0; }两个循环的边界是这道题唯一可能出错的地方。外层循环只需要n-1轮因为如果n-1个元素都到了正确位置剩下那一个自然就在正确位置。内层循环每轮结束后数组末尾i1个元素已经是全局最大的那部分所以比较区间可以缩短到n-1-i。写成 j n - 2 - i 也可以但我更习惯统一用小于号配合n-1-i一眼就能看出来最大下标是n-2-i和j1的最大值n-1-i对齐恰好不超过有效范围。每次写冒泡排序都这么核对一遍边界时间久了就不会错了。6. 实操环境VS Code配置C与调试建议6.1 本地编译环境的搭建要点ByteDance、AcWing很多同学用的是本地编辑器加命令行编译器的方式刷题VS Code是其中最常见的选择。热搜词里vscode配置c环境和vscode配置c/c环境出现频率很高说明环境配置对新手确实是一道门槛。这里给出一个最简方案关键在于理解编辑器负责写代码编译器负责把代码变成可执行文件两者是分离的。在Windows上最省事的方式是安装MinGW-w64然后把它下的bin目录里面含g.exe加到系统PATH环境变量里。然后在VS Code里安装C/C扩展ms-vscode.cpptools在终端里用命令编译运行g -Wall -stdc17 -g main.cpp -o main ./main-Wall参数会把所有警告显示出来一些不规范的写法比如未初始化变量会得到警告提示对新手排查潜在bug非常有帮助。加-g是为了生成调试信息方便后面用断点调试。单文件刷题这样编译足够了等需要写cmake工程再考虑更复杂的构建工具。6.2 数组调试的断点与监视技巧VS Code的调试功能对数组类的bug其实非常好用。设置断点在循环体内部然后在监视窗口添加表达式 a它会自动展开显示数组前几个元素的值也可以添加 a[0]10 这样的表达式显示从a[0]开始的10个元素。每次单步执行时观察数组的变化过程就能很直观地定位到逻辑错误。这个方法在排查排序算法、前缀和预处理这类问题时效果比单纯看输出值高太多了因为它能看到中间状态。使用监视功能时需要注意一点当数组越界时调试器可能无法正常显示后面的元素或者显示为内存中的垃圾值这时候第一反应应该是检查下标是否越界而不是怀疑调试器出了问题。另外VS Code调试C程序时如果同时开了多个终端和调试会话偶尔会抽风建议按顺序严格操作先编译CtrlShiftB配置好构建任务再点F5启动调试。把环境调顺了刷题效率能提升一个档次。6.3 关于C版本和标准库的选择AcWing语法基础课的题目通常用C11或C14标准足够但很多人会在本地配置时遇到C版本过旧导致语法报错的问题。如果出现 for (int i : a) 这类范围for循环报错检查一下编译命令里是否带了 -stdc11 或更高的标准参数。另外虽然数组是这一讲的主角但实际开发中动态数组很多时候用 std::vector 代替因为它能自动扩容且支持size()等方法不需要手动管理内存。不过如果在刷题尤其是算法题原生数组的访问速度略优于vectorvector的at()方法有边界检查operator[]没有而且很多经典代码模板就是基于原生数组写的所以语法基础课阶段把原生数组练扎实是必要的投入。vector可以等学到STL那块再系统掌握那时候你会发现数组的基础并没有白学反而让vector的学习变得非常简单。
阅读完成 · 觉得有帮助？
