数组

在我们认识数组之前，如果我们需要存储多个同类型的值，只能通过定义多个变量来完成。比如，要存储 5 个整数值，我们只能像下面这样定义和输入 5 个整型变量。

int a, b, c;
cin >> a >> b >> c;

如果需要存储 100 个这样的值呢，定义 100 这样的变量吗？那就太麻烦了，取名字都麻烦死了。

在 C++ 中，提供了数组（Array）这样一种数据结构，用于存储相同类型元素 。

可以把数组想像成一个抽屉，一个抽屉可以有多个格子，每个格子里存放着同样类型的物品，每个格子都有一个编号，我们可以通过编号去找到对应的格子，取出里面的物品。

C++ 中的数组具有以下特点：

1. 固定大小： 数组具有固定的大小，在创建时需要指定元素的数量，一旦创建后大小不能更改。
2. 连续存储： 数组中的元素在内存中是连续存储的，这使得访问数组元素的速度非常快。
3. 下标访问： 数组中的每个元素都有一个索引（下标），通过索引可以访问和修改数组中的元素。
4. 同一类型： 数组中的元素必须是相同的数据类型，例如整数数组只能存储整数，字符串数组只能存储字符串等。

数组的声明与初始化

数组的声明

在 C++ 中，数组的声明语法如下：

数据类型 数组名[数组大小];

例如，我们要定义一个可以装 100 个整型变量的数组（也就是我们想要一个包含 100 个格子的抽屉），可以下面这样声明：

int a[100]; // 声明了一个包含 100 个整数的数组

简单解释一下：

• int 代表每个格子里装的元素都是整数类型，当然你可以根据需要声明其它数据类型
• a 是数组的名字
• 100 是代表这个数组的大小，也就是格子的数量

数组的初始化

数组可以在声明时进行初始化，也可在声明后通过赋值来初始化。下面展示了对数组进行初始化（设置初始值）的几种不同情况。

#include <iostream>
using namespace std;

int main() {
    int a[3] = {1, 2, 3}; // 方式一，声明并初始化数组
    int b[] = {1, 2, 3}; // 方式二，声明并初始化数组
    int c[5] = {1, 2, 3}; // 方式三，声明并初始化数组

    // 方法四，声明后逐个赋值来初始化数组
    int d[100];
    int n;
    cin >> n;

    for (int i = 0; i < n; i++) {
      cin >> d[i]; // 通过循环逐个赋值
    }

    return 0;
}

方式一与方式二本质是一样的，只是一个是显示式指明数组大小，一个是在初始化时隐式指明的数组大小，两者数组大小都是 3 。

方法三，在定义数组 c 时，设定大小为 5，但实际上只初始化了前 3 个元素，只用了 3 个格子，剩下的格子我们后面还可以用。

第四种方式在实际应用中更常见，根据用户输入的数据，通过逐个赋值的方式来对数组进行初始化。

如果用户输入：

5
1 2 6 5 8

赋值完成后，数组 d 的前 5 个元素依次为：1、2、6、5、8 。

数组的访问与操作

声明和初始化数组，目的是把数据放到数组里去存储，存的目的是为了用。例如：

• 如何从数组中取出想要的元素？
• 如何删除数组中的某个元素？
• 如何对数组中的元素进行排序？
• 等等。

还是之前的类比，数组就像是抽屉，里面有多个格子，每个格子里装的需要存储的数据。每个格子都有一个编号，我们就是通过这个编号来访问对应格子里的元素。

例如，下面的代码定义了一个含有 5 个元素的数组 a。

int a[5] = {1, 2, 6, 5, 8};

如下图所示，数组中每个格子的编号从 0 开始，往后依次增加，这里共有 5 个元素，因此编号从 0 ~ 4。可以用 数组名[编号] 的方式来访问数组中的元素。

如， a[0] 就是指编号为 0 的格子里的元素，这里就是整数数字 1；a[3] 就是指编号为 3 的格子里的元素，这里是整数 5。

在 C++ 中，我们通常把格子编号称为索引（下标），我们在本指南中更多是使用下标这个说法。

从现在开始，大家就可以把 数组名[下标] 看作是一个普通变量，只是这个普通变量的名字稍微有点奇怪而以，对普通变量的各种操作也可以用在 数组名[下标] 上。

