03 数组与字符串

GESP 3-4 级CSP-J 基础

级别标注：GESP 3 级（一维数组、字符串、进制转换）/ 4 级（二维数组）（考级要求）/ CSP-J 必备基础（竞赛进阶）。

一、一维数组

数组是连续内存中存储的同类型元素集合，下标从 0 开始。

C++ 实例

#include <iostream>
using namespace std;
int main() {
    int a[10];               // 声明 10 个 int，下标 0~9
    for (int i = 0; i < 10; i++) a[i] = i * i;   // 存平方
    for (int i = 0; i < 10; i++) cout << a[i] << " ";
    cout << endl;
    return 0;
}

数组初始化

C++ 实例

int b[5] = {1, 2, 3};        // 其余自动补 0 -> {1,2,3,0,0}
int c[] = {1, 2, 3, 4};      // 长度自动推断为 4
int d[100] = {};             // 全 0 初始化

循环读入与求和、求最大

C++ 实例

#include <iostream>
using namespace std;
int main() {
    int n; cin >> n;
    int arr[10005];
    int sum = 0, mx = -2000000000, mn = 2000000000;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        sum += arr[i];
        if (arr[i] > mx) mx = arr[i];
        if (arr[i] < mn) mn = arr[i];
    }
    cout << "sum=" << sum << " max=" << mx << " min=" << mn << endl;
    return 0;
}

形象理解数组像一排贴好编号的储物柜：编号从 0 开始，a[0] 是第 1 个柜子，a[n-1] 是最后一个。声明 int a[10] 只表示“有 10 个柜子”，不会自动清空——局部数组初始值是随机的，竞赛里必须先赋值或用 {} 初始化。

易错点数组下标越界不会报编译错，但可能悄悄改坏别的变量（覆盖相邻内存），OJ 上表现为“本地好好的、提交就 WA/RE”。写循环时统一用 i < n 而不是 i <= n，能避开 90% 的越界。

二、二维数组

C++ 实例

#include <iostream>
using namespace std;
int main() {
    int grid[105][105];
    int n, m; cin >> n >> m;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> grid[i][j];
    // 输出蛇形/螺旋等题目中常用到行列下标运算
    int cnt = 0;
    for (int d = 0; d < m; d++) cnt += grid[0][d];  // 第一行和
    cout << cnt << endl;
    return 0;
}

二维数组是 GESP 4 级考点（矩阵旋转、行列求和、最大子矩阵）。

形象理解二维数组像教室座位表：grid[i][j] 表示第 i 行第 j 列。外层循环走“行”，内层循环走“列”；旋转、翻转、蛇形填数等题，本质就是反复做“行列下标变换”。

考级视角GESP 4 级高频题型：矩阵转置、行列求和、对角线求和、局部最大子矩阵。做题前先在草稿上画 3×3 矩阵并标出行列下标，比直接写代码快得多。

三、字符数组（C 风格字符串）

C++ 实例

#include <iostream>
#include <cstring>
using namespace std;
int main() {
    char s[100];
    cin >> s;                       // 读入不含空格的字符串
    int len = strlen(s);            // 长度
    cout << s << " len=" << len << endl;
    // 逐个处理字符
    for (int i = 0; i < len; i++) {
        if (s[i] >= 'a' && s[i] <= 'z') s[i] = s[i] - 'a' + 'A'; // 转大写
    }
    cout << s << endl;
    return 0;
}

字符常用技巧： - 数字字符转数字：int d = ch - '0'; - 大写转小写：ch = ch - 'A' + 'a'; - 判断字母：isalpha(ch)；数字：isdigit(ch)（需 #include <cctype>）。例：if (isalpha(ch))。

易错点字符数组末尾必须留位置给 '\0'：char s[5] 最多只能存 4 个可见字符。用 strlen 前确保字符串已以 '\0' 结尾，否则会一直数到越界。

考级视角字符处理的三个高频换算要背熟：数字字符转数字 ch - '0'、大写转小写 ch - 'A' + 'a'、小写转大写 ch - 'a' + 'A'。GESP 3 级读程序题常考。

四、C++ 的 string 类型（重点，推荐）

