数据结构课程设计-排序算法集成Word版

整理为word格式整理为word格式整理为word格式xx大学本科生课程设计论文题目：排序算法集成学生姓名：学号：专业：计算机班级：指导教师：2013年整理为word格式整理为word格式整理为word格式xx大学课程设计任务书课程名称数据结构课程设计设计题目排序算法集成指导教师时间2013.5.20-2013.5.30一、教学要求1.掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力2.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力4.训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风二、设计资料及参数每个学生在教师提供的课程设计题目中任意选择一题，独立完成，题目选定后不可更换。排序算法集成定义动态数组类（或类模板）以表示待排序数据，在此基础上实现多种排序算法。要求设计函数模板来实现下列排序算法：直接插入排序冒泡排序简单选择排序希尔排序快速排序堆排序并设计主函数测试动态数组类（或类模板），测试各排序算法的函数模板。三、设计要求及成果1.分析课程设计题目的要求

2.写出详细设计说明

3.编写程序代码，调试程序使其能正确运行

4.设计完成的软件要便于操作和使用

5.设计完成后提交课程设计报告四、进度安排资料查阅与讨论（1天）系统分析（2天）系统的开发与测试（5天）编写课程设计说明书和验收（2天）五、评分标准1.根据平时上机考勤、表现和进度，教师将每天点名和检查2.根据课程设计完成情况，必须有可运行的软件。

3.根据课程设计报告的质量，如有雷同，则所有雷同的所有人均判为不及格。4.根据答辩的情况，应能够以清晰的思路和准确、简练的语言叙述自己的设计和回答教师的提问六、建议参考资料1．《数据结构（C语言版）》严蔚敏、吴伟民主编清华大学出版社2004.112．《数据结构课程设计案例精编（用C/C++描述）》，李建学等编著，清华大学出版社2007.23.《数据结构:用面向对象方法与C++语言描述》，殷人昆主编，

