CC++ & Algorithm

数组的基本概念与操作

中等9
语言版本：通用
概述：数组就像一排带有编号的抽屉，可以快速存取数据，但队列固定，插入或删除较慢。

轻松掌握数组：你的第一个数据结构

数组就像一个带编号的储物柜，能快速存取物品，但柜子数量固定，要在中间加塞或拿走东西就得搬动后面的所有东西。在编程世界里，数组是最基础、最常用的数据结构，它把相同类型的数据（比如全班同学的考试成绩）整齐排列在一起，每个数据都有一个从0开始的编号（下标），你只要知道编号就能瞬间拿到对应数据。

生活中的数组——储物柜、班级座位、零食架

想象一下，学校体育馆有一排编号为0到49的储物柜（注意，编程里习惯从0开始编号）。你把自己的运动鞋放在3号柜里，水杯放在8号柜里。取鞋时，直接走到3号柜，掏出钥匙打开——不用翻遍所有柜子。即使有1000个柜子，只要知道编号，存取都一步到位。

再看教室里的座位：第一排从左到右有6个座位，编号0、1、2、3、4、5。小明坐在3号位，小红坐在5号位。老师要发作业本，只要根据座位号就能瞬间找到对应的同学。但如果突然插入一个新同学，让他坐在3号和4号之间，那就要把4号、5号的同学都往后挪一个位置，还得重新调整座位号，非常麻烦。

这些例子都体现了数组的两大特点：

  • 快速存取：通过下标（编号）直接拿到数据，速度不随数据量增大而变慢（O(1)）。
  • 固定大小，插入删除慢：一旦创建，柜子数量就不能变。想在中间插入一个数据，必须把后面的数据一个一个往后挪（O(n)）。

数组的核心原理——连续的内存格子

在计算机内存里，数组是一块 连续 的空间。比如你声明了一个存放5个整数的数组，每个整数占4个字节，那么这5个整数在内存里是紧挨着存放的。假设数组的起始地址是100，那么：

  • arr[0] 占地址 100~103
  • arr[1] 占地址 104~107
  • arr[2] 占地址 108~111
  • arr[3] 占地址 112~115
  • arr[4] 占地址 116~119

所以，要访问 arr[3]，计算机只需要计算：100 + 3 * 4 = 112，直接跳过去读数据，不需要像链表那样一个个找。这就是数组“随机访问”的秘诀——速度与数组长度无关（O(1)）。

不过，连续也带来一个麻烦：创建数组时就要告诉计算机“我要5个格子”，计算机在内存里找一块连续的空地给你。一旦用完，不能再往旁边加格子，因为旁边的内存可能已经被别人占用了。如果你想多存一个数，只能重新找一块更大的连续空地，把旧数据全部搬过去（这就是动态数组的原理）。

数组的基本操作——增删改查

数组的常见操作有：创建、访问、修改、遍历、查找、插入、删除。下面我们一个个来看，同时指出新手常犯的错误。

1. 创建数组

  • C++：必须指定大小（用常量或字面量），可以同时初始化。
  • Python：直接用列表（list），它虽然是动态数组，但我们可以先把它当作固定大小数组来学习。
// C++
const int SIZE = 5;
int scores[SIZE] = {85, 92, 78, 90, 88};  // 一个班级5个学生的成绩

# Python
scores = [85, 92, 78, 90, 88]

常见错误：忘记指定大小或大小写错。C++中数组大小必须是编译时确定的常量，不能用变量（除非用动态分配，但那是进阶内容）。

2. 访问和修改元素

通过 数组名[下标] 读写。下标从0开始，最大是长度减1。

// C++
cout << "第一个学生成绩：" << scores[0] << endl;  // 输出85
scores[0] = 100;  // 修改第一个成绩为100
cout << "修改后：" << scores[0] << endl;

# Python
print("第一个学生成绩：", scores[0])  # 输出85
scores[0] = 100
print("修改后：", scores[0])

常见错误：下标越界。比如数组长度是5，却访问 scores[5] 或 scores[-1]。C++中会读取内存垃圾数据（甚至崩溃）；Python中会报 IndexError。

3. 遍历数组

用循环依次访问每个元素。常用 for 循环。

// C++
cout << "全班成绩：";
for (int i = 0; i < 5; i++) {
    cout << scores[i] << " ";
}
cout << endl;

# Python
print("全班成绩：", end="")
for score in scores:  # 可以直接遍历元素
    print(score, end=" ")
print()

常见错误：循环条件写错，比如 i <= 5 导致越界；或者 Python 中同时需要下标时误用 for i in scores 而不知道索引。

4. 查找特定值

从第一个元素开始依次比较，直到找到目标值。这叫 顺序查找，最坏情况下要比较所有元素（O(n)）。

