第2章：数组与字符串（Arrays and Strings）

一、导读

2.1 本章学习目标

第2章将我们带入数据组织的世界。如果说第1章让我们学会了用变量存储单个数据，那么本章则要解决一个更实际的问题：如何高效地组织和处理一批数据。数组和字符串是编程中最基本、最常用的数据组织形式，也是后续学习一切高级数据结构的起点。

本章的核心学习目标包括：

深入理解一维数组：掌握声明、初始化、遍历和常见操作模式，理解数组在内存中的连续存储特性。
掌握二维数组的使用：能够用二维数组表示矩阵和网格，理解行优先存储和嵌套遍历。
精通字符串处理：理解 C 风格字符串以 \0 结尾的约定，熟练使用 strlen、strcpy、strcmp 等标准库函数。
掌握字符分类与转换：使用 isalpha、isdigit、toupper、tolower 等函数处理字符数据。
学会字符串与数字的转换：掌握 atoi、sprintf/sscanf 等实用技巧。
建立缓冲区安全意识：理解缓冲区溢出的危害，养成安全编程的习惯。

2.2 为什么本章如此重要

数组和字符串在算法竞赛中的出现频率几乎是最高的。无论是动态规划中的状态表、图论中的邻接矩阵、还是字符串匹配中的文本处理，数组都是最底层的数据载体。可以说，不理解数组，就无法写出任何有意义的算法。

字符串处理更是竞赛中的常客。从简单的回文判断到复杂的模式匹配，从字符串哈希到字典树，这些高级算法都建立在对字符数组的基本操作之上。本章培养的字符串处理能力，将在第8章（字符串算法）中得到充分的发挥。

另一个重要原因是，数组是理解"内存"这个概念的窗口。当你在代码中写下 int a[100] 时，计算机会在内存中分配 400 个连续字节。理解这种连续存储的特性，对于后续学习指针、链表、哈希表等数据结构至关重要。

2.3 核心问题引导

在阅读本章时，请带着以下问题思考：

数组在内存中是如何存储的？为什么数组下标从 0 开始？

二维数组的"行优先"存储是什么意思？对遍历顺序有什么影响？

字符串为什么需要 \0 结尾？如果不以 \0 结尾会发生什么？

strlen(s) 和 sizeof(s) 的区别是什么？为什么它们经常给出不同的结果？

如何安全地读入一行包含空格的字符串？gets 为什么被废弃？

什么是缓冲区溢出？为什么它是程序安全中的头号敌人？

二、核心概念详解

2.1 一维数组

2.1.1 声明与初始化

数组是相同类型元素的有序集合。在 C 语言中，数组在内存中占据一段连续的空间：

int a[5];                    // 声明：5 个 int，未初始化（值不确定）
int b[5] = {1, 2, 3, 4, 5}; // 声明并初始化
int c[5] = {1, 2};           // 部分初始化：c = {1, 2, 0, 0, 0}
int d[5] = {0};              // 全部初始化为 0
int e[] = {1, 2, 3, 4, 5};  // 自动推断大小：e 的大小为 5

为什么下标从 0 开始？ 这与内存寻址方式有关。数组名 a 本质上是首元素的地址，a[i] 等价于 *(a + i)。当 i = 0 时，a[0] 就是 *(a + 0)，即首元素本身。如果下标从 1 开始，每次访问都需要多减 1，这是不必要的开销。

2.1.2 遍历与常见操作

int a[100], n;
scanf("%d", &n);

// 读入
for (int i = 0; i < n; i++)
    scanf("%d", &a[i]);

// 求最大值
int max_val = a[0];
for (int i = 1; i < n; i++)
    if (a[i] > max_val) max_val = a[i];

// 求和
long long sum = 0;
for (int i = 0; i < n; i++)
    sum += a[i];

// 查找元素
int target, pos = -1;
scanf("%d", &target);
for (int i = 0; i < n; i++) {
    if (a[i] == target) {
        pos = i;
        break;
    }
}

2.1.3 前缀和与差分

前缀和是竞赛中非常重要的技巧，它可以将"区间求和"从 O(n) 优化到 O(1)：

int a[100005];
long long prefix[100005];  // 前缀和数组

// 构建前缀和
prefix[0] = 0;
for (int i = 1; i <= n; i++)
    prefix[i] = prefix[i - 1] + a[i];

