语法级-数组

# 数组

---

### 一、数组的定义和访问

期末考试，老师要把每个同学的成绩存储起来，以后进行最高分、最低分、平均分等统计，还要将成绩从高到低排序输出。

`理解`： 如果每个同学的成绩是一张试卷，老师要把所有试卷放入一个文件夹保存起来。

---

#### 1、数组的定义

如果有多个同类的数据（例如成绩），可以通过数组进行存储和访问。

```c++
int a[5];
//int a1,a2,a3,a4,a5;
//变量看成大楼中的一个房间，房间的名字就是变量名，比如，int n; 
//数组可以看成大楼的一层，这一层上有多个房间，楼层的名字就是数组名，数组的长度就是房间的个数
定义一个整数数组，里面有5个整数元素：
int：类型
a：变量名
[]：表示是一个数组
5：数组的长度（容量）
```

`理解`：向系统申请一个容纳5个int数据的空间，返回这个空间的地址，用a来表示这个地址。

---

#### 2、数组元素的赋值

* 现在我们拥有了由5个int元素组成的数组（空的房间），还需要赋值（放东西进去）。
* 数组元素通过中括号[]和下标0...4进行访问，如a[0] = 1，这里a[0]可理解成一个int变量。

| 下标     | 0    | 1    | 2    | 3    | 4    |
| -------- | ---- | ---- | ---- | ---- | ---- |
| 元素     | a[0] | a[1] | a[2] | a[3] | a[4] |
| 元素的值 | 1    | 空   | 空   | 空   | 空   |

```c++
int a[5];
a[0] = 1; //给第一个元素赋值
cout << a[0]; //输出第一个元素的值
```

---

#### 3、循环访问

下标是从0开始，到数组长度－1为止，可以用循环来访问。

```c++
for(int i=0; i<5; i++)
    cout << a[i] << " ";
```

---

#### 4、快速初始化

在数组定义的同时可以进行初始化，使用大括号{}。

```c++
int a[5] = {90, 85, 70, 48, 91};
cout << a[0];  //输出90
```

| 下标     | 0    | 1    | 2    | 3    | 4    |
| -------- | ---- | ---- | ---- | ---- | ---- |
| 元素     | a[0] | a[1] | a[2] | a[3] | a[4] |
| 元素的值 | 90   | 85   | 70   | 48   | 91   |

---

如果大括号里面的值比数组长度少，那么多出来的下标对应的值都是0。如

```
int a[5] = {90, 85, 70};
cout << a[0];  //输出90
cout << a[3]; //输出0
```

---

#### 4、扩展理解

#### 4.1、数组的理解

* 数组的定义：向系统申请一块空间。
* 数组名称：一个int变量，里面存储的是空间的地址。
* 数组下标：按照数组类型的大小，按空间地址往后移动。

---

例子：

```c++
int a[3];
  cout << "数组：" << a << endl; 
  cout << "元素0：" << &a[0] << endl; //&符号表示a[0]变量的地址
  cout << "元素1：" << &a[1] << endl;
  cout << "元素2：" << &a[2] << endl;
```

---

输出结果：

```
数组：0x7ffc66ee2900
元素0：0x7ffc66ee2900
元素1：0x7ffc66ee2904
元素2：0x7ffc66ee2908
```

---

`理解`：

* 数组a的地址，就是第一个元素a[0]的地址。
* a[1]的地址，是元素a[0]地址加上4（int类型4个字节，等于32位）
* a[2]的地址，是元素a[1]地址加上4

| 变量 | 地址           |
| ---- | -------------- |
| a    | 0x7ffc66ee2900 |
| a[0] | 0x7ffc66ee2900 |
| a[1] | 0x7ffc66ee2904 |
| a[2] | 0x7ffc66ee2908 |

---

#### 4.2、下标的理解

下标实际上就是在数组a的地址上，按照数据类型（大小）往后移动。
a[n]：a的地址 + n * 4

| 变量  | 地址           | 地址公式 |
| ----- | -------------- | -------- |
| a     | 0x7ffc66ee2900 |          |
| a[0]  | 0x7ffc66ee2900 |          |
| a[1]  | 0x7ffc66ee2904 | a + 4    |
| ...   |                |          |
| a[10] | 0x7ffc66ee2940 | a + 10*4 |

---

#### 4.3、下标越界

如果n超过了数组定义的大小，在代码编译时不会报错，但程序运行会出现不可预期的错误。

`原因`：a[n]只是从地址去访问数据，但那个地址不是我们的，不知道数据会怎么样！！！

---

#### 4.4、下标和中括号

a[0]：使用中括号[]将数组变量名和下标连接起来，这里中括号实际是一个运算符，并且遵循交换律。

