第一节  一维数组
第二节  二维数组
第三节  字符数组和字符串类型
一、为什么要使用数组
　　通过前面几章的学习，我们已经可以编写程序来解决各种相当复杂的问题了，但是当需要处理的数据比较多时，仅依靠前面的知识是不够的，即使简单的问题也可能需要比较复杂的程序来处理。请看下面的例子：
　　例题：输入50个学生的某门课程的成绩，打印出低于平均分的学生序号与成绩。
　　【分析】在解决这个问题时，虽然可以通过一个变量来累加读入的50个成绩求出学生的总分，进而求出平均分。但因为只有读入最后一个学生的分数后才能求得平均分，并且要求打印出低于平均分的学生序号和成绩，故必须把50个学生的成绩都保留起来，然后逐个和平均分比较，把低于平均分的成绩打印出来。如果，用简单变量a1，a2,…，a50存储这些数据，要用50个变量保存输入的数据，程序片断如下：
　　cin>>a1>>a2>>…>>a10;
　　…
　　cin>>a41>>a42>>…>>a50;
注意，如果真正要像上面这样编写程序，则上面的所有省略号必须用完整的语句写出来。可以看出，这样的程序是多么繁琐。如果说处理的数据规模达到成千上万，上面的例子单单读入就会异常复杂，电脑的优势没有得到体现。
　　从以上的讨论可以看出，如果只使用简单变量处理大量数据，就必须使用大量只能单独处理的变量，即使是简单问题也需要编写冗长的程序。
　　选手们可能已经看出，我们需要把一大批具有相同性质的数据组合成一个新类型的变量，可以用简单的程序（比如循环50次）对这个新变量的各个分量进行相同的处理，每个分量仍然保留单个变量的所有性质（在上面的例子中，各分量是整型变量或实型变量的性质）。
　　
如果能像数学中使用下标变量ai形式表示这50个数，则问题就容易实现。在C++语言中，具有下标性质的数据类型是数组。如果使用数组，上面的问题就变得十分简单、清晰。例如，读入50个学生的成绩，只需写如下语句即可：
　　 for (int i=1;i<=50;++i)
　　      cin>>a[i];
　　在这里引用了带下标的变量（分量变量称为数组元素）a[i]来代替a1,a2…,a50,方括号中的i称为下标，当循环变量i=1时a[i]就是a[1]；当i=2时a[i]就是a[2]……；当i=50时a[i]就是a[50]。输入的时候，让i从1变化到50，循环体内输入语句中的a[i]也就分别代表了a1,a2…,a50这50个带下标的变量。这样上述问题的程序可写为：
　　tot = 0;		// tot存储50个学生的总分
　　for (int i=1;i<=50;++i)	// 循环读入每一个学生的成绩，并把它累加到总分中
　　{
　　  cin>>a[i];
　　  tot+=a[i];
　　}
　　ave= tot/50;  	               //计算平均分
　　for (int i=1;i<=50;++i)
　　　if (a[i]<ave) cout<<"No. "<<i<<" "<<a[i];
　　//如果第i个同学成绩小于平均分，则将输出这个学生的序号和成绩。

       要在程序中使用下标变量，必须先说明这些下标变量的整体为数组，即数组是若干个同名（如上面的下标变量的名字都为a）下标变量的集合，这些变量的类型全部一致。
二、一维数组的定义
　　当数组中每个元素只带有一个下标时，我们称这样的数组为一维数组。
　　数组的定义格式如下：
　　　类型标识符  数组名[常量表达式]
　　说明：
　　①数组名的命名规则与变量名的命名规则一致。
　　②常量表达式表示数组元素的个数。可以是常量和符号常量，但不能是变量。
　　例如：
　　int a[10];           //数组a定义是合法的
    int b[n];            //数组b定义是非法的

三、一组数组的引用
　　通过给出的数组名称和这个元素在数组中的位置编号(即下标)，程序可以引用这个数组中的任何一个元素。
　　一维数组元素的引用格式：
　　　　数组名[下标]
　　例如：
　　int a[10];
    其中，a是一维数组的数组名，该数组有10个元素，依次表示为：
    a[0],a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8],a[9]。
    需要注意的是：a[10]不属于该数组的空间范围。
    当在说明部分定义了一个数组变量之后,C++编译程序为所定义的数组在内存空间开辟一串连续的存储单元。例如：
