数据结构课程课后习题集答案解析

}

ElemType tmp; while (i

while (A[i]!=0) i++; while (A[j]==0) j--; if (i

tmp=A[i]; A[i]=A[j]; A[j]=tmp;

（2）已知一个n×n矩阵B按行优先存于一个一维数组A[0..n(n-1)]中，试给出一个就地算法将原矩阵转置后仍存于数组A中。

解：矩阵转置是将矩阵中第i行第j列的元素与第j行第i列的元素互换位置。因此先应确定矩阵与一维数组的映射关系：bi,j在一维数组A中的下标为i～n+j，bj,i在一维数组A中的下标为j×n+i。对应的算法如下：

void trans(ElemType A[], int n) { }

int i, j; ElemType tmp; for (i=0;i

for (j=0;j

tmp=A[i*n+j]; A[i*n+j]=A[j*n+i]; A[j*n+i]=tmp;

（3）如果矩阵A中存在这样的一个元素A[i][j]满足条件：A[i][j]是第i行中值最小的元素，且又是第j列中值最大的元素，则称之为该矩阵的一个马鞍点。设计一个算法求出m×n的矩阵A的所有马鞍点。

解：先求出每行的最小值元素，放入min[m]之中，再求出每列的最大值元素，放入max[n]之中，若某元素既在min[i]中，又在max[j]中，则该元素A[i][j]便是马鞍点，找出所有这样的元素，即找到了所有马鞍点。实现程序如下：

#include #define m 3 #define n 4

void minmax(int A[m][n]) {

int i, j, have=0; int min[m], max[n]; for (i=0;i

min[i]=A[i][0]; for (j=1;j

if (A[i][j]

//计算出每行的最小值元素，放入min[m]之中

数据结构简明教程

} void main() { }

int a[m][n]; int i, j;

for (i=0;i

for (j=0;j

scanf(\

//调用minmax()找马鞍点

}

for (j=0;j

for (i=0;i

//判定是否为马鞍点

for (j=0;j

if (min[i]==max[j]) { }

printf(\显示马鞍点 have=1;

max[j]=A[0][j]; for (i=1;i

if (A[i][j]>max[j])

max[j]=A[i][j];

//计算出每列的最大值元素，放入max[1..n]之中

min[i]=A[i][j];

if (!have)

printf(\没有鞍点\\n\

minmax(a);

（4）设有二维数组A[m][n]，其元素为整数，每行每列都按从小到大有序，试给出一个算法求数组中值为x的元素的行号i和列号j。设值x在A中存在，要求比较次数不多于m+n次。

解：由于算法要求比较次数不多于m+n次，因此不能按行扫描数组的每一元素，否则比较次数在最坏情况下可达m×n次。根据该数组的特点可从矩阵右上角按副对角线方向向左下角查找，算法如下：

int find(int a[M][N],int x,int m,int n) {

int i=0,j=n-1,flag=0; while (i=0)

if (a[i][j]!=x) { }

if (a[i][j]>x) j--; else i++;

flag=1; break;

//修改列号

//修改行号 //a[i][j]==x

else

return flag;

}

上机实验题5

采用一维动态数组模拟二维数组的操作，即将一个二维数组的元素存放在一个一维数组中，一维数组的空间根据二维数组的大小动态分配。设计一个算法实现两个二维数组的相加运算。并用相关数据进行测试。

解：对应的程序如下：

#include #include typedef int ElemType; typedef struct {

ElemType *p; int m,n;

//存放二维数组元素 //存放二维数组的行数和列数

//初始化二维数组M

} Mat2;

void InitMat(Mat2 &M,int x,int y) { }

int Setij(Mat2 &M,int i,int j,ElemType x) //置二维数组(i,j)位置值为x { }

int Getij(Mat2 M,int i,int j,ElemType &x) //取二维数组(i,j)位置值并赋给x { }

void DispMat(Mat2 M) {

int i,j,k;

for (i=0;i

for (j=0;j

k=i*M.n+j;

//输出二维数组

int k;

if (i>=0 && i=0 && j

else return 0;

//参数错误返回0

k=i*M.n+j; x=M.p[k]; return 1;

//成功取值返回1

int k;

if (i>=0 && i=0 && j

else return 0;

//参数错误返回0

k=i*M.n+j; M.p[k]=x; return 1;

//成功赋值返回1

M.m=x; M.n=y;

M.p=(ElemType *)malloc(x*y*sizeof(ElemType));

数据结构简明教程

}

int AddMat(Mat2 A,Mat2 B,Mat2 &C) { }

void DestroyMat(Mat2 M) { } void main() { }

Mat2 A,B,C; InitMat(A,2,3);

Setij(A,0,0,1); Setij(A,0,1,1); Setij(A,0,2,1); Setij(A,1,0,1); Setij(A,1,1,1); Setij(A,1,2,1); printf(\InitMat(B,2,3);

Setij(B,0,0,2); Setij(B,0,1,2); Setij(B,0,2,2); Setij(B,1,0,2); Setij(B,1,1,2); Setij(B,1,2,2); printf(\InitMat(C,2,3); printf(\AddMat(A,B,C);

printf(\DestroyMat(A); DestroyMat(B); DestroyMat(C); free(M.p);

//销毁二维数组M

int i,j; ElemType x,y;

if (A.m!=B.m || A.n!=B.n)

return 0;

//两数组行列数不同返回0

for (i=0;i

for (j=0;j

Getij(A,i,j,x); Getij(B,i,j,y); Setij(C,i,j,x+y);

//两个二维数组相加运算

}

}

printf(\

printf(\

return 1;