★ FEATURED ARTICLE AcWing语法基础课第四讲数组前前后后我过了两遍。第一遍觉得简单变量、循环都学完了数组不就是开一块空间存一堆数吗真正开始刷题才发现数组这章才是前面所有语法知识的第一次汇合——它帮你建立连续内存下标边界批量操作这些概念而这些概念直接决定你后面学字符串、结构体、指针甚至STL的时候是顺畅还是反复翻车。这篇笔记是我比较完整的总结包含数组的存储原理、各种初始化方式、二维数组与字符数组的细节以及memset、fill这类批量操作的坑最后会复盘几道典型练习题的边界问题。适合正在学C语法基础的同学、准备蓝桥杯或者刚开始在AcWing、洛谷刷题的新手参考看到的是数组能做什么但更重要的是数组的边界在哪里。1. 数组的底层逻辑连续内存、固定长度与下标0的来历1.1 数组在内存里就是一段连续空间数组的定义大家都会背相同类型元素的集合但真正关键的是它的存储方式在内存中开辟一段连续空间每个元素占同样多的字节数。正因为连续你才能用a[i]直接命中第 i 个元素不用从头一个个找。a[i]的地址等价于数组起始地址 i * sizeof(元素类型)举个例子int a[10]起始地址假设是0x1000每个 int 占 4 个字节那么a[0]在0x1000a[1]在0x1004a[3]在0x100C这个地址计算是固定时间的也就是常说的 O(1) 随机访问。这是数组一切应用的底层基础也是它和链表最大的区别——链表的节点在内存里是散的访问第 k 个必须从头走 k 步。1.2 为什么下标从 0 开始下标本质是偏移量不是序号。a[i]的寻址公式里用的是i而不是i - 1所以第一个元素自然对应i 0。如果下标从 1 开始每次访问都要额外做一次减 1 运算虽然现代编译器也能优化掉但设计上就是从 0 开始最自然。不过这带来一个新手常见问题很多题目习惯从 1 开始编号比如有 n 个数第 1 个数是……不少人就直接写int a[100]然后从a[1]存到a[n]。这完全没问题a[0]空着不用就行。但你要时刻清楚自己用的是自然编号还是下标如果你从a[1]开始存循环就是for (int i 1; i n; i)这时候n是有效的a[n]是最后那个元素如果你从a[0]开始存循环就是for (int i 0; i n; i)a[n-1]才是最后一个。这两种写法混着用是最常见的 WA 来源。1.3 sizeof 测数组长度一个隐蔽的陷阱sizeof(a)返回整个数组占用的字节总数sizeof(a[0])是一个元素的大小两者相除得到元素个数这是写循环时常用的一段代码int a[100]; int len sizeof(a) / sizeof(a[0]); // len 100但这个写法有一个大坑数组作为参数传给函数时会退化成指针。看这段代码void f(int a[]) { // 这里 sizeof(a) 是指针大小不是数组大小 int len sizeof(a) / sizeof(a[0]); // 在64位系统上结果是 8 / 4 2 }void f(int a[])和void f(int* a)是等价的函数内部拿到的只是一个指针8 个字节64位系统用sizeof测出来的长度完全是错的。所以要么把长度作为参数传进去要么在函数外先算好长度再传入。C17 里的std::size(a)也只能用在数组还没有退化的地方别指望它救你。2. 一维数组的声明与初始化这些写法背后的差异2.1 长度必须是编译期常量int a[10]里的 10 在编译时就得确定。下面的写法在标准 C 里是不合法的int n; cin n; int a[n]; // 标准C不支持属于GCC的VLA扩展原因是数组在栈上分配编译器必须知道具体字节数才能生成代码。也是因为这一点后面才需要vector这样的动态数组——这是后话但你可以先记住定长数组的长度必须是编译期常量。还有一个环境问题要提醒全局数组开在数据段局部数组开在栈上而栈空间默认只有几 MB。局部开int a[1000000]也就是 4MB勉强可以但如果开到几百万甚至上千万 int就会爆栈程序直接崩。这种情况要么把数组放到全局要么用动态内存。2.2 各种初始化方式的缺省值C 数组初始化写法很多每种效果不一样我整理了一个对照写法结果int a[10];局部变量随机脏数据值是栈上残留的东西int a[10] {};全部初始化为 0int a[10] {0};第一个是 0其余也是 0int a[10] {1, 2};前两个是 1、2后面全是 0int a[] {1, 2, 3};编译器自动推导长度为 3全局/静态int a[10];不写初始化也是全 0初学者最容易踩的坑是第三种和第四种 {0}和 {1, 2}这类写法只有显式写出来的那几个位置被赋值剩余位置自动补 0。有人以为int a[10] {1};会把 10 个元素全设成 1这是错的只有a[0]是 1其他都是 0。这个规则在竞赛里经常用。比如统计字母出现次数开一个int cnt[26]如果它是全局变量就不用手动清零如果放在main里面必须显式初始化成{}或者用后面的memset。2.3 越界访问不会报错但后果很严重数组越界是最典型的 C/C 安全隐患。a[100]访问的是起始地址往后第 101 个 int 的位置编译器根本不会帮你检查。实际后果有三种运气好访问到一段还没被使用的内存程序假装正常访问到别的变量的地址悄悄把别人的数据改了产生难以排查的 bug直接访问到非法地址触发段错误Segmentation Fault程序崩溃。竞赛里最经典的数组开小了就是这么来的题面说 n 最大 100你开了a[100]循环里却访问了a[100]而最后一个合法下标是 99。这种 RE 很难一眼看出来我的习惯是开数组时留余量比如最大 100 就开a[105]或a[110]多几个字节几乎不占空间但能省掉很多调试时间。3. 二维数组的内存排列与遍历顺序3.1 二维数组本质上一维连续内存int a[3][4]在内存里就是 12 个 int 连续排着行与行之间没有空隙。a[2][3]的地址 起始地址 (2 * 4 3) * 4字节。这种按行优先的排列方式决定了编译器必须知道列数才能计算偏移。这也解释了一个常见的语法规定函数参数写二维数组时第二维不能省略void calc(int a[][4]); // 合法可以通过列数计算行偏移 void calc(int a[][]); // 不合法不知道每行多长初学者可能会问为什么第一维可以省而第二维不行因为数组名作为参数退化后编译器只知道首地址要访问a[i][j]必须先算出它离首地址多远这个距离依赖列数不依赖行数。3.2 遍历顺序影响缓存命中二维数组连续排列带来的实际影响是遍历顺序。下面两种写法逻辑上结果一样// 按行遍历先固定行内层逐列走 for (int i 0; i n; i) for (int j 0; j m; j) sum a[i][j]; // 按列遍历先固定列内层逐行走 for (int j 0; j m; j) for (int i 0; i n; i) sum a[i][j];按行遍历时每次访问的地址都是连续的CPU 缓存命中率高按列遍历时每次跳跃 m 个 int 的大小缓存频繁失效数据量一大耗时差距可能拉到几倍。这个细节在算法竞赛的卡常优化里经常被拿出来说写的时候养成按行遍历的习惯就好。3.3 二维数组的初始化与典型应用二维数组初始化同样支持按行给值int a[3][4] { {1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12} };可以省略某些行省略的部分自动补 0。使用场景就太常见了矩阵运算、棋盘、迷宫地图、动态规划的 DP 表格。尤其后面学动态规划基本每个题都要开一个二维表dp[i][j]表示某个状态。如果现在就把二维数组的内存模型画清楚了后面看状态转移方程会轻松很多。4. 字符数组与字符串\0 的约定让多少新手翻过车4.1 字符数组的两种初始化方式字符串在 C/C 里不是一种原生类型而是约定以\0结尾的字符数组。这个\0是 ASCII 码为 0 的字符用来标记字符串的结束位置。看这两个写法char s1[] abc; // 实际长度是4末尾自动补 \0 char s2[3] {a,b,c}; // 没有 \0s1有 4 个字符a、b、c、\0。s2只有三个字符没地方写\0。如果之后把s2当字符串用比如调用strlen(s2)它会一直往后读直到在内存里撞到一个字节为 0 的位置为止这是未定义行为结果完全不可控。还要注意单引号和双引号的区别a是字符a是字符串字面量后者实际上包含a和\0两个字符。4.2 输入函数的选择cin、scanf、getline往字符数组里读内容方式不同行为差别很大cin s或scanf(%s, s)遇到空格、Tab、换行就停止读不了带空格的句子cin.getline(s, 100)读一整行包括空格最多读 99 个字符并自动补\0fgets(s, 100, stdin)也读整行但会保留末尾的换行符需要自己处理。竞赛里更常用scanf和printf因为格式控制直接、性能也更好。一个容易记错的地方scanf(%s, s)里s前面不用加因为数组名本身在表达式里就会退化成首地址指针。char s[100]; scanf(%s, s); // 正确s 已经是地址 scanf(%s, s); // 也能工作但类型上不对不推荐4.3 字符函数与常见错误处理字符数组经常用到cstring里的几个函数strlen(s)返回\0之前的字符个数所以char s[100] hello;的strlen(s)是 5而sizeof(s)是 100strcpy(dest, src)把src的内容包括末尾\0复制到dest但它不检查目标容量dest小了就直接越界写strcmp(a, b)比较字符串大小返回负值、0 或正值。最常见的坑有两个。一是strcpy越界目标数组开小了src一长就崩尤其是循环里拼接字符串时更容易发生。二是自己构造字符串忘记补\0比如把数字转成字符串char s[20]; int len 0; while (x 0) { s[len] 0 x % 10; x / 10; } s[len] \0; // 这一行不能省少了最后一行strlen(s)或者printf(%s, s)就会一直读到内存里某个碰巧为 0 的字节为止。这种 bug 排查起来特别费劲因为错误不在眼前这几行而在你违反了约定。5. 批量操作三件套memset、fill与memcpy的正确边界5.1 memset 按字节填充的原理memset的功能是把一段内存的每一个字节都设成同一个值memset(a, 0, sizeof(a)); // 把数组a的每个字节设为0为什么memset(a, 0, sizeof(a))能把整个 int 数组清零因为 int 占 4 个字节把这 4 个字节都设成 0整个 int 自然就是 0。同理memset(a, -1, sizeof(a))可以因为 -1 的二进制表示是所有位全 14 个字节全是0xFF合成一个 int 还是 -1。但memset(a, 1, sizeof(a))就完全不是你想的样子了。每个字节被设成0x01一个 int 的 4 个字节合起来是0x01010101也就是十进制 16843009不是 1。这是数组操作里出现频率最高的低级错误没有之一。所以正确结论是memset只能可靠地设置 0 或 -1以及一些按字节有意义的值。5.2 竞赛里的 0x3f3f3f3f 无穷大很多算法题需要把数组初始化为一个很大的数用来表示无穷大。竞赛圈常用的写法是memset(dist, 0x3f, sizeof(dist));为什么是0x3f而不是更大的数因为memset按字节填充每个字节设为0x3f一个 int 四个字节就变成0x3f3f3f3f。这个数的十进制是 1061109567大约是 10 亿比 int 上限约 21 亿小不少但又足够大两个这样的大数相加不会溢出 int。最短路、最小生成树这类算法里初始化dist、f数组时非常常用。对比一下直接用memset(a, 0x7f, sizeof(a))得到的是0x7f7f7f7f约 21 亿两个相加就直接溢出变成负数反而破坏了比较逻辑。所以0x3f是实践检验出来的安全选择。5.3 fill 和 memcpy按元素赋值与按字节复制memset只适合填 0、-1 这类特殊值如果想把整个数组填成 5、10 这种普通整数应该用algorithm里的fillfill(a, a 10, 5); // 把a[0]到a[9]全部设为5fill是按元素赋值的填什么值都行。注意区间是左闭右开a 10表示结束位置这个位置本身不会被赋值。memcpy则是按字节复制memcpy(b, a, sizeof(a)); // 把数组a完整复制到b第三个参数是字节数不是元素个数。如果写成memcpy(b, a, 10)而a是 int 数组那实际上只复制了 10 个字节也就是 2.5 个 int绝大多数情况下是个致命错误。把这三个操作放一起对比函数原理适用场景典型坑memset按字节填充清零、设为 -1、设为 0x3f填普通整数得到错误结果fill按元素赋值任意值批量填充区间写错导致赋值范围不对memcpy按字节复制同类型数组整体复制第三个参数误写元素个数6. 题目复盘翻转、去重与冒泡排序的边界细节6.1 数组翻转双指针而不是再开一个数组翻转是最基础的操作比如把a[0]和a[n-1]对调a[1]和a[n-2]对调。最自然的思路是双指针int i 0, j n - 1; while (i j) { int t a[i]; a[i] a[j]; a[j] t; i; j--; }边界条件是i j而不是i j因为当i j时中间那个元素不需要和自己交换。有人喜欢写for循环i n / 2之类也不难但双指针的写法更通用后面学链表翻转等内容时能直接复用这个思路。这里也可以顺便熟悉std::swapswap(a[i], a[j]);本质和临时变量交换一样但代码更简洁。6.2 数组去重先想清楚是否要求保持顺序去重是一类很常见的题数组去重这个热搜词下面的解法很多但关键在于题目是否要求保持原顺序。如果要求保持原顺序最直接的做法是用标记数组bool vis[10010] {}; int n 0; for (int i 0; i m; i) { if (!vis[a[i]]) { vis[a[i]] true; res[n] a[i]; } }如果允许排序后去重就简单得多sort(a, a n); int m 0; for (int i 0; i n; i) { if (i 0 || a[i] ! a[i - 1]) { a[m] a[i]; } }注意sort的区间是左闭右开[a, a n)。去重后数组长度变成 m后面的元素即使仍然存在也不用管。6.3 冒泡排序的完整代码与循环边界冒泡排序是数组章节最经典的循环边界练习题完整的写法如下void bubbleSort(int a[], int n) { for (int i 0; i n - 1; i) { bool swapped false; for (int j 0; j n - i - 1; j) { if (a[j] a[j 1]) { int t a[j]; a[j] a[j 1]; a[j 1] t; swapped true; } } if (!swapped) break; // 这一趟没有交换说明已经有序 } }两个边界最容易写错的地方外层i n - 1最多需要 n - 1 趟因为剩下最后一个元素时不用再排内层j n - i - 1每一趟结束后最后 i 1 个元素已经就位不需要再比较所以上限要减掉 i 再加一个偏移写成n - i - 1。如果写成j n - 1每次都会访问a[j 1]当j n - 2时访问a[n - 1]越界。swapped标志位是优化关键如果某一趟从头到尾没有发生交换说明数组已经有序直接退出最坏情况 O(n²)最好情况能到 O(n)。7. 定长限制的出路动态数组与vector的使用取舍7.1 为什么需要动态数组定长数组在这个场景下很难受输入规模不确定或者在程序运行过程中需要不断追加元素。比如读入一串整数个数未知你没法提前确定数组长度。有人会开一个很大的数组先放着比如a[1000005]这在知道上限时完全可行也是一种常见做法。但如果上限都不知道或者需要反复增删就需要动态数组。C 里最常用的动态数组容器是vectorvectorint a; // 空数组 a.push_back(1); // 在末尾追加 a.push_back(5); cout a.size(); // 2如果一开始就知道大概规模可以直接提前指定长度vectorint a(n, 0); // 长度为n全部初始化为0vector内部帮你管理内存扩容时采用倍增策略平均下来每次追加的代价是 O(1)实际竞赛中性能也够用。7.2 二维vector与其他选择二维动态数组可以这样构造vectorvectorint g(n, vectorint(m, 0)); // n行m列全部为0这相当于开了一个动态的 n 行 m 列矩阵适合行数列数运行时才确定的情况。和原生二维数组相比语法上多了模板嵌套但灵活性高很多。我的个人习惯是这样的场景选择理由题面给了明确上限追求速度原生数组直接、快不用考虑扩容不确定大小需要追加元素vector自动管理内存支持动态增长行数或列数运行时才确定的二维结构vectorvectorint灵活避免手动管理内存需要极高性能且内存吃紧的卡常题原生数组少了容器层的开销有一点要注意vectorint::size()返回的是size_t是无符号类型。如果写成for (int i 0; i a.size(); i)i是int而a.size()是size_t常见情况下没问题但a为空时a.size()是 0int和size_t比较会有隐式转换警告。稳妥写法是for (int i 0; i (int)a.size(); i)或者用size_t i 0。7.3 指针数组与数组指针简单扩展学完数组之后后面学指针时还会遇到两个名字很像的东西int* p[10]是指针数组这个数组有 10 个元素每个元素都是int*指针常用于替代二维字符数组int (*p)[10]是指向数组的指针p是一个指针指向一个含有 10 个 int 的数组。《语法基础课》阶段不用深究但先有个印象后面接触指针不会觉得突兀。这里只提一点二维数组名传给函数时本质上就是指向数组的指针这和你看到的第二维不能省略规则是同一个原理。数组这一讲看起来全是基础语法但决定后面刷题效率的恰恰是那些最不起眼的边界循环最后一次执行的 i 是多少a[n]到底能不能碰memset能不能填 1字符数组末尾有没有\0。我自己在 AcWing 刷题时WA 和 RE 绝大多数不是思路问题而是数组边界和初始化细节翻车。分享两个我目前一直在用的习惯写循环前先想清楚这个下标最后停在哪再动手开数组时一律多开几个位置n最大 100 就开a[110]数组初始化要么{}要么memset不依赖局部变量的随机值。这些小习惯看起来笨但能省下大把调试时间。
阅读完成 · 觉得有帮助？
