2021-08-06 17:58 已编辑山东理工大学 C++

关注

数组入门指北

产品经理的需求

先看下面这样一段代码：

#include <stdio.h>

int main() {
    int a, b;
    scanf("%d %d", &a, &b);
    printf("%d+%d=%d\n", a, b, a+b);
    return 0;
}

稍有C语言基础的老铁，应该都能看明白：输入两个整数，然后求和并打印。在实现上：

我们先定义了两个int类型的变量a和b。
接着，借助库函数scanf读入数据并存储在a和b中。
最后，计算两者之和，并按照指定格式打印。

过了几天，产品经理说要调整需求：要求三个整数的累加和。机智如我，立马给出解决方案：添加一个int类型的变量c不就得了。于是，上述代码被修改为：

#include <stdio.h>

int main() {
    int a, b, c;
    scanf("%d %d %d", &a, &b, &c);
    printf("%d+%d+%d=%d\n", a, b, c, a+b+c);
    return 0;
}

又过了几天，产品经理又来了：要计算一百个整数的累加和。~~暴躁如我，立马爆出国粹WQNMLGB。~~勤奋如我，立马定义了一百个int类型的变量a0,a1,...,a99。于是，上述代码被修改为：

#include <stdio.h>

int main() {
    int a0, a1, ..., a99; // 太长了，上伪代码吧Orz
    scanf("%d %d ... %d", &a0, &a1, ..., &a99);
    printf("%d+%d+...+%d=%d\n", a0, a1, ..., a99, a0+a1+...+a99);
    return 0;
}

虽然代码很丑陋，不过还是实现了功能。不管了，先下班回家陪女朋友刷剧了。

又过了几天，产品经理又来了：要计算n个整数的累加和，n不超过十万，且不需要用户输入n。这直接给我整不会了：

首先，输入整数的数量上限是十万，总不能定义十万个变量吧？写到分手也写不完呀。
其次，输入的数量不固定了，那如何控制输入输出的格式呢？
最后，用户不告诉我n，我咋知道用户输没输完呢？

好学如我，遍查典籍后发现了数组，可将上述需求轻松解决。

什么是数组

类似于int,double，float这些变量类型，可以认为数组也是一种变量类型。只不过这种变量类型更高级，需要和其他变量类型组合使用。

int integer;
int integer_array[100000];

上述代码做了两件事情：

定义了一个int类型的变量
定义了一个可存放十万个 int 类型数据的数组类型变量。

与int类型变量不同的是，每个int类型变量仅能存储一个整数，而integer_array可以存储十万个整数。

不难发现，在定义数组类型的变量时，程序员要在代码中指明两个要素：

容量：该数组类型的变量能存储多少份数据。
类型：该数组类型的变量要存储什么类型的数据。

如下图示例，在 C/C++ 中，一行定义数组类型变量的代码，可以拆解为三部分：类型，变量名，容量。

通过不同类型和容量的组合，可以组装出各种各样的数组，如下所示：

double double_array[1000]; // 可存放一千个 double 类型数据的数组。
int int_array[1]; // 可存放一个 int 类型数据的数组。

综上所述，数组也是一种类型，在定义数组类型变量时，必须指明容量和类型两个要素。一行形如data_type variable_name[capacity];的代码，定义了一个名为variable_name的，可存放capacity个类型为data_type的数据的数组类型变量。

如何使用数组

本部分主要介绍数组的初始化和读写操作。

初始化

与int，double等基本类型的变量一样，数组类型的变量也可在定义时进行初始化。从语法上来讲，有以下几种初始化方式：

int array[5] = {};此时 array 中的所有元素都被初始化为零值。
int array[5] = {1,2,3，4，5};为每个元素都指定初始值。
int array[5] = {1,2};为部分元素指定初始值，其他元素会被初始化为零值。
int array[] = {1,2,3,4,5};隐式的指定容量，容量与初始化列表的长度相同。

如果在定义时，未指定初始化列表会怎样呢？这取决array的类型以及在内存中的位置。在讨论之前先明确一个概念——内置类型。C 的内置类型包括：

字符(char, unsigned char)
整数(short, int, long，以及对应的无符号类型等)
浮点数(float，double，long double，以及对应的无符号类型等)

在 C++ 中还多了布尔(bool)。

接下来，先讨论类型对初始值的影响，如下述代码所示：

struct Node {
   int val;
   Node() : val(-1) {}
};
Node array[100];

我们定义了一个数据类型为Node的数组。对于这种非内置类型的数组，其初始值该类型的构造函数决定。

如果array中的数据为内置类型，则要根据array在内存中位置，来确定初始值。

如果位于静态变量区，则全部元素被初始化为零值。比如由static修饰的变量均位于静态变量区。
位于其他区域时，值未定义。

读写

在一个容量为n的数组中，每个元素都会被独占一个下标。这n个下标分别为0，1，2，...，n-1。