// 查询区间 [l, r] 的和
long long range_sum = prefix[r] - prefix[l - 1];  // O(1)

2.2 二维数组

2.2.1 矩阵表示

二维数组可以自然地表示矩阵和网格：

int matrix[100][100];
int n, m;
scanf("%d%d", &n, &m);

// 读入 n×m 的矩阵
for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
        scanf("%d", &matrix[i][j]);

2.2.2 行优先存储

C 语言中，二维数组按行优先（row-major）顺序存储。matrix[100][100] 在内存中的排列是：

matrix[0][0], matrix[0][1], ..., matrix[0][99],
matrix[1][0], matrix[1][1], ..., matrix[1][99],
...
matrix[99][0], matrix[99][1], ..., matrix[99][99]

这意味着按行遍历比按列遍历对缓存更友好，性能可能相差数倍：

// 好的写法：按行遍历（缓存友好）
for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
        sum += matrix[i][j];

// 差的写法：按列遍历（缓存不友好）
for (int j = 0; j < m; j++)
    for (int i = 0; i < n; i++)
        sum += matrix[i][j];

2.2.3 矩阵转置

int a[100][100], b[100][100];
int n;
scanf("%d", &n);

for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
        scanf("%d", &a[i][j]);

// 转置
for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
        b[j][i] = a[i][j];

2.3 字符串

2.3.1 C 风格字符串

C 语言中的字符串是一个以 \0（空字符，ASCII 值为 0）结尾的字符数组。这个 \0 是字符串结束的标志，所有字符串处理函数都依赖它来确定字符串的长度：

char s[] = "hello";
// 内存中：h e l l o \0
// 下标：  0 1 2 3 4  5
// 数组大小为 6，不是 5！

关键区别：strlen(s) 返回字符串的逻辑长度（不包括 \0），而 sizeof(s) 返回数组占用的字节数（包括 \0）：

char s[] = "hello";
printf("%d\n", (int)strlen(s));   // 5
printf("%d\n", (int)sizeof(s));   // 6

2.3.2 字符串处理函数

C 标准库 <cstring>（或 <string.h>）提供了丰富的字符串操作函数：

#include <cstring>

char s1[100] = "hello";
char s2[100] = "world";

int len = strlen(s1);          // 5：字符串长度
strcpy(s1, s2);                // s1 = "world"：复制
strcat(s1, s2);                // s1 = "worldworld"：拼接
int cmp = strcmp(s1, s2);      // 字典序比较：<0 表示 s1<s2，0 表示相等，>0 表示 s1>s2
char *p = strchr(s1, 'o');     // 查找字符 'o' 第一次出现的位置
char *q = strstr(s1, "or");    // 查找子串 "or" 第一次出现的位置

常见错误：strcpy 和 strcat 不检查目标数组的大小，如果源字符串太长，会导致缓冲区溢出。竞赛中要确保数组开得足够大。

2.3.3 字符串的读入

char s[1000];

// 方式一：读入不含空格的单词
scanf("%s", s);

// 方式二：读入包含空格的整行
// gets(s);           // 已被废弃，不安全！
fgets(s, sizeof(s), stdin);  // 安全，但会保留末尾的换行符

// 方式三：C++ 的 getline（需要 <string> 和 <iostream>）
// string s;
// getline(cin, s);

2.3.4 字符分类与转换

<cctype> 头文件提供了一系列字符处理函数：

#include <cctype>

char c = 'A';
isalpha(c);   // 是否字母：true
isdigit(c);   // 是否数字：false
isalnum(c);   // 是否字母或数字：true
isupper(c);   // 是否大写：true
islower(c);   // 是否小写：false
isspace(c);   // 是否空白字符：false
toupper(c);   // 转大写：'A'
tolower(c);   // 转小写：'a'

2.4 字符串与数字的转换

2.4.1 atoi 系列

#include <cstdlib>

int n = atoi("123");        // 字符串转 int：123
long long ll = atoll("1234567890123");  // 字符串转 long long
double d = atof("3.14");    // 字符串转 double

2.4.2 sprintf 和 sscanf

sprintf/sscanf 是更灵活的转换工具，本质上是把字符串当作"文件"进行格式化读写：

char buf[100];

// 数字转字符串
sprintf(buf, "%d", 12345);       // buf = "12345"
sprintf(buf, "%05d", 42);        // buf = "00042"（补零到5位）
sprintf(buf, "%.2f", 3.14159);   // buf = "3.14"

