数据结构实验报告排序算法.doc

排序算法验证及评价实验报告班级：10020801 姓名：吴亮 学号：2008302651 电话日期：2010.1.8(一) 需求分析1、输入输出的形式： 根据题目要求与提示输入以文件名，并用你选择的排序进行排序，再编辑以文件名，把你的排好序的文件放入该文件。2、程序所能达到的功能： 程序对你的文件里的数据进行排序。3、测试数据： 打开你编辑的文件，查看文件是否已排序。 (二) 概要设计一，前五种排序：1 基本操作：（1）快速排序函数int partions(int l,int low,int high); 交换顺序表中llow.high的记录，使枢轴记录到位，并返回请其所在位置，此时在它之前（后）的记录均不大（小）于它，返回low值void qsort(int *l,int low,int high); 交换顺序表中llow.high的记录，使枢轴记录到位，并返回请其所在位置，此时在它之前（后）的记录均不大（小）于它void qsort(int *l,int low,int high) 对顺序表l中的子序列llow.hing作快速排序 （2）希尔排序函数void ShellInsert(int *L,int dk); 对顺序表做一趟希尔排序void ShellSort(int *L, int dlta, int t); 按增量序列dlta0.t-1对顺序表l做希尔排序（3）锦标赛排序函数void UpdateTree(int *tree, int *active, int pos); 建立具有最大根的树void TournamentSort(int *array, int length); 对array进行锦标赛排序（4）堆排序函数void HeapAdjust(int h, int s, int m); 已知hs.m中记录的关键字除hs之外均满足堆的定义，本函数调整hs的关键字，使hs.m成为一个大顶堆void heapsort(int h);对顺序表h进行堆排序 （5）归并排序void Merge(int array, int first, int mid, int last); 将有序表的SRi.m和SRm+1.n归并为有序的TRi.n void _MergeSort(int *array, int first, int last); 将SRs.t归并排序为TR1s.tvoid MergeSort(int *array, int length); 对顺序表l进行排序2、 模块调用图：main()void qsort(int *l,int low,int high)void ShellSort(int *L, int dlta, int t);void TournamentSort(int *array, int length)void heapsort(int h)void MergeSort(int *array, int length)int partions(int l,int low,int high);void ShellInsert(int *L,int dk)void UpdateTree(int *tree, int *active, int pos)void HeapAdjust(int h, int s, int m)void Merge(int array, int first, int mid, int last)void _MergeSort(int *array, int first, int last) 二，基数排序（1）本实验用到了链表结构类型。typedef struct /静态链表的结点类型long keysMAX_NUM_OF_KEY;long key0;int next;SLCell;typedef struct /静态链表类型SLCell *r;int keynum;long recnum;SLList;(2)实验基本操作：void CreatList_Sq(SLList &L,long k,long *a,long *b) 构造一个的静态链表。void RadixSort(SLList &L) L是采用静态链表表示的顺序表对L作基数排序，使得L成为按关键字自小到大的有序静态链表，L.r0为头结点void Distribute(SLCell *r,int i,ArrType &f,ArrType &e) 静态链表L的r域中记录已按(key0,.,keyi-1)有序，本算法按第i个关键字keyi建立RADIX个子表，使同一子表中记录的keysi相同，f0.RADIX-1和e0.RADIX-1分别指向各子表中第一个和最后一个记录void Collect(SLCell *r,int i,ArrType &f,ArrType &e) 本算法按keysi自小而大地将f0.RADIX-1所指各子表依次连接成一个链表，e0.RADIX为各子表的尾指针（3）模块调用分析：main()void CreatList_Sq(SLList &L,long k,long *a,long *b)void RadixSort(SLList &L)void Distribute(SLCell *r,int i,ArrType &f,ArrType &e)void Collect(SLCell *r,int i,ArrType &f,ArrType &e) (四) 程序使用说明及测试结果1 程序使用说明（1） 本程序的运行环境为VC6.0。（2） 进入演示程序后即显示提示信息：先选择排序类型（前五种排序在第一个程序里输入相应的数字，基数排序直接进入第二个程序） ，再输入文件名，如：data01.txt，待文件排序完成后，输入输出的文件名，这样排序后的数据就存储在输出文件中。在进行希尔排序时，在输入文件名后，还得根据提示输入你想要排序的趟数，以及每趟排序的增量。运行界面：3 调试中的错误及解决办法。(遇到时给出) 调试过程中，遇到了许多的问题，如：一开始直接用静态数组作为存储结构，结果在文件较大时，由于存储空间过小，系统崩溃。在同其他同学讨论后，我改用指针动态分配数组的存储空间。还有，在写锦标赛排序时，由于教材没有直接给出算法，导致我花了相当长的时间来思考和调试该算法。 （五）、实验总结(实验心得)你在编程过程中花时多少？零散的时间全部加上，大概有15-6个小时。多少时间在纸上设计？大概两个多小时。多少时间上机输入和调试？13到14个小时。多少时间在思考问题？不知道，一两个吧。遇到了哪些难题？调试过程中，遇到了许多的问题，如：一开始直接用静态数组作为存储结构，结果在文件较大时，由于存储空间过小，