所以，0[a]也是可以用的。

---

### 二、数组的输入

现在，老师想在程序运行之后自己录入同学们的成绩。

编写程序，定义int类型长度为5的数组a，运行后接收老师输入的5个成绩，然后循环输出。

---

#### 1、数组的输入

下标是从0开始，到数组长度－1为止，可以用循环来输入。

```c++
for(int i=0; i<5; i++)
    cin>>a[i];
```

---

1. 数组的5个元素，可以理解成5个int变量。
2. 使用for循环，在循环里使用cin 输入到数组的元素。
3. 运行时输入5个数，用空格隔开。

---

### 三、二维数组

期末考试要记录语文、数学、英语三科成绩，老师要输入班级里每个同学的三科成绩，然后再统计每个同学的成绩总分、平均分。

---

#### 1、二维数组

二维数组的定义与一维数组类似，一般格式为：

```c++
类型  数组名[行常量][列常量];
int score[4][3];
```

---

`说明`：

* score为数组名，表示成绩。
* 4是行数，这里表示4个学生。
* 3是列数，这里表示每个学生的3科成绩。

---

#### 2、下标访问

和一维数组类似，可通过下标访问，例如：

```
score[0][0] = 60;
```

---

注意这里的两个下标，范围分别为0..3，0..2，可通过循环来访问：

```
for(int i = 0; i<4; i++)
{
  for(int j = 0; j<3; j++)
    cout << score[i][j] << " ";
  cout << endl;
}
```

---

#### 3、初始化

一维数组的初始化使用一个大括号，二维数组的初始化可以看成同时初始化多个一维数组，每个为一行。

```
int score[4][3] = {{60, 70, 80}, {90, 94, 98}, {100, 60, 79}, {100, 100, 95}};
```

---

如果大括号里只写了部分初始化值，则剩下的为默认值（int类型的默认值是0）：

```
int a[10] = {0}; //第一个是0，后面都是默认值（也是0）
int b[10] = {1}; //第一个是1，后面都是0
int score[4][3] = {{60,70,80}}; //第一行是{60,70,80}，后面都是0
```

---

#### 4、存储

在内存里，二维数组的存储和一维数组是一样的，从首元素开始，依次往上递增。

---

#### 5、扩展理解

#### 5.1、二维数组与行列下标

二维数组既可循环访问每行数据，也可以循环访问每列数据：

```
//循环访问第一行的三个数据
for(int j = 0; j< 3; j++)
  cout << a[0][j];

//循环访问第二列的4个数据
for(int i=0; i<4; i++)
  cout << a[i][1];
```

---

#### 5.2、数组的元素个数

```
int a[2][3];  //2行3列，一共6个元素
sizeof(a);  //数组a一共占据的内存大小，24个字节
sizeof(int); //一个int类型占据的内存大小，4个字节
sizeof(a) / sizeof(int);   //6个元素
```

---

#### 5.3、二维与一维数组

二维数组可以看成多个一维数组（行），例如：

```
a[3][4]; //二维数组
a[0];  //第一行（由4个元素组成的一维数组，下同）
a[1];  //第二行
a[2];  //第三行
```

---

### 四、矩阵、桶、环

初始化一个N*N矩阵，把上边都设置为1，右边设置为2，下边设置为3，左边设置为4，其它为0，然后显示出来。

---

#### 1、行和列

* 数组的边：a[0][i]上边、a[i][0]左边、a[N-1][i]下边、a[i][N-1]下边。
* 数组的行：a[1][i]第二行、a[2][i]第三行……a[N-3][i]倒数第三行、a[N-2][i]倒数第二行。
* 数组的列：a[i][1]第二列、a[i][2]第三列……a[i][N-3]倒数第三列、a[i][N-2]倒数第二列。

---

#### 2、矩阵斜线

已知一个4*4的矩阵，把正对角线的元素值加上10，斜对角线的元素值加上20，然后输出新的矩阵.

初始矩阵：

```
1 2 3 4
5 6 7 8
9 8 7 6
5 4 3 2
```

---

#### 2.1、正斜线和反斜线

* 正对角线：a[i][i]  ,   i== j表示正对角线
* 反对角线：a[i][N-1-i],  i+j == N-1表示反对角线
* 正斜线：i = d + j，正对角线是特例（d=0）
* 反斜线：i = d - j，反对角线是特例（d=N-1）

---

#### 3、矩阵填充

编写程序，在3*3的矩阵中填入1到9的数字，成顺时针蛇形排列，然后输出。

`正确答案`：

```
1 2 3
8 9 4
7 6 5
```

---

**分析：**

对于边缘以外的任意点都有8个方向：

x和y为当前点的坐标：

