数据结构课程设计报告

《数据结构课程设计报告》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构课程设计题目3.排序算法功能的演示一、需求分析1.运行环境（软、硬件环境）Microsoftvisualstudio2010专业版（windows7）2.程序所实现的功能；1.待演示的排序算法如下：（1）直接插入排序；（2）冒泡排序；（3）简单选择排序；（4）快速排序；（5）堆排序；（6）归并排序。2.显示（1）显示所演示的排序算法的名称。（2）给出提示输入一组关键字，建立排序表。（3）显示初始的排序表的各个关键字。（4）显示每一趟的趟数以及每一趟的结果。3程序的输入：包含输入的数据格式和说明（1)排序种类三输入(2)排序数的个数的输入(3)所需

2、排序的所有数的输入4程序的输出：程序输出的形式(1)主菜单的输出(2)每一趟排序的输出，即排序过程的输出5测试数据，如果程序输入的数据量比较大，需要给出测试数据测试数据为根据需求随机输入的整数二、设计说明1.算法设计的思想22（1）交换排序（冒泡排序、快速排序）交换排序的基本思想是：对排序表中的数据元素按关键字进行两两比较，如果发生逆序（即排列顺序与排序后的次序正好相反），则两者交换位置，直到所有数据元素都排好序为止。（2）插入排序（直接插入排序）插入排序的基本思想是：每一次设法把一个数据元素插入到已经排序的部分序列的合适位置，使得插入后的序列仍然是有序

3、的。开始时建立一个初始的有序序列，它只包含一个数据元素。然后，从这个初始序列出发不断插入数据元素，直到最后一个数据元素插到有序序列后，整个排序工作就完成了。（3）选择排序（简单选择排序、堆排序）选择排序的基本思想是：第一趟在有n个数据元素的排序表中选出关键字最小的数据元素，然后在剩下的n-1个数据元素中再选出关键字最小（整个数据表中次小）的数据元素，依次重复，每一趟（例如第i趟，i=1，…，n-1）总是在当前剩下的n-i+1个待排序数据元素中选出关键字最小的数据元素，作为有序数据元素序列的第i个数据元素。等到第n-1趟选择结束，待排序数据元素仅剩下一个时

4、就不用再选了，按选出的先后次序所得到的数据元素序列即为有序序列，排序即告完成。（4）归并排序（两路归并排序）两路归并排序的基本思想是：假设初始排序表有n个数据元素，首先把它看成是长度为1的首尾相接的n个有序子表（以后称它们为归并项），先做两两归并，得n/2上取整个长度为2的归并项（如果n为奇数，则最后一个归并项的长度为1）；再做两两归并，……，如此重复，最后得到一个长度为n的有序序列。2.主要的数据结构设计说明constintmaxsize=100;//最多可输入100个数intnum=0;//定义全局变量，为每一趟的输出做准备intx=0;templa

5、teclasssortlist//定义排序类{private:intcurrentsize;//数据表中数据元素的个数public:type*arr;//存储数据元素的向量（排序表）sortlist():currentsize(0){arr=newtype[maxsize];}//构造函数sortlist(intn){arr=newtype[maxsize];currentsize=n;}voidinsert(inti,typex){arr[i]=x;}~sortlist(){delete[]arr;}//析构函数voidswap(

6、type&x,type&y)//数据元素x和y交换位置{typetemp=x;x=y;y=temp;}voidinsertionsort();//直接插入排序voidbubblesort();//冒泡排序voidselectsort();//简单选择排序voidquicksort(intlow,inthigh);//快速排序voidheapsort();//堆排序voidmergesort(sortlist&table);//归并排序22voidfilterdown(constintstart);//建立最大堆voidmergepass(so

7、rtlist&sourcetable,sortlist&mergedtable,constintlen);//一趟归并voidmerge(sortlist&sourcetable,sortlist&mergedtable,constintleft,constintmid,constintright);//两路归并算法};开始3.程序的主要流程图进入菜单选择排序方法0退出6归并排序5堆排序4快速排序3选择排序2冒泡排序1直接插入排序退出程序输出结果4.程序的主要模块，要求对主要流程图中出现的模块进行说明(1)

8、主菜单22主要功能：程序运行时，可使运行者根据提醒输入相关操作，从而进入不同的排