// C++
int target = 90;
int found_index = -1;  // 没找到就用-1表示
for (int i = 0; i < 5; i++) {
    if (scores[i] == target) {
        found_index = i;
        break;  // 找到立刻退出循环
    }
}
if (found_index != -1)
    cout << "分数" << target << "在第" << found_index << "个位置" << endl;
else
    cout << "没找到" << endl;

# Python
target = 90
if target in scores:  # 更Pythonic的写法
    idx = scores.index(target)
    print(f"分数{target}在第{idx}个位置")
else:
    print("没找到")

5. 插入元素（在指定位置）

插入前，必须确保数组有空间（因为长度固定）。实际操作中，我们会创建一个更大的临时数组，把原数组元素和新元素按顺序放进去。这个过程需要移动插入位置后面的所有元素。

生活例子：你有一个5格零食架，上面摆着薯片、饼干、巧克力、糖果、果冻。你想在饼干（位置1）和巧克力（位置2）之间插入一包瓜子，就必须把巧克力、糖果、果冻都往后挪一格，腾出第三个格子放瓜子。

// C++ 演示插入（模拟，原数组大小不变，我们用临时数组）
const int SIZE = 5;
int scores[SIZE] = {85, 92, 78, 90, 88};
int new_scores[SIZE+1];  // 扩大一格

int insert_pos = 2;  // 在下标2处插入（原来下标2是78）
int insert_val = 100;

// 分三段复制
for (int i = 0; i < SIZE+1; i++) {
    if (i < insert_pos)
        new_scores[i] = scores[i];
    else if (i == insert_pos)
        new_scores[i] = insert_val;
    else
        new_scores[i] = scores[i-1];  // 原数组元素后移一位
}
// 现在new_scores为 [85,92,100,78,90,88]

# Python 直接用列表内置方法
scores = [85, 92, 78, 90, 88]
scores.insert(2, 100)  # 在索引2插入100，自动后移
print(scores)  # [85, 92, 100, 78, 90, 88]

6. 删除元素（在指定位置）

删除后，后面的元素要往前移动填补空位，数组长度减1（同样需要新建数组）。

// C++ 演示删除
int del_pos = 2;  // 删除下标2的元素（原78）
int smaller_scores[SIZE-1];
for (int i = 0; i < SIZE; i++) {
    if (i < del_pos)
        smaller_scores[i] = scores[i];
    else if (i > del_pos)
        smaller_scores[i-1] = scores[i];
    // 跳过 i == del_pos 不复制
}
// smaller_scores 为 [85, 92, 90, 88]

# Python 直接用pop
scores = [85, 92, 78, 90, 88]
scores.pop(2)  # 删除下标2的元素，返回78
print(scores)  # [85, 92, 90, 88]

重要提示：插入和删除操作的时间都是 O(n)，因为需要移动最多 n 个元素。如果你程序里频繁执行这类操作，数组可能不是最好的选择——这时候就该考虑链表了。

完整可运行的代码示例

下面用 C++ 和 Python 分别写一个包含所有基础操作的完整程序。变量名用简短英文单词，每行都加了中文注释。

C++ 完整示例

#include <iostream>
using namespace std;

int main() {
    // 1. 创建：5个整数的数组，存储某次考试分数
    const int SIZE = 5;
    int scores[SIZE] = {85, 92, 78, 90, 88};  // 初始化

    // 2. 访问与修改
    cout << "原第1个分数: " << scores[0] << endl;  // 输出85
    scores[0] = 100;  // 把第一个改为100
    cout << "修改后第1个分数: " << scores[0] << endl;

    // 3. 遍历
    cout << "所有分数: ";
    for (int i = 0; i < SIZE; i++) {
        cout << scores[i] << " ";
    }
    cout << endl;

    // 4. 查找：找到分数90的下标
    int target = 90;
    int found_index = -1;  // -1表示没找到
    for (int i = 0; i < SIZE; i++) {
        if (scores[i] == target) {
            found_index = i;
            break;
        }
    }
    if (found_index != -1)
        cout << "分数" << target << "在下标" << found_index << endl;
    else
        cout << "分数" << target << "未找到" << endl;

    // 5. 插入演示：在下标2处插入99，需要新数组
    int insert_pos = 2;
    int insert_val = 99;
    int new_scores[SIZE + 1];  // 新数组比原数组多一格
    for (int i = 0; i < SIZE + 1; i++) {
        if (i < insert_pos) {
            new_scores[i] = scores[i];          // 原封不动复制前面
        } else if (i == insert_pos) {
            new_scores[i] = insert_val;          // 放入新值
        } else {
            new_scores[i] = scores[i - 1];       // 原数组后移一位
        }
    }
    cout << "插入后新数组: ";
    for (int i = 0; i < SIZE + 1; i++) {
        cout << new_scores[i] << " ";
    }
    cout << endl;

    // 6. 删除演示：删除下标2的元素（原78），注意大小减少
    int del_pos = 2;
    int smaller_scores[SIZE - 1];  // 新数组少一格
    for (int i = 0; i < SIZE; i++) {
        if (i < del_pos) {
            smaller_scores[i] = scores[i];        // 前面不变
        } else if (i > del_pos) {
            smaller_scores[i - 1] = scores[i];    // 后面前移
        }
        // i == del_pos 跳过
    }
    cout << "删除后新数组: ";
    for (int i = 0; i < SIZE - 1; i++) {
        cout << smaller_scores[i] << " ";
    }
    cout << endl;

    return 0;
}