清华大学出版社2007.6整理为word格式整理为word格式整理为word格式目录目录 3引言 4一．算法的设计思想 4二．算法的流程图 4三．算法的设计与分析 53.1 建立数组 53.2算法思想 53.3 主要函数 63.4 主要函数声明 63.5主要变量说明 10四．程序源代码 11五．运行结果与分析（测试） 18六．总结（收获与体会） 20七．参考文献 21整理为word格式整理为word格式整理为word格式引言一．算法设计的思想数据结构是与数据相关的一门重要学科，不论是想通过升学考试还是想把程序编得有水平，都要对这门学科下一点功夫才行。而课程设计是让我们更好的掌握这门学科的重要方式。排序是计算机程序中的一种重要操作，它的功能是将一个数据元素（或记录）的任意序列重新排列成一个按关键字有序的序列。而内部排序中包括各种不同的排序，本课程设计主要讨论的是插入排序、希尔排序、冒泡排序、快速排序、选择排序、堆排序。完成这几种排序最主要的就是弄好不同排序的算法，只有深刻的认识了这不同排序的算法，才能了解不同排序的优点与缺点。通过对不同排序算法的分析，了解它们的优劣特点。插入排序、希尔排序、冒泡排序、快速排序、选择排序、堆排序的不同算法，写出实现各个排序算法的函数。然后通过在主函数中对不同排序的子函数的调用来实现对某个序列的具体排序。二．算法的流程图整理为word格式整理为word格式整理为word格式如图2.1建立数组建立数组设计main函数建立各排序函数结束开始图2.1主要设计思想流程图三．算法的设计与分析3.1建立数组在程序中建立一个数组data[]，用于存储程序运行中的数据。3.2算法思想（1）插入排序插入排序的主要算法思想是将一个记录插入到已排好的有序表中，从而得到一个新的、记录数增1的有序表。（2）希尔排序希尔排序的基本思想是先将整个待排记录列分割成若干子序列分别进行直接插入排序，待整个序列中的记录整理为word格式整理为word格式整理为word格式“基本有序”时，再对全体记录进行一次直接插入排序。（3）冒泡排序函数冒泡排序首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序则将两个记录交换，然后比较第二个记录和第三个记录的关键字，依次类推。（4）选择排序函数选择排序的基本思想是：每一趟在n-i+1(i=1,2,…,n-1)个记录中选取关键字最小的记录作为有序序列中第i个记录。（5）堆排序先将一个序列进行建堆，然后将大顶堆的第一个元素和最后一个元素对换（或将小顶堆的最后一个元素和第一个元素对换），再对除最后一个元素的序列进行求大顶堆（或对除第一个元素的序列进行求小顶堆），依次类推。3.3主要函数（1）插入排序函数voidinsertion_sort(int[],int);/*插入排序*/（2）希尔排序函数voidshell_sort(int[],int);/*希尔排序*/（3）冒泡排序函数voidbubble_sort(int[],int);/*冒泡排序*/（4）选择排序函数voidselect_sort(int[],int);/*选择排序*/（5）将数据调整为堆的函数voidadjust(int,int);/*将数据调整为堆树*/3.4主要函数声明整理为word格式整理为word格式整理为word格式①插入排序插入排序的主要算法思想是将一个记录插入到已排好的有序表中，从而得到一个新的、记录数增1的有序表。voidinsertion_sort(intdata[],intsize)/*插入排序*/{intbase,compare,temp,i,j=0;for(base=1;base<size;base++)/*当数据小于第一个时，则插于前方，否则与后面数据对比找出插入位置*/{temp=data[base];compare=base;j++;while(compare>0&&data[compare-1]>temp){data[compare]=data[compare-1];compare--;}data[compare]=temp;printf("第%d趟排序:",j);for(i=0;i<size;i++) printf("%d",data[i]);printf("\n");}printf("\n最终排序结果:");for(i=0;i<size;i++)printf("%d",data[i]);printf("\n");}②希尔排序希尔排序的基本思想是先将整个待排记录列分割成若干子序列分别进行直接插入排序，待整个序列中的记录整理为word格式整理为word格式整理为word格式“基本有序”时，再对全体记录进行一次直接插入排序。voidshell_sort(intdata[],intsize)/*希尔排序*/{inti,j,k,incr,temp,num=0;incr=size/2;printf("\n");while(incr>0){ for(i=incr+1;i<size;i++){j=i-incr;while(j>0)if(data[j]>data[j+incr])/*比较每部分的数据大小顺序不对则交换*/{ temp=data[j];data[j]=data[j+incr]; data[j+incr]=temp; j=j-incr;}elsej=0;}num++;printf("\n第%d趟排序:",num);for(k=1;k<size;k++)printf("%d",data[k]);incr=incr/2;}printf("\n最终排序结果：");整理为word格式整理为word格式整理为word格式for(i=1;i<size;i++)printf("%d",data[i]);printf("\n");}③冒泡排序冒泡排序首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序则将两个记录交换，然后比较第二个记录和第三个记录的关键字，依次类推。voidbubble_sort(intdata[],intsize)/*冒泡排序*/{inti,j,flag,k,temp,num=0;for(i=0;i<size-1;i++){flag=0;for(j=0;j<size-1;j++)/*让数据两两比较，将小的置于前*/ {if(data[j]>data[j+1]){flag=1; temp=data[j]; data[j]=data[j+1]; data[j+1]=temp; } num++; printf("\n第%d趟排序：",num); for(k=0;k<size;k++) printf("%d",data[k]); printf("\n"); }printf("\n最终排序结果：");for(i=0;i<size;i++)printf("%d",data[i]);printf("\n");整理为word格式整理为word格式整理为word格式if(flag!=1) break;}}④选择排序选择排序的基本思想是：每一趟在n-i+1(i=1,2,…,n-1)个记录中选取关键字最小的记录作为有序序列中第i个记录。voidselect_sort(intdata[],intsize)/*选择排序*/{intbase,compare,min,temp,i,num=0;for(base=0;base<size-1;base++)/*将目前数据与后面数据中最小的对调*/{min=base;for(compare=base+1;compare<size;compare++) if(data[compare]<data[min]) min=compare; temp=data[min]; data[min]=data[base]; data[base]=temp;num++; printf("第%d趟排序：",num); for(i=0;i<size;i++) printf("%d",data[i]); printf("\n");}printf("\n最终排序结果：");for(i=0;i<size;i++)printf("%d",data[i]);printf("\n");}整理为word格式整理为word格式整理为word格式3.5主要变量说明Intdata[]:整型数组，用于储存序列Intsize:整型变量，用于记录序列长度Inttemp:整型变量，用于交换元素Intm,n,k,i,j,num:一般整型变量四．程序源代码#include<stdio.h>voidinsertion_sort(int[],int);/*插入排序*/voidshell_sort(int[],int);/*希尔排序*/voidbubble_sort(int[],int);/*冒泡排序*/voidselect_sort(int[],int);/*选择排序*/voidadjust(int,int);/*将数据调整为堆树*/voidinsertion_sort(intdata[],intsize)/*插入排序*/{intbase,compare,temp,i,j=0;for(base=1;base<size;base++)/*当数据小于第一个时，则插于前方，否则与后面数据对比找出插入位置*/{temp=data[base];compare=base;j++;while(compare>0&&data[compare-1]>temp){data[compare]=data[compare-1];compare--;}data[compare]=temp;printf("第%d趟排序:",j);for(i=0;i<size;i++)整理为word格式整理为word格式整理为word格式printf("%d",data[i]);printf("\n");}printf("\n最终排序结果:");for(i=0;i<size;i++)printf("%d",data[i]);printf("\n");}voidshell_sort(intdata[],intsize)/*希尔排序*/{inti,j,k,incr,temp,num=0;incr=size/2;printf("\n");while(incr>0){ for(i=incr+1;i<size;i++) {j=i-incr;while(j>0)if(data[j]>data[j+incr])/*比较每部分的数据大小顺序不对则交换*/ { temp=data[j];data[j]=data[j+incr]; data[j+incr]=temp; j=j-incr; }elsej=0; }整理为word格式整理为word格式整理为word格式num++;printf("\n第%d趟排序:",num);for(k=1;k<size;k++)printf("%d",data[k]);incr=incr/2;}printf("\n最终排序结果：");for(i=1;i<size;i++)printf("%d",data[i]);printf("\n");}voidbubble_sort(intdata[],intsize)/*冒泡排序*/{inti,j,flag,k,temp,num=0;for(i=0;i<size-1;i++){flag=0;for(j=0;j<size-1;j++)/*让数据两两比较，将小的置于前*/{if(data[j]>data[j+1]){flag=1; temp=data[j]; data[j]=data[j+1]; data[j+1]=temp;}num++;printf("\n第%d趟排序：",num);for(k=0;k<size;k++)printf("%d",data[k]);printf("\n");}printf("\n最终排序结果：");整理为word格式整理为word格式整理为word格式for(i=0;i<size;i++)printf("%d",data[i]);printf("\n");if(flag!=1) break;}}voidselect_sort(intdata[],intsize)/*选择排序*/{intbase,compare,min,temp,i,num=0;for(base=0;base<size-1;base++)/*将目前数据与后面数据中最小的对调*/{min=base;for(compare=base+1;compare<size;compare++) if(data[compare]<data[min]) min=compare; temp=data[min]; data[min]=data[base]; data[base]=temp;num++; printf("第%d趟排序：",num); for(i=0;i<size;i++) printf("%d",data[i]); printf("\n");}printf("\n最终排序结果：");for(i=0;i<size;i++)printf("%d",data[i]);printf("\n");}整理为word格式整理为word格式整理为word格式voidadjust(inti,intn)/*将数据调整为堆树*/{intdata[20],j,k,done=0;k=data[i];j=2*i;while((j<=n)&&(done==0)){if((j<n)&&(data[j]<data[j+1]))j++;if(k>=data[j])done=1;else{data[j/2]=data[j];j=2*j;}}data[j/2]=k;}voidmain(){intdata[20];intsize=0,m=0,i,j,num,k,temp,n=0;printf("\n请输入初始关键字（输入0结束）:\n");do{ scanf("%d",&data[size]); m++;}while(data[size++]!=0);printf("你输入的初始关键字为：");整理为word格式整理为word格式整理为word格式for(j=0;j<m-1;j++)printf("%d",data[j]);printf("\n排序方法：\n");printf("\n1、插入排序\n");printf("\n2、希尔排序\n");printf("\n3、冒泡排序\n");printf("\n4、选择排序\n");printf("\n5、堆排序\n");printf("\n请选择排序方法：\n");scanf("%d",&num);switch(num){case1:printf("****************插入排序************\n");for(i=0;i<50;i++)printf("-");printf("\n");insertion_sort(data,--size);for(i=0;i<50;i++)printf("-");printf("\n");break;case2: printf("****************希尔排序************\n"); for(m=0;m<50;m++)printf("-");shell_sort(data,--size); for(i=0;i<50;i++)printf("-");printf("\n");break;case3: printf("****************冒泡排序************\n"); for(i=0;i<50;i++)printf("-");printf("\n");bubble_sort(data,--size);for(i=0;i<50;i++)printf("-");printf("\n");break;case4:整理为word格式整理为word格式整理为word格式 printf("****************选择排序************\n"); for(i=0;i<50;i++)printf("-");printf("\n");select_sort(data,--size);for(i=0;i<50;i++)printf("-");printf("\n");break;case5: size=size-1; printf("*****************堆排序*************\n"); for(i=0;i<50;i++)printf("-"); for(i=size/2;i>0;i--)adjust(i,size); printf("\n堆："); for(k=1;k<siz