數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告十四-基數(shù)排序

問題描述：基數(shù)排序是采用“分配”與“收集”的辦法，用對多關(guān)鍵碼進(jìn)行排序的思想實(shí)現(xiàn)對單關(guān)鍵碼進(jìn)行排序的方法。實(shí)現(xiàn)多關(guān)鍵碼排序有兩種常用的方法：（1）最高位優(yōu)先MSD(MostSignificantDigitfirst)；（2）最低位優(yōu)先LSD(LeastSignificantDigitfirst)。實(shí)現(xiàn)基數(shù)排序功能?；疽螅?（1）需排序的數(shù)據(jù)是英文單詞，從文件中讀取。 （2）根據(jù)詞典順序排列。排序結(jié)果寫入文件保存。需求分析：本程序需要利用二維數(shù)組來存放操作數(shù)，并進(jìn)行相應(yīng)的操作。實(shí)現(xiàn)提示：（1）根據(jù)讀入的英文單詞的最長的，決定基數(shù)排序的趟數(shù)。（2）基數(shù)使用24（字母的個數(shù)）（3）從單詞的第一個字母開始進(jìn)行基數(shù)排序。二、概要設(shè)計(jì)：抽象數(shù)據(jù)類型：需二維數(shù)組來進(jìn)行相應(yīng)的操作。算法的基本思想：基數(shù)排序是屬于“分配式排序”，又稱“桶子法”，它是透過鍵值的部份資訊，將要排序的元素分配至某些“桶”中，藉以達(dá)到排序的作用。最高位優(yōu)先(MostSignificantDigitfirst)法，簡稱MSD法：先按k1排序分組，同一組中記錄，關(guān)鍵碼k1相等，再對各組按k2排序分成子組，之后，對后面的關(guān)鍵碼繼續(xù)這樣的排序分組，直到按最次位關(guān)鍵碼kd對各子組排序后。再將各組連接起來，便得到一個有序序列。最低位優(yōu)先(LeastSignificantDigitfirst)法，簡稱LSD法：先從kd開始排序，再對kd-1進(jìn)行排序，依次重復(fù)，直到對k1排序后便得到一個有序序列。另外,對于本實(shí)驗(yàn)還有要求就是在文件中讀取字符串，同時(shí)間字符串保存與文件中，這就需要#include<ifstream>頭文件，同時(shí)用函數(shù)ofstreamoutfile(“d:\\f1.dat”,ios::out)；保存到指定的文件和ifstreaminfile("file.txt",ios::in);打開指定的文件。程序的流程 程序由三個模塊組成：輸入模塊：讀入基數(shù)存放在數(shù)組里面。處理模塊：進(jìn)行相應(yīng)操作。輸出模塊：將數(shù)據(jù)輸出。三、詳細(xì)設(shè)計(jì)算法的具體步驟：voidradix(stringc[],inta){ inti=0,j=0,k=0,d=0,m=0; stringstr[26][20];//用來存放基數(shù)排序的桶for(j=9;j>=0;j--){//根據(jù)基數(shù)排序法，//對單詞各位（0—n-1）進(jìn)行排序 for(i=0;i<a;i++){//對count個單詞進(jìn)行J位進(jìn)排序桶 k=c[i][j]-97; if(k<0){k=0;} str[k][m++]=c[i]; } for(i=0,k=0;i<n&&k<26;k++)//按順序回收排序桶 for(d=0;d<n;d++) if(str[k][d][0]>96&&str[k][d][0]<123||str[k][d][0]>64&&str[k][d][0]<91){//判斷26各排序桶是否有單詞 c[i++]=str[k][d]; str[k][d][0]=32; } m=0;}}四、測試結(jié)果本實(shí)驗(yàn)的測試結(jié)果截圖如下：輸入：輸出：五、用戶使用說明（可選）1、本程序的運(yùn)行環(huán)境為windows操作系統(tǒng)，執(zhí)行文件為14.exe2、本程序是從文件中讀取數(shù)據(jù)，然后把數(shù)據(jù)存儲到指定文件中去。六、實(shí)驗(yàn)心得（可選）此次實(shí)驗(yàn)比較困難，由于對這方面的知識掌握的不是很牢固，所以編寫實(shí)驗(yàn)時(shí)不明白之處比較多，后來在同學(xué)的幫助下完成了實(shí)驗(yàn)。通過此次實(shí)驗(yàn)對基數(shù)排序有了比較深刻的了解，還是比較有收獲的。附錄（實(shí)驗(yàn)代碼）：#include<iostream>#include<string>#include<fstream>usingnamespacestd;#definen10//假設(shè)沒個單詞最大數(shù)目是10voidradix(stringc[],inta){ inti=0,j=0,k=0,d=0,m=0; stringstr[26][20];//用來存放基數(shù)排序的桶for(j=9;j>=0;j--){//根據(jù)基數(shù)排序法，//對單詞各位（0—n-1）進(jìn)行排序 for(i=0;i<a;i++){//對count個單詞進(jìn)行J位進(jìn)排序桶 k=c[i][j]-97; if(k<0){k=0;} str[k][m++]=c[i]; } for(i=0,k=0;i<n&&k<26;k++)//按順序回收排序桶 for(d=0;d<n;d++) if(str[k][d][0]>96&&str[k][d][0]<123||str[k][d][0]>64&&str[k][d][0]<91){//判斷26各排序桶是否有單詞 c[i++]=str[k][d]; str[k][d][0]=32; } m=0;}}intmain(){ inta,i; cout<<"請輸入元素個數(shù)："; cin>>a; stringc[10]; ifstreaminfile("file.txt",ios::in); if(!infile){ cout<<"openerror..."<<endl; exit(1); }else{ cout<<"openok....."<<endl; for(i=0;i<a;i++) infile>>c[i]; }radix(c,a); ofstreamoutfile("d:\\f1.txt",ios::out);//定義文件流對象，打開磁盤文件也可以更改其他路徑if(!outfile)//如果打開失敗，outfile返回0值{cerr