有关数据结构的论文.doc

数据结构课程设计报告-排序器（排序算法验证及评价）一、题目与要求：问题描述：排序器（排序算法验证及评价）要 求：实现以下六种排序算法，将给定的不同规模大小的数据文件（data01.txt，data02.txt，data03.txt，data04.txt）进行排序，并将排序结果分别存储到sorted01.txt，sorted02.txt，sorted03.txt和sorted04.txt文件中。1）、Shell排序；2）、Quick排序3）、锦标赛排序；4）、堆排序5）、归并排序；6）、基数排序在实现排序算法1）4）时，统计数据元素比较的次数和交换的次数，进而对这四种算法在特定数据条件下的效率进行分析和评判。二、题目分析：首先需要读取4个不同大小文件中的数据，然后对其进行六种不同方法的排序，最后将结果储存在不同的文件中。其次，需要定义两个变量分别来记录前四种排序中数据的比较次数和移动次数，从而对这四种算法在特定数据条件下的效率进行分析和评判。三、函数说明及概要设计：以下为本程序中所涉及到的所有函数或重要变量，在设计思想中有具体解释：/*全局变量*/intcomp;/用来记录数据间比较次数intmove;/用来记录数据的移动次数四、本论文所付源代码请查阅本站：排序器（排序算法验证及评价）（C语言源代码）/*主函数*/intmain()/*菜单选择函数*/int menu()/*从文件中读取待排序数据*/intReadInfo(LinkList *p,char *f)/*在屏幕上输出每次排序的数据数目,比较次数,移动次数*/intPrintInfo(SqList *p)/*排序结果写入文件中*/int WriteInfo(SqList *p,char *f)/*希尔排序*/int Shell_Sort(SqList *p)/*希尔排序中的插入函数*/int Shell_Insert(SqList *p,int dk)/*快速排序*/int Quick_Sort(SqList *p)/*递归形式的快速排序函数*/int QSort(SqList *p,int low,int high)/*快排中计算枢轴位置的函数*/int Partition(SqList *p,int low,int high)/*锦标赛排序*/int Tournament_Sort(SqList *p)/*锦标赛排序中的调整函数*/int UpdateTree(DataNode *tree,int i)/*堆排序*/int Heap_Sort(SqList *H)/*堆排序中的筛选函数*/void HeapAdjust(SqList *H,int s,int m)/*归并排序*/int Merg_Sort(SqList *p)/*递归形式的归并排序函数*/int MSort(RedType SR,RedType TR1,int s,int t)/*归并排序中将一维数组中前后相邻的两个有序序列归并为一个有序序列*/int Merge(RedType SR,RedType TR,int i,int m,int n)/*基数排序*/int Radix_Sort(SqList *p,char *f1)/*链式基数排序中一趟收集函数*/int Collect(SLCell *r,int i,ArrType f,ArrType e)/*链式基数排序中一趟分配函数*/int Distribute(SLCell *r,int i,ArrType f,ArrType e)本程序采用的数据存储结构有三种:/*链式基数排序的数据结构*/typedefstructintkeysMAX_NUM_OF_KEY;int info;intkeysnum;int next;SLCell;typedef structSLCell*r;intkeynum;int recnum;SLList;typedef int ArrTypeRADIX;/*胜者树数据结点类的定义*/归并排序typedef structRedTypedata;int key;/关键字项int index;/满二叉树中的顺序号int active;/1,参选 0,不参选DataNode;/*其余排序的数据结构*/typedefstructintkey;/关键字项intinfo;/其他数据项RedType;/记录类型typedef structRedType*r;/MAXSIZE+1intlength;/顺序表长度SqList,*LinkList;1.首先建立起改程序的框架:需要一个主函数: int main( )，在主函数中调用菜单函数int menu()即可。2在菜单函数中，使屏幕上输出以下语句，以便进行选择。1.Shell排序2.Quick排序3.锦标赛排序4.堆排序5.归并排序6.基数排序7.退出并根据选择的结果来确定要调用的排序函数，这里特别要指出的是，由于基数排序与其他排序的参数调用型式略有不同，所以本函数中定义了两个函数指针int(*f)(SqList *),(*f1)(SqList *,char *)，分别用来指向基数排序函数和其他排序函数。确定了要进行的排序，接下来，在for(i=0;iX的值，6549,两者交换，此时I：=3 )进行第三次交换后： 27 38 13 97 76 49 65( 按照算法的第五步将又一次执行算法的第三步从后开始找进行第四次交换后： 27 38 13 49 76 97 65( 按照算法的第四步从前面开始找大于X的值，9749,两者交换，此时J：=4 )此时再执行第三不的时候就发现I=J，从而结束一躺快速排序，那么经过一躺快速排序之后的结果是：27 38 13 49 76 97 65，即所以大于49的数全部在49的后面，所以小于49的数全部在49的前面。 快速排序就是递归调用此过程在以49为中点分割这个数据序列，分别对前面一部分和后面一部分进行类似的快速排序，从而完成全部数据序列的快速排序，最后把此数据序列变成一个有序的序列。5锦标赛排序:与体育淘汰赛类似，首先取得n个元素的关键字，进行两两比较，得到 n/2 个比较的优胜者，将其作为第一次比较的结果保留下来，然后对这些元素再进行关键值的两两比较，如此重复，直到选出一个关键字最大的对象为止。每次两两比较的结果是把排序码小者作为优胜者上升到双亲结点,称这种树称为胜者树.位于最底层的叶结点叫做胜者树的外结点.非叶结点称为胜者树的内结点.每个结点除了存放对象的排序码data外,还存放了该对象是否要参选的标志active和该对象在满二叉树中的序号index.胜者树数据结点类的定义typedef structRedTypedata;int key;/关键字项int index;/满二叉树中的顺序号int active;/1,参选 0,不参选DataNode;6堆排序堆排序利用了大根堆(或小根堆)堆顶记录的关键字最大(或最小)这一特征，使得在当前无序区中选取最大(或最小)关键字的记录变得简单。 (1)用大根堆排序的基本思想 先将初始文件R1.n建成一个大根堆，此堆为初始的无序区 再将关键字最大的记录R1(即堆顶)和无序区的最后一个记录Rn交换，由此得到新的无序区R1.n-1和有序区Rn，且满足R1.n-1.keysRn.key 由于交换后新的根R1可能违反堆性质，故应将当前无序区R1.n-1调整为堆。然后再次将R1.n-1中关键字最大的记录R1和该区间的最后一个记录Rn-1交换，由此得到新的无序区R1.n-2和有序区Rn-1.n，且仍满足关系R1.n-2.keysRn-1.n.keys，同样要将R1.n-2调整为堆。 直到无序区只有一个元素为止。7归并排序本程序中采用递归的归并排序算法。在递归的归并排序方法中，首先要把整个待排序序列划分为两个长度大致相等的部分，分别称之为左子表和右子表。对这些子表分别递归地进行排序，然后再把排好序的两个子表进行归并。待排序对象序列的关键码为 21, 25, 49, 25*,16, 08 ，先是进行子表划分，待到子表中只有一个对象时递归到底。再是实施归并，逐步退出递归调用的过程。8基数排序基数排序是采用“分配”与“收集”的办法，用对多关键码进行排序的思想实现对单关键码进行排序的方法。基数排序的具体方法如下:1、根据数据项个位上的值，把所有的数据项分为10组；2、然后对这10组数据重新排列：把所有以0结尾的数据排在最前面，然后是结尾是1的数据项，照此顺序直到以9结尾的数据，这个步骤称为第一趟子排序。3、在第二趟子排序中，再次把所有的数据项分为10组，但是这一次是根据数据项十位上的值来分组的。这次分组不能改变先前的排序顺序。也就是说，第二趟排序之后，从每一组数据项的内部来看，数据项的顺序保持不变；4、然后再把10组数据项重新合并，排在最前面的是十位上为0的数据项，然后是10位为1的数据项，如此排序直到十位上为9的数据项。5、对剩余位重复这个过程，如果某些数据项的位数少于其他数据项，那么认为它们的高位为0。五、六种排序算法的效率分析和评判1.Shell排序数据数目1001000100003000000比较次数83814913242052220017731移动次数242391160023400206902.Quick排序数据数目1001000100003000000比较次数61510724152079117156800移动次数330476063718270517603.锦标赛排序数据数目1001000100003000000比较次数594873815207962377873移动次数92012013166369731942814.堆排序数据数目1001000100003000000比较次数102416888235473120019842移动次数578912512426461962523从对前四种排序中的数据比较次数和移动次数来看，快速排序最佳，其所需时间最省，但快速排序在比较坏的情况下的时间性能不如锦标赛排序和堆排序。当序列中的记录“基本有序”或数据数目较小时，Shell排序是最佳的排序方法。由文件中的排序结果可知，希尔排序、快速排序和堆排序都是不稳定的排序方法。四、心得：在本程序的调试过程中，最大的体会就是对时间复杂度和空间复杂度逐步的认识。一开始调试较小的文件时，还并未涉及到这两个问题，所以只考虑到了算法的正确性，而难免忽略了程序中对时间、空间复杂度的要求。举个例子，在调试第四个大小为32.3M的文件时，经常因为程序中一个极小的错误而导致程序无限运行直至系统提示虚拟内存不足。在刚开始的编写中，由于并没有释放内存空间，而导致经常