// 字符串转数字
int n;
sscanf("12345", "%d", &n);       // n = 12345

// 混合解析
int year, month, day;
sscanf("2024-01-15", "%d-%d-%d", &year, &month, &day);
// year=2024, month=1, day=15

三、实战案例

3.1 案例一：字符串反转

问题描述：输入一个字符串，输出它的反转。

#include <cstdio>
#include <cstring>

void reverse(char *s) {
    int len = strlen(s);
    for (int i = 0; i < len / 2; i++) {
        char tmp = s[i];
        s[i] = s[len - 1 - i];
        s[len - 1 - i] = tmp;
    }
}

int main() {
    char s[1005];
    scanf("%s", s);
    reverse(s);
    printf("%s\n", s);
    return 0;
}

解析：反转字符串的经典方法是"双指针交换"——左指针从头部开始，右指针从尾部开始，向中间靠拢，沿途交换对应位置的字符。只需交换 len/2 次。

3.2 案例二：字符频率统计

问题描述：输入一个字符串，统计每个小写字母出现的次数，按字母序输出出现过的字母及其频率。

#include <cstdio>
#include <cstring>

int main() {
    char s[1005];
    scanf("%s", s);
    int cnt[26] = {0};
    
    for (int i = 0; s[i]; i++) {
        if (s[i] >= 'a' && s[i] <= 'z')
            cnt[s[i] - 'a']++;
    }
    
    for (int i = 0; i < 26; i++) {
        if (cnt[i] > 0)
            printf("%c: %d\n", 'a' + i, cnt[i]);
    }
    return 0;
}

解析：利用数组做"桶计数"是竞赛中的常用技巧。s[i] - 'a' 将字符映射为 0~25 的下标，'a' + i 则是反向映射。注意循环条件 s[i] 等价于 s[i] != '\0'，这是遍历 C 字符串的惯用写法。

3.3 案例三：TeX 括号问题

问题描述：在 TeX 中，左双引号是 ` ，右双引号是 ''。输入一段包含直引号 "` 的文本，将交替出现的直引号替换为 TeX 格式的双引号。

#include <cstdio>
#include <cctype>

int main() {
    int c;
    int left = 1;  // 下一个 " 应该是左引号
    while ((c = getchar()) != EOF) {
        if (c == '"') {
            if (left) printf("``");
            else printf("''");
            left = !left;
        } else {
            putchar(c);
        }
    }
    return 0;
}

解析：这个题目看似简单，但考察了字符级处理的多个要点：getchar() 逐字符读入、状态变量 left 的交替切换、以及 EOF 的处理。注意 getchar() 的返回值是 int 而不是 char，因为 EOF 的值是 -1，无法用 char 表示。

四、本章小结

本章深入讲解了数组和字符串这两个最基本的数据结构：

一维数组是最基本的数据容器，前缀和技巧可以将区间求和优化到 O(1)。

二维数组按行优先存储，按行遍历对缓存更友好。它可以表示矩阵和网格。

C 字符串以 \0 结尾，strlen 和 sizeof 的含义不同。

字符串处理函数（strcpy、strcmp、strcat 等）是处理文本的基础工具。

字符分类函数（isalpha、isdigit 等）简化了字符判断逻辑。

字符串与数字的转换可以通过 sprintf/sscanf 灵活实现。

数组和字符串是算法竞赛的"地基"。无论是排序、搜索、动态规划还是字符串算法，都离不开对数组的熟练操作。在后续章节中，我们会反复用到本章学到的技巧。

五、思考与练习

思考题

如果声明 int a[100] 作为局部变量和全局变量，它们的初始值有什么不同？为什么？

char s[10] = "hello" 中，s[5] 到 s[9] 的值分别是什么？

为什么 strcmp("abc", "abd") 返回负数？字符串比较的规则是什么？

sprintf 和 printf 的区别是什么？它们的返回值分别表示什么？

编程练习

回文判断：输入一个字符串，判断它是否是回文串（正读和反读相同）。

周期串：如果一个字符串可以由某个长度为 k 的前缀重复拼接而成，称 k 为该串的一个周期。求一个字符串的最小周期。

矩阵乘法：输入两个 n×m 和 m×p 的矩阵，输出它们的乘积。

凯撒密码：输入一段文本和偏移量 k，将每个字母向后移动 k 位（z 之后回到 a）。