在定义数组时，我们通过[]来指定数组的容量。在访问数组时，我们也通过[]来告诉编译器待访问元素的下标，此时,[]被称为下标运算符。下面是一个读写指定下标数据的样例。

int array[10] = {}; // 定义一个数组，全部初始为零值。
printf("%d\n", array[5]); // 访问下标为 5 的元素，输出 0。
array[2] = 10; // 更新下标为 2 的元素
printf("%d\n", array[2]); // 输出 10。

值得一提的是，对于一个容量为n的数组，在读写时，下标应位于[0, n-1]之内。否则程序可能会抛出异常Segmentation fault。反向思考，当你看到这个错误时，也要意识到有可能是下标越界啦。

完成产品经理的需求

好啦，我们现在学会了数组的一些基本知识。接下来，一起来解决产品经理的需求。回忆一下产品经理的需求：要计算n个整数的累加和，n不超过十万，且不需要用户输入n。

在动手之前，还需要学习一个知识——scanf的返回值。scanf声明如下：

int scanf ( const char * format, ... );

返回值分为两种情况：

当函数成功执行结束时，返回值为读入变量的数量。
- scanf("%d", &a);返回 1
- scanf("%d %d", &a, &b)返回 2
当函数发生错误，或到达文件末尾时，返回 EOF (一个宏定义，一般值为 -1)。到达文件末尾，可由两种方式触发(可能还有其他的？欢迎补充)：
- 程序从磁盘文件读入，在调用该次scanf之前已经读入了文件的所有数据，则该次调用返回 EOF。
- 用户按下了特定的组合键，通知进程读入结束了(mac 是 ctrl+d, windows 是 ctrl+c)。

因此，我们每次调用scanf都只读取一个整数，如果scanf返回了 -1，则说明已经读入了所有数据。想明白这些只有，就有了下述代码：

#include <stdio.h>

int data[100000]; // 定义一个数组

int main() {
  int n = 0; // 计数器，记录读取数字的个数，初始为 0。
  while (scanf("%d", &data[n]) != EOF) { //读取整数，并将其存放在下标 n 处。
    n = n+1; // 下标移动到下个位置。
  }
  int sum = 0; // 读入结束啦，统计累加和。
  for (int i = 0; i < n; i++) {
    sum += data[i];
    printf("%d%c", data[i], ((i+1 < n) ?'+': '=')); // 按格式输出
  }
  printf("%d\n", sum); // 输出累加和。
  return 0;
}

数组可以有多个维度

using IntArray10w = int[100000];
IntArray10w data;

在上述代码中，我们通过using关键字，定义了一个新类型IntArray10w—— 可存放 10w 个 int 的数组类型。

因此IntArray10w data;和int data[100000];可以认为是完全等价的。更为惊喜的是：

IntArray10w two_dim_array[10];

我们定义了一个可存储 10 个IntArray10w的数组。这等价于int two_dim_array[10][100000];。为了区分，我们将其分别称为一维数组和二维数组。

更高级的是，C/C++ 并没有对维度进行限制，你可以定义出任意维度的数据，只要你的内存放的下。

int d1[10]; // 一维数组
int d2[2][3] = {{1,2,3},{4,5,6}}; // 二维数组
int d5[10][2][30][4][50] = {}; // 五维数组。

高维数组在一些动态规划类的题目中，经常会用到。这个后面有机会我们再一起讨论。

数组在内存中的存储方式

在 C/C++ 中，内存的最小分配单位为字节(byte, 八个 bit)。简单来讲，存储一个数组所需的字节数，取决于数组的容量以及单个元素所需字节数。

比如，int32_t data[8];，容量为 8，类型为int32_t，一个int32_t需占 4 字节。因此存储data需要 8*4=32 个字节。

这意味着，下标相邻的两个元素，在内存中也是存放在相邻位置。通过下述代码验证一下：

#include <stdio.h>

int main() {
  int32_t data[8] = {};
  printf("data's addr: %x(%u)\n", &data, &data);
  for (int i = 0; i < 8; i++) {
    printf("i: %d, addr: %x(%u)\n", i, &data[i], &data[i]);
  }
  return 0;
}

输出如下：

data's addr: e22b8990(3794504080)
i: 0, addr: e22b8990(3794504080)
i: 1, addr: e22b8994(3794504084)
i: 2, addr: e22b8998(3794504088)
i: 3, addr: e22b899c(3794504092)
i: 4, addr: e22b89a0(3794504096)
i: 5, addr: e22b89a4(3794504100)
i: 6, addr: e22b89a8(3794504104)
i: 7, addr: e22b89ac(3794504108)

值得一提的是，首地址即data的地址每次执行时均可能发生变化（原因我们后续再讨论），但是相邻元素的地址的偏移量是不会变化的。偏移量为 4, 即存储一个int32_t所需的字节数量。