内容发布更新时间 : 2025/3/29 13:57:59星期一 下面是文章的全部内容请认真阅读。
}
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
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
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
k=i*M.n+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));
数据结构简明教程
}
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;