竞极 Ace

5 一维数组精讲

正在加载视频播放器…

GESP C++ 三级：一维数组精讲

核心目标：掌握一维数组的定义、初始化、访问与遍历，能熟练进行求最值、求和、计数、查找、逆序等操作，理解数组越界与变长数组的限制，能结合枚举法和模拟法解决综合问题。
数组是一排连续的同类型存储单元，下标从0开始，长度必须是编译期常量；累加初值为0，累乘初值为1，最值初值取第一个元素。

一、数组的基本概念

1. 什么是数组

数组是存储固定大小、相同数据类型元素的集合，这些元素在内存中是连续存放的。

可以把数组想象成一排储物柜：每个柜子有唯一编号（下标），从0开始计数，通过编号存取数据。

2. 数组的核心特性

特性 说明
相同类型 所有元素类型必须一致
连续存储 元素在内存中地址连续，按元素大小递增
下标从0开始 长度为 n 的数组，有效下标是 0 ~ n-1
长度固定 静态数组长度必须是编译期常量

3. 考纲限制：不包括变长数组

新版GESP考纲明确：三级“C++一维数组基本应用”剔除变长数组考查。即数组长度必须是编译期常量，不能是变量。

int arr[5];          // ✅ 正确，5是常量
const int N = 10;
int arr2[N];         // ✅ 正确，N是const常量
int n = 10;
int arr3[n];         // ❌ 错误，n是变量

二、数组的定义与初始化

1. 基本语法

数据类型 数组名[长度];

int scores[5];        // 长度为5的整型数组
double prices[10];    // 长度为10的浮点型数组
char letters[26];     // 长度为26的字符数组

2. 初始化的四种方式

方式一：完全列表初始化

int arr[5] = {10, 20, 30, 40, 50};

方式二：部分初始化，其余自动补0

int arr[5] = {1, 2};   // arr = {1, 2, 0, 0, 0}

方式三：自动推导长度

int arr[] = {1, 2, 3, 4};   // 长度自动确定为4

方式四：全部初始化为0（最常用）

int arr[100] = {0};   // 100个元素全部为0

考试提示：int arr[100] = {0}; 是大数组清零的经典写法，务必记住。

3. 数组占用的字节数

int arr[5];   // 5 × 4 = 20 字节
long long arr2[3];  // 3 × 8 = 24 字节
char arr3[10];      // 10 × 1 = 10 字节

三、数组元素的访问与遍历

1. 访问单个元素

int arr[5] = {10, 20, 30, 40, 50};
cout << arr[0];   // 10
cout << arr[4];   // 50
arr[2] = 99;      // 修改第三个元素

2. 标准遍历

for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
}

关键：循环条件必须用 i < n，不能用 i <= n，否则会访问越界位置。

3. 逆序遍历

for (int i = n - 1; i >= 0; i--) {
    cout << arr[i] << " ";
}

4. 范围 for 循环（C++11，了解）

for (int x : arr) {
    cout << x << " ";
}

一级/二级不要求，三级了解即可。

5. 读入数组

int n;
cin >> n;
int arr[100];
for (int i = 0; i < n; i++) {
    cin >> arr[i];
}

四、数组与循环结合的常见操作

1. 求和

int sum = 0;
for (int i = 0; i < n; i++) {
    sum += arr[i];
}

2. 求最大值与最小值

int maxv = arr[0];   // 初值取第一个元素
for (int i = 1; i < n; i++) {
    if (arr[i] > maxv) maxv = arr[i];
}

int minv = arr[0];
for (int i = 1; i < n; i++) {
    if (arr[i] < minv) minv = arr[i];
}

3. 计数（统计满足条件的元素个数）

int cnt = 0;
for (int i = 0; i < n; i++) {
    if (arr[i] % 2 == 0) cnt++;   // 统计偶数个数
}

4. 查找

查找第一个出现的位置：

int pos = -1;
for (int i = 0; i < n; i++) {
    if (arr[i] == target) {
        pos = i;
        break;
    }
}

查找最后一次出现的位置：

int pos = -1;
for (int i = 0; i < n; i++) {
    if (arr[i] == target) pos = i;   // 不break，继续找
}

5. 逆序

for (int i = 0, j = n - 1; i < j; i++, j--) {
    int t = arr[i];
    arr[i] = arr[j];
    arr[j] = t;
}

6. 频次统计（桶数组）

当元素范围有限且连续时，可以用数组作“桶”统计频次。

const int M = 101;     // 元素范围 0~100
int bucket[M] = {0};

for (int i = 0; i < n; i++) {
    bucket[arr[i]]++;   // 统计每个值出现的次数
}

// 输出每个值出现的次数
for (int v = 0; v <= 100; v++) {
    if (bucket[v] > 0) {
        cout << v << "出现了" << bucket[v] << "次" << endl;
    }
}