示例代码如下：

#include <bits/stdc++.h>
using namespace std;

int main() {
  int a[5] = {1, 2, 6, 5, 8};

  a[3] = 5; // 赋值，修改数组元素的值
  a[1] = 2 * a[1]; // 赋值，修改数组元素的值

  swap(a[0], a[4]); // 交换数组中两个元素的值

  return 0;
}

数组遍历

数组遍历，也就是依次去读取数组中的每个元素，这是一个经常会用到的高频操作。

可以通过循环去遍历数组中的所有元素。

方式一：标准的 for 循环

int a[5] = {1, 2, 6, 5, 8};

// for 循环数组遍历
for (int i = 0; i < 5; i++) {
  cout << a[i] << " "; // 输出时每个元素后添加一个空格
}
// 运行结果是：1 2 6 5 8

当然，用 while 循环也是一样的。

方式二：Ranged for 循环

C++ 11（2011 版本），引入了一种新的基于范围（Range-Based）的 for 循环，类似 Python 中的 for ... in 循环，用于数组遍历更加方便。

int a[5] = {1, 2, 6, 5, 8};

// Ranged for 数组遍历
for (int num : a) {
  cout << num << " "; // 输出时每个元素后添加一个空格
}
// 运行结果是：1 2 6 5 8

在实际应用中，如果我们仅仅是访问数组元素而不用改变数组的元素，下面这样写更好一些。

int a[5] = {1, 2, 6, 5, 8};

// 数组遍历
for (const int &num : a) {
  cout << num << " "; // 输出时每个元素后添加一个空格
}
// 运行结果是：1 2 6 5 8

• 既然不用改变数组的元素，使用 const 常量更安全一些，避免误用
• 如果使用 int num，在每次数组的元素迭代时，都会将数组元素拷贝一份给 num，而改用 &num，则是使用内存地址去访问数据，不会有多余的数据拷贝，这样内存使用效率更高

数组读入输出基础模板

对于初学者来说，下面是一个比较常见的数组元素读入与输出的基础模板，需要熟练掌握。

#include <iostream>
using namespace std;

const int MAX_N = 100; // 定义一个常量，用于数组的大小指定

int main() {
    int n, q[MAX_N];
    cin >> n;

    // 依次从外部读入 n 个数据到数组
    for (int i = 0; i < n; i++) cin >> q[i];

    // 核心逻辑代码
    // 在这里写你要对数组的各种操作，例如排序

    // 依次输出数组中的数据
    for (int i = 0; i < n; i++) cout << q[i] << " ";

    return 0;
}

输入：

5
1 2 6 5 8

输出：

1 2 6 5 8

获取数组的长度

在 C++ 中，并没有能直接拿到数组长度（有多少个元素）的函数，在实际应用中又经常需要用到，怎么办呢？

一种方法是使用我们后面会讲到的向量（vector）。当然，我们也可以利用 sizeof() 这个函数去间接获取到数组的长度。

先用 sizeof() 来看看数组的大小代表的是什么。

int a[] = {1, 2, 6, 5, 8, 3, 9};
cout << sizeof(a);
// 输出结果是：28

这里的 sizeof() 是获取数组所占的内存空间大小，为什么是 28 呢？因为在大多数系统中，int 变量所占大小是 4 个字节（Byte），这里刚好有 7 个元素，总共大小就应该是 7 × 4 = 28 个字节。

有这样一个简单的计算公式：

数组的大小 = 数组的元素个数 × 一个元素所占的大小

借由这个公式我们可以得到一个求数组长度的方法：

int a_len = sizeof(a) / sizeof(a[0]);

这里取 a[0]用来代表其中一个元素所占的大小。

数组排序

排序是编程中一个非常常见的操作，老师统计班上的成绩会有从高到低的排序，去网上购物，我们经常用到价格从低到高的排序，体育老师上课整队，经常会让大家按身高从矮到高来排序。

这里我们讨论的是如何利用 C++ 内置的 sort() 函数来对数组进行排序。以后我们还会学习到各种排序算法，自己实现这些算法，来完成对元素的排序。