上例中的a数组在内存的存储如表所示：
   a数组共有10个元素组成，在内存中10个数组元素共占10个连续的存储单元。a数组最小下标为0，最大下标9。按定义a数组所有元素都是整型变量。
      再次提醒注意：类型和变量是两个不同概念，不能混淆。就数组而言，程序的执行部分使用的不是数组类型而是数组变量。
说明：
       (1)下标可以是整型常量或整型表达式。如果使用表达式作为下标，就要计算表达式的值以确定下标。
　　(2)C++语言中，每个数组第一个元素的下标都是0，因此第一个元素为第0个数组元素。
　　(3)C++语言只能逐个引用数组元素，而不能一次引用整个数组。
　　例如：int a[100],b[100];   a=b;这样的写法是非法的。
　　(4)数组元素可以像同类型的普通变量那样使用，对其进行赋值和运算的操作，和普通变量完全相同。
例如： c[10]=34;实现了给c[10]赋值为34。
四、一维数组的初始化
    数组的初始化可以在定义时一并完成。格式：
    　类型标识符  数组名[常量表达式]={值1，值2，…}
　　例如：
　　　int a[5]={1,2,3,4,5}
　　说明：
　　(1)在初值列表中可以写出全部数组元素的值，也可以写出部分。例如，以下方式可以对数组进行初始化：
　　int x[10]={0,1,2,3,4};
　　该方法一次仅对数组的前5个元素依次进行初始化。
　　(2)对数组元素全部初始化为0，可以简写为：{0}。
　　例如：
       int a[5]={0}; 将数组a的5个元素都初始化为0。

五、一维数组的应用
　　例5.1  输入n个数,要求程序按输入时的逆序把这n个数打印出来，已知整数不超过100个。也就是说，按输入相反顺序打印这n个数。
　　【分析】我们可定义一个数组a用以存放输入的n个数, 然后将数组a中的内容逆序输出。
#include<cstdio>
int a[100];
int main()
{
    int x,n=0;
    while(scanf("%d",&x)==1) a[n++]=x;  //相当{a[n]=x;n++;}
    for (int i=n-1;i>=1;--i)
        printf("%d ",a[i]);  //注意%d后面有一个空格，保证行首行尾均无空格
    printf("%d\n",a[0]);
    return 0;	
}
【说明】：
    语句int a[100]声明了一个包含100个整型变量的数组，它们是：a[0]，a[1]，a[2]，…，a[99]。注意，没有a[100]。在上述程序中，数组a被声明在main函数的外面。只有放在外面时，数组a才可以开得很大；放在main函数内时，数组稍大就会异常退出。它的道理将在后面讨论，只需要记住规则即可。
    数组不能够进行赋值操作：如果声明的是int a[MAXN]，b[MAXN],是不能赋值b=a的(Pascal语言可以的)。如果要从数组a复制k个元素到数组b，可以这样做：memcpy(b,a,sizeof(int)*k)。当然了，如果数组a和b都是浮点型的，复制时要写成memcpy(b,a,sizeof(double)*k)。如果需要把数组a全部复制到数组b中，可以写得简单一些：memcpy(b,a,sizeof(a))。使用memcpy函数要包含头文件cstring。
   例5.2  将a数组中第一个元素移到最后数组末尾,其余数据依次往前平移一个位置。
　　【分析】为完成题目所要求的操作，其算法应该包括以下几个主要步骤： 
　　①把第一个元素的值取出放在一个临时单元 temp中； 
　　②通过 a[2]→a[1], a[3]→a[2], a[4]→a[3]，……， a[n]→a[n-1],实现其余元素前移 
　   ③将 temp值送入a[n]. 
#include<iostream>
#include<iomanip>			   //调用setw函数需注明使用该库
const int n=10;
using namespace std; 
int a[n],temp; 
int main()
{
    cout<<"read "<<n<<" datas"<<endl;
　　for (int i=0; i<n; ++i) cin>>a[i];
　　temp=a[0];
　　for (int i=0; i<n-1; ++i) a[i]=a[i+1];
　　a[n-1]=temp;
　　cout<<"Result:"<<endl;
　　for (int i=0; i<n; ++i) cout<<setw(3)<<a[i];   //setw函数控制输出场宽
　　return 0;	 
 }
