数据结构实验报告十四-基数排序

问题描述：基数排序是采用“分配”与“收集”的办法，用对多关键码进行排序的思想实现对单关键码进行排序的方法。实现多关键码排序有两种常用的方法：（1）最高位优先MSD(MostSignificantDigitfirst)；（2）最低位优先LSD(LeastSignificantDigitfirst)。实现基数排序功能。基本要求： （1）需排序的数据是英文单词，从文件中读取。 （2）根据词典顺序排列。排序结果写入文件保存。需求分析：本程序需要利用二维数组来存放操作数，并进行相应的操作。实现提示：（1）根据读入的英文单词的最长的，决定基数排序的趟数。（2）基数使用24（字母的个数）（3）从单词的第一个字母开始进行基数排序。二、概要设计：抽象数据类型：需二维数组来进行相应的操作。算法的基本思想：基数排序是属于“分配式排序”，又称“桶子法”，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用。最高位优先(MostSignificantDigitfirst)法，简称MSD法：先按k1排序分组，同一组中记录，关键码k1相等，再对各组按k2排序分成子组，之后，对后面的关键码继续这样的排序分组，直到按最次位关键码kd对各子组排序后。再将各组连接起来，便得到一个有序序列。最低位优先(LeastSignificantDigitfirst)法，简称LSD法：先从kd开始排序，再对kd-1进行排序，依次重复，直到对k1排序后便得到一个有序序列。另外,对于本实验还有要求就是在文件中读取字符串，同时间字符串保存与文件中，这就需要#include<ifstream>头文件，同时用函数ofstreamoutfile(“d:\\f1.dat”,ios::out)；保存到指定的文件和ifstreaminfile("file.txt",ios::in);打开指定的文件。程序的流程 程序由三个模块组成：输入模块：读入基数存放在数组里面。处理模块：进行相应操作。输出模块：将数据输出。三、详细设计算法的具体步骤：voidradix(stringc[],inta){ inti=0,j=0,k=0,d=0,m=0; stringstr[26][20];//用来存放基数排序的桶for(j=9;j>=0;j--){//根据基数排序法，//对单词各位（0—n-1）进行排序 for(i=0;i<a;i++){//对count个单词进行J位进排序桶 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;}}四、测试结果本实验的测试结果截图如下：输入：输出：五、用户使用说明（可选）1、本程序的运行环境为windows操作系统，执行文件为14.exe2、本程序是从文件中读取数据，然后把数据存储到指定文件中去。六、实验心得（可选）此次实验比较困难，由于对这方面的知识掌握的不是很牢固，所以编写实验时不明白之处比较多，后来在同学的帮助下完成了实验。通过此次实验对基数排序有了比较深刻的了解，还是比较有收获的。附录（实验代码）：#include<iostream>#include<string>#include<fstream>usingnamespacestd;#definen10//假设没个单词最大数目是10voidradix(stringc[],inta){ inti=0,j=0,k=0,d=0,m=0; stringstr[26][20];//用来存放基数排序的桶for(j=9;j>=0;j--){//根据基数排序法，//对单词各位（0—n-1）进行排序 for(i=0;i<a;i++){//对count个单词进行J位进排序桶 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<<"请输入元素个数："; 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