sort() 函数的用法说明如下：

sort(开始位置, 结束位置, 比较方法);

• 开始位置：指明排序范围从哪里开始
• 结束位置：指明排序范围到哪里结束（结束位置不包括在排序范围内）
• 比较方法：按什么规则来排序，从小到大？从小到小？还是其它

我们在这里对 sort() 的讨论更多是从初学者的使用角度来谈，无论是说法还是用法，都简化了很多，后面还会讨论到更完整、更严谨的用法。

下面来看几个简单的用法示例：

数组元素从小到大排序

#include <bits/stdc++.h>
using namespace std;

int main() {
  int n, q[100];
  cin >> n;

  for (int i = 0; i < n; i++) cin >> q[i];

  sort(q, q + n); // 默认从小到大排序

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

  return 0;
}

如果输入数据：

5
6 5 1 2 8

运行程序，将得到从小到大排序后的结果：

1 2 5 6 8

数组元素从大到小排序

#include <bits/stdc++.h>
using namespace std;

int main() {
  int n, q[100];
  cin >> n;

  for (int i = 0; i < n; i++) cin >> q[i];

  sort(q, q + n, greater<int>()); // 指定从大到小排序

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

  return 0;
}

如果输入数据：

5
6 5 1 2 8

运行程序，将得到从小到大排序后的结果：

8 6 5 2 1

这里的 greater<int>() 是 C++ 提供的函数对象，用于定义排序规则。

• less<int>() 用于指定数据按从小到大的排序规则
• greater<int>() 用于指定数据按从大到小的排序规则

当我们使用 sort() 函数时，如果不指定第三个用于排序规则的参数，默认是从小到大排序（less<int>()）。另外，这里 <> 里的 int 还可以替换成其它数据类型，甚至自定义数据类型，以后我们还会讲到。

练习: 数组中的最小值及位置

题目描述

输入一个整数 $n (1 \lt n \le 10001)$，并从外部读入 $n$ 个数据到数组 $a$，找出数组 $a$ 中所有元素的最小值，并输出它的值和下标。若有多个最小值，则返回下标最小的那个数。

输入输出样例

输入

8
2 8 -1 3 -3 7 9 0

输出

-3
4

题目分析

我们在条件判断章节中，有一个从三个数中找出最大值的练习，其中讲到了用 打擂 的方法来求最大值或最小值。这里我们也可以用同样的方法去找到最小值。

另外，这里除了求最小值，还需要最小值的下标。在数组中，通过下标去得到对应的值很方便，直接用 数组名[下标]就可以得到；反过来，要通过值去得到该值所对应的下标是很麻烦的，如果数据元素各不相同，还可以通过遍历的方式去找到该值所对应的下标值，如果数组有值相同的元素，通过值去找下标就行不通了。

因此我们在选擂主时直接用下标更方便一些，当然，打擂时还是用值去打，而不是用下标去打的，这一点需要特别注意。

参考代码

#include <iostream>
using namespace std;

const int N = 1010;

int a[N];

int main() {
    int n;
    cin >> n;

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

    int min_idx = 0; // 选择最初的擂主

    // 依次打擂，求出最小值的下标
    for (int i = 1; i < n; i ++) {
      if (a[i] < a[min_idx]) min_idx = i;
    }

    // 输出结果
    cout << a[min_idx] << endl;
    cout << min_idx << endl;


    return 0;
}

练习：数组的旋转

题目描述

输入一个 n，再输入 n 个整数。将这个数组顺时针旋转 k(k≤n) 次，最后将结果输出。 旋转一次是指：将最左边的数放到最右边。

什么是旋转 1 次呢，例如有 5 个数

1 2 3 4 5

旋转 1 次就是把最后一个数字挪到最前面去，得到 5 1 2 3 4 。旋转 2 次就是按同样的规则做两次，结果应该是 4 5 1 2 3

样例

输入

5 2
1 2 3 4 5

输出

4 5 1 2 3

题目分析

这里的实现方法是利用基本的数组元素交换来完成，需要注意的是，我们如果要将最后一个元素挪到第 1 个元素的位置上去，那第 1 个元素的位置应该空出来，为了第 1 个元素的位置空出来，就需要给第 1 个元素挪到一个地方，依此类推。