Python 完整示例

# 1. 创建数组（Python 列表）
scores = [85, 92, 78, 90, 88]  # 5个分数

# 2. 访问与修改
print("原第1个分数:", scores[0])
scores[0] = 100  # 修改
print("修改后第1个分数:", scores[0])

# 3. 遍历
print("所有分数: ", end="")
for score in scores:
    print(score, end=" ")
print()

# 4. 查找：找到分数90的下标
target = 90
if target in scores:
    idx = scores.index(target)  # 返回第一个匹配的下标
    print(f"分数{target}在下标{idx}")
else:
    print(f"分数{target}未找到")

# 5. 插入：在下标2处插入99
insert_pos = 2
insert_val = 99
scores.insert(insert_pos, insert_val)  # 自动移动元素
print("插入后数组:", scores)

# 6. 删除：删除下标2的元素（原78被移到了下标3？注意插入后数组变了）
# 我们重新创建一个删除的例子
scores2 = [85, 92, 78, 90, 88]  # 新数组，原样
del_pos = 2
deleted_value = scores2.pop(del_pos)  # 删除并返回
print(f"删除下标{del_pos}的值{deleted_value}后数组:", scores2)

运行上面 Python 代码时要注意：步骤5的插入会改变 scores 列表，所以步骤6应该用另一个独立的列表来演示删除，避免混淆。我已在代码中说明。

常见错误与注意事项

  1. 下标越界：新手最容易犯的错误。比如数组有5个元素，却访问 arr[5]（最后一个下标是4）。C++ 中不会报错，但会返回垃圾值（或导致程序崩溃）；Python 中会抛出 IndexError。记住：下标从0开始，最大是长度-1。

  2. 忘记给数组分配足够空间：在C++里，如果声明 int arr[10]; 然后试图放20个元素，会覆盖后面的内存，导致不可预料的错误。

  3. 遍历时循环条件写错：比如 for (int i=0; i<=SIZE; i++) 会多循环一次导致越界。常用 i < SIZE。

  4. 插入删除时移动元素顺序搞反：比如插入时，应该从最后一个元素开始往后移，而不是从插入位置开始（否则会覆盖数据）。上面的C++代码使用临时数组避开了这个坑，但如果你试图在原数组上操作，要多加小心。

  5. 混淆静态数组和动态数组：C++静态数组大小在编译时就固定了；Python的list是动态的，可以自动扩容，但底层也是数组，插入删除依然要移动元素。

总结与下一步

数组就像一排编号固定的储物格，存取快（O(1)），但修改中间的内容慢（O(n)）。它是计算机科学里最基础的数据结构，理解数组是学习其他数据结构（如链表、栈、队列、哈希表）的垫脚石。

如果你经常需要在中间插入或删除数据，用数组就会很痛苦——每次都要搬动一堆元素。这时候就要请出它的好兄弟——链表。链表就像一条锁链，每个节点既存数据又存下一个节点的位置，插入和删除只需要断开或接通两端的链子，非常快（O(1)），但查找某个元素必须从头一个个找（O(n)）。这两种结构各有优势，根据不同需求选择。

接下来，你可以继续学习 链表，看看它是怎么解决数组的痛点的，以及动态数组（如Python的list、C++的vector）是如何结合两者优点的。

例题精讲

1单选题

以下关于数组的描述，哪一项是正确的？

A数组的长度在程序运行过程中可以动态改变
B在数组中插入或删除一个元素，通常需要移动大量元素
C数组支持随机访问，但访问任意元素的时间复杂度为O(n)
D数组中的所有元素必须是同一类型，且类型不能是基本类型
2单选题

已知数组A有n个元素（下标从0到n-1），现要在下标为i的位置（0 ≤ i ≤ n）插入一个新元素，则需要移动的元素个数为（假设插入后数组长度变为n+1）：

An - i
Bn - i + 1
Cn - i - 1
Di
3判断题

在数组中，通过下标访问任意元素的时间复杂度是O(1)。

4判断题

在大多数主流编程语言（如C、C++、Java、Python）中，数组的下标都是从1开始的。

5填空题
以下C语言代码定义了一个长度为5的整型数组，并将第一个元素赋值为10。请补充完整。
int arr[5];
___ = 10;