chjshen 的博客
C++语法基础4-数组
chjshen 教练 LV 5 SU @ 2023-11-21 9:06:09

数组

一、数组的定义和访问

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

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

1、数组的定义

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

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	空

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

3、循环访问

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

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

4、快速初始化

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

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变量，里面存储的是空间的地址。
数组下标：按照数组类型的大小，按空间地址往后移动。

例子：

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为止，可以用循环来输入。

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

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

三、二维数组

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

1、二维数组

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

类型  数组名[行常量][列常量];
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，然后输出新的矩阵.

初始矩阵：

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]

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

#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被淘汰），从第一个猴子开始报数，输出每次被淘汰的猴子编号，以及最后大王的编号。

样例输入和输出：

样例输入：

样例输出：

分析：

用数组表示猴子，0表示在圈内，1表示被淘汰。下标递增求余表示环接（圈）
```
pos = (pos+1)%N
```
循环：
- 用计数器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;

参考代码：

#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;
}

C++语法基础4-数组

数组