一、二维数组的定义

    当一维数组元素的类型也是一维数组时，便构成了“数组的数组”，即二维数组。

    二维数组定义的一般格式：

    数据类型  数组名[常量表达式1] [常量表达式2] ； 例如：int   a[4][10];

    a数组实质上是一个有4行、10列的表格，表格中可储存40个元素。第1行第1列对应a数组的a[0][0]，第n行第m列对应数组元素a[n-1][m-1]。

    说明：当定义的数组下标有多个时，我们称为多维数组，下标的个数并不局限在一个或二个，可以任意多个，

    例如：定义一个三维数组a和四维数组b：   

              int   a [100] [3] [5];     

              int   b [100] [100] [3] [5];   

    多维的数组引用赋值等操作与二维数组类似。

二、二维数组元素的引用

    二维数组的数组元素引用与一维数组元素引用类似，区别在于二维数组元素的引用必须给出两个下标。

    引用的格式为：        <数组名> [下标1] [下标2]

    说明：显然，每个下标表达式取值不应超出下标所指定的范围，否则会导致致命的越界错误。

    例如,设有定义：int  a[3] [5]; 则表示a是二维数组（相当于一个3行*5列的表格），共有3*5=15个元素，

    它们是： a[0][0]   a[0][1]   a[0][2]   a[0][3]   a[0][4]

                    a[1][0]   a[1][1]   a[1][2]   a[1][3]   a[1][4]

                    a[2][0]   a[2][1]   a[2][2]   a[2][3]   a[2][4]

    因此可以看成一个矩阵（表格），a [2] [3]即表示第3行第4列的元素。

三、二维数组的初始化

    二维数组的初始化和一维数组类似。可以将每一行分开来写在各自的括号里，也可以把所有数据写在一个括号里。

    例如： int direct [4] [2] = {{1,0},{0,1},{-1,0},{0,-1}}      

                int direct [4] [2] = {1,0,0,1,-1,0,0,-1}               //尽量不要用

四、二维数组程序设计

例1、  设有一程序

程序的输入:

2 1 3

3 3 1

1 2 1

程序的输出:

2    3    1

1    3    2

3    1    1

#include<bits/stdc++.h>
using namespace std;
int a[5][5];
int main()
{   int n=3;
    for (int i=1; i<=n; ++i)
       for (int j=1; j<=n; ++j)  cin>>a[i][j];    
    for (int i=1; i<=n; ++i)
    {  for (int j=1; j<=n; ++j)  cout<<setw(5)<<a[j][i];
       cout<<endl;
    }
    return 0;
}

 

例2、 已知一个6*6的矩阵（方阵），把矩阵二条对角线上的元素值加上10，然后输出这个新矩阵。

【分析】 矩阵即表格，是一个二维数组，有6行6列共36个元素，每个矩阵都有二条对角线，本题难点在于对角线的元素怎么确定。

#include<bits/stdc++.h>
using namespace std;
int a[7][7];
int main()
{   for (int i=1; i<=6; ++i)	       
       for (int j=1; j<=6; ++j) cin>>a[i][j];  //输入矩阵元素
    for (int i=1; i<=6; ++i)	                 //更改对角线上元素的值
       for (int j=1; j<=6; ++j)
          if ((i==j)||(i+j==7)) a[i][j]+=10;    //寻找对角线的特征
    for (int i=1; i<=6; ++i)	       //输出6行6列的矩阵元素
    {  for (int j=1; j<=6; ++j) cout<<setw(5)<<a[i][j];
       cout<<endl;
    }
    return 0;
}

 

例3、   稀疏矩阵

大部分元素是0的矩阵称为稀疏矩阵，假设有k个非0元素，则可把稀疏矩阵用K*3的矩阵简记之，其中第一列是行号，第二列是列号，第三列是该列下的非元素的值。

如： 0  0  0  5      写简记成： 1  4  5      //第1行第4列有个数是5

        0  2  0  0                         2  2  2      //第2行第2列有个数是2

        0  1  0  0                         3  2  1      //第3行第2列有个数是1

        试编程读入一稀疏矩阵，转换成简记形式，并输出。

      【分析】 本题中需要解决的主要问题是查找非零元素并记忆位置。将原始矩阵存于数组a。转换后的矩阵存于数组b，当然b数组的行数可以控制在一个小范围内。

#include<bits/stdc++.h>
using namespace std;
const int n=3,m=5;
int main()
{   int  a[n+1][m+1],b[101][4],k=0;
    for (int i=1; i<=n; ++i)        //矩阵初始
       for (int j=1; j<=m; ++j)  cin>>a[i][j]; 
    for (int i=1; i<=n; ++i)
       for (int j=1; j<=m; ++j)
         if (a[i][j]!=0)     //找到非零值，存储
         {  ++k;
            b[k][1]=i;
            b[k][2]=j;
            b[k][3]=a[i][j];
         }
    for (int i=1; i<=k; ++i)      //输出
    {  for (int j=1; j<=3; ++j) cout<<setw(3)<<b[i][j];
       cout<<endl;
    }
    return 0;
}  

