數據結構考研分類復習真題 第十章 答案[44]

　　 手工模擬排序過程略

　　#define  n  待排序記錄的個數
　　typedef  struct
　　{ int  key[d];     //關鍵字由d個分量組成
　　int  next;       //靜態鏈域
　　AnyType  other;  //記錄的其它數據域
　　} SLRecType;
　　SLRecType  R[n+]; //R[n]存放n個記錄
　　typedef  struct
　　{ int  fe;     //隊列的頭尾指針
　　} SLQueue;
　　SLQueue B[m]    //用隊列表示桶共m個
　　int   RadixSort(SLRecType  R[] int n)
　　{ //對R[n]進行基數排序返回收集用的鏈頭指針
　　for(i=;i<n;i++)  R[i]next=i+;//將R[n]鏈成一個靜態鏈表
　　R[n]next=; p=;   //將初始鏈表的終端結點指針置空 p指向鏈表的第一個結點
　　for(j=d;j>=;j)  //進行d趟排序
　　{for(i=;i<m;i++) { B[i]f=;B[i]e=;}//初始化桶
　　while(p!=)         //按關鍵字的第j個分量進行分配
　　{ k=R[p]key[j];   //k為桶的序號
　　if(B[k]f==)  B[k]f=p;     //將R[p]鏈到桶頭
　　else  R[B[k]e]next=p;       //將R[p]鏈到桶尾
　　B[k]e=p;                     //修改桶的尾指針
　　p=R[p]next;                  //掃描下一個記錄
　　}//while
　　i=;
　　while(B[i]f==)  i++;   //找第一個非空的桶
　　t=B[i]e;  p=B[i]f       //p為收集鏈表的頭指針t為尾指針
　　while(i<m)
　　{i++;
　　if(B[i]f!=){ R[t]next=B[i]f; t=B[i]e; } //連接非空桶
　　}//while
　　R[t]next=;       //本趟收集完畢將鏈表的終端結點指針置空
　　}//for
　　return  p;
　　}//RadixSort

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

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