基数排序实验报告.doc

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