《数据结构课程设计53349new.doc》由会员分享，可在线阅读，更多相关《数据结构课程设计53349new.doc（6页珍藏版）》请在金锄头文库上搜索。
1、数据结构课程设计说明书题目： 排序DEMO 院 系： 信电工程学院 专业班级： 06级计本（3）班 学 号： 学生姓名： 指导教师： 杨兴运 2008年 6 月 17 日一 需求分析设计一个程序，使该程序可以实现排序功能，即希尔排序，快速排序，堆排序和归并排序。在这个程序运行时，能够根据要求将要排序的内容正确的排列出来。二 流程图定义函数类型希尔排序开始希尔排序结束快速排序开始快速排序结束堆排序开始堆排序结束归并排序开始建立链表输出三. 详细设计（1） 定义函数类型及大小：#include #include#include#define MAXSIZE 1000typedef struct i
2、nt keyMAXSIZE; int length;Sqlist;long compCount,shiftCount;（2） 定义四种排序：void shellsort(Sqlist L)void QuickSort(Sqlist pL)void heapsort(Sqlist b)void Mergesort(Sqlist L)（3） 希尔排序while (dk0) compCount+; for(i=dk+1;i0) compCount+; if(L.keyjL.keyj+dk) compCount+; AS=L.keyj; L.keyj=L.keyj+dk; L.keyj+dk=AS;
3、j=j-dk; shiftCount+=3; else j=0;（4） 对顺序表L中的子序列pL.keylow.high作快速排序int pivotloc; if(lowhigh) compCount+; pivotloc=Partition(pL,low,high); QSort(pL,low,pivotloc-1);QSort(pL,pivotloc+1,high); (5) 堆排序while(j=n) compCount+; if(jkeyjkeyj+1) j+;compCount+=2; if(tempa-keyj) break; else compCount+; a-keyi=a-k
4、eyj; i=j; shiftCount+=2; j=2*i; a-keyi=temp;shiftCount+;return a;Sqlist * initheap(Sqlist *a)int i,n;Sqlist *b;n=a-length;（6） 归并排序while(lb1+size)n) ub2=n-1; compCount+; shiftCount+; else ub2=lb2+size-1; compCount+; shiftCount+; i=lb1; j=lb2; while(i=ub1)&(j=ub2) compCount+;compCount+; if(sourcei=sou
5、rcej) resultp+=sourcei+; shiftCount+; compCount+; else resultp+=sourcej+; shiftCount+; compCount+; while(i=ub1) resultp+=sourcei+; shiftCount+; compCount+; while(j=ub2) resultp+=sourcej+; shiftCount+; compCount+; lb1=ub2+1; i=lb1; while(pn) compCount+; resultp+=sourcei+;shiftCount+;（7） 建立链表Sqlist ci
6、n()Sqlist L四 调试分析a. 问题及处理在本程序的编译运行过程中，遇到了许多问题。首先，在关于希尔排序的程序设计时，每趟增量由gap=n/2得到，而并不一定满足除1之外的公因子条件，所以会在我编写过程中造成遗漏的情况；在编写快速排序时，记录的标准元素的左右关键字出现错误；对于归并排序的递归和非递归两种实现方法的选择上仍然存在混淆。b. 经验与体会在数据结构课程设计的实习中，通过自己动脑动手，借助书本资料以及网上信息，编写了关于四种排序方法的实现的程序。在编写程序过程中，让我温故知新，对于各种排序的方法作进一步的了解与掌握，能过熟练的运用到以后的学习工作中去。通过自己的课程设计，也让我
7、汲取了从各个途径获得的有关计算机专业方面的信息，也了解了如何深入的掌握本专业的课程学习。五 测试结果input list length:6input list key：12 3 31 28 15 31sortkinds compcount shiftcount Resultshellsort 24 0 3 7 12 15 28 31 Quicksort 23 0 3 7 12 15 28 31 Heapsort 54 0 3 7 12 15 28 31 Mergesort 55 0 3 7 12 15 28 31 input list length:10input list key：1 17
8、99 65 45 23 78 61 44 10sortkinds compcount shiftcount Resultshellsort 66 0 1 10 17 23 44 45 61 65 78 99 Quicksort 71 0 1 10 17 23 44 45 61 65 78 99 Heapsort 136 0 1 10 17 23 44 45 61 65 78 99 Mergesort 103 0 1 10 17 23 44 45 61 65 78 99 input list length:7input list key：12 33 21 1 5 78 18sortkinds compcount shiftcount Resultshellsort 32 0 1 5 12 18 21 33 78 Quicksort 33 0 1 5 12 18 21 33 78 Heapsort 71 0 1 5 12 18 21 33 78 Mergesort 75 0 1 5 12 18 21 33 78 六 参考文献a) 数据结构与算法分析C语言描述（原书第二版） 机械工业出版社b) 数据库系统概论（第三版） 高等教育出版社c) 数据结构（第二版） 清华大学出版社d) 数据库系统开发与应用 中国水利水电出版社e) 相关的网络资源6
