发布时间 : 星期二 文章数据结构课程 课后习题答案更新完毕开始阅读dd1568d5f46527d3250ce09f
{ }
int i=0,j=n-1; 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 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 29 //计算出每行的最小值元素，放入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]之中 if (A[i][j] 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 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 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 //输出二维数组 int k; if (i>=0 && i else return 0; //参数错误返回0 k=i*M.n+j; x=M.p[k]; return 1; //成功取值返回1 int k; if (i>=0 && i 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)); 31 数据结构简明教程 } 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(\ k=i*M.n+j; printf(\ return 1;