數據結構考研分類復習真題 第五章 答案[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)

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

From:http://tw.wingwit.com/Article/program/sjjg/201311/23040.html