第 6 讲 · 数组、字符串、排序与查找

数组把一批同类型数据放进连续内存。它带来了批量处理能力，也带来了 C 最典型的风险：语言不会替你检查下标、长度和字符串结尾。

1. 数组是一段有边界的连续空间

int a[5] = {1, 2, 3};

五个元素依次为 1, 2, 3, 0, 0，合法下标是 0～4。

下标    0    1    2    3    4
      +----+----+----+----+----+
a     |  1 |  2 |  3 |  0 |  0 |
      +----+----+----+----+----+

数组越界属于未定义行为：它可能崩溃，也可能改坏相邻变量后继续运行。后者更危险，因为错误表现可能远离真正原因。

1.1 遍历模板

for (int i = 0; i < n; ++i) {
    printf("%d\n", a[i]);
}

防越界最有效的习惯不是“运行后看会不会崩”，而是让所有边界都从同一个 n 推导，始终使用半开区间 [0, n)。

1.2 数组不能整体赋值

int a[5] = {1, 2, 3, 4, 5};
int b[5];
/* b = a; 错误 */

普通数组不是可赋值对象。可逐元素复制，或在明确字节数时使用 memcpy：

for (int i = 0; i < 5; ++i) {
    b[i] = a[i];
}

数组也不能直接用 == 比较内容，必须逐元素比较。

1.3 长度和存储位置

课件基于 C89 教学，强调数组长度使用编译期常量：

#define N 1000
int data[N];

C99 支持变长数组，但数组一旦创建仍不能改变长度，且大型局部数组可能耗尽栈。数据上限明确时使用固定数组；大小运行时才知道且可能很大时，用动态内存更合适。

2. 数组作为函数参数

double dot(const double a[], const double b[], int n)
{
    double result = 0;
    for (int i = 0; i < n; ++i) {
        result += a[i] * b[i];
    }
    return result;
}

参数里的 a[] 实际按 const double *a 处理。传递的是首元素地址，因此函数能访问原数组，但不知道它有多长。

size_t wrong_length(int a[])
{
    return sizeof a / sizeof a[0]; /* 错：sizeof a 是指针大小 */
}

数组长度必须显式传入，或由接口的固定约定保证。

3. 排序到底在做什么

排序按关键字重新排列元素。开始写代码前明确：

  • 升序还是降序；
  • 关键字有几个，优先级是什么；
  • 相等元素是否要保持原先顺序；
  • 排原数据，还是只排索引。

课件列出冒泡、选择、插入、归并、快速排序等方法，重点展开冒泡排序。

4. 冒泡排序

升序冒泡每次比较相邻元素，逆序就交换。一轮后，当前最大的元素“冒”到未排序区末尾。

void bubble_sort(int a[], int n)
{
    for (int end = n - 1; end > 0; --end) {
        int changed = 0;
        for (int i = 0; i < end; ++i) {
            if (a[i] > a[i + 1]) {
                int t = a[i];
                a[i] = a[i + 1];
                a[i + 1] = t;
                changed = 1;
            }
        }
        if (!changed) {
            break;
        }
    }
}

两个循环边界分别表达：

  • end 之后已经排好；
  • 本轮只比较到 a[end]，所以 i < end 才能安全访问 a[i+1]。

若一轮没有交换，数组已经有序，可以提前结束。最好情况降为 O(n)O(n)，平均和最坏仍为 O(n2)O(n^2)。

只在严格逆序 > 时交换，相等元素不会越过彼此，所以该实现稳定。若改成 >=，会破坏稳定性。

4.1 多关键字排序

例如先按总分降序，再按学号升序：

int should_come_after(Student a, Student b)
{
    if (a.total != b.total) {
        return a.total < b.total;
    }
    return a.id > b.id;
}

把“谁应排在后面”封装成判断函数，排序循环不必混入业务规则。

5. 选择、插入、归并和快速排序的定位

  • 选择排序：每轮找最小值放到前面，O(n2)O(n^2)，交换少，通常不稳定；
  • 插入排序：把新元素插入前面已排序部分，近乎有序时很快，稳定；
  • 归并排序：分成两半排序后线性归并，稳定，O(nlog⁡n)O(n\log n)，需额外空间；
  • 快速排序：按枢轴划分，平均 O(nlog⁡n)O(n\log n)，最坏 O(n2)O(n^2)，通常不稳定。

本课后续通过标准库 qsort 使用高效通用排序；理解这些差异比死背每份代码更重要。

6. 查找

6.1 线性查找

无序数组从头扫到尾：

int linear_find(const int a[], int n, int key)
{
    for (int i = 0; i < n; ++i) {
        if (a[i] == key) {
            return i;
        }
    }
    return -1;
}

最坏比较 nn 次，复杂度 O(n)O(n)。

6.2 二分查找

前提是数组已经按同一规则升序排列：

int binary_find(const int a[], int n, int key)
{
    int left = 0;
    int right = n; /* 搜索区间 [left, right) */

    while (left < right) {
        int mid = left + (right - left) / 2;
        if (a[mid] < key) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }

    if (left < n && a[left] == key) {
        return left;
    }
    return -1;
}

