数据结构考研分类复习真题 第五章 答案[31]

[题目分析]题目中要求矩阵两行元素的平均值按递增顺序排序由于每行元素个数相等按平均值排列与按每行元素之和排列是一个意思所以应先求出各行元素之和放入一维数组中然后选择一种排序方法对该数组进行排序注意在排序时若有元素移动则与之相应的行中各元素也必须做相应变动

void Translation（float *matrixint n）

//本算法对n×n的矩阵matrix通过行变换使其各行元素的平均值按递增排列

{int ijkl

float summin //sum暂存各行元素之和

float *p *pi *pk;

for(i=; i<n; i++)

{sum=; pk=matrix+i*n; //pk指向矩阵各行第个元素

for (j=; j<n; j++){sum+=*(pk); pk++;} //求一行元素之和

*(p+i)=sum; //将一行元素之和存入一维数组

}//for i

for(i=; i<n; i++) //用选择法对数组p进行排序

{min=*(p+i); k=i; //初始设第i行元素之和最小

for(j=i+;j<n;j++) if(p[j]<min) {k=j; min=p[j];} //记新的最小值及行号

if(i!=k) //若最小行不是当前行要进行交换(行元素及行元素之和)

{pk=matrix+n*k; //pk指向第k行第个元素

pi=matrix+n*i; //pi指向第i行第个元素

for(j=;j<n;j++) //交换两行中对应元素

{sum=*(pk+j); *(pk+j)=*(pi+j); *(pi+j)=sum;}

sum=p[i]; p[i]=p[k]; p[k]=sum; //交换一维数组中元素之和

}//if

}//for i

free(p); //释放p数组

}// Translation

[算法分析] 算法中使用选择法排序比较次数较多但数据交换(移动)较少若用其它排序方法虽可减少比较次数但数据移动会增多算法时间复杂度为O(n)

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []