第五章 数组与广义表 （答案版）

第五章 数组与广义表 1、 按行优先顺序列出四维数组A[2][3][2][3]所有元素在内存中的存放次序。 答：四维数组A[2][3][2][3]行优先的存放次序（下标从1开始，为简化计，以A1111代替A[1][1][1][1]）： A1111,A1112,A1113,A1121,A1122,A1123,A1211,A1212,A1213,…A2322,A2323，最右边的维度变化是最快的，最左边的维度变化最慢。 可以从二维的角度来考虑，还可以基于以下代码来分析： for( int a = 1; a <= 2; a++ ) for( int b = 1; b <= 3; b++ ) for( int c = 1; c <= 2; c++ ) for( int d =1; d <= 3; d++ ) printf( "%d ", A[a][b][c][d] ); 2、三维数组按行优先顺序存储的地址计算公式。 答：一个三维数组记为Amnp,以行优先次序顺序存储，每个元素占m存储单元，首元A111所在地址为D，则元素Aijk所在的地址计算公式为： Loc(Aijk)=D+((i-1)*n*p+(j-1)*p+k-1)*m 分析如下：第一个下标为i，则前面已有n*p*(i-1)个元素； 第二个下标j,则前面有p*(j-1)个元素； 第三个下标k时，前面有（k-1）个元素。 3、三对角矩阵，将其按行优先顺序（跳过零元素）存放于数组B[3*n-2]中，使得B[k-1]=，求： 1）用i,j表示k的下标变化公式； 2）用k表示的i,j下标变化公式。 答：设下标都从1开始 1）则k= 2) 分析：脑中有对应的三对角矩阵的图形以及行优先保存的顺序表，记住，矩阵第一行及最后一行都仅有两个元素，其余每行有三个元素，而求解本题时，不涉及最后一行。 4、若在矩阵中存放一个元素A[i-1][j-1]满足：A[i-1][j-1]是第i行元素中最小值，且又是第j列元素中最大值，则称此元素为该矩阵的一个马鞍点。假设以二维数组存储矩阵，试编写求出矩阵中所有马鞍点的算法，并分析你的算法在最坏情况下的时间复杂度。 int main() { int n, m, i, j, k, l, minn, maxx, flag ; int a[256][256]; while(1) { printf("请输入矩阵的行列数： "); scanf("%d %d",&n,&m); printf("请输入与行列数相符的矩阵： "); for(i=0; i<n; i++) for(j=0; j<m; j++) scanf("%d",&a[i][j]); flag=0; printf("马鞍点输出(输出该点所在的行数与列数)： "); for(i=0; i<n; i++) { for( j = 0; j < m; j++) { minn = a[i][j]; for( k = 0 ; k < m; k++) { if( minn > a[i][k]) break; } if( k==m) { maxx=a[i][j]; for(l=0; l<n; l++) { if(maxx<a[l][j]) break; } if(l==n) { printf("%d %d %d ",i , j ,a[i][j]); flag = 1;