因此我们可以按上图所示这样，先用一个临时变量 temp 把最后一个元素存起来，然后从倒数第 2 个元素开始，依次向后挪，直到把 a[0] 空出来，最后再把临时的 temp 放到 a[0] 中去，这就完成了一次旋转。

代码实现

#include <iostream>
using namespace std;

const int N = 100;

int main() {
    int n, k;
    cin >> n >> k;

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

    // 倒着去依次挪位置
    while (k--) {
      int t = a[n - 1]; // 将最后一个元素临时存起来

      for (int i = n - 2; i >= 0; i--) {
        a[i + 1] = a[i];
      }

      a[0] = t; // 第一个位置挪出来后，把临时存的数据放进去
    }

    for (int i = 0; i < n; i++) cout << a[i] << ' ';

    return 0;
}

二维数组

上面我们讲到的都属于一维数组，你可以把它理解成只有一排格子的抽屉。在实际应用场景中，可能会遇到有多排格子的数据要存储，这时就需要用到二维数组。

例如，电影票上都是用几排几号来表示一个位置的，这就是一个典型的多行多列，可以使用二维数组来存储和处理。

从另外一个角度来理解，数组的元素本身也可以是数组。元素类型为一维数组的数组就是二维数组，元素类型为二维数组的数组是三维数组。依次类推，也有四维及以上的数组。二维及二维以上的数组统称多维数组。不过超过二维的多维数组不在我们讨论的范围之内。

下面我们只讨论二维数组。

二维数组声明与初始化

二维数组的声明与一维数组区别不大，下面定义了一个二维数组（数组的元素类型为数组），用于存储电影票的位置，每张电影票包括几排几号两个数组，定义如下：

int matrix[3][2] = {
  {2, 3}, // 代表 2 排 3 号
  {5, 6}, // 代表 5 排 6 号
  {8, 9} // 代表 8 排 9 号
};

需要注意的是，这里故意调整了一下括号层级的对齐方式，让我们看几行几列更加清楚。

如果只是看数据，上面的 matrix 可以看做是三行两列的表格数据

2 3
5 6
8 9

我们仍然可以通过数组的下标去访问数组内的每个元素，第一个下标表示行，第二个下标表示列。

cout << matrix[0][1]; // 输出第1行第2列的元素：3
cout << matrix[2][1]; // 输出第3行第1列的元素：8

二维数组遍历

我们可以使用嵌套循环来访问多维数组的元素，像上面的 matrix 数组，我们可以用下面的程序来访问。

#include <iostream>
using namespace std;

int main() {
    int matrix[3][2] = {
      {2, 3},
      {5, 6},
      {8, 9}
    };

    for (int i = 0; i < 3; i++) {
      for (int j = 0; j < 2; j++) {
        cout << matrix[i][j] << " ";
      }
      cout << endl;
    }

    return 0;
}

可以看到，外层循环代表的是几行，内层循环代表的是几列。

练习：输出杨辉三角的前N行

问题描述

输出杨辉三角的前 $N$ 行（$N \lt 10$） 。

输入描述

输入只有一行，包括 1 个整数 $N$。

输出描述

输出为 $N$，表示杨辉三角的前 $N$ 行。

输入输出样例

输入

5

输出

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1

题目解析

观察样例中的输出，可以得出：

1. 第 1 列全是 1
2. 除开第 1 列外，每个数 = 正上方的数 + 正方数左侧的数

参考代码

#include <bits/stdc++.h>
using namespace std;

int n, q[15][15];

int main() {
  cin >> n;

  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= i; j++) {
      if (j == 1) q[i][j] = 1;
      else {
        q[i][j] = q[i - 1][j] + q[i - 1][j - 1];
      }
    }
  }

  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= i; j++) {
      cout << q[i][j] << " ";
    }
    cout << endl;
  }
  return 0;
}

小结

总之，C++ 中的数组是一种常见的数据结构，用于存储和处理一组相同类型的元素。其固定大小和连续存储的特性使其成为处理数据的重要工具。我们在后面要学习的算法，基本上也都会用到数组，因此熟练掌握数组的用法对于学习后面的知识是至关重要的。