1 软件需求分析 1.1 软件达到的目的 1.2 软件功能说明 1.3 设计环境 2 系统设计 2.1 数据结构设计
2.1.1 主要数据结构类型的分析与选择（逻辑结构） 2.1.2 数据结构中的数据对象以及具体的操作的确定 2.2 对象设计
2.2.1 系统中的类及对象 2.2.2 类图设计 2.3 消息设计
2.3.1 对象之间的消息传递说明 2.3.2 关键算法设计 2.4 界面设计 3 系统实现
3.1 类的定义（存储结构） 3.2 关键源代码的实现 3.2.1 主函数源代码
3.2.2 主要功能的实现（功能描述、流程图或N-S图） 3.3 软件测试（包括有效测试数据和无效测试数据） 4 结果分析与总结 4.1 结果分析 4.2 总结
数据结构程序设计
内部排序算法比较
目录
摘 要 ........................................................................................................................... 1 1绪论 ............................................................................................................................ 1 2系统分析 .................................................................................................................... 1 2.1 功能需求 ............................................................................................................. 1 2.2数据需求 .............................................................................................................. 1 2.3 性能需求 ............................................................................................................. 2 3总体设计 .................................................................................................................... 2 3.1系统设计方案 ...................................................................................................... 2 3.2功能模块设计 ...................................................................................................... 2 4详细设计 .................................................................................................................... 3 4.1 数据结构定义 ..................................................................................................... 3 4.2伪随机产生数据模块 .......................................................................................... 4 4.3简单选择排序模块 ............................................................ 错误！未定义书签。 4.4起泡排序模块 ...................................................................................................... 4 4.5直接插入排序模块 ............................................................ 错误！未定义书签。 4.6希尔排序模块 ...................................................................................................... 5 4.7快速排序模块 ...................................................................................................... 6 4.8归并排序模块 ...................................................................................................... 8 4.9条形图模块 .......................................................................................................... 9 5调试与测试 .............................................................................................................. 10 5.1 调试 ................................................................................................................... 10 5.2 测试 .................................................................................. 错误！未定义书签。 6结论 .......................................................................................................................... 12 结束语 ......................................................................................................................... 12 参考文献 ..................................................................................... 错误！未定义书签。 附录1－用户手册 ...................................................................................................... 13 附录2－源程序 .......................................................................................................... 15
I
数据结构程序设计
摘 要
本程序是比较几种排序算法的关键字比较次数和移动次数以取得直观感受。 内部算法有冒泡排序、直接插入排序、快速排序、希尔排序、归并排序等。每种算法都有自己的比较方法和优缺点，本程序能更直观的显示出各种排序的比较次数、移动次数和排序时间，并能用条形图（星号表示）进行表示，以便比较各种排序的优劣。该程序运用了数据结构中线性表的顺序存储结构和各种排序算法来共同实现的。
关键词：内部排序、条形图。 1绪论
随着科技的快速发展，越来越多的企业不再浪费人力财力去计算一些统计性结果，而是应用一些简单的程序或系统来完成这些任务。随着学习数据结构课程的深入，了解了不同排序算法的不同排序方法，每种排序对数据的比较次数、移动次数和排序用时都是不同的，本程序实现了六种内部排序算法的比较，并用条形图直观的显示出各种算法的优劣。运用伪随机产生的数据，调用六种排序算法，记录其比较次数、移动次数和排序时间，再分别用条形图（星号表示）表示出来。 2系统分析 2.1 功能需求
(1)对起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、归并排序算法进行比较。
(2)待排序的元素的关键字为整数，其中数据要用伪随机产生程序产生，并且至少用5组的输入数据做比较，再使用各种算法对其进行排序，记录其排序时间，再汇总比较。
(3)演示程序以人机对话的形式进行，每次测试完毕显示各种比较指标值，比较次数、移动次数和排序时间的列表，并用条形图即星号表示出来，以便比较各种排序的优劣。 2.2数据需求
抽象数据类型：线性表、排序算法 (1) 输入数据：需要比较的数据数目
1
数据结构课程设计
(2) 输出数据：不同算法的比较次数、移动次数、排序时间的数据以及对应的条形图。 2.3 性能需求
在运行本程序时，只要按照正确的操作方法不会出现无法运行的情况，系统稳定性好，安全，可靠，响应速度由需比较的数字数目多少来决定。 3总体设计 3.1系统设计方案
(1) 输入要排序的数据数目 (2) 抽象数据类型定义 typedef struct { int key;
}ElemType; //关键字 typedef struct {
ElemType *elem; int length;
}SqList;//分配顺序存储结构
(3) 存储结构：本程序采用了线性表的顺序存储结构。 (4) 算法设计：
起泡排序：时间复杂度O(n2)，空间复杂度O(1) 希尔排序：时间复杂度O(n1.3)，空间复杂度O(1) 快速排序：时间复杂度O(nlog2n)，空间复杂度O(nlog2n) 归并排序：时间复杂度O(nlog2n)，空间复杂度O(n) 堆排序: 时间复杂度 O(nlogn), 空间复杂度O(1)
3.2功能模块设计
根据分析整个程序主要划分为8个功能模块，分别执行要求中的功能。1个产生伪随机数据模块、6个内部排序算法模块以及1个形成条形图模块。功能模块图如图1所示
2
数据结构课程设计
内部排序算法比较系统
伪随机产生数据; 气泡排序 快速排序 希尔排序 归并排序 堆排序
图1功能模块图
(1)伪随机产生数据模块：本程序要求数据是要用伪随机产生程序产生，再用不同排序算法进行排序。
(2) 起泡排序模块：运用起泡排序法对伪随机产生的数据进行排序。 (3)希尔排序模块：运用希尔排序法对伪随机产生的数据进行排序。 (4)快速排序：运用快速排序法对伪随机产生的数据进行排序。 (5) 堆排序模块：运用堆排序法对伪随机产生的数据进行排序。
(6)归并排序：运用归并排序法对伪随机产生的数据进行排序。 (7) 基数排序模块：运用基数排序法对伪随机产生的数据进行排序。
4详细设计 4.1 数据结构定义
typedef struct {int key;
}ElemType; //关键字 typedef struct {
ElemType *elem;
3
数据结构课程设计
int length;
}SqList;//分配顺序存储结构 4.2伪随机产生数据模块
伪随机产生数据模块可实现伪随机产生不同数目的数据以供排序，运用顺序存储结构来实现的。该模块具体实现程序流程如图2所示。
//20000改成1000
开始int i;输入要要比较的数据个数Nn>20000Yprintf(\"超出范围重新输入!!!\\n\");L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));N!L.elemYexit(0); L.length=0;i=1;Ni 图2 伪随机产生数据模块 4.4起泡排序模块 起泡排序模块可实现运用起泡排序法对数据进行排序，该模块具体实现程序 4 数据结构课程设计 流程如图4所示。 开始start_t=clock();int i=0,j,com=0,mov=0;Ni 4.6希尔排序模块 希尔排序模块可实现运用希尔排序法对数据进行排序，该模块具体实现程序 5 数据结构课程设计 流程如图6所示。 开始start_t=clock();int i,d=L.length/2,j,w=0,k,com=0,mov=0;NYw=1;w 图6 希尔排序模块 4.7快速排序模块 快速排序模块可实现用快速排序法对数据进行排序，该模块具体实现程序流程如图7所示。 6 数据结构课程设计 开始start_t=clock();int pivotkey;yd1=0,bj1=0;L.elem[0]=L.elem[low]; yd1++;pivotkey=L.elem[low].key;Nlow 4.8堆排序模块 堆排序模块可实现运用堆排序法对数据进行排序，该模块具体实现程序流程如图6所示。 7 数据结构课程设计 图8 堆排序模块 4.9归并排序模块 归并排序模块可实现用归并排序法对数据进行排序，该模块具体实现程序流程如图8所示。 8 数据结构课程设计 开始start_t=clock();int i=low, j=m+1, k=low;yd1=0,bj1=0;Ni<=m&&j<=highYR[i].key<=R[j].keyY bj1++; R1[k]=R[i]; yd1++; i++; k++;Nbj1++； R1[k]=R[j]; yd1++; j++; k++;NYR1[k]=R[i]; yd1++; i++; k++;i<=mj<=highYR1[k]=R[j]; yd1++; j++; k++;Nend_t=clock();t5=(double)(end_t-start_t)/CLK_TCK;输出bj1，yd1，t5结束 图8 归并排序模块 4.9条形图模块 条形图模块可用星号显示出各种算法排序的比较结果，该模块具体实现程序流程如图9所示。 9 数据结构课程设计 开始long int d[6];int i,n; i=0;Ni<5;Yd[i]= sqrt (A[i]/A[5]); printf(\"\\n 归并排序： *\"); printf(\" 选择排序： \");n=0,i=0;Nn<=d[i];Y printf(\"*\");n++printf(\" 冒泡排序： \");n=0,i=1;Nn<=d[i];Yprintf(\"*\");n++其他排序同理结束 图9 条形图模块 5调试与测试 5.1 调试 调试过程主要是运行编制好的程序，然后遇到错误后根据系统的提示，找到 10 数据结构课程设计 相关的问题所在。本系统调试过程中遇到的主要问题、原因和解决方法如下面介绍。 (1)问题：用条形图表示时，不能根据数据而表示出星号的多少。 解决办法：选择要表示的数据最小的一种排序作为基数，每种排序所要比较的数据可运用数学运算计算出是基数的多少倍，从而输出几个星号。 (2)问题：输入数据数目为2个时程序运行错误。 原因：待比较的数据为2个时，作为基数的那种排序的数据为0，不能做分母，所以会出现运行错误。 解决方法：输入较大的数，使要用条形图表示出来的数据不为0即可。 5.2测试 软件测试是软件生存期中的一个重要阶段，是软件质量保证的关键步骤从用户的角度来看，普遍希望通过软件测试暴露软件中隐藏的错误和缺陷，所以软件测试应该是“为了发现错误而执行程序的过程”。或者说，软件测试应该根据软件开发各阶段的规格说明和程序的内部结构而精心设计一批测试用例（即输入数据及其预期的输出结果），并利用这些测试用例去运行程序，以发现程序错误或缺陷。过度测试则会浪费许多宝贵的资源。到测试后期，即使找到了错误，然而付出了过高的代价。 测试数据过程如下。 (1) 输入功能测试 输入数据1：100 预期结果：输出各排序算法的比较次数、移动次数和排序用时，随后输出数据比较所对应的条形图。 运行结果：输出各排序算法的比较次数、移动次数和排序用时，随后输出数据比较所对应的条形图。 说明：预期和运行结果相同。 输入数据2：25000 预期结果：输出各排序算法的比较次数、移动次数和排序用时，随后输出数据比较所对应的条形图。 运行结果：超出范围重新输入! 说明：不能输入比1000大的数。 11 数据结构课程设计 (2)输出功能测试 输入数据1：200 预期结果：输出各排序算法的比较次数、移动次数和排序用时，随后输出数据比较所对应的条形图。 运行结果：输出各排序算法的比较次数、移动次数和排序用时，随后输出数据比较所对应的条形图。 说明：：预期和运行结果相同。 输入数据2：4 预期结果：输出各排序算法的比较次数、移动次数和排序用时，随后输出数据比较所对应的条形图。 运行结果：在输出移动次数比较的条形图时出现运行错误。 说明：不能输入比5小的数。 6结论 经过这一段时间的程序设计，该课设任务书中题目所要求的功能也都一一实现。可以伪随机产生不同的数据，六种内部排序算法对其数据进行排序，记录比较次数、移动次数和排序用时，并用条形图直观的表示出不同算法的优劣。不过本程序还可以添加细节，例如：可输出个选择排序方法的菜单，挑选不同排序方法对数据进行比较，也可以再循环选择并用条形图表示出来。 结束语 为期两个星期的课程设计终于顺利完成，这段时间让我对数据结构这门课程有更多的了解和认识，同时也从编程中所遇到的挫折和困难中吸取更多有价值的经验。编程需要耐心和信心，要有缜密的心思来全面考虑问题，否则编出的程序不能完全满足题目要求或运行错误。通过这次课设，我更深入了解了六种内部排序算法的排序方法和时间复杂度，从而还算顺利的完成了本次课程设计。编程的道路不好走，不过我会更加努力的学习，让编程不再那么困难辛苦，让以后自己能有信心的轻松面对。 12 数据结构程序设计 附录1－用户手册 点击运行，首先出现的是要输入伪随机产生数据的数目，如图9所示。 图9 输入界面 输入数据个数然后回车，可显示出不同排序算法的比较次数、移动次数和排序用时。如图10所示。 图10 显示比较结果界面 显示比较次数的条形图。如图11所示。 13 数据结构课程设计 图11 比较次数条形图界面 显示移动次数条形图。如图12所示 图12 移动次数条形图界面 显示排序用时条形图。如图13所示 图13 排序用时条形图界面 14 数据结构课程设计 附录2－源程序 主要模块源代码清单： #include #define LIST_INIT_SIZE 30000 int bj1,yd1,n,com,mov; long int A[5],B[5]; double t0,t1,t2,t3,t4,t5,C[5]; clock_t start_t,end_t; typedef struct { int key; }ElemType; typedef struct { ElemType *elem; int length; }SqList; void addlist(SqList &L) { int i; a: printf(\"请输入你要输入的个数:\"); scanf(\"%d\ if(n>20000) { printf(\"超出范围重新输入!!!\\n\"); goto a; } L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType)); if(!L.elem)exit(0); 15 数据结构课程设计 L.length=0; for(i=1;i void bubblesort(SqList &L) //起泡排序 { int i=1,j,com=0,mov=0; while(i L.elem[0].key=L.elem[j].key; L.elem[j].key=L.elem[j+1].key; L.elem[j+1].key=L.elem[0].key; mov+=3; } } i++; } printf(\"比较次数为 %d移动次数为 %d\\n\A[1]=com; B[1]=mov; } void xier(SqList &L) //希尔排序 { 16 数据结构课程设计 int i,d=L.length/2,j,w=0,k,com=0,mov=0; while(w L.elem[0].key=L.elem[i].key; L.elem[i].key=L.elem[k].key; L.elem[k].key=L.elem[0].key; mov+=3; } w++; } d=d/2; w=1; } printf(\"比较次数为 %d移动次数为 %d\\n\A[3]=com; B[3]=mov; } void BeforeSort() { 17 数据结构课程设计 yd1=0,bj1=0; } void display(int m,int n) { printf(\"比较次数为 %d移动次数为 %d\\n\} int Partition(SqList L,int low,int high) //快速排序 { int pivotkey; L.elem[0]=L.elem[low]; yd1++; pivotkey=L.elem[low].key; while (low L.elem[low]=L.elem[high]; bj1++; yd1++; } while (low L.elem[low]=L.elem[0]; yd1++; return low; 18 数据结构课程设计 } void QSort(SqList &L,int low,int high) { int pivotloc; if(low void QuickSort(SqList &L) { BeforeSort(); QSort(L,1,L.length); display(bj1,yd1); end_t=clock(); A[4]=bj1; B[4]=yd1; } void Merge(ElemType R[],ElemType R1[],int low,int m,int high) //归并排序 { int i=low, j=m+1, k=low; while(i<=m&&j<=high) { if(R[i].key<=R[j].key) { bj1++; R1[k]=R[i]; yd1++; i++; k++; } 19 数据结构课程设计 else { bj1++; R1[k]=R[j]; yd1++; j++; k++; } } while(i<=m) { R1[k]=R[i]; yd1++; i++; k++; } while(j<=high) { R1[k]=R[j]; yd1++; j++; k++; } } void MergePass(ElemType R[],ElemType R1[],int length, int n) { int i=0,j; while(i+2*length-1 if(i+length-1 20 数据结构课程设计 else for(j=i;j int length=1; while (length MergePass(R1,R,length,n); length=2*length; } } void MergeSort(SqList &L) { start_t=clock(); BeforeSort(); MSort(L.elem,L.elem,L.length); display(bj1,yd1); end_t=clock(); t5=(double)(end_t-start_t)/CLK_TCK; printf(\"排序用时为 %f\\n\ A[5]=bj1; B[5]=yd1; C[5]=t5; } void printf(SqList &L) { long int d[6]; int i,n; printf(\"\\n★★★★★★比较次数★★★★★★\\n\"); 21 数据结构课程设计 printf(\"\\n=====================\\n\"); for(i=0;i<5;i++) d[i]= sqrt (A[i]/A[5]); printf(\"\\n 归并排序： *\"); printf(\"\\n=====================\\n\"); printf(\" 选择排序： \"); for(n=0,i=0;n<=d[i];n++) { printf(\"*\"); } printf(\"\\n=====================\\n\"); printf(\" 冒泡排序： \"); for(n=0,i=1;n<=d[i];n++) { printf(\"*\"); } printf(\"\\n=====================\\n\"); printf(\" 希尔排序： \"); for(n=0,i=3;n<=d[i];n++) { printf(\"*\"); } printf(\"\\n=====================\\n\"); printf(\" 快速排序： \"); for(n=0,i=4;n<=d[i];n++) { printf(\"*\"); } printf(\"\\n=====================\\n\"); printf(\"\\n★★★★★★移动次数★★★★★★\\n\"); printf(\"\\n=====================\\n\"); double e[6]; 22 数据结构课程设计 for(i=0;i<6;i++) e[i]= sqrt (B[i]/B[3]); printf(\"\\n 希尔排序： *\"); printf(\"\\n=====================\\n\"); printf(\" 选择排序： \"); for(n=0,i=0;n<=e[i];n++) { printf(\"*\"); } printf(\"\\n=====================\\n\"); printf(\" 冒泡排序： \"); for(n=0,i=1;n<=e[i];n++) { printf(\"*\"); } printf(\"\\n=====================\\n\"); printf(\" 快速排序： \"); for(n=0,i=4;n<=e[i];n++) { printf(\"*\"); } printf(\"\\n=====================\\n\"); printf(\" 归并排序： \"); for(n=0,i=5;n<=e[i];n++) { printf(\"*\"); } printf(\"\\n=====================\\n\"); void main() { SelectSort(L); 23 数据结构课程设计 addlist(L); printf(\"\\n起泡排序: \\n\"); InsertSort(L); addlist(L); printf(\"\\n希尔排序: \\n\"); xier(L); addlist(L); printf(\"\\n快速排序: \\n\"); QuickSort(L); addlist(L); printf(\"\\n归并排序: \\n\"); MergeSort(L); printf(L); } 24 数据结构程序设计 完成日期：2009年12月23日 25 因篇幅问题不能全部显示，请点此查看更多更全内容