wzf2000 C/C++ 语法教程（6）——数组（1）
Contents
数组
回顾
上次讲了 if 和 for 、while 等语句，重新声明下其中 condition 的作用，也就是对于为 $0$ 的不执行，非 $0$ 的执行。
但是，光有 for 等循环语句并不能满足所有的要求，像是一些拥有 $n$ 个变量的问题，还是难以解决。
所以这次我们来讲一下数组的问题。
数组的引入
在程序中可能会遇到这样一种问题，比如让你计算 $n$ 个数的方差等等。
在方差公式中，你会发现存在 $x_1,x_2,\cdots,x_n$ 等类似的变元。
那么在程序中，我们也希望拥有类似的存在，可以使得我们配合 for 语句中的循环变量 $i$（只是举例）获取或者修改 $x_i$ 的值。
也就是我们需要一种定义带下标的相互关联的一批变量的办法。
我们称之为数组。
数组：带下标的相互关联的变量序列
数组是计算机语言提供的组织多个数据的一种重要方式：
- 提供了多个同类型的数据（值）在内存中连续存放的工具；
- 提供了对大量内存单元进行高效“命名”的途径；
- 提供了在程序运行过程中动态改变“变量名称”的手段；
- 是一些重要算法思想的实现基础。
（上述引用自徐明星老师的课件）
数组的使用
数组的定义
一般我们采用 类型说明符 数组名[常量表达式]; 的方式定义数组。
或者说 TYPE array_name[const_expr];
Type 就是前面所说的各种类型，比如 int、double、char 等等。
array_name 相当于变量名，命名规范完全相同（当然数组名跟变量名也不能相同）。
const_expr 表示数组大小，一般就是一个常数，称其为常量表达式，是因为计算机也能“看得懂”形如 1000+9 和4*10009 的“常数”。
具体可以看一下以下的例子：
const int N=10009;//N 是常量
char ch[1009];
int _[N<<2];
double Above1[5000/10];
理论上来讲，定义数组的大小也可以用一些已给出确定的值的变量。比如：
int n=100;
int a[n];
但是，我们非常不建议这么使用，不仅是因为难以分析内存，也是因为不同的编译器可能导致奇怪的问题。
练习题：
下面哪些定义符合数组定义的规范：
INT stu[4000];
double SCORE[50+4];
char name(10);
float ______[1];
数组中的元素
数组中每个元素所在的内存单元，可以通过 数组名[位置下标] 来访问（赋值、读取）。在 C/C++ 语言中，数组元素的位置下标从 $0$ 开始计数。
也就是说，对于数组 int a[10];，其定义了一个含有 $10$ 个 int 型变量的数组，各元素访问方法为：
a[0],a[1],...,a[9]
注意其中每一个都相当于一个单独的变量，而且这里是可以使用形如 a[i] 的方法访问对应元素的（$i$ 是一个整型变量），其赋值与运算和普通变量无异。
数组的初始化
初始化只能在定义同时进行。
一般形式为：
type_name array_name[N]={v1,v2,v3,...,vN};
（省略号是真的表示省略也就是并不是程序里用的）
其中，后面的 vi 每个都是一个常量表达式，依次对应于 array_name[0] 到 array_name[N-1]。
当然，也可以只在初始化时赋值一部分，这样后面未赋值的部分编译器会初始化为 $0$。
特别注意，当定义数组并初始化时，可以省略数组大小 const_expr。
举例如下：
int a[5]={1,3,4,2,5};
char b[5]={'C','h','i','n','a'};
double c[]={0.1,0.2};
int prime[101]={1,1};//后面的 prime[2] 至 prime[100] 均为 0
特别地，如果是 char 类型的数组，则可以使用：
char ch[6]="China";
注意，数组长度至少为字符串长度加一，在将字符填充完后，之后数组将以 '\0'（字符数组结束标志）填充。
练习题：
下面这种写法是否正确：
int b[5];
b={1,2,3,4,5};
数组的输入输出（cin 和 cout）
cin>>ch; 和 cout<<ch; 可用于读入和输出一个字符数组。
对于其它类型的数组 $a$，cout<<a; 会输出其数组变量地址（也就是 a[0] 的地址）。
本章习题
- 输出 $200$ 以内的所有质数，请使用数组的方法实现（不要抄网上的素数表）。思路提示：一个合数总能表示成另一个数的 $k$ 倍（$k \ge 2$），所以可以将除了 $1$ 每个数的 $k$ 倍全部排除（欧拉筛）。（还是没有看懂或者难以实现可以联系作者）
此题没有输入。
输入 $n$ 和 $n$ 个整数 $a_i$，保证在
int范围内，请将它们按照从小到大的顺序输出。思路提示：先找到最小的，放到a[0]，再重复进行以上类似过程（类似冒泡排序）。样例输入：
5 1 3 4 2 5样例输出：
1 2 3 4 5- 附加题（选做题）：输入 $n$ 和 $n$ 个整数 $a_i$，再输入 $m$ 和 $m$ 个整数 $b_i$，表示 $m$ 次询问，每次尝试在 $a_i$ 中查找 $b_i$，如果不存在输出
NO，否则输出它在 $n$ 个整数中从小到大排名第几，保证 $a_i$ 互不相同。思路提示：先同 $2$，然后可以采取顺序查找或者二分（折半）查找的方法，我们希望你能采用二分查找，具体方法可以自行学习或者参考高中数学中算无理数 $\sqrt{2}$ 的二分方法类比得出（之后会在算法教程中涉及）。样例输入：
5 1 3 4 2 5 3 6 2 5样例输出：
NO 2 5
其中 2、3 题的 $n$ 均小于等于 $1000$，第 3 题的 $m$ 小于等于 $100000$。
No Comments