运行结果 : 
read 10 datas: 
•  1 2 3 4 5 6 7 8 9 10 
Result: 
•  2 3 4 5 6 7 8 9 10 1 
例5.3  宾馆里有一百个房间，从1-100编了号。第一个服务员把所有的房间门都打开了，第二个服务员把所有编号是2的倍数的房间“相反处理”，第三个服务员把所有编号是3的倍数的房间作“相反处理”…，以后每个服务员都是如此。当第100个服务员来过后，哪几扇门是打开的。（所谓“相反处理”是：原来开着的门关上，原来关上的门打开。）
　　【分析】此题较简单，用a[1],a[2],…,a[n]表示编号为1，2，3，…,n的门是否开着。模拟这些操作即可，参考程序如下：
#include<cstdio>
#include<cstring>
#define MAXN 100+10
int a[MAXN];
int main()
{
	int n,k,first=1;
	memset(a,0,sizeof(a));
              for (int i=1;i<=100;++i)
	  for (int j=1;j<=100;++j)
	     if (j%i==0) a[j]=!a[j];
for (int i=1;i<=100;++i)
      if (a[i])
      {
        	 if(first) first=0; 
                     else printf(" ");
               printf("%d",i);  
      }
printf("\n");
return 0;	
}

运行结果：
1　4  9  16  25  36  49  81  100
【说明】：
    memset(a,0,sizeof(a))的作用是把数组a清零，它在cstring中定义。虽然也能用for循环完成相同的任务，但是用memset又方便又快捷。另一个技巧在输出：为了避免输出多余空格，设置了一个标志变量first，可以表示当前要输出是否为第一个。第一个变量前不应该有空格，但其他都有。
例5.4  约瑟夫问题：N个人围成一圈，从第一个人开始报数，数到M的人出圈；再由下一个人开始报数，数到M的人出圈；…输出依次出圈的人的编号。N，M由键盘输入。
　　【分析】 （1）由于对于每个人只有出圈和没有圈两种状态，因此可以用布尔型标志数组存储游戏
                                过程中每个人的状态。不妨用true表示出圈，false 表示没有出圈。
         	    （2）开始的时候，给标志数组赋初值为false，即全部在圈内。
　　	    （3）模拟报数游戏的过程，直到所有的人出圈为止。
　程序如下：
　　#include<iostream>
　　using namespace std;
　　int n,m,s,f,t;
　　bool a[101];		//根据题意开出数组大小
　　int main()
       {
            cin>>n>>m;		//共n人，报到m出圈
            cout<<endl;
            for (t=1;t<=n;++t) a[t]=false;        //等同于memset(a,0,sizeof(a)),要调用cstring库
            f=0;  t=0;  s=0;                             //刚开始所有变量默认值也是0,或者用f=t=s=0;
           do
           {
	++t;		//逐个枚举圈中的所有位置
         	if (t==n+1) t=1;	//数组模拟环状，最后一个与第一个相连
         	if (a[t]==false) ++s;	//第t个位置上有人则报数
         	if (s==m) 		//当前报的数是m
         	{
   	    s=0;		//计数器清零
             	    cout<<t<<" ";	//输出出圈人的编号
             	    a[t]=true;		//此处的人已出圈，设置为空
             	    f++;	 	//出圈的人数增加一个
               }
            } while(f!=n);		//直到所有的人都出圈为止
         return 0;
　　}

