数据�l�构�W�五章算法设计题[3]_跨考网

1�Q�编写一个过�E�，对一�?/span>n×n矩阵�Q�通过行变换，使其每行元素的��^均值按递增��序排列。【中�U�院软�g所 1996 �?/span>

　　【参考答案�?/span>

　　[题目分析]题目中要求矩阵两行元素的�q�_��值按递增��序排序�Q�由于每行元素个数相�{�，按��^均值排列与按每行元素之和排列是一个意思。所以应先求出各行元素之和，攑օ�一�l�数�l�中�Q�然后选择一�U�排序方法，对该数组�q�行排序�Q�注意在排序时若有元素移动，则与之相应的行中各元素也必须做相应变动�?/span>

　　void Translation�Q?/span>float *matrix�Q?/span>int n�Q?/span>

　　//本算法对n×n的矩�?/span>matrix�Q�通过行变换，使其各行元素的��^均值按递增排列�?/span>

　　{int i,j,k,l�Q?/span>

　　float sum�Q?/span>min�Q?/span> //sum暂存各行元素之和

　　float *p, *pi, *pk;

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

　　{sum=0.0; pk=matrix+i*n; //pk指向矩阵各行�W?/span>1个元�?/span>.

　　for (j=0; j<n; j++){sum+=*(pk); pk++;} //求一行元素之�?/span>.

　　*(p+i)=sum; //���一行元素之和存入一�l�数�l?/span>.

　　}//for i

　　for(i=0; i<n-1; i++) //用选择法对数组p�q�行排序

　　{min=*(p+i); k=i; //初始讄���i行元素之和最��?/span>.

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

　　if(i!=k) //若最���行不是当前�?/span>,要进行交�?/span>(行元素及(qi��ng)行元素之�?/span>)

　　{pk=matrix+n*k; //pk指向�W?/span>k行第1个元�?/span>.

　　pi=matrix+n*i; //pi指向�W?/span>i行第1个元�?/span>.

　　for(j=0;j<n;j++) //交换两行中对应元�?/span>.

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

　　sum=p[i]; p[i]=p[k]; p[k]=sum; //交换一�l�数�l�中元素之和.

　　}//if

　　}//for i

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

　　}// Translation

　　[���法分析] ���法中��用选择法排�?/span>,比较�ơ数较多,但数据交�?/span>(�U�d��)较少.若用其它排序�Ҏ(gu��)��,虽可减少比较�ơ数,但数据移动会(x��)增多.���法旉���复杂度�ؓ(f��)O(n2).