例4、  打印杨辉三角形的前13行。杨辉三角形如下图：

 

    【问题分析】观察上图，大家不容易找到规律，但是如果将它转化为下图，不难发现杨辉三角形其实就是一个二维表的小三角形部分。

      假设通过二维数组yh存储，每行首尾元素为1，且其中任意一个非首位元素yh[i][j]的值，其实就是yh[i-1][j-1]与yh[i-1][j]的和，另外每一行的元素个数刚好等于行数。

      有了数组元素的值，要打印杨辉三角形，只需要控制好输出起始位置就行了。

#include<bits/stdc++.h>
using namespace std;
int main()
{  int a[11][11]={},j,i;
   a[1][1]=1;                              //设定第一行的值
   for(i=2;i<=10;++i) 
   {   a[i][1]=1;  a[i][i]=1;	          //从第二行开始推,设定每一行的首尾值为1
       for (j=2; j<=i-1; ++j)		      //当前行非首尾的数
           a[i][j]=a[i-1][j-1]+a[i-1][j]; //每个数等于上一行的二个数之和
   }
   for (i=1; i<=10; i++)
   {  if (i!=10) cout<<setw(30-3*i)<<" ";		//控制每行的起始位置，即空格数量
      for (j=1; j<=i; j++) cout<<setw(6)<<a[i][j];
      cout<<endl;        
   }
   return 0;
}

 

例5、 输入一串字符,字符个数不超过100,且以“.”结束。 判断它们是否构成回文。

      【分析】所谓回文指从左到右和从右到左读一串字符的值是一样的，如12321,ABCBA,AA等。先读入要判断的一串字符（放入数组letter中），并记住这串字符的长度，然后首尾字符比较，并不断向中间靠拢，就可以判断出是否为回文。

#include<bits/stdc++.h>
using namespace std;
int main()
{  char ch,letter[101];
   int i=0,j=1;
   cout<<"Input a string:";
   cin>>ch;
   while (ch!='.')				//读入一个字符串以'.'号结束
   {  ++i;
      letter[i]=ch;
      cin>>ch;
   }
    while ((j<i)&&(letter[j]==letter[i]))		//判断它是否是回文
    { --i; ++j; }
       if (j>=i) cout<<"Yes"<<endl;
       else   cout<<"No"<<endl;
    return 0;
}   

例6、  蛇形填数

    在n*n方阵里填入1,2,3,…,n*n，要求填成蛇形。例如n=4时方阵为：  

      10 11 12  1  

      9  16 13  2  

      8  15 14  3    

      7    6   5  4    

     上面的方阵中，多余的空格只是为了便于观察规律，不必严格输出，n<=8。

【分析】：    类比数学中的矩阵，我们可以用一个所谓的二维数组来储存题目中的方阵。只需声明一个int a[MAXN][MAXN]，就可以获得一个大小为MAXN×MAXN的方阵。在声明时，两维的大小不必相同，因此也可以声明int a[30][50]这样的数组，第一维下标范围是0,1,2,…,29，第二维下标范围是0,1,2,…,49。     让我们从1开始依次填写。设“笔”的坐标为(x,y)，则一开始x=0，y=n-1，即第0行，第n-1列（别忘了行列的范围是0到n-1，没有第n列）。“笔”的移动轨迹是：下，下，下，左，左，左，上，上，上，右，右，下，下，左，上。总之，先是下，到不能填了为止，然后是左，接着是上，最后是右。“不能填”是指再走就出界（例如4→5），或者再走就要走到以前填过的格子（例如12→13）。如果我们把所有格子初始为0，就能很方便地加以判断。

#include<bits/stdc++.h>
using namespace std;
#define MAXN 10
int a[MAXN][MAXN];
int main()
{	int n,x,y,tot=0;
	scanf("%d",&n);
	memset(a,0,sizeof(a));
	tot=a[x=0][y=n-1]=1;
	while (tot<n*n)
	{   while (x+1<n && !a[x+1][y]) a[++x][y]=++tot;
        while (y-1>=0 && !a[x][y-1]) a[x][--y]=++tot;
        while (x-1>=0 && !a[x-1][y]) a[--x][y]=++tot;
        while (y+1<n && !a[x][y+1]) a[x][++y]=++tot;
    }
    for(x=0;x<n;++x)
    {   for (y=0;y<n;++y) printf("%3d",a[x][y]);
	printf("\n");
    }
    return 0;	
}

        【说明】：这段程序充分利用了C++语言简洁的优势。首先，赋值x=0和y=n-1后马上要把它们作为a数组的下标，因此可以合并完成；tot和a[0][n-1]都要赋值1，也可以合并完成。这样，我们用一条语句完成了多件事情，而且并没有牺牲程序的可读性，这段代码的含义显而易见。

         那4条while语句有些难懂，不过十分相似，因此只需介绍其中的第一条：不断向下走，并且填数。我们的原则是：先判断，再移动，而不是走一步以后发现越界了再退回来。这样，我们需要进行“预判”，即是否越界，以及如果继续往下走会不会到达一个已经填过的格子。越界只需判断x+1<n，因为y值并没有修改；下一个格子是(x+1,y)，因此只需a[x+1][y]==0，简写成!a[x+1][y]（其中!是“逻辑非”运算符）。

       细心的也许会发现这里的一个“潜在bug”；如果越界，x+1会等于n，a[x+1][y]将访问非法内存！幸运的是，这样的担心是不必要的。&&是短路运算符。如果x+1<n为假，将不会计算!a[x+1][y]，也就不会越界了。     

      为什么是++tot而不是tot++，留给同学们思考。

 

五、二维数组【上机练习】