7. 数组元素的筛选与标记

// 将不能被2整除也不能被3整除的元素置为0
for (int i = 0; i < n; i++) {
    if (arr[i] % 2 != 0 && arr[i] % 3 != 0) {
        arr[i] = 0;
    }
}

五、数组与枚举法、模拟法结合

1. 枚举法：遍历数组找满足条件的元素

// 输出数组中所有大于平均值的元素
int sum = 0;
for (int i = 0; i < n; i++) sum += arr[i];
double avg = 1.0 * sum / n;

for (int i = 0; i < n; i++) {
    if (arr[i] > avg) {
        cout << arr[i] << " ";
    }
}

2. 模拟法：数组清零 [GESP202509 三级] 数组清零

题目描述：给定n个非负整数数组，每次操作找到最大元素（多个取下标最大的），再找到最小非零元素，将最大值减去最小值，重复直到数组全为0，求操作次数。

解题思路：直接模拟每一步，忠实复现规则。

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int a[105];
    for (int i = 0; i < n; i++) cin >> a[i];

    int ops = 0;
    while (true) {
        // 检查是否全部为0
        bool allZero = true;
        for (int i = 0; i < n; i++) {
            if (a[i] != 0) { allZero = false; break; }
        }
        if (allZero) break;

        // 找最大元素（多个取下标最大的）
        int maxIdx = -1;
        for (int i = 0; i < n; i++) {
            if (a[i] > 0) {
                if (maxIdx == -1 || a[i] >= a[maxIdx]) {
                    maxIdx = i;   // 注意用 >= 取下标最大的
                }
            }
        }

        // 找最小非零元素
        int minVal = 1000000000;
        for (int i = 0; i < n; i++) {
            if (a[i] > 0 && a[i] < minVal) {
                minVal = a[i];
            }
        }

        // 最大值减去最小值
        a[maxIdx] -= minVal;
        ops++;
    }

    cout << ops << endl;
    return 0;
}

模拟法要点：每一步都要忠实复现规则——“找最大（多个取下标最大的）”“找最小非零”“相减”三步不能少、顺序不能乱。

3. 综合应用：[GESP202512 三级] 小杨的智慧购物

题目要求：从大量商品信息中筛选出每种文具的最低价格，计算购买所有M种文具的总花费。

思路：用数组存储每种文具的最低价格，遍历所有商品，更新最低价，最后求和。

// 伪代码思路
int minPrice[1005];   // 每种文具的最低价格
// 初始化为一个大数
for (int i = 1; i <= M; i++) minPrice[i] = 1000000000;

// 遍历商品，更新最低价
for (int i = 0; i < N; i++) {
    int type, price;
    cin >> type >> price;
    if (price < minPrice[type]) {
        minPrice[type] = price;
    }
}

// 求和
int total = 0;
for (int i = 1; i <= M; i++) {
    total += minPrice[i];
}
cout << total << endl;

六、数组排序与查找（了解）

三级考纲涉及排序和查找的基本概念，但一维数组模块中主要考查线性查找。

1. 线性查找

int find(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target) return i;
    }
    return -1;
}

2. 冒泡排序（了解）

for (int i = 0; i < n - 1; i++) {
    for (int j = 0; j < n - 1 - i; j++) {
        if (arr[j] > arr[j + 1]) {
            int t = arr[j];
            arr[j] = arr[j + 1];
            arr[j + 1] = t;
        }
    }
}

3. 二分查找（了解）

前提：数组必须已排序。

int binarySearch(int arr[], int n, int target) {
    int low = 0, high = n - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) low = mid + 1;
        else high = mid - 1;
    }
    return -1;
}

七、易错点汇总

1. 数组越界（最高频错误）

长度为 n 的数组，有效下标是 0 ~ n-1。访问 arr[n] 或负下标都是越界访问，会导致未定义行为（可能崩溃、数据错乱，也可能表面正常）。

int arr[5];
for (int i = 0; i <= 5; i++) {   // ❌ i=5时越界
    arr[i] = 0;
}
for (int i = 0; i < 5; i++) {    // ✅ 正确
    arr[i] = 0;
}

注意：数组越界不会产生编译错误，编译器看不出来，程序可能正常结束，也可能崩溃。

2. 数组长度必须是常量

int n = 10;
int arr[n];    // ❌ 标准C++不允许（变长数组）
int arr[10];   // ✅ 正确
const int N = 10;
int arr[N];    // ✅ 正确

3. 累加/累乘变量初始化错误

  • 求和：sum 初始化为 0。
  • 求积：prod 初始化为 1。
  • 初始值错误会导致整个运算结果全错。
int sum = 0;        // ✅
int prod = 1;       // ✅
int sum2;           // ❌ 未初始化，结果不确定

4. 最值变量初始化错误