　　运行结果：
　　输入： 8  5
　　输出： 5 2 8 7 1 4 6 3
　　这是一个在算法设计上很有名气的经典约瑟夫（Josephu）问题，它有很多变例。如猴子选大王、持密码报数、狐狸追兔子等（见上机练习）。
例5.5  输入十个正整数,把这十个数按由大到小的顺序排列。（选择排序 ）
　　将数据按一定顺序排列称为排序，排序的算法有很多，其中选择排序是一种较简单的方法。
【问题分析】
　　要把十个数按从大到小顺序排列，则排完后，第一个数最大，第二个数次大，……。因此，我们第一步可将第一个数与其后的各个数依次比较，若发现，比它大的，则与之交换，比较结束后，则第一个数已是最大的数。同理，第二步，将第二个数与其后各个数再依次比较，又可得出次大的数。如此方法进行比较，最后一次，将第九个数与第十个数比较，以决定次小的数。于是十个数的顺序排列结束。
　　如对5个进行排序，这个五个数分别为8　2　9　10　5。按选择排序方法，过程如下：
　　初始数据　：8　2　9　10　5
　　第一次排序：8　2　9　10　5
　　　　　　　　9　2　8　10　5
　　　　　　　　10　2　8　9　5
　　　　　　　　10　2　8　9　5
　　第二次排序：10　8　2　9　5
　　　　　　　　10　9　2　8　5
　　　　　　　　10　9　2　8　5
　　第三次排序：10　9　8　2　5
　　　　　　　　10　9　8　2　5
　　第四次排序：10　9　8　5　2
　　对于十个数，则排序要进行9次。
程序如下：
　#include<iostream>
　#include<iomanip>
　using namespace std;
　int t,a[11];
　int main()
　{
　　cout<<"Input 10 intergers:"<<endl;	 
                                //读入10个初始数据
　    for (int i=1; i<=10; ++i) cin>>a[i];
　　cout<<endl;
　    for (int i=1; i<=9; ++i)               //进行9次排序
　　   for (int j=i+1; j<=10; ++j) 
                                //将第i个数与其后所有数比较
　　　     if (a[i]<a[j]) { t=a[i]; a[i]=a[j]; a[j]=t;}
                                //若有比a[i]大,则与之交换
　　　    for (int i=1;i<=10;++i)
                    cout<<setw(5)<<a[i];
　　　    return 0;
　　　}


运行结果：
输入： 8 67 52 189 74 5 58 9 23 41
输出： 189   74   67   58   52   41   23    9    8    5
例5.6  编程输入十个正整数，然后自动按从大到小的顺序输出。（冒泡排序）
【问题分析】
　　①用循环把十个数输入到A数组中；
　　②从A[1]到A[10]，相邻的两个数两两相比较，即：
　　  A[1]与A[2]比，A[2]与A[3]比，……A[9]与A[10]比。
　　只需知道两个数中的前面那元素的标号，就能进行与后一个序号元素（相邻数）比较，可写成通用形式A[i]与A[i+1]比较，那么，比较的次数又可用1～( n-i )循环进行控制(即循环次数与两两相比较时前面那个元素序号有关) ；
　　③在每次的比较中，若较大的数在后面，就把前后两个对换，把较大的数调到前面，否则不需调换位置。
　　下面例举5个数来说明两两相比较和交换位置的具体情形：
　　   5   6   4   3   7  
         5和6比较，交换位置，排成下行的顺序；
　　   6   5   4   3   7         
         5和4比较，不交换，维持同样的顺序；
　　   6   5   4   3   7         
         4和3比较，不交换，顺序不变
　　   6   5   4   3   7         
         3和7比较，交换位置，排成下行的顺序；
　　   6   5   4   7   3         
         经过（1～（n-1））次比较后，将3调到了末尾
　　
经过第一轮的1～ (N-1)次比较，就能把十个数中的最小数调到最末尾位置，第二轮比较1～ (N-2)次进行同样处理，又把这一轮所比较的“最小数”调到所比较范围的“最末尾”位置；……；每进行一轮两两比较后，其下一轮的比较范围就减少一个。最后一轮仅有一次比较。在比较过程中，每次都有一个“最小数”往下“掉”，用这种方法排列顺序，常被称之为“冒泡法”排序。
程序如下：
　#include<iostream>
　#include<iomanip>
　using namespace std;
　const int n=10;
　int t,a[n+1];	        //定义数组
　int main()
　{
　   for (int i=1; i<=n; ++i) cin>>a[i];			                           //输入十个数
　    for (int j=1; j<=n-1; ++j)				        //冒泡法排序
　    for (int i=1; i<=n-j; ++i)  //两两相比较           
            if (a[i]<a[i+1])            //比较与交换
　           {t=a[i]; a[i]=a[i+1]; a[i+1]=t;}
　    for (int i=1; i<=n; ++i)               
               cout<<setw(5)<<a[i];
                                    //输出排序后的十个数
　    cout<<endl;
　    return 0;
　}

