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

　　 [題目分析]本題是基數排序的特殊情況關鍵字只含一位數字的整數

　　typedef struct
　　{ int key;
　　int next;
　　} SLRecType;
　　SLRecType R[N+];
　　typedef struct
　　{ intfe;
　　} SLQueue;
　　SLQueue B[];
　　int Radixsort(SLRecType R[]int n)  //設各關鍵字已輸入到R數組中
　　{for (i=;i<n;i++ ) R[i]next=i+;
　　R[n]next=; p=;   //表示靜態鏈表結束
　　for (i=;i<=;i++);{ B[i]f=; B[i]e=;} //設置隊頭隊尾指針初值
　　while (p!=)             //一趟分配
　　{k=R[p]key;             //取關鍵字
　　if(B[k]f==)B[k]f=p; //修改隊頭指針
　　else R[B[k]e]next=p;
　　B[k]e=p;
　　p=R[p]next;             //下一記錄
　　}
　　i=;                       //一趟收集
　　while (B[i]f==) i++;
　　t=B[i]e; p=B[i]f;
　　while (i<)
　　{i++;
　　if (B[i]f!=)
　　{ R[t]next=B[i]f;t=B[i]e;}  }
　　R[t]next=;
　　return  p;    //返回第一個記錄指針
　　}

　　[算法討論]若關鍵字含d位則要進行d趟分配和d趟收集關鍵字最好放入字符數組以便取關鍵字的某位

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

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