数据结构课程设计---排序综合.doc

信息科学与技术学院数据结构课程设计报告题目名称： 排 序 综 合专业班级：1111学生姓名： 1111学生学号： 1111指导教师： 111完成日期：1111目 录1 课程设计的目的41.1 课程设计的目的41.2 课程设计的题目41.3 题目要求42 概要设计52.1 存储结构52.2 基本操作53 详细设计63.1 流程图63.2 源程序124 测试224. 1 主菜单224. 2 插入排序功能224.3 选择排序功能234.4 冒泡排序功能234.5 快速排序功能244.6 合并排序功能244.7 5种排序方法比较255 课程设计总结266参考书目：261 课程设计的目的1.1 课程设计的目的数据结构课程主要是研究非数值计算的程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。数据结构是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程，它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等各种领域。学习数据结构是为了将实际问题中所涉及的对象在计算机中表示出来并对它们进行处理。通过课程设计可以提高学生的思维能力，促进学生的综合应用能力和专业素质的提高。通过此次课程设计主要达到以下目的：n 了解并掌握数据结构与算法的设计方法，掌握数组、链表、队列、堆栈、树等基本数据结构，具备初步的独立分析和设计能力；n 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；n 提高综合运用所学的理论知识和方法独立分析和解决问题的能力；n 训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。1.2 课程设计的题目排序综合，利用随机函数产生N个随机整数（20000以上），对这些数进行多种方法进行排序。 1.3 题目要求 要求：1) 至少采用三种方法实现上述问题求解（提示，可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序）。并把排序后的结果保存在不同的文件中。2) 统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的方法。3) 如果采用4种或4种以上的方法者，可适当加分。2 概要设计2.1 存储结构定义的主要的数据：(1):class SortableSListpublic: SortableSList(); void InsertSort(); void SelectSort(); void BubbleSort(); void QuickSort(); void MergeSort(); void QuickSort(int left,int right); int QSort(int left,int right); void Merge(int left,int right1,int right2); int *I,*S,*Q,*B,*M; int n;声明的类对象d;(2) :int a5,b5,c5, 分别记录比较次数，交换次数，移动次数;(3) :long int a15; /记录排序所用的时间(4) int a25; /记录排名2.2 基本操作 (1):void SortableSList:BubbleSort(); 冒泡排序: (2):void SortableSList:InsertSort(); 直接插入排序 (3):void SortableSList:MergeSort(); 合并排序 (4):void SortableSList:QuickSort(); 快速排序 (5):void SortableSList:SelectSort(); 简单选择排序3 详细设计3.1 流程图开始主流程图：定义对象，变量输入要比较的数的个数n进入菜单，输入功能选项序号p判断输入的p P= =0 P=1 p=2 p=3 p=4 p=5 P=6 插入排序合并排序选择排序时间效率比较排序快速排序冒泡排序执行完相应操作并输出结果后，按任意键返回菜单结束 流程图-1子流程图： （1）：插入排序：开始判断i0&tempIj-1 是 否 比较次数a0加1；Ij=Ij-1;j- -;移动次数c0加1;比较次数a0加1；找到插入位置j，Ij=temp；结束 流程图-2 开始（2）：选择排序： 判断in-1 假定待排序列第一个元素最小，s=i; 是 j=i+1 否判断jn 是 否比较次数a1加1； 判断Sj0进入循环就将last置为0 , last=0; 是判断ji判 断Bj+1Bj 是 否 否 是交换Bj,Bj+1, Swap(Bj,Bj+1);交换次数b2加1;移动次数c2加3;last=j;比较次数a2加1如果没有交换元素，则last=0,退出循环i=last;结束流程图-4（4） ：快速排序：开始调用函数QuickSort(0,n-1);判断leftright 是调用QSort(left,right)，开始一趟快速排序，Qleft作为分割元素，并且j=QSort(left,right)； 否递归调用函数QuickSort(left,j-1)， 对低端序列快速排序递归调用函数QuickSort(j+1,right)， 对高端序列快速排序结束 流程图-5开始(5) :合并排序: 判断sizen 是初始化left=0; 否 否 判断left+sizen-1 否 right2=right1+size;right2=n-1; 是 否递归调用Merge(left,right1,right2)，合并相邻的两个子序列；left=right2+1， 确定下次合并的子序列的下界元素个数扩大一倍，size*=2结束流程图-63.2 源程序#include#include #include#include#include#include/包含列表的函数using namespace std;int a5,b5,c5;/a,b,c分别记录比较次数，交换次数，移动次数ifstream outfile;class SortableSListpublic: SortableSList(); void InsertSort(); void SelectSort(); void BubbleSort(); void QuickSort(); void MergeSort(); void QuickSort(int left,int right); int QSort(int left,int right); void Merge(int left,int right1,int right2); int *I,*S,*Q,*B,*M; int n;SortableSList:SortableSList()printf( 输入排序数字的个数:n);scanf(%d,&n);I=new intn; /创建一个指向整型数据的数组,并将地址赋给指向整型数据的指针S=new intn;Q=new intn;B=new intn;M=new intn;for(int i=0;in;i+) Ii=Si=Qi=Bi=Mi=rand();/将随机生成的资料写入文件ofstream infile;infile.open(data.txt);/将对象与文件关联for(i=0;in;i+)double w=Ii;infilew ; infile.close();void Swap(int&a,int&b)/交换函数int T=a;a=b;b=T;void SortableSList:InsertSort()/直接插入排序 for(int i=1;i0&tempIj-1)/从后往前查找插入位置a0+;Ij=Ij-1;j-;c0+;a0+;Ij=temp;/将待插入的元素存入找到的插入位置 void SortableSList:SelectSort()/简单选择排序int s;for(int i=0;in-1;i+) s=i; /假定待排序序列中的第一个元素最小 for(int j=i+1;jn;j+)/每趟扫描n-i-1次 a1+; if(SjSs) s=j;/记下每次比较的较小元素的下标 Swap(Si,Ss);/最小元素与待排序序列的第一个交换 c1=c1+3,b1+;void SortableSList:QuickSort()/快速排序 QuickSort(0,n-1); /以初始序列为待排序序列开始快速排序int SortableSList:QSort(int left,int right)int i=left,j=right+1;do /开始一趟快速排序，Qleft作为分割元素 do i+; a3+;while(QiQleft); if(ij) Swap(Qi,Qj),b3+;while(ij);Swap(Qleft,Qj); /交换分割元素Qleft和Qj的位置c3=c3+3,b3+;return j;void SortableSList:QuickSort(int left,int right)if(left0) /最多进行n-1趟 last=0; /进入循环就将last置为0 for(j=0;ji;j+)/从上往下进行比较 if(Bj+1Bj) Swap(Bj,Bj+1);c2=c2+3;b2+;last=j;a2+; i=last; /如果没有交换元素，则last=0,退出循环/两路合并排序void SortableSList:Merge(int left,int right1,int right2)/两路合并/right1,right2分别为两个子序列的上界int*temp=new intright2-left+1; /创建存放两个子序列的临时数组int i=left,j=right1+1,k=0; /i,j是两个子序列的游动指针，k是temp的游动指针while(i=right1)&(j=right2)/若两个子序都不空，则循环 a4+; if(Mi=Mj) /将Mi,Mj中较小的存入tempk tempk+=Mi+,b4+; else tempk+=Mj+,c4+,b4+;while(i=right1) /若第一个子序列还有剩余的就存入temp tempk+=Mi+,c4+,b4+;while(j=right2) /若第二个子序列还有剩余的就存入temp tempk+=Mj+,c4+,b4+;for(i=0,k=left;k=right2;) /将temp中的元素放回 Mk+=tempi+,c4+,b4+;void SortableSList:MergeSort()/合并排序int left,right2,right1;int size=1; /初始化子序列中元素的个数为1while(sizen) left=0; while(left+sizen-1)right2=n-1;elseright2=right1+size;Merge(left,right1,right2); /合并相邻的两个子序列left=right2+1; /确定下次合并的子序列的下界 size*=2;/元素个数扩大一倍void Wrong()/错误输出printf(n*按键错误!请重新输入*n);getchar();/从标准输入获取字符并返回下一个字符void menu()printf( n);printf( *尊敬的用户您好* n);printf( n);printf( *欢迎使用由计科1班 喻思远 2011508025 编辑的综合排序系统!* n);printf( n);printf( n);printf( 现在请您做出以下选择 n);printf( n);printf( n);printf( * n);printf( n);printf( * 1:插入排序 *n);printf( * 2:选择排序 *n);printf( * 3:冒泡排序 *n);printf( * 4:快速排序 *n);printf( * 5:合并排序 *n);printf( * 6:时间效率比较 *n);printf( * 0:退出 *n);printf( n);printf( * n);void main()int i,p;for(i=0;i5;i+)ai=bi=ci=0;long int a15; /排序所用的时间int a25; /排名long int start,finish;printf( *尊敬的用户您好* n);printf( nn);printf( *欢迎使用由计科1班 喻思远 2011508025 编辑的综合排序系统!* nnn);printf( 首先请您输出要比较数的个数 nnn);SortableSList d;/循环执行,直到按0退出 while(1) system(cls); menu();/显示选择界面 scanf(%d,&p); /等待输入 /输入0退出 if(p=0) printf( *谢谢!欢迎下次使用*!n); getchar(); break; /判断输入值，选择相应的操作 switch(p) case 1:outfile.open(data.txt);/将对象与文件关联for(i=0;iw;d.Ii=w;outfile.close();start=GetTickCount();d.InsertSort();finish=GetTickCount();a10=finish-start;printf(|排序名称|比较次数|交换的次数|移动次数|时 间|时间复杂度n);printf(|插入排序|%8d|%10d|%8d|%ld毫秒|n*nn,a0,b0,c0,a10);printf(n请按任意键继续.);getchar();getchar();break; case 2: outfile.open(data.txt);/将对象与文件关联for(i=0;iw;d.Si=w;start=GetTickCount();d.SelectSort ();finish=GetTickCount();a11=finish-start;printf(|排序名称|比较次数|交换的次数|移动次数|时 间|时间复杂度n);printf(|选择排序|%8d|%10d|%8d|%ld毫秒|n*nn,a1,b1,c1,a11);printf(n请按任意键继续.);getchar();getchar();break; case 3: outfile.open(data.txt);/将对象与文件关联for(i=0;iw;d.Bi=w; start=GetTickCount();d.BubbleSort ();finish=GetTickCount();a12=finish-start;printf(|排序名称|比较次数|交换的次数|移动次数|时 间|时间复杂度n);printf(|冒泡排序|%8d|%10d|%8d|%ld毫秒|n*nn,a2,b2,c2,a12);printf(n请按任意键继续.);getchar();getchar();break; case 4: outfile.open(data.txt);/将对象与文件关联for(i=0;iw;d.Qi=w;start=GetTickCount();d.QuickSort();finish=GetTickCount();a13=finish-start;printf(|排序名称|比较次数|交换的次数|移动次数|时 间|时间复杂度n);printf(|快速排序|%8d|%10d|%8d|%ld毫秒|n*log2nn,a3,b3,c3,a13);printf(n请按任意键继续.);getchar();getchar();break; case 5: outfile.open(data.txt);/将对象与文件关联for(i=0;iw;d.Mi=w; start=GetTickCount();d.MergeSort();finish=GetTickCount();a14=finish-start;printf(|排序名称|比较次数|交换的次数|移动次数|时 间|时间复杂度n);printf(|合并排序|%8d|%10d|%8d|%ld毫秒|n*log2nn,a4,b4,c4,a14);printf(n请按任意键继续.);getchar();getchar();break; case 6: system(cls);outfile.open(data.txt);/将对象与文件关联for(i=0;iw;d.Ii=d.Si=d.Qi=d.Bi=d.Mi=w;outfile.close(); for(i=0;i5;i+) ai=bi=ci=0;long int t1,t2,t3,t4,t5,t6,t7,t8,t9,t10;t1=GetTickCount();/从系统启动到现在所经过的毫秒数d.InsertSort();t2=GetTickCount();t3=GetTickCount();d.SelectSort();t4=GetTickCount();t5=GetTickCount();d.BubbleSort();t6=GetTickCount();t7=GetTickCount();d.QuickSort();t8=GetTickCount();t9=GetTickCount();d.MergeSort();t10=GetTickCount();a10=t2-t1;a11=t4-t3;a12=t6-t5;a13=t8-t7;a14=t10-t9;for(i=0;i5;i+)int t=1;for(int j=0;ja1j)t+;a2i=t; printf( 各种内排序的性能比较n); printf( | 排序名称 |比较次数|交换的次数|移动次数|时 间|时间排名|时间复杂度n); printf( | 插入排序 |%8d|%10d|%8d|%6l