跳转至

9. 数组与字符串

9.1 一维数组

数组把一批同类型元素连续放在内存中，下标从 0 开始：

int a[5] = {1, 2, 3};        /* 其余元素初始化为 0 */
int b[] = {1, 2, 3, 4};      /* 编译器推断长度为 4 */
int n = sizeof b / sizeof b[0];

按本课程使用的编译环境，定义数组时长度要写整型常量表达式，可以用符号常量，不能临时输入一个变量再写 int a[n]。

长度为 n 的数组，合法下标只有 0 到 n - 1。C 不替我们查越界，写到 a[n] 已经出了数组。数组定义好后也不能整体赋值，比较内容时要逐个元素比。

9.2 二维数组

int matrix[2][3] = {
    {1, 2, 3},
    {4, 5, 6}
};

二维数组按行存放：第一行放完，紧接着才是第二行。matrix[i][j] 等价于 *(*(matrix + i) + j)。作为函数参数时第一维可以不写，但列数不能省，因为编译器要靠列数算“跨过一行”究竟跨多少元素：

void print_matrix(int a[][3], int rows);
/* 等价参数形式：void print_matrix(int (*a)[3], int rows); */

9.3 数组作为函数参数

数组传进函数后只剩首元素地址，长度信息不会跟着过去，所以数组长度要另外传。形参虽然写成 int a[]，到函数里实际按 int *a 处理；此时 sizeof a 得到的是指针大小，不是原数组大小。

若函数只读取数组，可写：

double average(const double a[], size_t n);

只读数组参数加上 const，一眼就能看出这个函数不会改数组内容。

9.4 字符数组与字符串

C 字符串没有单独的字符串类型，就是一串以 \0 结尾的字符。有没有这个结尾，决定了它能不能安全地交给 strlen、printf("%s") 等字符串函数：

char s1[] = "hello";         /* 可修改数组，大小为 6 */
const char *s2 = "hello";    /* 指向字符串字面量，不应修改 */
char s3[5] = {'h', 'e', 'l', 'l', 'o'}; /* 没有 \0，不是 C 字符串 */

常用 <string.h> 函数：

函数 作用 注意
strlen(s) 返回 \0 前的字符数 不含 \0
strcpy(dst, src) 复制字符串 目标空间必须足够
strcat(dst, src) 追加字符串 目标空间必须足够
strcmp(a, b) 按字典序比较 返回负、0、正，不保证是 -1/0/1
strchr(s, c) 查找字符 返回指针或 NULL
strstr(s, sub) 查找子串 返回首次出现位置或 NULL

scanf("%s", s) 一遇到空格就停，只适合读一个单词。要读整行用 fgets。旧代码里的 gets 没法限制长度，很容易越界，不要再用。

9.5 查找与排序

顺序查找就是从头比到尾，一般数组都能用。二分查找快得多，但前提是数组已经有序。每一轮看中点：相等就结束，目标更大就丢掉左半边，否则丢掉右半边。

int binary_search(const int a[], int n, int key)
{
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (a[mid] == key) return mid;
        if (a[mid] < key) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

三种基础排序不要只背名字，要记住每一轮结束后“哪一部分已经有序”：

  • 冒泡排序：相邻元素逆序就交换，一轮结束后最大值到了最右边；
  • 选择排序：从未排序区找最小值，放到这一段最前面；
  • 插入排序：左边始终有序，把当前元素向左插到合适位置。

三者平均时间复杂度都是 \(O(n^2)\)。读排序程序时先判断它维护的是哪一种“有序区”，内外层边界就容易看懂了。

课件里的其他数组题也可以按“下标代表什么”来整理：有序表插入、删除时要先给元素腾位置或补空位；用数组做超长整数时，每个元素存一位或一段数字；数值与下标映射时，先找出两者的换算关系。递归找最大值和递归排序，则是把数组前 \(n\) 项的问题缩成前 \(n-1\) 项。

评论