int maxv = arr[0];       // ✅ 取第一个元素
int maxv = 0;            // ❌ 如果数组全是负数，结果错误
int maxv = -1000000000;  // ✅ 也可以取足够小的数

5. 查找时忘记保存结果

// 查找最后一次出现的位置
int pos = -1;
for (int i = 0; i < n; i++) {
    if (arr[i] == target) pos = i;   // ✅ 不break，持续更新
}

6. 数组清零时忘记全部置0

int arr[5] = {0};      // ✅ 全部为0
int arr[5];            // ❌ 未初始化，值是随机的

7. 循环边界错误

for (int i = 0; i < n; i++)    // ✅
for (int i = 0; i <= n; i++)   // ❌ 越界
for (int i = 1; i <= n; i++)   // ⚠️ 如果数组从0开始存储，会漏掉arr[0]

8. 数组大小不够

int n;
cin >> n;           // 如果 n 可能达到 1000
int arr[100];       // ❌ 数组太小
int arr[1005];      // ✅ 留足余量

9. 浮点数比较

if (arr[i] == 3.14)    // ❌ 可能不成立
if (fabs(arr[i] - 3.14) < 1e-6)  // ✅ 了解即可

10. 输出格式错误

注意空格和换行，严格按题目要求输出。GESP评测系统要求输出与标准答案完全一致。

八、阅读程序写结果

题目 1

int arr[5] = {1, 2, 3, 4, 5};
int sum = 0;
for (int i = 0; i < 5; i += 2) {
    sum += arr[i];
}
cout << sum << endl;

输出：

9

解释：arr[0]+arr[2]+arr[4] = 1+3+5 = 9。

题目 2

int arr[6] = {1, 2, 3, 4, 5, 6};
for (int i = 0; i < 6; i += 2) {
    int t = arr[i];
    arr[i] = arr[i+1];
    arr[i+1] = t;
}
for (int i = 0; i < 6; i++) cout << arr[i] << " ";

输出：

2 1 4 3 6 5

解释：交换相邻两个元素。

题目 3

int arr[5] = {3, 1, 4, 1, 5};
int cnt = 0;
for (int i = 0; i < 5; i++) {
    if (arr[i] > 2) cnt++;
}
cout << cnt << endl;

输出：

3

解释：大于2的元素有3、4、5，共3个。

题目 4

int arr[5] = {5, 3, 8, 1, 9};
int maxv = arr[0];
for (int i = 1; i < 5; i++) {
    if (arr[i] > maxv) maxv = arr[i];
}
cout << maxv << endl;

输出：

9

题目 5

int arr[6] = {1, 2, 3, 4, 5, 6};
for (int i = 0, j = 5; i < j; i++, j--) {
    int t = arr[i];
    arr[i] = arr[j];
    arr[j] = t;
}
for (int i = 0; i < 6; i++) cout << arr[i] << " ";

输出：

6 5 4 3 2 1

九、速查表

需求 写法
定义数组 int arr[10];
全部初始化为0 int arr[10] = {0};
访问元素 arr[i]
遍历 for (int i = 0; i < n; i++)
逆序遍历 for (int i = n-1; i >= 0; i--)
求和 sum = 0; for (...) sum += arr[i];
求最大值 maxv = arr[0]; for (...) if (arr[i] > maxv) maxv = arr[i];
求最小值 minv = arr[0]; for (...) if (arr[i] < minv) minv = arr[i];
计数 cnt = 0; for (...) if (条件) cnt++;
查找 for (...) if (arr[i] == target) { pos = i; break; }
逆序 for (i=0,j=n-1; i<j; i++,j--) swap(arr[i], arr[j]);
桶统计 int bucket[M] = {0}; for (...) bucket[arr[i]]++;
冒泡排序 双重循环，相邻比较交换
二分查找 low=0, high=n-1; while (low <= high)

十、总结

一维数组是GESP三级从基础语法迈向算法应用的关键知识点。

  1. 数组是连续存储的同类型元素集合，下标从0开始。
  2. 数组长度必须是编译期常量，三级不考变长数组。
  3. 遍历用 for (i=0; i<n; i++)，边界用 < 不用 <=。
  4. 数组越界不会产生编译错误，但会导致未定义行为。
  5. 求和初值为0，求积初值为1，最值初值取第一个元素。
  6. 查找第一个出现的位置用 break，查找最后出现的位置不用 break。
  7. 桶数组适合范围有限的频次统计。
  8. 模拟法的关键是忠实复现规则，每一步都不能少、不能乱。
  9. 数组大小要留足余量，防止越界。
  10. 输出格式严格按题目要求，不多空格、不多换行。

复习建议：先把数组的定义、初始化、遍历、求和、求最值、计数六个基础模板写熟，重点体会模拟法和枚举法在数组中的应用。考试中先确定数组长度和存储方式，再写遍历循环，最后检查边界和输出格式。