运行结果：
输入： 2 5 8 6 12 34 65 22 16 55
输出： 65  55  34  22  16   12   8   6   5   2
例5.7  用筛法求出100以内的全部素数，并按每行五个数显示。
【问题分析】
　　　⑴ 把2到100的自然数放入a[2]到a[100]中（所放入的数与下标号相同）；
　　　⑵ 在数组元素中，以下标为序，按顺序找到未曾找过的最小素数minp,和它的位置p（即下标号）；
　　　⑶ 从p+1开始，把凡是能被minp整除的各元素值从a数组中划去（筛掉），也就是给该元素值置 0；
　　　⑷ 让p=p+1，重复执行第②、③步骤，直到minp>floor(sqrt(N)) 为止；
　　　⑸ 打印输出a数组中留下来、未被筛掉的各元素值，并按每行五个数显示。
　　用筛法求素数的过程示意如下（图中用下划线作删去标志）：
① 2 3 4 5 6 7 8 9 10 11 12 13 14 15…98 99 100      //置数
② 2 3 4 5 6 7 8 9 10 11 12 13 14 15…98 99 100      //筛去被2整除的数
③ 2 3 4 5 6 7 8 9 10 11 12 13 14 15…98 99 100      //筛去被3整除的数
　　                 ……
    2 3 4 5 6 7 8 9 10 11 12 13 14 15…98 99 100      
//筛去被整除的数
程序如下：
　#include<iostream>
　#include<math.h>    
              //在Dev C++中可调用数学函数库cmath
　#include<iomanip>
　using namespace std;
　const int n=100;
　int t;
　bool a[n+1];
　int main()
　{
　  for (int i=0; i<=n; ++i) a[i]=true;      
        //等同于memset(a,1,sizeof(a)) ,
          要调用cstrin库
　    a[1]=false;
　    for (int i=2; i<=sqrt(n); ++i)
　      if (a[i])
　        for (int j=2; j<=n/i; ++j)
　          a[i*j]=false;
　    t=0;
　    for (int i=2; i<=n; ++i)
　      if (a[i]) 
　      {
　          cout<<setw(5)<<i;
　          t++;
　          if (t%5==0) cout<<endl;
　      }
　     return 0;
　}
【上机练习5.1】
1、国际象棋盘中，第1格放1粒米，第2格放2粒米，第3格放4粒米，第4格放8粒米，第5格放16粒米，．．．．．．问：16个格子总共可以放多少粒米？
　【分析】第i个格子可放多少粒米：2i–1
2、输出斐波列契数列的前N项（5个1行）
    0  1   1   2   3   5   8   13   21   ．．．．．．．．．．
3、输入N个整数，找出最大数所在位置，并将它与第一个数对调位置。
4、将一个数组中的所有元素倒序存放 。
　【分析】A[1]←→A[N]   A[2] ←→A[N-1]…… A[I] ←→A[J] 
          I 从1开始，每交换1次，I 加1；直到 I = N  DIV 2
5、读入n个数，打印其中的最大数及其位置号。
6、有52张朴克牌，使它们全部正面朝上。从第2张牌开始，把凡是2的倍数位置上的牌翻成正面朝下；接着从第3张牌开始，把凡是3的倍数位置上的牌正面朝上的翻成正面朝下，正面朝下的翻成正面朝上；接着从第4张牌开始，把凡是4的倍数位置上的牌按此规律翻转；依此类推，直到第1张要翻的牌是第52张为止。统计最后有几张牌正面朝上，并打印出它们的位置。
7、围绕着山顶有10个洞，一只狐狸和一只兔子各住一个洞。狐狸总想吃掉兔子。一天兔子对狐狸说：“你想吃我有一个条件，先把洞从1～10编上号，你从10号洞出发，先到1号洞找我；第二次隔1个洞找我，第三次隔2个洞找我，以后依此类推，次数不限。若能找到我，你就可以饱餐一顿。不过在没有找到我以前不能停下来。”狐狸满口答应就开始找了，它从早到晚找了1000次洞，累得昏了过去也没有找到兔子。请问，免子躲在几号洞里？【答案】2，4，7，9