C++ 实例

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main() {
    string s1, s2;
    cin >> s1 >> s2;            // 输入
    cout << "长度: " << s1.size() << " " << s1.length() << endl;

    string t = s1 + s2;         // 拼接
    cout << t << endl;

    cout << "第一个字符: " << s1[0] << endl;
    cout << "是否相等: " << (s1 == s2) << endl;

    // 求子串（从下标0开始取3个）
    string sub = s1.substr(0, 3);
    cout << "substr: " << sub << endl;

    // 查找
    size_t pos = s1.find("ab");
    if (pos != string::npos) cout << "找到,位置: " << pos << endl;
    else cout << "未找到" << endl;

    // 排序（注意：会改变原字符串）
    sort(s1.begin(), s1.end());
    cout << "排序后: " << s1 << endl;
    return 0;
}

字符串常用方法速查

方法	作用
`s.size()` / `s.length()`	长度
`s[i]`	下标访问（可读写）
`s.substr(pos, len)`	子串
`s.find(str)`	查找，返回下标或 `string::npos`
`s.insert(pos, str)`	插入
`s.erase(pos, len)`	删除
`s.append(str)` / `s += str`	追加
`getline(cin, s)`	读一整行（含空格）
`stoi(s)` / `stoll(s)`	字符串转 int / long long
`to_string(x)`	数字转字符串

形象理解string 像会自动伸缩的储物柜：不用管长度、不用管 '\0'，还能直接 + 拼接、== 比较、substr 裁剪。竞赛中能用 string 就别用字符数组，省心且不易错。

易错点s.find(str) 找不到时返回 string::npos（一个很大的数），不能直接当 -1 比较：要写 if (pos == string::npos)。另外 sort(s.begin(), s.end()) 会改变原字符串，想保留原串要先拷贝。

五、进制转换（GESP 3 级考点）

C++ 实例

#include <iostream>
using namespace std;

// 十进制转 2/8/16 进制（逆序输出即为结果）
string toBase(int n, int base) {
    string digits = "0123456789ABCDEF";
    string res;
    if (n == 0) return "0";
    while (n > 0) {
        res = digits[n % base] + res;   // 头插法
        n /= base;
    }
    return res;
}

int main() {
    cout << toBase(10, 2) << endl;   // 1010
    cout << toBase(255, 16) << endl; // FF
    return 0;
}

形象理解进制转换像换零钱：十进制转二进制，就是“把整钱不断换成 2 的零钱”——每次取余数（n % 2）记下来，再除以 2（n /= 2），余数逆序读就是结果。

考级视角GESP 3 级必考进制：10↔2、10↔8、10↔16、2↔16。牢记“2 进制每 4 位 = 16 进制 1 位”（如 1010 = A），可大幅提速。

六、易错点 / 常见坑点

⚠️ 数组越界：声明 int a[n]，下标必须是 0 ~ n-1，访问 a[n] 越界（C++ 不报错但结果未定义，OJ 上可能 WA 或 RE）。
⚠️ 数组长度必须为常量：int n; cin >> n; int a[n]; 在部分编译环境下非标准，建议 const int MAXN = 10005; int a[MAXN];。
⚠️ 字符数组 vs string：cin >> s 遇空格就停止；getline 慎与 cin >> 混用（残留换行符需先 cin.ignore()）。
⚠️ string::npos 是 size_t 最大值的常量，判断 find 失败需写 if (pos == string::npos)，不要与 -1 直接比较造成类型歧义。
⚠️ 'a' 与 "a" 区别：前者是 char（单字符），后者是字符串字面量。
⚠️ 二维数组行列下标方向搞反（先循环行还是先循环列）。
⚠️ 读入带空格的整行含前导空格时，getline 会先把上一行遗留的 \n 吃掉。

七、考级要求 vs 竞赛进阶

考级要求：一维数组、字符串与进制转换（GESP 3 级），二维数组（GESP 4 级）。
竞赛进阶（CSP-J）：string 熟练使用（KMP 前置）、std::sort 对数组/字符串排序、字符串题目的 O(n) 手工写法、大数据范围下的字符统计。

八、课内练习建议

数组去重：读入 n 个数，输出不重复的个数（可用标记数组）。
矩阵转置（n×m 翻转为 m×n）。
统计一段英文（含空格）中每个字母出现的次数。
判断字符串是否为回文串。
把一个十进制数转成任意 2~16 进制。