二维数组的定义和操作

学习目标：
1、理解二维数组及其存储结构。
2、掌握二维数组的初始化、输入输出等基本操作。
引入：
由前面介绍可知，一维数组的元素可以是任何基本数据类型，也可以是结构体。那么，如果一维数组的每一个元素又是一个一维数组，则称这种数组为“二维数组”。

1.二维数组的定义和初始化

定义二维数组的一般格式为:
类型标识符数组名[常量表达式1][常量表达式2];
常量表达式1的值表示第一维大小，常量表达式2的值表示第二维大小，常量表达式1和常量表达式2的乘积就是二维数组的元素个数。例如:
int h[4][5];
表示数组h有4x5=20个元素,每个元素都是int型。可以把h[0]~h[3]作为一维数组的名字,数组h[0]又有5个元素h[0][0]、h[0][1]、h[0][2]、h[0][3]和h[0][4]。形式上可以把二维数组看作一张表格或一个矩阵。例如，h数组可以被看作下面这个表格：

在二维数组定义的同时,可以进行初始化赋值。例如
int a[2][3]={{1,2,3},{4,5,6}};//分行初始化
int a[2][3]={1,2,3,4,5,6}; //不分行初始化
以上两种初始化都相当于下面6个语句:
a[0][0]=1;a[0][1]=2;a[0][2]=3;
a[1][0]=4;a[1][1]=5;a[1][2]=6;
也可以给数组中的部分元素初始化。例如:
int a[2][3]={{1,2},{4}};
第一行只有2个初值,按顺序分别赋值给a[0][0]和a[0][1]，第二行的初值4赋给 a[1][0]，其他元素默认为0。
在定义二维数组时，可以省略第一维的大小，但是第二维的大小不能省略。例如，“int a[][5];”是允许的,被省略的第一维大小根据初值的个数由系统来确定。例如:
int a[][4] = {1,2,3,4,5,6,7,8,9,10,11,12};
系统根据 {} 中的元素个数，自动确定a数组的第一维大小为3。

2.二维数组的存储及元素引用

因为二维数组本质上是一维数组的每一个元素又是一个一维数组，而计算机内部存储一维数组采用的是连续存储单元。所以，二维数组的存储方式是“行优先”的连续存储，先逐个存储第0行上的所有元素，再逐个存储第1行上的所有元素，依此类推。
引用二维数组的某一个元素，格式为:
数组名[下标1][下标2]
例如:
cin>>h[0][0]; h[0][0]=h[0][0] *2; cout<<h[0][0];

3.二维数组的输人输出

