很多人觉得 C 语言数组没什么好讲的一个连续内存块循环下标访问排序查找翻来覆去就那几个算法。但我在带新人、看笔试面试题时发现数组恰恰是暴露问题最多的地方——有人分不清数组名和指针有人在二维数组传参时被编译错误卡住有人写二分查找死循环到半夜抓狂。这篇文章打算按“从一维到多维从排序到查找”这条主线把数组相关的关键点串起来讲透。它既适合刚学完指针、正在学构造数据类型的同学也适合准备考研刷题、想系统复查 C 基础的人。看完之后你会清楚数组在内存中到底是什么为什么下标从 0 开始怎么分析多维数组怎么把排序查找写稳。我会把平时容易踩的坑、调试时真正有用的手段一起放进来尽量让这些内容可以直接用到你自己的代码里。1. 从内存视角拆解数组理解数组本质1.1 数组就是一块连续内存数组的第一性原理是“连续内存”。声明int a[5]之后编译器会为你分配一块足够放下 5 个 int 的连续空间。每个 int 占 4 字节32位平台所以 5 个元素一共 20 字节。这些字节是紧挨着的不像链表那样东一块西一块。正是这种连续性让数组可以在 O(1) 时间内随机访问任意元素因为编译器只需要做一次加法——元素地址 首地址 下标 × 单个元素大小——就能直接算出目标位置。从这个角度也能理解为什么数组要求所有元素类型一致类型一致才能保证每个元素宽度相同编译器才能用统一的步长去偏移。如果数组里既有 4 字节的 int 又有 8 字节的 doublea[i]的地址计算就彻底乱套了。很多初学者一开始会忽略这个“连续”的含义导致后面理解指针偏移、多维数组、缓冲区溢出时都很吃力。我的建议是学习数组的第一步不是背语法而是先在纸上画出内存格子标出a[0]、a[1]、a[2]分别占哪几个字节。用代码验证一下连续地址是最直观的#include stdio.h int main(void) { int a[5] {10, 20, 30, 40, 50}; for (int i 0; i 5; i) { printf(a[%d] %p\n, i, (void *)a[i]); } return 0; }运行后会看到相邻地址相差正好 4 个字节比如0x7ffd...00、0x7ffd...04、0x7ffd...08。这个实验我建议每个人都亲手做一次。看一眼地址的输出比你背十遍“数组是连续内存”都管用。数组存在哪块区域呢如果声明在函数内部通常分配在栈上如果是全局数组或 static 数组分配在全局/静态区如果是用malloc申请的则在堆上。不管在哪块区域只要是数组元素之间的地址一定是连续递增的。1.2 下标从 0 开始本质是偏移量不少人问过为什么数组下标不从 1 开始明明从 1 开始更符合日常计数习惯。这个问题的答案就藏在上面那个公式里a[i]真正的意思是“相对于首地址偏移 i 个元素”也就是*(a i)。当 i 0 时偏移量为 0直接访问首元素。如果从 1 开始那么访问首元素时要写a[1]编译器每次都要算a (i - 1)不仅多一次减法还让“下标即偏移”的语义变得含糊。这个设计不是拍脑袋定的而是从指针运算继承过来的。a i本身就是指针算术要求 i 表示步数。既然指针指向首元素时步数为 0下标自然从 0 开始。理解这个之后再看到a[i]、*(a i)、i[a]这三种写法相等你就不会觉得奇怪了——因为它们本质上都是同一件事。顺便说一句i[a]这种写法虽然合法在笔试中偶尔出现但实际项目里绝对不要用纯粹是炫技而且可读性极差。围绕下标还有一个容易混淆的细节是a[i]和a[i]的区别。这跟单独看某个表达式int b a;是一样的道理a是先自增再取新值a是先用旧值再自增。放到数组里a[i]表示先读取a[i]的当前值参与运算之后再把a[i]加 1a[i]则是先把a[i]加 1再用新值。如果一条语句里既有赋值又对同一个数组元素自增强烈建议拆成两行写不要挑战自己和编译器的理解力。1.3 数组长度的求法sizeof 的边界与陷阱求一个真正数组的长度C 语言里有一个经典写法int a[7] {0}; size_t len sizeof(a) / sizeof(a[0]);sizeof(a)返回整个数组占用的字节数sizeof(a[0])返回单个元素字节数两者一除就是元素个数。这个写法对任何类型都成立所以很多项目里会封装成宏#define ARRAY_SIZE(a) (sizeof(a) / sizeof((a)[0]))但注意这个宏只能在“真正的数组”上使用。一旦数组作为函数参数传递出去就会退化成指针。我在下一节会细讲退化这里先记住一个结论在函数形参里写int arr[]编译器的真实处理是int *arr此时在函数内部执行sizeof(arr)得到的是指针大小64 位平台上通常是 8 字节不再是数组容量。这也是为什么 C 函数传递数组时必须额外传一个长度参数比如void print_array(int arr[], size_t n) { for (size_t i 0; i n; i) { printf(%d , arr[i]); } }n必须由调用者提供。很多题库里把“从标准输入读 n再读 n 个数”这种题做成函数要求你实现排序或查找函数的签名往往就是void sort(int *a, int n)原因就在这里。另外求字符数组长度时还有个坑char s[] hello的sizeof(s)是 6因为末尾自动多了一个\0结束符而strlen(s)返回 5它只统计到结束符之前。初学者如果错把sizeof当字符串长度去用后面一涉及循环就越界。2. 一维数组的初始化、遍历与数组名的本质2.1 初始化方式与局部变量陷阱一维数组的初始化看起来简单实际藏了不少细节。常见写法有这四种int a[5] {1, 2, 3, 4, 5}; // 完整初始化 int b[5] {1, 2}; // 部分初始化其余补 0 int c[] {1, 2, 3}; // 由初始化列表推断长度为 3 int d[5] {0}; // 全部清 0第二种写法特别容易忽略int b[5] {1, 2}等价于{1, 2, 0, 0, 0}。编译器对未显式给出的元素统一做“零初始化”。这在实际开发中非常有用想快速清空一个数组时直接int a[N] {0}就不用写循环memset了。但要注意这种“补零”只对初始化有效如果你先声明int a[5];然后在后面写a[5] {0};是不行的数组一旦声明完成就不能再用花括号整体赋值。局部变量和全局变量的初始化行为也不一样。全局数组或 static 数组不写初始化时默认全 0但局部非 static 数组的内容是不确定的可能是上次栈上遗留的脏数据。我见过不少新手定义局部数组后直接拿来统计结果里面全是随机值程序结果每次运行都不一样。正确做法是要么初始化要么先用memset清零。另外int a[5] {};这种写法在旧标准里并不是合法初始化C 语言里想清空数组请写 {0}不要留空。到了 C23 标准才引入空初始化列表但为了兼容主流编译器还是老老实实写{0}最稳。2.2 数组名与指针的三次“表里不一”数组名和指针是 C 语言里最容易让人纠结的一对概念。严格来说数组名并不是一个指针变量但在大多数表达式中它会“退化”为指向首元素的指针。正是这种退化导致下面三种情况经常被混淆。第一sizeof(arr)计算的是整个数组的大小不是指针大小。这和在函数形参里得到的 8 字节完全不同。第二arr的类型不是int *而是“指向整个数组的指针”类型是int (*)[5]。看下面两行输出int a[5] {0}; printf(%p\n, (void *)a); // 首元素地址 printf(%p\n, (void *)a); // 整个数组的地址两个地址在数值上往往相同因为数组首元素的地址和数组本身的起始地址重合。但它们的类型不同导致指针运算结果完全不同a 1只偏移 1 个 int也就是 4 字节a 1跳过整个数组偏移 5 个 int也就是 20 字节。很多笔试题喜欢在这里挖坑。第三数组名不能作为赋值左值。int b[5]; a b;是编译错误因为数组名不是一个可修改的变量它更像一个地址常量。但int *p a;没问题这是让指针指向数组首元素。之后你可以通过p修改数组内容比如p[2] 99效果和a[2] 99一样。当年我学到这里时是把数组名想象成“贴着数组首元素的一张标签”标签本身不能撕下来贴到别处但你可以另外拿一个指针指向它。这个类比救了我也救过我后来教过的不少学弟学妹。2.3 字符数组与字符串C 语言里的字符串本质上就是 char 数组加一个\0结束符。这句话很多书都写过但真正理解的人不多。看两个定义char s1[] hello; char *s2 hello;s1是一个字符数组hello的内容会被拷贝到栈上的数组里所以你可以修改s1[0] H没问题。但s2是指向字符串字面量的指针字符串字面量在多数系统上存放在只读区尝试s2[0] H会导致未定义行为常见结果就是段错误。理解这个区别能避免不少莫名其妙的崩溃。字符串和数组紧密结合的场景还有“指针数组存放字符串”。比如char *names[] {Alice, Bob, Charlie};这个数组本身是一个指针数组每个元素是一个char *指向不同的字符串字面量。如果你想用某种规则对这些字符串做排序就不能直接用或比较而要调用strcmp来按字典序比较。这个场景在第五节的排序实战里我会再展开。字符数组最常见的坑是空间不够放结束符。比如char s[5] hello;hello加上\0一共需要 6 个字节数组只有 5 个初始化的结果就是\0被丢掉。后续调用strlen(s)或printf(%s, s)时程序会继续往后读取内存直到碰巧遇到一个 0 字节为止轻则打印出乱码重则越界读导致崩溃。解决办法很简单数组长度至少写成6或者干脆不写长度让编译器自己算。3. 多维数组从“数组的数组”说起3.1 二维数组到底长什么样一维数组是“一排盒子”二维数组就是“一个盒子里的每个元素又是一个一维数组”。严格地说int a[3][4]是一个长度为 3 的数组它的每个元素都是一个长度为 4 的int数组。这种“数组的数组”定义非常有用因为理解之后你就能推导出一系列访问方式。内存布局上C 语言的多维数组是行优先存储的也就是先完整存放第 0 行再存放第 1 行再存放第 2 行。a[1][2]在内存中的位置其实是首地址偏移(1 * 4 2)个 int。这句话非常关键因为它意味着二维数组在内存里依然是连续的一段空间并不是那种“嵌套的数组指针结构”。访问二维数组元素的标准写法是a[i][j]但它的底层表达式是*(*(a i) j)。拆开来看a退化为指向第 0 行的指针a i指向第 i 行*(a i)得到第 i 行的首元素地址再加j并解引用就是第 i 行第 j 列的值。很多书会用“二维数组名是行指针”这种说法意思就是这里。下面的表格可以帮你建立内存布局的直观印象逻辑视角列0列1列2列3第0行a[0][0]a[0][1]a[0][2]a[0][3]第1行a[1][0]a[1][1]a[1][2]a[1][3]第2行a[2][0]a[2][1]a[2][2]a[2][3]实际上a[0][3]和a[1][0]在物理内存里是紧挨着的。这个特性让二维数组可以被当作一维数组来操作比如用int *p a[0][0]然后p[i * 4 j]就能访问同样元素。在实际工程里很多矩阵运算就是这么做的。3.2 多维数组的初始化和遍历二维数组初始化有两种风格。分行写法可读性好int a[2][3] { {1, 2, 3}, {4, 5, 6} };连续列表写法则省事但要自己数数int b[2][3] {1, 2, 3, 4, 5, 6};编译器会按行优先顺序把 6 个数依次放进 2 行 3 列。部分初始化同样会补 0比如int c[2][3] {{1}, {4}};结果第一行是1, 0, 0第二行是4, 0, 0。这个“花括号按行对应”的规则理解之后基本不会写错。遍历二维数组时最自然的写法是外层循环遍历行、内层循环遍历列for (int i 0; i 2; i) { for (int j 0; j 3; j) { printf(%d , a[i][j]); } putchar(\n); }这个遍历顺序其实是刻意的因为内存是行优先连续存放按行遍历时访问的是相邻地址缓存命中率高如果反着来先列后行每次访问都会跳到另一个行区域性能会差不少。在数据量小的时候体会不明显但在图像处理这类动辄上百万像素的场景里遍历顺序选错可能让程序慢好几倍。多维数组的应用远不止数学里的矩阵。图像处理里的灰度图就是典型的二维数组pixel[x][y]表示第 x 行第 y 列的灰度值。还有一种场景叫“多维密度估计”本质是把连续的数值范围划分成网格用多维数组保存每个网格里的样本数量再统计分布。比如二维坐标点落在某个小方格内就把grid[i][j]加 1。这个思路在数据分析和科学计算里非常常见而底层结构就是 C 的多维数组。3.3 多维数组作为函数参数为什么第二维必须给把二维数组传给函数时形参至少有两种等价写法void f(int a[][4], int rows); void g(int (*a)[4], int rows);a[][4]和(*a)[4]是完全等价的都表示“a 是指向长度为 4 的 int 数组的指针”。这里的核心问题是为什么第二维必须写死不能写成int a[][]原因还是地址计算。编译器要通过a[i][j]定位元素必须知道每行有多少个元素才能算出第 i 行的起始地址。如果第二维未知a[i]就无法确定跳过多远。有人会想那我写成int **a行不行不行。int **a表示“a 指向一个 int *”而二维数组名退化的结果是“指向一整个 int[4] 的指针”这两者指向的类型不同。虽然它们在内存里的数值可能都是某个地址但步长语义完全不同。强行传过去轻则编译警告重则运行时取数据取错位置。如果你确实想让函数同时支持不同列数的矩阵最灵活的方式是“扁平化”把二维数组当成连续内存传一维指针、行数和列数void print_matrix(int *a, int rows, int cols) { for (int i 0; i rows; i) { for (int j 0; j cols; j) { printf(%2d , a[i * cols j]); } putchar(\n); } }调用时传(int *)a或a[0][0]即可。这种写法在工程里很常见因为它把“维度”变成了普通参数灵活性大大提升。代价是a[i][j]得手动写成a[i * cols j]可读性稍微下降一些但换来的是函数可以处理任意列数的矩阵值了。4. 数组排序实战从冒泡到 qsort4.1 冒泡排序的实现与优化排序是数组最经典的应用场景之一。先写最基础的冒泡排序——核心思想是相邻元素两两比较如果顺序不对就交换每一轮把当前未排序区间里的最大值“冒”到最右边。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; // 本轮没有交换说明已经有序 } } }这里两个边界最容易写错。外层循环只需要执行n - 1轮因为剩下最后一个元素时它已经不用再比了。内层循环每轮结束后最后 i 个元素已经是全局最大的一批所以内层只需比较到n - 1 - i。如果你写成j n - i或者j n - i - 1可能产生越界访问或多余的比较。我见过太多人在写冒泡时把j 1访问到数组末尾之外那个错是隐蔽的程序不一定崩溃但结果往往有个莫名其妙的数混进来。加入swapped标志位是常见的优化如果一整轮下来没有任何交换说明数组已经有序可以提前终止。最好情况下数组已经有序第一轮就发现没有交换整体复杂度降到 O(n)。平均和最坏情况依然是 O(n^2)因为要频繁比较和交换。冒泡排序是稳定的相同元素的相对顺序不会变这一点在按多个字段排序时很重要。4.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; } } }写选择排序时最容易犯的错是内层循环从 0 开始找最小值。那样的话每轮找出来的都是全局最小值但前面的位置已经被固定再换一次就把已排好的元素又换乱了。所以内层循环一定要从i 1开始。不少人会觉得选择排序“交换次数少”实际上它每一轮最多只交换一次确实比冒泡的交换次数少但比较次数依然是 O(n^2)整体时间复杂度和冒泡差不多。需要留意的是选择排序不稳定比如数组[5, 5, 3]第一轮会把 3 和第一个 5 交换两个 5 的相对顺序在排序后发生改变。插入排序则是另一种思路把数组看成“左边已排序、右边未排序”两个区域每次把右边的第一个元素插入到左边合适的位置。对于接近有序的数据插入排序非常高效时间复杂度可以降到 O(n)。代码实现void insertion_sort(int arr[], int n) { for (int i 1; i n; i) { int key arr[i]; int j i - 1; while (j 0 arr[j] key) { arr[j 1] arr[j]; j--; } arr[j 1] key; } }插入排序的交换过程是用“后移覆盖”完成的不是相邻交换因此效率比冒泡高一些。这三种排序适合用来练手和理解算法思想但在真实项目里数据量一大基本不会手写它们而是直接调库。C 语言标准库已经提供了强大的qsort我们下一节细说。三种基础排序可以整理成下面这张对比表排序算法平均时间复杂度最坏时间复杂度空间复杂度稳定性冒泡排序O(n^2)O(n^2)O(1)稳定选择排序O(n^2)O(n^2)O(1)不稳定插入排序O(n^2)O(n^2)O(1)稳定qsort快排O(n log n)O(n^2)O(log n)不稳定4.3 用 qsort 优雅排序从基础算法走向工程实践qsort是 C 标准库提供的快速排序实现函数原型在stdlib.h里void qsort(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *));四个参数分别是数组首地址、元素个数、每个元素大小、比较函数指针。compar是比较函数它返回负值表示第一个参数排在第二个前面返回正值表示相反返回 0 表示相等。对一个 int 数组升序排序比较函数可以这样写int cmp_int(const void *a, const void *b) { int va *(const int *)a; int vb *(const int *)b; return (va vb) - (va vb); }为什么要用 而不是直接return *(int*)a - *(int*)b因为直接做减法在极端情况下可能溢出。比如va是INT_MAXvb是-1相减的结果超出了 int 能表达的范围行为是未定义的。用(va vb) - (va vb)这种写法返回值只在 -1、0、1 之间绝对安全。虽然大多数排序数据不会触发这种极端但养成好习惯总没错。排序结构体数组也很常用比如按成绩从高到低排typedef struct { char name[32]; int score; } Student; int cmp_student(const void *a, const void *b) { const Student *sa (const Student *)a; const Student *sb (const Student *)b; return (sb-score sa-score) - (sb-score sa-score); }注意这里为了降序把 b 和 a 的位置换了一下。调用qsort(stu, n, sizeof(Student), cmp_student)即可。对字符串数组排序时比较函数里要调用strcmp因为不能直接比较两个 char 指针的内容。在“数组排序统计”这一类需求里qsort 同样立竿见影。比如先统计每个数字出现的次数存入数组然后对统计数组排序就能快速找到出现次数最多或最少的元素。实际开发中我也经常用 qsort 排序结构体数组之后再配合二分查找这就是下一节的内容。5. 数组查找实战线性查找与二分查找5.1 线性查找的适用场景查找和排序是一对孪生问题。最简单的查找就是线性查找从头到尾遍历数组找到目标值就返回下标int linear_search(int arr[], int n, int target) { for (int i 0; i n; i) { if (arr[i] target) { return i; } } return -1; }返回 -1 是 C 语言中表示“没找到”的常见约定因为数组下标从 0 开始-1 合法且不冲突。线性查找的时间复杂度 O(n)适合数据量小、数组无序或需要返回多个匹配位置的场景。如果目标是在数组中查找另一个数组里的元素比如两个数组求交集直接用双重循环可能会很慢更好的做法是排序后二分查找或者用哈希表C 里可以用开放地址法自己实现。但作为最基础的查找手段线性查找仍然是入门必须写熟的一段代码。5.2 二分查找边界与死循环的实战总结二分查找的前提是数组已经有序。它的思路是每次把搜索区间对半缩小比较中间元素与目标值从而排除一半数据。迭代版本是笔试面试最常考的实现int binary_search(int arr[], int n, int target) { int low 0; int high n - 1; while (low high) { int mid low (high - low) / 2; if (arr[mid] target) { return mid; } else if (arr[mid] target) { low mid 1; } else { high mid - 1; } } return -1; }这里有两个关键细节必须强调。第一mid的计算不要写成(low high) / 2。如果low和high都接近INT_MAX相加会溢出导致 mid 变成负数。写成low (high - low) / 2就能避免这个问题。第二更新边界时low mid 1和high mid - 1都必须带上±1因为 mid 已经被检查过了。如果写成high mid或low mid当区间长度为 1 或 2 时可能永远无法缩小到空区间程序就死循环了。死循环问题在 PTA 和各类 OJ 上特别常见。你可以在本机测试一个长度为 3 的数组手动模拟几个目标值重点观察low和high在每轮结束后的变化。很多人在low high时循环不退出其实问题就出在边界更新策略上。记一句口诀“用low high做循环条件就配合low mid 1与high mid - 1如果坚持low high则配套策略要复杂得多初学阶段不建议碰。” 二分查找的时间复杂度是 O(log n)在有序数组中查找一个元素效率远超线性查找。递归版本的二分查找也常见int binary_search_rec(int arr[], int low, int high, int target) { if (low high) { return -1; } int mid low (high - low) / 2; if (arr[mid] target) { return mid; } else if (arr[mid] target) { return binary_search_rec(arr, mid 1, high, target); } else { return binary_search_rec(arr, low, mid - 1, target); } }递归版本思路清晰但每次递归有函数调用开销深度在 O(log n)对正常数量级没问题。如果数组极大迭代版更稳。5.3 二分查找的变体与应用二分查找真正考验人的是变体问题在有序数组中找到第一个等于 target 的位置或者最后一个等于 target 的位置。标准二分查找只要命中就返回而变体要求在众多重复值中定位边界。找第一个等于 target 的位置代码可以这样写int lower_bound(int arr[], int n, int target) { int low 0; int high n; // 注意这里 high 的语义是开区间 while (low high) { int mid low (high - low) / 2; if (arr[mid] target) { high mid; } else { low mid 1; } } return low; }这段代码的返回值是“第一个大于等于 target 的下标”。如果所有元素都小于 target返回值是 n。想找第一个等于 target 的位置就检查返回值是否在范围内且arr[low] target。这种写法的优点是边界语义一致不容易出死循环。类似的找最后一个小于等于 target 的位置可以再推导。建议你把这些变体写成自己的模板做题时直接套用比自己临时推边界可靠得多。工程里最常见的组合是“qsort 排序 二分查找”。比如一个结构体数组按 id 排序然后根据 id 查找用户信息先排序 O(n log n)之后每次查找 O(log n)非常适合“一次排序、多次查询”的场景。如果要在有序数组中插入一个新元素并保持有序可以先二分找到插入位置再用memmove把后面的元素整体后移在动态数组里这就是核心操作。6. 常见问题与排查技巧实录6.1 数组越界C 不检查但后果自己担C 语言不对数组越界做运行时检查这是它高性能的来源也是许多 BUG 的根源。越界读可能只是读到相邻变量的旧值导致计算结果错误越界写更加危险可能把一个变量、一个指针甚至函数的返回地址直接改掉。最典型的案例是int a[3]; for (int i 0; i 3; i) { a[i] i; }循环条件写成i 3最后一次写入的是a[3]而这个位置其实在数组之外。它可能正好是循环变量 i 所在的内存于是程序的行为变得完全不可预测可能 i 被改成 3循环继续执行也可能程序直接崩溃。做实验时这种 bug 很多情况下“碰巧没问题”但这正是最危险的地方——一旦你更换编译器、开启优化或改变周围变量的声明顺序问题就会爆发。有条件的同学建议在编译时开启地址消毒器一把就能定位到越界。GCC 和 Clang 都支持-fsanitizeaddress运行时会在越界发生的第一时间报告是哪一行代码、访问了哪个地址。比如gcc -g -fsanitizeaddress -o demo demo.c ./demo我调试越界问题时就靠这个工具省了大量时间。另一个常用手段是 GDB 下断点观察变量值的变化。越界的排查思路可以整理成一个速查表现象可能原因排查手段局部变量莫名被改前一个数组越界写入开启 ASan、观察相邻变量地址函数结束就崩溃返回地址被越界覆盖GDB 看栈回溯字符串打印出乱码字符数组缺少\0检查数组大小、初始化排序结果有随机数内层循环访问到数组外重新检查循环边界6.2 数组“赋值”为什么不能用等号两个数组之间不能直接用赋值比如int a[5], b[5]; b a;是编译错误。原因还是数组名不是可修改的左值。要想复制数组内容要么逐个元素拷贝要么调用memcpymemcpy(b, a, sizeof(a));注意这里要保证b的空间不小于a。复制字符串也同理strcpy(dest, src)会不断复制字符直到遇到\0所以目标数组必须足够大否则就会发生缓冲区溢出。我建议在需要复制大量数据时优先用memcpy它底层按块搬运比逐元素循环快得多。但用的时候要记住memcpy的两个指针如果指向重叠区域行为是未定义的这时应该用memmove。判断数组是否相等也不能用if (a b)这个比较的是两个指针的地址不是内容本质上又是一个“数组名退化”的坑。6.3 二维数组与 int** 的爱恨纠葛这一点值得单独拿出来讲因为面试题里出镜率太高。很多人以为二维数组名传到函数里就是int **结果编译警告或者运行时崩溃。回到本质int a[2][3]退化为“指向int[3]的指针”也就是int (*)[3]而int **是指向指针变量的指针。一个是“指向一行数据”另一个是“指向保存指针的变量”它们的二级索引方式完全不同。强行把a当成int **传给函数函数里做a[i][j]时会按错误步长去解读内存轻则读到错位数据重则段错误。正确传二维数组的方法前面已经说过要么写成int a[][3]要么写成int (*a)[3]。如果你非要用int **访问二维数据那需要自己手动构建“指针数组模拟二维数组”int row0[3] {1, 2, 3}; int row1[3] {4, 5, 6}; int *p[2] {row0, row1};现在p的类型就是int **可以接受的类型每个元素是一个指向 int 的指针第二维的“三个 int”靠每个行数组自己保证。这种结构在内存中并不像二维数组那样连续它的每一行可能分散在不同地方。搞清楚这两种结构的区别才能应对各类数组指针和指针数组的笔试题。6.4 PAT 1037 霍格沃茨找零钱数组里的进制与进位思想竞赛题里有很多看起来和数组无关、实际却是数组应用的题目。就拿 PAT 乙级 1037“在霍格沃茨找零钱”来说题目描述的货币单位是 Galleon、Sickle、Knut进率分别是 1 Galleon 17 Sickle1 Sickle 29 Knut。给定应付和实付要求输出找零按三个单位分别表示。最直观的思路是把所有钱统一成最小单位 Knut计算完毕再转换回来而不是在三个单位之间逐位借位。用数组存钱就很方便typedef struct { int g, s, k; } Money; int to_knut(Money m) { return (m.g * 17 m.s) * 29 m.k; } Money to_money(int knut) { Money m; m.g knut / (17 * 29); knut % 17 * 29; m.s knut / 29; m.k knut % 29; return m; }这里数组的体现是如果你把三个币值当成一个长度为 3 的数组int money[3]那么to_money就是在做“数组元素按进制还原”的过程。很多所谓“进制转换、找零钱、加密解密”类题目本质上都是在数组上做带权累加和带权分解。理解这一点之后碰到新题会更容易套用熟悉的方法。6.5 动态数组数组不够大怎么办普通数组在声明时长度就固定了但现实需求经常是“运行到一半才发现要装更多数据”。这时可以用malloc、calloc、realloc在堆上动态维护一块内存当作动态数组使用。一个简单的动态数组结构体可以是typedef struct { int *data; size_t size; size_t capacity; } DynArray;初始分配一个容量比如 4当size capacity时需要扩容。扩容通常的做法是容量翻倍然后用realloc重新分配内存int *new_data realloc(arr-data, new_cap * sizeof(int)); if (new_data NULL) { // 注意realloc 失败会返回 NULL但原来的内存仍然有效 // 这里不能直接覆盖 arr-data否则原指针丢失 } arr-data new_data; arr-capacity new_cap;为什么容量翻倍而不是每次只增加一个位置因为realloc是有代价的它可能要把旧数据整体搬到新地址。如果每插入一个元素就扩容一次总的移动次数是 O(n^2)。而按倍数扩容后总共的移动次数被摊还到每次插入上均摊复杂度降到 O(1)。C 的 vector、Java 的 ArrayList 动态扩容也是这个思路。从底层看realloc向操作系统申请的是进程虚拟地址空间中的连续内存页这和你普通数组在栈上申请连续内存的本质是相通的只是生命周期不同。动态数组很有用但也增加了很多需要小心的点要检查 malloc/realloc 返回值、要及时 free 防止内存泄漏、要区分 size 和 capacity。初学者先把静态数组玩熟再来碰动态数组会轻松很多。我个人在实际操作中的体会是数组这一关最主要的障碍不是语法而是脑子里没有内存图。你把上面每个例子都敲一遍在 main 函数里打印地址用 GDB 看一次内存区域的字节内容很多疑问会直接消失。数组作为 C 语言最基础的数据结构它往后的每一条延伸——字符串、指针运算、排序查找、二维矩阵、动态扩容——都是用连续内存这块地基盖起来的。踩过的坑越多越能体会那句老话先把数组吃透C 语言就入门了一半。最后再分享一个我的习惯凡是写与数组相关的函数第一行一定先把能计算的数组长度算出来比如n sizeof(arr) / sizeof(arr[0])变量声明先写上后面所有边界条件都围着它转。这一招确实能少写很多 bug。
C语言数组完全指南：从内存布局到排序查找实战
很多人觉得 C 语言数组没什么好讲的一个连续内存块循环下标访问排序查找翻来覆去就那几个算法。但我在带新人、看笔试面试题时发现数组恰恰是暴露问题最多的地方——有人分不清数组名和指针有人在二维数组传参时被编译错误卡住有人写二分查找死循环到半夜抓狂。这篇文章打算按“从一维到多维从排序到查找”这条主线把数组相关的关键点串起来讲透。它既适合刚学完指针、正在学构造数据类型的同学也适合准备考研刷题、想系统复查 C 基础的人。看完之后你会清楚数组在内存中到底是什么为什么下标从 0 开始怎么分析多维数组怎么把排序查找写稳。我会把平时容易踩的坑、调试时真正有用的手段一起放进来尽量让这些内容可以直接用到你自己的代码里。1. 从内存视角拆解数组理解数组本质1.1 数组就是一块连续内存数组的第一性原理是“连续内存”。声明int a[5]之后编译器会为你分配一块足够放下 5 个 int 的连续空间。每个 int 占 4 字节32位平台所以 5 个元素一共 20 字节。这些字节是紧挨着的不像链表那样东一块西一块。正是这种连续性让数组可以在 O(1) 时间内随机访问任意元素因为编译器只需要做一次加法——元素地址 首地址 下标 × 单个元素大小——就能直接算出目标位置。从这个角度也能理解为什么数组要求所有元素类型一致类型一致才能保证每个元素宽度相同编译器才能用统一的步长去偏移。如果数组里既有 4 字节的 int 又有 8 字节的 doublea[i]的地址计算就彻底乱套了。很多初学者一开始会忽略这个“连续”的含义导致后面理解指针偏移、多维数组、缓冲区溢出时都很吃力。我的建议是学习数组的第一步不是背语法而是先在纸上画出内存格子标出a[0]、a[1]、a[2]分别占哪几个字节。用代码验证一下连续地址是最直观的#include stdio.h int main(void) { int a[5] {10, 20, 30, 40, 50}; for (int i 0; i 5; i) { printf(a[%d] %p\n, i, (void *)a[i]); } return 0; }运行后会看到相邻地址相差正好 4 个字节比如0x7ffd...00、0x7ffd...04、0x7ffd...08。这个实验我建议每个人都亲手做一次。看一眼地址的输出比你背十遍“数组是连续内存”都管用。数组存在哪块区域呢如果声明在函数内部通常分配在栈上如果是全局数组或 static 数组分配在全局/静态区如果是用malloc申请的则在堆上。不管在哪块区域只要是数组元素之间的地址一定是连续递增的。1.2 下标从 0 开始本质是偏移量不少人问过为什么数组下标不从 1 开始明明从 1 开始更符合日常计数习惯。这个问题的答案就藏在上面那个公式里a[i]真正的意思是“相对于首地址偏移 i 个元素”也就是*(a i)。当 i 0 时偏移量为 0直接访问首元素。如果从 1 开始那么访问首元素时要写a[1]编译器每次都要算a (i - 1)不仅多一次减法还让“下标即偏移”的语义变得含糊。这个设计不是拍脑袋定的而是从指针运算继承过来的。a i本身就是指针算术要求 i 表示步数。既然指针指向首元素时步数为 0下标自然从 0 开始。理解这个之后再看到a[i]、*(a i)、i[a]这三种写法相等你就不会觉得奇怪了——因为它们本质上都是同一件事。顺便说一句i[a]这种写法虽然合法在笔试中偶尔出现但实际项目里绝对不要用纯粹是炫技而且可读性极差。围绕下标还有一个容易混淆的细节是a[i]和a[i]的区别。这跟单独看某个表达式int b a;是一样的道理a是先自增再取新值a是先用旧值再自增。放到数组里a[i]表示先读取a[i]的当前值参与运算之后再把a[i]加 1a[i]则是先把a[i]加 1再用新值。如果一条语句里既有赋值又对同一个数组元素自增强烈建议拆成两行写不要挑战自己和编译器的理解力。1.3 数组长度的求法sizeof 的边界与陷阱求一个真正数组的长度C 语言里有一个经典写法int a[7] {0}; size_t len sizeof(a) / sizeof(a[0]);sizeof(a)返回整个数组占用的字节数sizeof(a[0])返回单个元素字节数两者一除就是元素个数。这个写法对任何类型都成立所以很多项目里会封装成宏#define ARRAY_SIZE(a) (sizeof(a) / sizeof((a)[0]))但注意这个宏只能在“真正的数组”上使用。一旦数组作为函数参数传递出去就会退化成指针。我在下一节会细讲退化这里先记住一个结论在函数形参里写int arr[]编译器的真实处理是int *arr此时在函数内部执行sizeof(arr)得到的是指针大小64 位平台上通常是 8 字节不再是数组容量。这也是为什么 C 函数传递数组时必须额外传一个长度参数比如void print_array(int arr[], size_t n) { for (size_t i 0; i n; i) { printf(%d , arr[i]); } }n必须由调用者提供。很多题库里把“从标准输入读 n再读 n 个数”这种题做成函数要求你实现排序或查找函数的签名往往就是void sort(int *a, int n)原因就在这里。另外求字符数组长度时还有个坑char s[] hello的sizeof(s)是 6因为末尾自动多了一个\0结束符而strlen(s)返回 5它只统计到结束符之前。初学者如果错把sizeof当字符串长度去用后面一涉及循环就越界。2. 一维数组的初始化、遍历与数组名的本质2.1 初始化方式与局部变量陷阱一维数组的初始化看起来简单实际藏了不少细节。常见写法有这四种int a[5] {1, 2, 3, 4, 5}; // 完整初始化 int b[5] {1, 2}; // 部分初始化其余补 0 int c[] {1, 2, 3}; // 由初始化列表推断长度为 3 int d[5] {0}; // 全部清 0第二种写法特别容易忽略int b[5] {1, 2}等价于{1, 2, 0, 0, 0}。编译器对未显式给出的元素统一做“零初始化”。这在实际开发中非常有用想快速清空一个数组时直接int a[N] {0}就不用写循环memset了。但要注意这种“补零”只对初始化有效如果你先声明int a[5];然后在后面写a[5] {0};是不行的数组一旦声明完成就不能再用花括号整体赋值。局部变量和全局变量的初始化行为也不一样。全局数组或 static 数组不写初始化时默认全 0但局部非 static 数组的内容是不确定的可能是上次栈上遗留的脏数据。我见过不少新手定义局部数组后直接拿来统计结果里面全是随机值程序结果每次运行都不一样。正确做法是要么初始化要么先用memset清零。另外int a[5] {};这种写法在旧标准里并不是合法初始化C 语言里想清空数组请写 {0}不要留空。到了 C23 标准才引入空初始化列表但为了兼容主流编译器还是老老实实写{0}最稳。2.2 数组名与指针的三次“表里不一”数组名和指针是 C 语言里最容易让人纠结的一对概念。严格来说数组名并不是一个指针变量但在大多数表达式中它会“退化”为指向首元素的指针。正是这种退化导致下面三种情况经常被混淆。第一sizeof(arr)计算的是整个数组的大小不是指针大小。这和在函数形参里得到的 8 字节完全不同。第二arr的类型不是int *而是“指向整个数组的指针”类型是int (*)[5]。看下面两行输出int a[5] {0}; printf(%p\n, (void *)a); // 首元素地址 printf(%p\n, (void *)a); // 整个数组的地址两个地址在数值上往往相同因为数组首元素的地址和数组本身的起始地址重合。但它们的类型不同导致指针运算结果完全不同a 1只偏移 1 个 int也就是 4 字节a 1跳过整个数组偏移 5 个 int也就是 20 字节。很多笔试题喜欢在这里挖坑。第三数组名不能作为赋值左值。int b[5]; a b;是编译错误因为数组名不是一个可修改的变量它更像一个地址常量。但int *p a;没问题这是让指针指向数组首元素。之后你可以通过p修改数组内容比如p[2] 99效果和a[2] 99一样。当年我学到这里时是把数组名想象成“贴着数组首元素的一张标签”标签本身不能撕下来贴到别处但你可以另外拿一个指针指向它。这个类比救了我也救过我后来教过的不少学弟学妹。2.3 字符数组与字符串C 语言里的字符串本质上就是 char 数组加一个\0结束符。这句话很多书都写过但真正理解的人不多。看两个定义char s1[] hello; char *s2 hello;s1是一个字符数组hello的内容会被拷贝到栈上的数组里所以你可以修改s1[0] H没问题。但s2是指向字符串字面量的指针字符串字面量在多数系统上存放在只读区尝试s2[0] H会导致未定义行为常见结果就是段错误。理解这个区别能避免不少莫名其妙的崩溃。字符串和数组紧密结合的场景还有“指针数组存放字符串”。比如char *names[] {Alice, Bob, Charlie};这个数组本身是一个指针数组每个元素是一个char *指向不同的字符串字面量。如果你想用某种规则对这些字符串做排序就不能直接用或比较而要调用strcmp来按字典序比较。这个场景在第五节的排序实战里我会再展开。字符数组最常见的坑是空间不够放结束符。比如char s[5] hello;hello加上\0一共需要 6 个字节数组只有 5 个初始化的结果就是\0被丢掉。后续调用strlen(s)或printf(%s, s)时程序会继续往后读取内存直到碰巧遇到一个 0 字节为止轻则打印出乱码重则越界读导致崩溃。解决办法很简单数组长度至少写成6或者干脆不写长度让编译器自己算。3. 多维数组从“数组的数组”说起3.1 二维数组到底长什么样一维数组是“一排盒子”二维数组就是“一个盒子里的每个元素又是一个一维数组”。严格地说int a[3][4]是一个长度为 3 的数组它的每个元素都是一个长度为 4 的int数组。这种“数组的数组”定义非常有用因为理解之后你就能推导出一系列访问方式。内存布局上C 语言的多维数组是行优先存储的也就是先完整存放第 0 行再存放第 1 行再存放第 2 行。a[1][2]在内存中的位置其实是首地址偏移(1 * 4 2)个 int。这句话非常关键因为它意味着二维数组在内存里依然是连续的一段空间并不是那种“嵌套的数组指针结构”。访问二维数组元素的标准写法是a[i][j]但它的底层表达式是*(*(a i) j)。拆开来看a退化为指向第 0 行的指针a i指向第 i 行*(a i)得到第 i 行的首元素地址再加j并解引用就是第 i 行第 j 列的值。很多书会用“二维数组名是行指针”这种说法意思就是这里。下面的表格可以帮你建立内存布局的直观印象逻辑视角列0列1列2列3第0行a[0][0]a[0][1]a[0][2]a[0][3]第1行a[1][0]a[1][1]a[1][2]a[1][3]第2行a[2][0]a[2][1]a[2][2]a[2][3]实际上a[0][3]和a[1][0]在物理内存里是紧挨着的。这个特性让二维数组可以被当作一维数组来操作比如用int *p a[0][0]然后p[i * 4 j]就能访问同样元素。在实际工程里很多矩阵运算就是这么做的。3.2 多维数组的初始化和遍历二维数组初始化有两种风格。分行写法可读性好int a[2][3] { {1, 2, 3}, {4, 5, 6} };连续列表写法则省事但要自己数数int b[2][3] {1, 2, 3, 4, 5, 6};编译器会按行优先顺序把 6 个数依次放进 2 行 3 列。部分初始化同样会补 0比如int c[2][3] {{1}, {4}};结果第一行是1, 0, 0第二行是4, 0, 0。这个“花括号按行对应”的规则理解之后基本不会写错。遍历二维数组时最自然的写法是外层循环遍历行、内层循环遍历列for (int i 0; i 2; i) { for (int j 0; j 3; j) { printf(%d , a[i][j]); } putchar(\n); }这个遍历顺序其实是刻意的因为内存是行优先连续存放按行遍历时访问的是相邻地址缓存命中率高如果反着来先列后行每次访问都会跳到另一个行区域性能会差不少。在数据量小的时候体会不明显但在图像处理这类动辄上百万像素的场景里遍历顺序选错可能让程序慢好几倍。多维数组的应用远不止数学里的矩阵。图像处理里的灰度图就是典型的二维数组pixel[x][y]表示第 x 行第 y 列的灰度值。还有一种场景叫“多维密度估计”本质是把连续的数值范围划分成网格用多维数组保存每个网格里的样本数量再统计分布。比如二维坐标点落在某个小方格内就把grid[i][j]加 1。这个思路在数据分析和科学计算里非常常见而底层结构就是 C 的多维数组。3.3 多维数组作为函数参数为什么第二维必须给把二维数组传给函数时形参至少有两种等价写法void f(int a[][4], int rows); void g(int (*a)[4], int rows);a[][4]和(*a)[4]是完全等价的都表示“a 是指向长度为 4 的 int 数组的指针”。这里的核心问题是为什么第二维必须写死不能写成int a[][]原因还是地址计算。编译器要通过a[i][j]定位元素必须知道每行有多少个元素才能算出第 i 行的起始地址。如果第二维未知a[i]就无法确定跳过多远。有人会想那我写成int **a行不行不行。int **a表示“a 指向一个 int *”而二维数组名退化的结果是“指向一整个 int[4] 的指针”这两者指向的类型不同。虽然它们在内存里的数值可能都是某个地址但步长语义完全不同。强行传过去轻则编译警告重则运行时取数据取错位置。如果你确实想让函数同时支持不同列数的矩阵最灵活的方式是“扁平化”把二维数组当成连续内存传一维指针、行数和列数void print_matrix(int *a, int rows, int cols) { for (int i 0; i rows; i) { for (int j 0; j cols; j) { printf(%2d , a[i * cols j]); } putchar(\n); } }调用时传(int *)a或a[0][0]即可。这种写法在工程里很常见因为它把“维度”变成了普通参数灵活性大大提升。代价是a[i][j]得手动写成a[i * cols j]可读性稍微下降一些但换来的是函数可以处理任意列数的矩阵值了。4. 数组排序实战从冒泡到 qsort4.1 冒泡排序的实现与优化排序是数组最经典的应用场景之一。先写最基础的冒泡排序——核心思想是相邻元素两两比较如果顺序不对就交换每一轮把当前未排序区间里的最大值“冒”到最右边。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; // 本轮没有交换说明已经有序 } } }这里两个边界最容易写错。外层循环只需要执行n - 1轮因为剩下最后一个元素时它已经不用再比了。内层循环每轮结束后最后 i 个元素已经是全局最大的一批所以内层只需比较到n - 1 - i。如果你写成j n - i或者j n - i - 1可能产生越界访问或多余的比较。我见过太多人在写冒泡时把j 1访问到数组末尾之外那个错是隐蔽的程序不一定崩溃但结果往往有个莫名其妙的数混进来。加入swapped标志位是常见的优化如果一整轮下来没有任何交换说明数组已经有序可以提前终止。最好情况下数组已经有序第一轮就发现没有交换整体复杂度降到 O(n)。平均和最坏情况依然是 O(n^2)因为要频繁比较和交换。冒泡排序是稳定的相同元素的相对顺序不会变这一点在按多个字段排序时很重要。4.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; } } }写选择排序时最容易犯的错是内层循环从 0 开始找最小值。那样的话每轮找出来的都是全局最小值但前面的位置已经被固定再换一次就把已排好的元素又换乱了。所以内层循环一定要从i 1开始。不少人会觉得选择排序“交换次数少”实际上它每一轮最多只交换一次确实比冒泡的交换次数少但比较次数依然是 O(n^2)整体时间复杂度和冒泡差不多。需要留意的是选择排序不稳定比如数组[5, 5, 3]第一轮会把 3 和第一个 5 交换两个 5 的相对顺序在排序后发生改变。插入排序则是另一种思路把数组看成“左边已排序、右边未排序”两个区域每次把右边的第一个元素插入到左边合适的位置。对于接近有序的数据插入排序非常高效时间复杂度可以降到 O(n)。代码实现void insertion_sort(int arr[], int n) { for (int i 1; i n; i) { int key arr[i]; int j i - 1; while (j 0 arr[j] key) { arr[j 1] arr[j]; j--; } arr[j 1] key; } }插入排序的交换过程是用“后移覆盖”完成的不是相邻交换因此效率比冒泡高一些。这三种排序适合用来练手和理解算法思想但在真实项目里数据量一大基本不会手写它们而是直接调库。C 语言标准库已经提供了强大的qsort我们下一节细说。三种基础排序可以整理成下面这张对比表排序算法平均时间复杂度最坏时间复杂度空间复杂度稳定性冒泡排序O(n^2)O(n^2)O(1)稳定选择排序O(n^2)O(n^2)O(1)不稳定插入排序O(n^2)O(n^2)O(1)稳定qsort快排O(n log n)O(n^2)O(log n)不稳定4.3 用 qsort 优雅排序从基础算法走向工程实践qsort是 C 标准库提供的快速排序实现函数原型在stdlib.h里void qsort(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *));四个参数分别是数组首地址、元素个数、每个元素大小、比较函数指针。compar是比较函数它返回负值表示第一个参数排在第二个前面返回正值表示相反返回 0 表示相等。对一个 int 数组升序排序比较函数可以这样写int cmp_int(const void *a, const void *b) { int va *(const int *)a; int vb *(const int *)b; return (va vb) - (va vb); }为什么要用 而不是直接return *(int*)a - *(int*)b因为直接做减法在极端情况下可能溢出。比如va是INT_MAXvb是-1相减的结果超出了 int 能表达的范围行为是未定义的。用(va vb) - (va vb)这种写法返回值只在 -1、0、1 之间绝对安全。虽然大多数排序数据不会触发这种极端但养成好习惯总没错。排序结构体数组也很常用比如按成绩从高到低排typedef struct { char name[32]; int score; } Student; int cmp_student(const void *a, const void *b) { const Student *sa (const Student *)a; const Student *sb (const Student *)b; return (sb-score sa-score) - (sb-score sa-score); }注意这里为了降序把 b 和 a 的位置换了一下。调用qsort(stu, n, sizeof(Student), cmp_student)即可。对字符串数组排序时比较函数里要调用strcmp因为不能直接比较两个 char 指针的内容。在“数组排序统计”这一类需求里qsort 同样立竿见影。比如先统计每个数字出现的次数存入数组然后对统计数组排序就能快速找到出现次数最多或最少的元素。实际开发中我也经常用 qsort 排序结构体数组之后再配合二分查找这就是下一节的内容。5. 数组查找实战线性查找与二分查找5.1 线性查找的适用场景查找和排序是一对孪生问题。最简单的查找就是线性查找从头到尾遍历数组找到目标值就返回下标int linear_search(int arr[], int n, int target) { for (int i 0; i n; i) { if (arr[i] target) { return i; } } return -1; }返回 -1 是 C 语言中表示“没找到”的常见约定因为数组下标从 0 开始-1 合法且不冲突。线性查找的时间复杂度 O(n)适合数据量小、数组无序或需要返回多个匹配位置的场景。如果目标是在数组中查找另一个数组里的元素比如两个数组求交集直接用双重循环可能会很慢更好的做法是排序后二分查找或者用哈希表C 里可以用开放地址法自己实现。但作为最基础的查找手段线性查找仍然是入门必须写熟的一段代码。5.2 二分查找边界与死循环的实战总结二分查找的前提是数组已经有序。它的思路是每次把搜索区间对半缩小比较中间元素与目标值从而排除一半数据。迭代版本是笔试面试最常考的实现int binary_search(int arr[], int n, int target) { int low 0; int high n - 1; while (low high) { int mid low (high - low) / 2; if (arr[mid] target) { return mid; } else if (arr[mid] target) { low mid 1; } else { high mid - 1; } } return -1; }这里有两个关键细节必须强调。第一mid的计算不要写成(low high) / 2。如果low和high都接近INT_MAX相加会溢出导致 mid 变成负数。写成low (high - low) / 2就能避免这个问题。第二更新边界时low mid 1和high mid - 1都必须带上±1因为 mid 已经被检查过了。如果写成high mid或low mid当区间长度为 1 或 2 时可能永远无法缩小到空区间程序就死循环了。死循环问题在 PTA 和各类 OJ 上特别常见。你可以在本机测试一个长度为 3 的数组手动模拟几个目标值重点观察low和high在每轮结束后的变化。很多人在low high时循环不退出其实问题就出在边界更新策略上。记一句口诀“用low high做循环条件就配合low mid 1与high mid - 1如果坚持low high则配套策略要复杂得多初学阶段不建议碰。” 二分查找的时间复杂度是 O(log n)在有序数组中查找一个元素效率远超线性查找。递归版本的二分查找也常见int binary_search_rec(int arr[], int low, int high, int target) { if (low high) { return -1; } int mid low (high - low) / 2; if (arr[mid] target) { return mid; } else if (arr[mid] target) { return binary_search_rec(arr, mid 1, high, target); } else { return binary_search_rec(arr, low, mid - 1, target); } }递归版本思路清晰但每次递归有函数调用开销深度在 O(log n)对正常数量级没问题。如果数组极大迭代版更稳。5.3 二分查找的变体与应用二分查找真正考验人的是变体问题在有序数组中找到第一个等于 target 的位置或者最后一个等于 target 的位置。标准二分查找只要命中就返回而变体要求在众多重复值中定位边界。找第一个等于 target 的位置代码可以这样写int lower_bound(int arr[], int n, int target) { int low 0; int high n; // 注意这里 high 的语义是开区间 while (low high) { int mid low (high - low) / 2; if (arr[mid] target) { high mid; } else { low mid 1; } } return low; }这段代码的返回值是“第一个大于等于 target 的下标”。如果所有元素都小于 target返回值是 n。想找第一个等于 target 的位置就检查返回值是否在范围内且arr[low] target。这种写法的优点是边界语义一致不容易出死循环。类似的找最后一个小于等于 target 的位置可以再推导。建议你把这些变体写成自己的模板做题时直接套用比自己临时推边界可靠得多。工程里最常见的组合是“qsort 排序 二分查找”。比如一个结构体数组按 id 排序然后根据 id 查找用户信息先排序 O(n log n)之后每次查找 O(log n)非常适合“一次排序、多次查询”的场景。如果要在有序数组中插入一个新元素并保持有序可以先二分找到插入位置再用memmove把后面的元素整体后移在动态数组里这就是核心操作。6. 常见问题与排查技巧实录6.1 数组越界C 不检查但后果自己担C 语言不对数组越界做运行时检查这是它高性能的来源也是许多 BUG 的根源。越界读可能只是读到相邻变量的旧值导致计算结果错误越界写更加危险可能把一个变量、一个指针甚至函数的返回地址直接改掉。最典型的案例是int a[3]; for (int i 0; i 3; i) { a[i] i; }循环条件写成i 3最后一次写入的是a[3]而这个位置其实在数组之外。它可能正好是循环变量 i 所在的内存于是程序的行为变得完全不可预测可能 i 被改成 3循环继续执行也可能程序直接崩溃。做实验时这种 bug 很多情况下“碰巧没问题”但这正是最危险的地方——一旦你更换编译器、开启优化或改变周围变量的声明顺序问题就会爆发。有条件的同学建议在编译时开启地址消毒器一把就能定位到越界。GCC 和 Clang 都支持-fsanitizeaddress运行时会在越界发生的第一时间报告是哪一行代码、访问了哪个地址。比如gcc -g -fsanitizeaddress -o demo demo.c ./demo我调试越界问题时就靠这个工具省了大量时间。另一个常用手段是 GDB 下断点观察变量值的变化。越界的排查思路可以整理成一个速查表现象可能原因排查手段局部变量莫名被改前一个数组越界写入开启 ASan、观察相邻变量地址函数结束就崩溃返回地址被越界覆盖GDB 看栈回溯字符串打印出乱码字符数组缺少\0检查数组大小、初始化排序结果有随机数内层循环访问到数组外重新检查循环边界6.2 数组“赋值”为什么不能用等号两个数组之间不能直接用赋值比如int a[5], b[5]; b a;是编译错误。原因还是数组名不是可修改的左值。要想复制数组内容要么逐个元素拷贝要么调用memcpymemcpy(b, a, sizeof(a));注意这里要保证b的空间不小于a。复制字符串也同理strcpy(dest, src)会不断复制字符直到遇到\0所以目标数组必须足够大否则就会发生缓冲区溢出。我建议在需要复制大量数据时优先用memcpy它底层按块搬运比逐元素循环快得多。但用的时候要记住memcpy的两个指针如果指向重叠区域行为是未定义的这时应该用memmove。判断数组是否相等也不能用if (a b)这个比较的是两个指针的地址不是内容本质上又是一个“数组名退化”的坑。6.3 二维数组与 int** 的爱恨纠葛这一点值得单独拿出来讲因为面试题里出镜率太高。很多人以为二维数组名传到函数里就是int **结果编译警告或者运行时崩溃。回到本质int a[2][3]退化为“指向int[3]的指针”也就是int (*)[3]而int **是指向指针变量的指针。一个是“指向一行数据”另一个是“指向保存指针的变量”它们的二级索引方式完全不同。强行把a当成int **传给函数函数里做a[i][j]时会按错误步长去解读内存轻则读到错位数据重则段错误。正确传二维数组的方法前面已经说过要么写成int a[][3]要么写成int (*a)[3]。如果你非要用int **访问二维数据那需要自己手动构建“指针数组模拟二维数组”int row0[3] {1, 2, 3}; int row1[3] {4, 5, 6}; int *p[2] {row0, row1};现在p的类型就是int **可以接受的类型每个元素是一个指向 int 的指针第二维的“三个 int”靠每个行数组自己保证。这种结构在内存中并不像二维数组那样连续它的每一行可能分散在不同地方。搞清楚这两种结构的区别才能应对各类数组指针和指针数组的笔试题。6.4 PAT 1037 霍格沃茨找零钱数组里的进制与进位思想竞赛题里有很多看起来和数组无关、实际却是数组应用的题目。就拿 PAT 乙级 1037“在霍格沃茨找零钱”来说题目描述的货币单位是 Galleon、Sickle、Knut进率分别是 1 Galleon 17 Sickle1 Sickle 29 Knut。给定应付和实付要求输出找零按三个单位分别表示。最直观的思路是把所有钱统一成最小单位 Knut计算完毕再转换回来而不是在三个单位之间逐位借位。用数组存钱就很方便typedef struct { int g, s, k; } Money; int to_knut(Money m) { return (m.g * 17 m.s) * 29 m.k; } Money to_money(int knut) { Money m; m.g knut / (17 * 29); knut % 17 * 29; m.s knut / 29; m.k knut % 29; return m; }这里数组的体现是如果你把三个币值当成一个长度为 3 的数组int money[3]那么to_money就是在做“数组元素按进制还原”的过程。很多所谓“进制转换、找零钱、加密解密”类题目本质上都是在数组上做带权累加和带权分解。理解这一点之后碰到新题会更容易套用熟悉的方法。6.5 动态数组数组不够大怎么办普通数组在声明时长度就固定了但现实需求经常是“运行到一半才发现要装更多数据”。这时可以用malloc、calloc、realloc在堆上动态维护一块内存当作动态数组使用。一个简单的动态数组结构体可以是typedef struct { int *data; size_t size; size_t capacity; } DynArray;初始分配一个容量比如 4当size capacity时需要扩容。扩容通常的做法是容量翻倍然后用realloc重新分配内存int *new_data realloc(arr-data, new_cap * sizeof(int)); if (new_data NULL) { // 注意realloc 失败会返回 NULL但原来的内存仍然有效 // 这里不能直接覆盖 arr-data否则原指针丢失 } arr-data new_data; arr-capacity new_cap;为什么容量翻倍而不是每次只增加一个位置因为realloc是有代价的它可能要把旧数据整体搬到新地址。如果每插入一个元素就扩容一次总的移动次数是 O(n^2)。而按倍数扩容后总共的移动次数被摊还到每次插入上均摊复杂度降到 O(1)。C 的 vector、Java 的 ArrayList 动态扩容也是这个思路。从底层看realloc向操作系统申请的是进程虚拟地址空间中的连续内存页这和你普通数组在栈上申请连续内存的本质是相通的只是生命周期不同。动态数组很有用但也增加了很多需要小心的点要检查 malloc/realloc 返回值、要及时 free 防止内存泄漏、要区分 size 和 capacity。初学者先把静态数组玩熟再来碰动态数组会轻松很多。我个人在实际操作中的体会是数组这一关最主要的障碍不是语法而是脑子里没有内存图。你把上面每个例子都敲一遍在 main 函数里打印地址用 GDB 看一次内存区域的字节内容很多疑问会直接消失。数组作为 C 语言最基础的数据结构它往后的每一条延伸——字符串、指针运算、排序查找、二维矩阵、动态扩容——都是用连续内存这块地基盖起来的。踩过的坑越多越能体会那句老话先把数组吃透C 语言就入门了一半。最后再分享一个我的习惯凡是写与数组相关的函数第一行一定先把能计算的数组长度算出来比如n sizeof(arr) / sizeof(arr[0])变量声明先写上后面所有边界条件都围着它转。这一招确实能少写很多 bug。