* 上 a[x-1][y]
* 右上 a[x-1][y+1]
* 右 a[x][y+1]
* 右下 a[x+1][y+1]
* 下 a[x+1][y]
* 左下 a[x+1][y-1]
* 左 a[x][y-1]
* 左上 a[x-1][y-1]

---

在填充的时候应该确定一个起点然后按照方向填充.

```c++
#include <iostream>
using namespace std;

int main() {
  const int N=3;
	int a[N][N]={{1,2,3},{8,9,4},{7,6,5}};
  
  int x=0,y=-1,count=0;
  while(count < 9) {
    while((y+1)<N && a[x][y+1]!=0) {
      y++;
      cout << a[x][y] << " ";
      a[x][y] = 0;
      count++;
    }
    while((x+1)<N && a[x+1][y]!=0) {
      x++;
      cout << a[x][y] << " ";  
      a[x][y] = 0;
      count++;
    }
    while((y-1)>=0 && a[x][y-1]!=0) {
      y--;
      cout << a[x][y] << " ";  
      a[x][y] = 0;
      count++;
    }
    while((x-1)>=0 && a[x-1][y]!=0) {
      x--;
      cout << a[x][y] << " ";  
      a[x][y] = 0;
      count++;
    }
  }
  
  return 0;
}
```

---

#### 4、桶数组

桶数组指数组下标被赋予特殊含义的数组。

比如：

- 计数排序中，桶数组a[i]的值为n，表示待排序数据中有n个i
- 筛法找质数中，桶数组a[i]的值为0，表示i为质数；为1则表示i为合数

在实际应用中，桶数组常定义于全局作用域中，数组大小和值的含义都许需要随题目内容变化

---

#### 5、 环接数组

环接数组指逻辑上首尾相连接呈环状的数组，即最后一个数的下一个是第一个数，第一个数的上一个是最后一个数。实际是通过控制数组下标变化在一定范围内来实现。

比如：

- 约瑟夫环类问题
- 其它需要成环的题目

---

#### 6、例题

问题

N个猴子围成一圈，从某个猴子开始报数1-2-3-……，报M的猴子就被淘汰出圈外，游戏一直进行到圈内只剩一只猴子，称为猴子大王。

编写程序，设定N=20个猴子，编号从1到N，输入m（报m被淘汰），从第一个猴子开始报数，输出每次被淘汰的猴子编号，以及最后大王的编号。

`样例输入和输出：`

`样例输入：`

```
3
```

`样例输出：`

```
3
6
9
12
15
18
1
5
10
14
19
4
11
17
7
16
8
2
13
20
```

---

`分析`：

1. 用数组表示猴子，0表示在圈内，1表示被淘汰。下标递增求余表示环接（圈）
   ```
   pos = (pos+1)%N
   ```
2. 循环：
   - 用计数器count记录剩余的猴子数，到0表示结束
   - 用pos记录被淘汰的下标，count==0时，pos为大王
   - 表达式和状态变化：count > 0， count --
   - 执行语句:
     - s表示报数，当a[pos]==0时，s递增
     - s递增到M：
       - s设置为0下次继续递增
       - a[pos]设置为1（淘汰）
       - count递减（剩余猴子数）
       - 输出淘汰信息和大王信息
     - pos递增，求余，表示环接

---

`步骤`

1、初始化和输入

```
const int N=20;
  int a[N] = {0};
  int m;
  cout << "输入m：";
  cin >> m;
```

---

2、报数循环结构

```
int count=N, pos=0, s=0;
  while(count > 0) {
     if (a[pos] == 0) s++; //2.1. 报数：如果pos位置猴子没有被淘汰，s递增
     if (s == m) {
       // 3. 如果s递增到了m，进入淘汰过程
     }
     pos = (pos+1)%N; //2.2. 遍历猴子：pos递增并求余
  }
```

`理解`： 2.1和2.2 合起来，表示没被淘汰的猴子报数。

---

3、淘汰

```
a[pos] = 1;  //淘汰这个位置的猴子
      s = 0;  //计数器重新设置
      count--;  //剩余猴子减1
      if (count > 0)  //输出淘汰信息
      	cout << pos+1<< endl;
      else
        cout << pos+1  << endl;
```

---

参考代码：

```c++
#include <iostream>
using namespace std;

int main() {
  const int N=20;
  int a[N] = {0};
  int m;
  cin >> m;

int count=N, pos=0, s=0;
  while(count > 0) {
    if (a[pos] == 0) s++;
    if (s == m) {
      a[pos] = 1;
      s = 0;
      count--;
      cout << pos+1<< endl;
    }
    pos = (pos+1)%N;
  }

return 0;
}
```