二维数组的输入、输出操作也是针对每一个元素进行，结合两个维度的下标变化，用循环嵌套实现。
例1 回型方阵。(1s,256MB)
【问题描述】
输人一个正整数n，输出n*n的回型方阵。例如，n=5 时,输出:
1 1 1 1 1
1 2 2 2 1
1 2 3 2 1
1 2 2 2 1
1 1 1 1 1
【输入格式】
一行一个正整数 n,2≤n≤9。
【输出格式】
共n行,每行包含n个正整数，之间用一个空格隔开。
【输入样例】
5
【输出样例】
1 1 1 1 1
1 2 2 2 1
1 2 3 2 1
1 2 2 2 1
1 1 1 1 1
【问题分析】
定义一个二维数组a[n][n]存储回型方阵。
方法1：先给左上角的四分之一区域赋值，a[i][j]=min(i,j),右上角、左下角、右下能部分,通过下标的对称性复制过去即可。a[i][n+1-j]=a[n+1-i][j]=a[n+1-i][n+1-j]=a[i][j];。
方法2：通过从外向内赋值的方法做，先给a[1][1]-[n[n]全部赋值1，然后a[2][2]-a[n-1][n-1]全部赋值2，……共n/2圈(如果n奇数,则最后一圈就是一个数）。
方法3：通过“一圈一圈”跑动赋值的方法做，a[1][1]=1;然后按照“右下左上”
的顺序不停地跑圈，一直到所有元素赋值完毕。

#include<iostream> 
using namespace std;
int n,i,j,k,mi,ma,a[10][10];
int main(){cin >> n;for(i=1;i<=(n+1)/2;i++)for(j=1;j<=(n+1)/2;j++){a[i][j]=min(i,j);a[i][n+1-j]=a[n+1-i][j]=a[n+1-i][n+1-j]=a[i][j];}for(i=1;i<=n;i++){for(j=1;j<=n-1;j++)cout<<a[i][j]<<" ";cout<<a[i][n]<<endl;}return 0;
}

#include<iostream> 
using namespace std; 
int n,i,j,k,a[10][10]; 
int main(){cin >> n;for(k=1;k<=(n+1)/2;k++)for(i=k;i<=n+1-k;i++)for(j=k;j<=n+1-k;j++)a[i][j]=k;for(i=1;i<=n;i++){for(j=1;j<n;j++)cout<<a[i][j]<<" ";cout<<a[i][n]<<endl;}return 0;
}

#include<iostream> 
using namespace std; 
int n,i,j,k,a[10][10]; 
int main(){cin>>n;k=1; i=1; j=1;a[i][j]=1;while(k<=(n+1)/2){while(a[i][j+1]==0 && j+1<=n){j++;a[i][j]=k;}while(a[i+1][j]==0 && i+1<=n){i++;a[i][j]=k;}while(a[i][j-1]==0 && j-1>=1){j--;a[i][j]=k;}while(a[i-1][j]==0 && i-1>=1){i--;a[i][j]=k;}	k++;}for(i=1;i<=n;i++){for(j=1;j<n;j++)cout<<a[i][j]<<" ";cout<<a[i][n]<<endl;}return 0;
}

实践巩固

1.对于定义“inta[3][4];”,则对a数组元素的非法引用是（）。
A. a[0][2*1] B. a[1][3] C. a[4-2][0] D. a[0][4]
2.对二维数组进行定义,正确的语句是( )。
A. int a[3][ ] B. float a[3,2] C. double a[3][4] D. float a(3)(4)
3.对二维数组进行初始化,正确的语句是( )。
A.int a[3][ ]={{3},{3},{4}};
B.int a[ ][3]={{3},{3}.{4}};
C.int a[3][2]={{3},{3},{4},{5}};
D.int a[ ][3]={{3},{1},{1,2,3,4}}:
4. 数字三角形。(numtri,ls,256MB)
【问题描述】
读入一个正整数n，输出一个n行的数字三角形(见输出样例)。
【输入格式】
一行一个正整数n，2≤n<10。
【输出格式】
共n行，第i行包含i个正整数，每个整数占5列。
【输人样例】
5
【输出样例】
1
2 3
4 5 6
7 8 9 10
11 12 13 14 15

二维数组应用举例

例1 杨辉三角形。(triangle,1s,256MB)
【问题描述】
输人正整数，输出杨辉三角形的前n行。
【输入格式】
一行一个正整数n，1≤n≤20。
【输出格式】
共n行，第 i 行包含 i 个正整数，之间用一个空格隔开。
【输人样例】
5
【输出样例】
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
【问题分析】
定义一个二维数组tri存储杨辉三角形(其实只用到二维数组的左下部分)。对于第i行(1≤i≤n),共有i个数，其中第一个数和最后一个数都是1，其他数tri[i][j]=tri[i-1][j-1]+tri[i-1][j];。具体实现,采用“递推法”，逐行逐列给每个数组元素赋值。

#include<iostream>
#include<cstring>
#include<iomanip> 
using namespace std; 
int n,i,j,tri[21][21]; 
int main(){cin>>n;for(i=1;i<=n;i++){tri[i][1]=1; tri[i][i]=1;for(j=2;j<i;j++)tri[i][j]=tri[i-1][j-1]+tri[i-1][j];}for(i=1;i<=n;i++){for(j=1;j<i;j++) cout<<setw(5)<<tri[i][j]<<" "; cout<<setw(5)<<tri[i][i]<<endl;}return 0;
}

例2 数字三角形。(numtri,1s,256MB)
【问题描述】
读人一个正整数n，输出如下形式的数字三角形(具体见样例)。
【输入格式】
一行一个正整数n，1≤n<100。
【输出格式】
共n行，第i行包含i个正整数，每个正整数占5列。
【输入样例】
5
【输出样例】

【问题分析】定义二维数组a存储所求的数字三角形,初始化为0。对于右上角的每一个元素a[i][j]，分析发现:a[i][j]=j-i+1。具体实现采用“赋值法”。

#include<iostream>
#include<iomanip> 
using namespace std; 
int a[101][101]; 
int main(){int n,i,j; cin>>n;for(i=1;i<=n;i++)for(j=i;j<=n;j++)  a[i][j]=j-i+1; for(i=1;i<=n;i++){for(j=1;j<=n;j++)if(!a[i][j]) cout<<setw(5)<<""; else cout<<setw(5)<<a[i][j];cout<<endl;}return 0;
}

例3 奖学金。(NOIP2007普及组复赛，scholar,1s,256MB)
【问题描述】
学校得到了一笔赞助，打算拿出其中一部分为学习成绩优秀的前5名学生发奖学金。期末，每个学生都有语文、数学、英语3门课的成绩。先按总分从高到低排序，如果两个同学总分相同再按语文成绩从高到低排序；如果两个同学总分和语文成绩都相同，那么规定学号小的同学接在前面。这样，每个学生的排序是唯一确定的。
任务：先根据输人的3门课的成绩计算总分，然后按上述规则排序，最后按排名顺序输出!5名学生的学号和总分。注意，在前5名同学中，每个人的奖学金都不相同，因此必须严格按上述规则排序。例如，在某个正确答案中，如果前两行的输出数据（每行输出两个数:学号、总分）是：
7 279
5 279
这两行数据的含义是:总分最高的两个同学的学号依次是7号、5 号。这两名同学的总分都是279(总分等于输入的语文、数学、英语三科成绩之和)，但学号为7的学生语文成绩更高一些。如果前两名的输出数据是:
5 279
7 279
则按输出错误处理,不能得分。
【输人格式】
第1行为一个正整数n，表示该校参加评选的学生人数。
第2–n+1行，每行有3个用一个空格隔开的数字，每个数字都在 0–100之间。第 j 行的 3个数字依次表示学号为 j-1 的学生的语文、数学、英语的成绩。每个学生的学号按照输入顺序编号为1~n(恰好是输人数据的行号减1)。
所给的数据都是正确的,不必检验。
【输出格式】
输出共有5行,每行是两个用一个空格隔开的正整数,依次表示前5名学生的学号和总分。
【输入样例】
6
90 67 80
87 66 91
78 89 91
88 99 77
67 89 64
78 89 98
【输出样例】
6 265
4 264
3 258
2 244
1 237
【数据规模】
对于50%的数据满足：各学生的总成绩各不相同。
对于100%的数据满足:6≤n≤300。
【问题分析】
本题涉及“多关键字”排序。用一个二维数组stu保存n位同学的学号、语文、数学、英语、总分成绩，然后以总分成绩为第一关键字(降序)、语文成绩为第二关键字(降序)、学号为第三关键字(升序)排序。最后输出排序后的前5个同学的学号和总分。
方法一：二维数组

#include<iostream> 
#include<cstdio>
using namespace std;
int n,i,j,temp,stu[350][5];//stu[i][0]、stu[i][1]、stu[i][2]、stu[i][3]stu[i][4]分别表示第i个同学的学号，语文、数学、英语、总分成绩
int main(){cin>>n;for(i = 1; i <= n; i++){stu[i][0] = i;cin >> stu[i][1] >> stu[i][2] >> stu[i][3]; for(j = 1; j <= 3; j++) stu[i][4] += stu[i][j];}for(i = 1; i < n; i++){//排序for(j = i + 1; j <= n; j++)if (stu[i][4] < stu[j][4] || stu[i][4] == stu[j][4] &&stu[i][1] < stu[j][1] || stu[i][4] == stu[j][4] && stu[i][1] == stu[j][1] && stu[i][0] > stu[j][0]){temp=stu[i][0],stu[i][0]=stu[j][0],stu[j][0] = temp; temp=stu[i][1],stu[i][1]=stu[j][1],stu[i][1] = temp; temp=stu[i][2],stu[i][2]=stu[j][2],stu[j][2] = temp; temp=stu[i][3],stu[i][3]=stu[j][3],stu[j][3] = temp; temp=stu[i][4],stu[i][4]=stu[j][4],stu[j][4] = temp;}}for(i = 1; i <= 5; i++)cout << stu[i][0] << " " << stu[i][4] << endl; return 0;
}

方法二：结构体

#include<iostream>
#include<algorithm>
using namespace std;
struct stu
{int num;//编号int c,m,e; int sum;
}student[310];
bool cmp(stu a,stu b)
{if(a.sum>b.sum) return 1;else if(a.sum<b.sum) return 0;else{if(a.c>b.c) return 1;else if(a.c<b.c) return 0;else{if(a.num>b.num) return 0;else return 1;}}
}
int main()
{int n;cin>>n;for(int i=1;i<=n;i++){student[i].num=i;//录入编号cin>>student[i].c>>student[i].m>>student[i].e;//输入student[i].sum=student[i].c+student[i].m+student[i].e;//计算总分}sort(student+1,student+1+n,cmp);for(int i=1;i<=5;i++)cout<<student[i].num<<' '<<student[i].sum<<endl;return 0;
}

实践
铺地毯。(NOIP2011提高组复赛,carpet1s,256MB)

数字方阵

例1 n阶奇数幻方。(magic,1s,256MB)
【问题描述】
行列数相等的矩阵称为方阵。把正整数1~n²(n为奇数)排成一个n*n方阵,使得方阵中的每一行、每一列以及两条对角线上的数之和都相等，这样的方阵称为“n 阶奇数幻方”。
编程输入n，输出n阶奇数幻方。
【输入格式】
一行一个正整数 n,1≤n<20,n 为奇数。
【输出格式】
共n行，每行n个正整数，每个正整数占5列。
【输入样例】
5
【输出样例】
17 24 1 8 15
23 5 7 14 16
4 6 13 20 22
10 12 19 21 3
11 18 25 2 9
【问题分析】
定义一个二维数组模拟填数的过程。分析样例发现，n奇数幻方可以按下列方法生成:把数字1填在第1行的正中间a[1][n/2+1]，然后用一个循环穷举k，填入数字 2~n²，每次先找位置再填数，找位置的规律如下：如果数k填在第 i 行第 j 列，那么一般情况下,下一个数k+1该填在它的右上方,即第 i-1 行第 j+1 列。但是，有两种特殊情况；如果右上方无格子，也就是越界了(i-1=0或 j+1=n+1),那么就应该把下一个数放到第n行或者第1列;如果右上方已经有数了(a[i][j]不等于初值)，那么下一个数 k+1 就应该填在第k个数的正下方。

#include<iostream>
#include<iomanip>
#include<cstring>
using namespace std;
int dx[4]={0,1,0.-1}; 
int dy[4]={1,0,-1,0}; 
int main(){int n,i,j,k,ni,nj,a[21][21]; memset(a,0,sizeof(a)); cin>>n;i=1;j=n/2+1; a[i][j] = 1;for(k=2;k<=n*n;k++){if(k%n==1) i++; //每个斜线上n个数 else{i--; j++;if(i==0) i=n; if(j==n+1) j=1;}a[i][j]= k;}for(i=1;i<=n;i++){for(j=1;j<=n;j++)cout<<setw(5)<<a[i][j];cout << endl;}return 0;
}

例2 螺旋方阵。(square,1s,256MB)
【问题描述】
一个n行n列的螺旋方阵，如下：

#include<iostream>
#include<cstdio>
#include<iomanip>
#include<cstring>
using namespace std;
int dx[4] = {0,-1,0,1};
int dy[4] = {1,0,-1,0};
int main(){int n,i,j,k,d,a[51][51];cin >> n;for(i = 0; i <= n+1; i++)for(j = 0; j <= n+1; j++)a[i][j] = -1;for(i = 1; i <= n; i++)for(j = 1; j <= n; j++)a[i][j] = 0;	i = n; j = 1; d = 0;for(k = 1; k <= n * n; k++){a[i][j] = k;if(a[i + dx[d]][j + dy[d]] != 0) d = (d + 1) % 4;   i = i + dx[d];j = j + dy[d];}for(i = 1; i <= n; i++){for(j = 1; j <= n; j++)cout << setw(5) << a[i][j];cout << endl;}return 0;
}

例3 蛇形方阵。(square,1s,256MB)
【问题描述】
一个n行n列的蛇形方阵，如下：

#include<iostream>
#include<cstdio>
#include<iomanip>
#include<cstring>
using namespace std;
int main(){int n,i,j,k,t = 0;int a[21][21] = {0};cin >> n;for(k = 1; k <= n; k++)if(k % 2 == 0) for(i = 1; i <= k; i++){j = n - k + i;t++;a[i][j] = t;a[n + 1 - i][n + 1 - j] = n * n + 1 - t;}else for(i = k; i >= 1; i--){j = n - k + i;t++;a[i][j] = t;a[n + 1 - i][n + 1 - j] = n * n + 1 - t;}for(i = 1; i <= n; i++){for(j = 1; j <= n; j++)cout << setw(5) << a[i][j];cout << endl;}return 0;
}

例4 拐角方阵
【问题描述】
一个n行n列的拐角方阵，如下：

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