搜索
课程设计(论文)任务书软件学院学院软件+桥梁专业2013—1班一、课程设计(论文)题目内部排序算法比较二、课程设计(论文)工作自2014年1月6日起至2014年1月12日止三、课程设计(论文)地点:创新大楼软件实训中心机房四、课程设计(论文)内容要求：1．本课程设计的目的⑴训练学生灵活应用所学数据结构知识，独立完成问题分析，结合数据结构理论知识，编写程序求解指定问题；⑵初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；⑶提高综合运用所学的理论知识和方法独立分析和解决问题的能力，巩固、深化学生的理论知识，提升编程水平。2．课程设计的任务及要求1）基本要求：⑴要求从分析题目的需求入手，按设计抽象数据类型、构思算法、通过设计实现抽象数据类型、编写上机程序和上机调试等若干步骤完成题目，最终写出完整的报告；⑵在程序设计阶段应尽量利用已有的标准函数，加大代码的重用率；⑶程序设计语言推荐使用C/C++，程序书写规范，源程序需加必要的注释；⑷每位同学需提交可独立运行的程序和规范的课程设计报告。2）课程设计论文编写要求⑴理论设计部分以课程设计论文的形式提交，格式必须按照课程设计论文标准格式进行书写和装订；⑵课程设计报告（论文）包括中文目录、设计任务、需求分析、概要设计、详细设计、编码实现、调试分析、课设总结、谢辞、参考文献、附录等；⑶设计部分应包含系统功能模块图，调试分析应包括运行截图等。3）课程设计评分标准：⑴学习态度：10分；⑵系统设计：20分；⑶编程调试：20分；⑷回答问题：20分；⑸论文撰写：30分。4）参考文献：⑴严蔚敏,吴伟民.数据结构(C语言版)[M].清华大学出版社.2010.3⑵严蔚敏,吴伟民.数据结构题集(C语言版)[M].清华大学出版社.1999.2⑶何钦铭,冯燕等.数据结构课程设计[M].浙江大学出版社.2007.85）课程设计进度安排⑴准备阶段（4学时）：选择设计题目、了解设计目的要求、查阅相关资料；⑵程序模块设计分析阶段（4学时）：程序概要设计、详细设计；⑶代码编写调试阶段（8学时）：程序模块代码编写、调试、测试；⑷撰写论文阶段（4学时）：总结课程设计任务和设计内容，撰写课程设计论文。学生签名：2014年1月5日6）课程设计题目具体要求：通过随机数据比较算法的关键字比较次数和关键字移动次数，以取得直观感受任务：（1）至少采用三种不同的方法实现上述问题求解（2）待排序的表长不小于100，其中的数据要用伪随机数产生程序产生；至少要用5组不同的输入数据作比较；比较的指标为有关键字的比较次数和关键字的移动次数（关键字交换计为3次移动）（3）最后对结果做出简单分析，包括对各组数据波动大小的解释课程设计(论文)评审意见（1）学习态度（10分）：优（）、良（）、中（）、一般（）、差（）；（2）系统设计（20分）：优（）、良（）、中（）、一般（）、差（）；（3）编程调试（20分）：优（）、良（）、中（）、一般（）、差（）；（4）回答问题（20分）：优（）、良（）、中（）、一般（）、差（）；（5）论文撰写（30分）：优（）、良（）、中（）、一般（）、差（）；（6）格式规范性及考勤是否降等级：是（）、否（）评阅人：王英华职称：讲师2014年1月13日目录一、问题描述……………………………………………..1二、设计任务…………………………………………….1三、需求分析……………………………………………..2四、编码实现……………………………………………..6五、调试分析…………………………………………..…11六、课设总结……………………………………………..14七、参考文献………………………………………141内部排序算法比较一、问题描述排序是数据结构中重要的一个部分，也是在实际开发中易遇到的问题，所以研究各种排算法的时间消耗对于在实际应用当中很有必要通过分析实际结合算法的特性进行选择和使用哪种算法可以使实际问题得到更好更充分的解决！该系统通过对各种内部排序算法如直接插入排序，冒泡排序，简单选择排序，快速排序，希尔排序，堆排序、二路归并排序等，以关键码的比较次数和移动次数分析其特点，并进行比较，估算每种算法的时间消耗，从而比较各种算法的优劣和使用情况！排序表的数据是多种不同的情况，如随机产生数据、极端的数据如已是正序或逆序数据。比较的结果用一个直方图表示。二、设计任务基本要求：⑴至少采用三种方法实现上述问题求解（提示，可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序）。⑵待排序表的表长不小于100，其中的数据要用伪随机数产生程序产生；至少要用5组不同的输入数据作比较；比较的指标为有关键字参加的比较次数和关键字的移动次数（关键字交换计为3次移动）。⑶最后对结果作出简单分析，包括对各组数据得出结果波动大小的解释。2三、需求分析排序是数据处理中经常遇到的一种重要操作，然而排序的算法有很多种，各有其优点和缺点。本程序设计的主要目的是通过比较各种内部排序的时间复杂度，即元素比较次数和移动次数来判断各个算法的波动性，和适合于哪些排序。1.系统用到的数据：a,b,c,d,L五个线性表数组a[10]，ak[MAXV]这里的MAXV表示100002.系统用到的函数：intCreateSqList(SqList&L)//给定随机数voidHeapAdjust(SqList&L,ints,intk)//堆调整voidHeapSort(SqList&L)//进行堆排序voidmaopao(SqList&L)//进行冒泡排序voidInsert(SqList&L)//进行直接插入排序voidSelect(SqList&L)//进行简单选择排序voidShellInsert(SqList&L,intzL)//一趟希尔排序voidShell(SqList&L,intdata[])//进行希尔排序voidbijiao()//判断波动性小的排序方式3.记录类型和线性表的定义typedefintKeyType;typedefstruct{KeyTypekey;}RedType;typedefstruct{3RedTyper[MAXV+1];RedTyperc,t;intlength;}SqList;4.系统设计：系统有九个函数，八个函数在各个排序时会用到，另外一个是用来判定排序波动性的，系统先通过intCreateSqList(SqList&L)获得一个随机数然后将随机数放到顺序表中，在通过各个排序函数将其排序，其中m记录比较次数，n记录移动次数，交换一次当做移动三次。图1-1系统功能模块5.设计数据元素：采用的是结构体定义关键字key数组r[MAXV+1],记录类型元素rc,t顺序表表长length给定随机数赋值给顺序表a,b,c,d,L堆排序冒泡排序直接插入排序简单选择排序希尔排序46.各个函数的设计：1.构建随机数放到顺序表中：intCreateSqList(SqList&L)设计思路：手动输入数据元素的元素个数k由L.r[x].key=rand()%k;来产生所要的随机数，并放到顺序表L中2.进行堆排序：voidHeapAdjust(SqList&L,ints,intk)//堆调整voidHeapSort(SqList&L)设计思路：通过for(i=L.length/2;i0;i--)HeapAdjust(L,i,L.length);构造大顶堆然后将顶部元素与最后一个交换，再进行调整，这个第一个最大的换到最后一个，第二个最大的放到倒数第二个，以此类推则可以按从小到大排好序。3.进行冒泡排序：voidmaopao(SqList&L)设计思路：首先将关键字L.r[1].key与L.r[2].key比较，若L.r[1].key大，互换，然后比较第二个记录和第三个记录的关键字，依次类推直到第n-1个记录和第n个记录的关键字进行比较为止，这是第一趟排序。第二趟排序是对前n-1个元素进行同样的操作，直到第n-1趟排序也是如此，则可以排好序了。4.直接插入排序：voidInsert(SqList&L)设计思路：现将第一个记录看成是有序列，然后从第二个纪录开始进行逐个插入，直至整个序列变成按关键字非递减排列，第i趟直接插入排序的操作是在含有i-1个记录5的有序子列r[1]到r[i-1]中插入r[i]后变成含有i个记录的有序列，为了防止出界设立哨兵r[0]。5.简单选择排序voidSelect(SqList&L)设计思路：每一趟在n-i+1个记录中选取关键字最小的记录作为有序序列中第i个记录。这里是用r[0]来暂存最小的元素，l来记录此时剩余元素最小的下标，按顺序依次将最小的次小的给r[0],r[1].....6.进行希尔排序：voidShellInsert(SqList&L,intzL)voidShell(SqList&L,intdata[])设计思路：通过while(j=0){++t;j-=2;}确定排序的次数t；j=L.length/2;确定每一次排序的增量，通过每一趟排序的两两比较，最终确定整个序列的排序，这里的第i个总是与第i-j个进行比较，i是从j+1开始逐渐，使得每个数都比较了。7.排序波动性的判定：voidbijiao()设计思路：6每一各排序的移动次数我都按顺序放到了a[10]数组中，只需要找到数组中最小的元素记录下标，通过switch语句就可以找到移动次数最小的排序方式;四、编码实现2.1给定随机数模块intCreateSqList(SqList&L){intk;cout输元素个数:;cink;L.length=k;srand(time(NULL));for(intx=1;x=k;x++){L.r[x].key=rand()%k;//随机域为0~k}return1;}2.2堆排序模块voidHeapAdjust(SqList&L,ints,intk)//堆调整{intj;L.rc=L.r[s];//是暂存要正进行调整的非叶子节点，从最后一个非叶子节点开始for(j=2*s;j=k;j*=2){m++;if(jk&&LS(L.r[j].key,L.r[j+1].key))//L.r[j]对应记录的左孩子++j;//大的孩子下标给jif(!LS(L.rc.key,L.r[j].key))break;L.r[s]=L.r[j];n++;s=j;}L.r[s]=L.rc;}voidHeapSort(SqList&L){inti;for(i=L.length/2;i0;i--)//构造大顶堆HeapAdjust(L,i,L.length);//i对应的是非叶子节点for(i=L.length;i1;i--)//将每一个根与最后一个节点互换{L.t=L.r[1];7L.r[1]=L.r[i];L.r[i]=L.t;n+=3;HeapAdjust(L,1,i-1);//将其他的节点调整}coutendl*********堆排序后的序列*********endl;for(i=1;i=L.length;i++)coutL.r[i].key;coutendl;cout堆排序的比较次数:;coutmendl;cout堆排序的移动次数:;coutnendl;a[0]=n;}2.3冒泡排序模块voidmaopao(SqList&L)//冒泡排序{inti,j,t,k=L.length,m=0,n=0;for(i=1;i=L.length-1;i++){for(j=1;j=k-1;j++){++m;if(LT(L.r[j].key,L.r[j+1].key)){t=L.r[j].key;L.r[j].key=L.r[j+1].key;L.r[j+1].key=t;n+=3;}}--k;}coutendl*********冒泡排序后的序列*********endl;for(i=1;i=L.length;i++)coutL.r