这个版本先找第一个“不小于 key”的位置，再确认是否相等；有重复元素时会返回第一次出现的位置。

二分每轮把候选区间缩小一半，时间复杂度 O(log⁡n)O(\log n)。但“先排序一次再查一次”不一定比直接线性查找更快；它适合数据本来有序，或同一批数据要查询很多次。

课件还用二分思想求单调函数零点。二分的核心是单调判定能排除一半答案，并不局限于数组。

7. 字符数组与字符串

char s1[] = "123";
char s2[4] = {'1', '2', '3', '\0'};

两者都是合法字符串。下面这个数组没有结尾的 \0，不能交给 %s、strlen、puts 等字符串函数：

char not_string[3] = {'1', '2', '3'};

7.1 初始化差异

  • 静态存储期数组未显式初始化时，元素为 0；
  • 自动局部数组未初始化时，元素值不确定；
  • char s[64] = "" 会把全部元素初始化为 0；
  • 字符串容量必须包含末尾 \0。

7.2 读一个单词和读一整行

char word[100];
scanf("%99s", word); /* 遇到空白停止，限制最多读 99 个字符 */
char line[100];
if (fgets(line, sizeof line, stdin) != NULL) {
    line[strcspn(line, "\n")] = '\0';
}

fgets 最多读容量减一的字符并补 \0，若读到换行通常会保留。课件还介绍了 gets，并专门展示了其越界攻击风险；gets 无法限制长度，已从现代 C 标准删除，不能使用。

puts(s) 会自动追加换行；fputs(s, stdout) 不会。

8. 常用字符串函数

需要 <string.h>：

函数作用必须自己保证
strlen(s)可见字符长度s 以 \0 结束
strcmp(a,b)字典序比较两者都是字符串
strcpy(dst,src)复制字符串dst 容量足够
strcat(dst,src)追加字符串容量足够且 dst 已结束
strchr(s,c)首次查找字符s 合法
strrchr(s,c)最后查找字符s 合法
strstr(s,t)首次查找子串两者合法

strcmp 返回负数、0、正数，不保证恰好返回 -1、0、1：

if (strcmp(a, b) < 0) {
    /* a 的字典序在 b 前 */
}

strncpy 和 strncat 并非自动安全：strncpy 在源过长时可能不补 \0，参数语义也与目标总容量不同。任何复制都要先算清目标剩余空间。

9. 字符串与格式转换

snprintf 把格式化结果写进字符数组，并带容量限制：

char out[64];
snprintf(out, sizeof out, "%.*f", digits, value);

课件的 sprintf 不知道目标容量，能用 snprintf 时更安全。

sscanf 从已有字符串按格式解析：

int year, month, day;
if (sscanf(text, "%d-%d-%d", &year, &month, &day) == 3) {
    /* 解析成功 */
}

它适合拆固定格式的日期时间，但仍要检查返回值和数值范围。

10. 二维数组

int matrix[3][4] = {
    {1, 2, 3, 4},
    {5, 6, 7, 8},
    {9, 10, 11, 12}
};

可以把它看成“长度为 3 的数组，每个元素又是长度为 4 的 int 数组”。C 按行优先连续存储：

matrix[0][0], matrix[0][1], ... matrix[0][3],
matrix[1][0], matrix[1][1], ...

元素 [i][j] 相对首元素的线性偏移为：

i×列数+j.i\times\text{列数}+j.

因此传入二维数组时，函数必须知道每行列数：

void print_matrix(int rows, int a[][4])
{
    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < 4; ++j) {
            printf("%d%c", a[i][j], j == 3 ? '\n' : ' ');
        }
    }
}

第一维可以省略，因为函数只需首行地址和行数；第二维决定 a + 1 应跨过多少字节，不能省略。

二维字符数组可以保存多个定长字符串：

char names[100][32]; /* 最多 100 个名字，每个最多 31 个字符 */

课件以星期计算、最长行和成绩表为例，分别展示了二维数组怎样表示查表、多个字符串和“学生 × 课程”的表格。

11. 更高维数组与简单数据结构

三维及更高维数组仍是连续的一维内存，只是下标映射多了一层；最右下标变化最快。

课件把队列、栈和散列表列为数组的自学应用：

  • 栈：后进先出，用数组加栈顶下标；
  • 队列：先进先出，用头尾下标，循环队列可复用前端空间；
  • 散列表：通过哈希函数把关键字映射到数组位置，还要处理冲突。

这些结构的共同底座都是：数组负责存储，额外的下标和规则定义“哪些位置当前有效”。

12. 数组题的检查顺序

  1. 容量能装下最大输入和必要的 \0 吗？
  2. 当前有效长度是多少？
  3. 每个循环的访问区间是什么？
  4. 是否在读取未初始化元素？
  5. 传给函数时长度是否一起传了？
  6. 排序比较规则与后续查找规则一致吗？
  7. 二维数组的行列是否写反？

把“容量、有效长度、合法下标”三件事始终分开，数组和字符串的大多数错误都会在写代码前被挡住。

评论