数据结构课程设计快速排序和归并排序

1、XX学院信息科学与工程系课程设计说明书课程名称:数据结构课程代码:题目 :快速排序与归并排序年级/专业/班:学生姓名:奉 XX学号 :1440000000指导教师:易开题时间:2015年 12月 30日完成时间:2016年 1月 10日目录摘要1一、引言3二、设计目的与任务31、课程设计目的32、课程设计的任务3三、设计方案31、需求分析32、概要设计43、详细设计54、程序清单13四、调试分析与体会19五、运行结果20六、结论24七、致谢24八、参考文献25摘要数据结构课程设计，列举了数据结构课程设计实例，通过综合训练， 能够培养学生实际分析问题、解决问题、编程和动手操作等多方面的能力，最终

2、目的是帮助学生系统地掌握数据结构的基本内容，并运用所学的数据结构知识去解决实际问题。其中内容包括数组、链接表、栈和队列、递归、树与森林、图、堆与优先级队列、集合与搜索结构、排序、索引与散列结构等关键字 ：数据结构；分析；掌握Abstract1Data structure course design, lists the datastructure course designas an example, throughthe comprehensivetraining,to cultivatestudentspracticalanalysisand solveproblemsinmany asp

3、ects, programming, and hands-on ability, the ultimate goal is to help students tosystematically master the basic content of data structure, and using the data structure ofknowledge to solvepracticalproblems.Contentincludingarray,linkedlist,stackand queue,recursion, tree and forest, graph, heap and p

4、riorityqueue, the structure ofthe collectionand search, sorting, indexing and hashing structure, etcKeywords:data structure；Analysis； master2数据结构课程设计-快速排序与归并排序一、引言二、 将一组数据运用快速排序与归并排序进行排序，要求使用递归与非递归方法三、本次课程设运用到了数组、链接表、栈、递归、排序等结构。四、 在学校机房进行程序设计，编写代码，实现程序的功能二、设计目的与任务1、课程设计目的1、能够更灵活地应用所学数据结构知识，独立完成问题分析，

5、结合数据结构理论知识，编写程序求解指定问题。2. 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；3. 提高综合运用所学的理论知识和方法独立分析和解决问题的能力；4. 数据结构课程设计是学习 C 语言的一个重要过程，通过此次实践，学生对书本上的知识通过上机操作有了更形象的理解，对今后的学习有很大的帮助。2、课程设计的任务问题描述 :做一个快速排序与归并排序三、设计方案1、需求分析1) 对一组数据进行快速排序和递归排序2) 快速排序：快速排序对气泡排序的一种改进。它的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，

6、则可分别对两部分记录继续进行排序，以达到整个序列有序。3) 归并排序： 归并排序是又一类不同的排序方法。 “归并” 的含义是将两个或两个以上的有序表组合成一个新的有序表。无论是顺序存储结构还是链表存储结构，都可在O（ m+n)（ m,m分别为有序表的长度）的时间量级上实现。利3用归并的思想容易实现排序。2、概要设计1) 抽象数据类型 (ADT)如下：ADT SqLint数据对象 ： D=a|a iint, i=1,2,n,n0数据关系 ： R1= | ai-1,ai D,i=2,n 基本操作：int InitSqlint(SqLint &L)/ 构造一个空的线性表 Lvoid Assignme

7、nt(SqLint &L)/ 给表 L.element 赋值void Output(SqLint L)/ 输出表里的L.ELenght个元素Status InitStack(SqStack &S)/ 栈的初始化Status Push(SqStack &S,SElemType e)/ 入栈Status Pop(SqStack &S,SElemType &e)/ 出栈int Partition(SqLint &L,int low,int high)/ 交换顺序表 L.element 里的值，以枢轴为中心，小的在前，大的在后int QuickSort(SqLint &L,int low,int hi

8、gh)/ 非递归快速排序算法int RQuickSort(SqLint &L,int low,int high)/ 递归快速排序算法void Merge(SqLint &L,int low,int mid,int high)/ 对子串进行合并排序int MergeSort(SqLint &L)/ 非递归归并排序算法int RMergeSort(SqLint &L,int low,int high)/ 递归归并排序算法2)存储结构Typedef struct int *element; /存储空间基址int ELenght;/ 当前分配的存储容量个数 SqLint;3)过程图43、详细设计本程序

9、中的重要程序段如下， 功能是分别实现快速排序与归并排序， 并且分别用不同的方法 ( 递归与非递归 ) ，并且判断程序是否正确等 ( 简要介绍设计中的重要程序段 )快速排序： 通过一趟排序将待排序记录分割成独立的两个区间，其中左区间记录的关键字的值均比右区间中记录的关键字的值小，再分别对这两个区间中的记录进行快速排序，以达到整个序列有序为止。1) 重要程序段 1/ 交换顺序表 L.element 里的值，以枢轴为中心，小的在前，大的在后5int Partition(SqLint &L,int low,int high)int pivot=L.elementlow;/ 将第一个元素给piovt作为

10、枢轴while(low!=high)/ 从表中的两端交替地向中间扫描while(low=pivot) high-;/ 一路将后端的值进行扫描，直到找到比枢轴小的值为止L.elementlow=L.elementhigh;/ 将比枢轴小的值移到低端while(lowhigh&L.elementlow=S.stacksize)/栈满，追加存储空间S.base=(SElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType);if(!S.base) return ERROR;/ 存储分配失败S.top=S.base+

11、S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+=e;return OK;/Push/ 出栈Status Pop(SqStack &S,SElemType &e)/ 若栈不空，则删除 S 的栈顶元素，用 e 返回其值，并返回 OK，否则返回 ERROR if(S.base=S.top) return ERROR;e=*-S.top; return OK;/Top3) 重要程序段 3/ 非递归快速排序算法int QuickSort(SqLint &L,int low,int high)/ 采用快速排序的方法对L.element进行升序排序/ 利用栈，

12、保存每一个待排序子串的首尾元素下标，下一次while循环时取出这个范围，/ 对这段子序列进行 partition 操作SqStack S;/ 定义一个栈Sint p,l,h;/p记录枢轴的位置，l 记录子串首元素位置，h l记录子串尾元素位置InitStack(S); /初始化栈7if(lowlow)/ 取枢轴前子串的首尾位置入栈Push(S,low);Push(S,p-1);if(p+1l)/ 取枢轴前子串的首尾位置入栈Push(S,l);Push(S,p-1);if(p+1h)/ 取枢轴后子串的首尾位置入栈Push(S,p+1);Push(S,h);free(S.base); /释放 S.

13、bese的空间return 1;/ 排序成功返回14) 重要程序段 4/ 递归快速排序算法int RQuickSort(SqLint &L,int low,int high)/ 采用快速排序的方法对L.element进行升序排序8/ 运用递归的方法，对串进行排序，int p; /p用来记录枢轴的位置if(lowhigh) /判断长度是否大于1p=Partition(L,low,high);/ 将串 L.elementlow.,high一分为二RQuickSort(L,low,p-1);/ 对底子表进行递归排序RQuickSort(L,p+1,high);/ 对底子表进行递归排序return 1

14、;/ 排序成功返回1归并排序： 先将前后相连的元素比较合并成有序的子序列，然后再将前后的子序列进行比较合并成有序的新的子序列，重复以上步骤，直到整个序列有序为止1) 重要程序段 1/ 对子串进行合并排序void Merge(SqLint &L,int low,int mid,int high)/ 对子串 L.element进行二分排序，以mid 为分界点，将L.element分为底端和高端，然后底端和高端进行比较排序，int i=low,j=mid+1,k;/i记录底端最前位置，j 记录高端最前位置，k 用来记录 temp 元素个数int *temp;temp=(int *)malloc(L.

15、ELenght*sizeof(int);/ 给 temp 分配存储空间if(!temp) printf(分配空间失败 n); return ;/ 存储分配失败k=0; / 赋值第一个位置while(i=mid&jL.elementj)tempk+=L.elementi+;elsetempk+=L.elementj+;while(i=mid) /判断底端是否有值，有则赋值给temptempk+=L.elementi+;while(j=high)/ 判断高端是否有值，有则赋值给temp9tempk+=L.elementj+;for(i=low,j=0;i=high;j+,i+)/ 把 temp 里

16、的值给 L.elementL.elementi=tempj;free(temp);/ 释放 temp2)重要程序段 2/ 非递归归并排序算法int MergeSort(SqLint &L)/ 采用归并排序的方法对L.element进行降序排序/ 将一个数组对半分为两个子串，并且这两个子串是有序的。/ 再将两个 有序的子串 合并 为 一个有序的数组。int i,j,low,mid,high;/i记录每次子序列比较的步长，j记录在 temp 中记录存放的个数, low记录/ 子串的 最前端位置， mid 记录子串的中间位置， high 记录最后端位置for(i=1;iL.ELenght;i*=2)

17、/ 记录并控制每一步步长for(low=0;lowL.ELenght)/ 判断 high是否比总元素个数大high=L.ELenght;Merge(L,low,mid-1,high-1);/ 把 结构体 L 子串最底端，中间端的前一个，最高端给Mergereturn 1; /归并排序成功返回 13) 重要程序段 3/ 递归归并排序算法int RMergeSort(SqLint &L,int low,int high)/ 采用归并排序的方法对L.element进行降序排序10/ 将一个数组对半分为两个子串，并且这两个子串是有序的。/ 再将两个 有序的子串 合并 为 一个有序的数组。int mid

18、;/ 记录中间位置if(lowhigh) /判断长度是否大于1mid=(low+high)/2;/ 将 L.elementlow ，high 分为 L.elementlow.mid和 L.elementmid+1.highRMergeSort(L,low,mid);/ 递归将 L.elementlow.mid归并为有序的 L.elementlow.midRMergeSort(L,mid+1,high);/ 递归将 L.elementmid+1.high 归并为有序的 L.elementmid+1.highMerge(L,low,mid,high);/ 把 结构体 L 子串最底端，中间端的前一个

19、，最高端给Mergereturn 1;/归并排序成功返回 1主函数与排序函数的调用void Sort()SqLint L; /定义一个结构体Lint *a,i; /a记录输入数据的原值 ,i记录 a 的元素个数长度printf(请输入要排序的长度个数n);scanf(%d,&L.ELenght); /给 L.ELenght赋值，给定要输入值的个数if(InitSqlint(L) /判断是否开辟存储空间成功，开辟成功则执行以下步骤Assignment(L);/ 给 L.element依次赋值a=(int *)malloc(L.ELenght*sizeof(int);/ 给 a 分配存储空间if(

20、!a) printf(分配空间失败 n); return ;/ 存储分配失败for(i=0;iL.ELenght;i+) /将 L.element里的值给aai=L.elementi;printf(nn此时表里的数据顺序依次为：n);Output(L);printf(n升序快速排序过程： （非递归） );if(QuickSort(L,0,L.ELenght-1)/ 判断是否进行非递归快速排序成功，成功则输出表中的有序序列printf(n经过非递归快速排序之后，表中的顺序为：n);11Output(L);else printf(排序失败 n);for(i=0;iL.ELenght;i+)/ 将

21、a里的值给 L.elementL.elementi=ai;printf(nn此时表里的数据顺序依次为：n);Output(L);printf(n升序快速排序过程： （递归） );if(RQuickSort(L,0,L.ELenght-1)/ 判断是否进行递归快速排序成功，成功则输出表中的有序序列printf(n经过递归快速排序之后，表中的顺序为：n);Output(L);else printf(排序失败 n);for(i=0;iL.ELenght;i+)/ 将 a里的值给 L.elementL.elementi=ai;printf(nn此时表里的数据顺序依次为：n);Output(L);pri

22、ntf(n降序归并排序过程： （非递归） );if(MergeSort(L)/ 判断是否进行非递归归并排序成功，成功则输出表中的有序序列printf(n经过非递归归并排序之后，表中的顺序为：n);Output(L);else printf(排序失败 n);for(i=0;iL.ELenght;i+)/ 将 a里的值给 L.elementL.elementi=ai;printf(nn此时表里的数据顺序依次为：n);Output(L);printf(n降序归并排序过程： （递归） );if(RMergeSort(L,0,L.ELenght-1)12/ 判断是否进行递归归并排序成功，成功则输出表中的

23、有序序列printf(n经过递归归并排序之后，表中的顺序为：n);Output(L);else printf(排序失败 n);/ 主函数int main()Sort();return 0;4、程序清单#include#include#define ERROR 0#define TRUE 1#define OK 1#define STACK_INIT_SIZE 100 /栈的存储空间初始分配量#define STACKINCREMENT 10/ 栈的空间分配增量typedef int SElemType;typedef int Status;/ 定义结构体进行存储数据typedef struct

24、 int *element; /存储空间基址int ELenght;/ 当前分配的存储容量个数SqLint;/ 构造一个空的线性表Lint InitSqlint(SqLint &L)L.element=(int *)malloc(L.ELenght*sizeof(int); /分配存储空间if(!L.element) return 0;/ 检查分配是否成功，分配失败返回0return 1;/分配成功则返回1 /InitSqlint13/ 给表 L.element赋值void Assignment(SqLint &L)int i;printf(请输入 %d个整形数据作为元素n,L.ELenght

25、);for(i=0;iL.ELenght;i+)/ 给表 L.element从键盘上输入进行逐个赋值scanf(%d,&L.elementi);/ 输出表里的L.ELenght个元素void Output(SqLint L)int i;for(i=0;i=S.stacksize)/栈满，追加存储空间S.base=(SElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType);if(!S.base) return ERROR;/ 存储分配失败S.top=S.base+S.stacksize;S.stacksiz

26、e+=STACKINCREMENT;*S.top+=e;return OK;14/Push/ 出栈Status Pop(SqStack &S,SElemType &e)/ 若栈不空，则删除 S 的栈顶元素，用 e 返回其值，并返回 OK，否则返回 ERROR if(S.base=S.top) return ERROR;e=*-S.top; return OK;/Top/ 交换顺序表 L.element 里的值，以枢轴为中心，小的在前，大的在后int Partition(SqLint &L,int low,int high)/ 交换顺序表L.element里的值，以第一个（low 的位置 ) 做

27、为枢轴值，首先往前取值与枢轴比较，/ 如大于枢轴则取它前一个继续与枢轴比较，如果还是大于枢轴，再往前取，直到取到比枢轴小，/ 当值比枢轴小时，把它放到 low 的位置，然后取 low 位置的值与枢轴比较，小于枢轴时，取下一个/ 继续比较，大于枢轴时，比它放到high 的位置，然后再取 high 位置的值，进时比较，大于枢轴时/ 取它的前一个继续比较，以些类堆，直到low 等于 gigh 为止，int pivot=L.elementlow;/ 将第一个元素给piovt作为枢轴while(low!=high)/ 从表中的两端交替地向中间扫描while(low=pivot) high-;/ 一路将后

28、端的值进行扫描，直到/ 找到比枢轴小的值为止L.elementlow=L.elementhigh;/ 将比枢轴小的值移到低端while(lowhigh&L.elementlow=pivot) low+;/ 一路将后端的值进行扫描，直到/ 找到比枢轴大的值为止L.elementhigh=L.elementlow;/ 将比枢轴大的值移到高端L.elementlow=pivot;/ 枢轴记录到们printf(n);Output(L);return low;/ 返回枢轴位置/ 非递归快速排序算法int QuickSort(SqLint &L,int low,int high)/ 采用快速排序的方法对L

29、.element进行升序排序/ 利用栈，保存每一个待排序子串的首尾元素下标，下一次while循环时取出这个范围，/ 对这段子序列进行partition操作SqStack S;/ 定义一个栈Sint p,l,h;/p记录枢轴的位置，l 记录子串首元素位置，h l记录子串尾元素位置InitStack(S); /初始化栈if(lowlow)/ 取枢轴前子串的首尾位置入栈15Push(S,low);Push(S,p-1);if(p+1l)/ 取枢轴前子串的首尾位置入栈Push(S,l);Push(S,p-1);if(p+1h)/ 取枢轴后子串的首尾位置入栈Push(S,p+1);Push(S,h);f

30、ree(S.base); /释放 S.bese的空间return 1;/ 排序成功返回1/ 递归快速排序算法int RQuickSort(SqLint &L,int low,int high)/ 采用快速排序的方法对L.element进行升序排序/ 运用递归的方法，对串进行排序，int p; /p用来记录枢轴的位置if(lowhigh) /判断长度是否大于1p=Partition(L,low,high);/ 将串 L.elementlow.,high一分为二RQuickSort(L,low,p-1);/ 对底子表进行递归排序RQuickSort(L,p+1,high);/ 对底子表进行递归排序

31、return 1;/ 排序成功返回1/ 对子串进行合并排序void Merge(SqLint &L,int low,int mid,int high)/ 对子串 L.element进行二分排序，以mid 为分界点，将L.element分为底端和高端，然后/ 底端和高端进行比较排序，int i=low,j=mid+1,k;/i记录底端最前位置，j 记录高端最前位置，k 用来记录 temp 元素个数int *temp;16temp=(int *)malloc(L.ELenght*sizeof(int);/ 给 temp 分配存储空间if(!temp) printf(分配空间失败 n); retur

32、n ;/ 存储分配失败k=0; / 赋值第一个位置while(i=mid&jL.elementj)tempk+=L.elementi+;elsetempk+=L.elementj+;while(i=mid) /判断底端是否有值，有则赋值给temptempk+=L.elementi+;while(j=high)/ 判断高端是否有值，有则赋值给temptempk+=L.elementj+;for(i=low,j=0;i=high;j+,i+)/ 把 temp 里的值给 L.elementL.elementi=tempj;free(temp);/ 释放 tempprintf(n);Output(L)

33、;/ 非递归归并排序算法int MergeSort(SqLint &L)/ 采用归并排序的方法对L.element进行降序排序/ 将一个数组对半分为两个子串，并且这两个子串是有序的。/ 再将两个 有序的子串 合并 为 一个有序的数组。int i,j,low,mid,high;/i记录每次子序列比较的步长，j记录在 temp 中记录存放的个数, low记录/ 子串的 最前端位置， mid 记录子串的中间位置， high 记录最后端位置for(i=1;iL.ELenght;i*=2)/ 记录并控制每一步步长for(low=0;lowL.ELenght)/ 判断 high是否比总元素个数大high=

34、L.ELenght;Merge(L,low,mid-1,high-1);/ 把 结构体 L 子串最底端，中间端的前一个，最高端给Mergereturn 1; /归并排序成功返回 1/ 递归归并排序算法int RMergeSort(SqLint &L,int low,int high)/ 采用归并排序的方法对L.element进行降序排序/ 将一个数组对半分为两个子串，并且这两个子串是有序的。/ 再将两个有序的子串合并为 一个有序的数组。17int mid;/ 记录中间位置if(lowhigh) /判断长度是否大于1mid=(low+high)/2;/ 将 L.elementlow，high 分

35、为 L.elementlow.mid和 L.elementmid+1.highRMergeSort(L,low,mid);/ 递归将 L.elementlow.mid归并为有序的L.elementlow.midRMergeSort(L,mid+1,high);/ 递归将 L.elementmid+1.high归并为有序的L.elementmid+1.highMerge(L,low,mid,high);/ 把结构体 L 子串最底端，中间端的前一个，最高端给Mergereturn 1;/归并排序成功返回 1void Sort()SqLint L; /定义一个结构体Lint *a,i; /a记录输入

36、数据的原值 ,i记录 a 的元素个数长度printf(请输入要排序的长度个数n);scanf(%d,&L.ELenght); /给 L.ELenght赋值，给定要输入值的个数if(InitSqlint(L) /判断是否开辟存储空间成功，开辟成功则执行以下步骤Assignment(L);/ 给 L.element依次赋值a=(int *)malloc(L.ELenght*sizeof(int);/ 给 a 分配存储空间if(!a) printf(分配空间失败 n); return ;/ 存储分配失败for(i=0;iL.ELenght;i+) /将 L.element里的值给aai=L.elementi;printf(nn此时表里的数据顺序依次为：n);Output(L);printf(n升序快速排序过程： （非递归） );if(QuickSort(L,0,L.ELenght-1)/ 判断是否进行非递归快速排序成功，成功则输出表中的有序序列printf(n经过非递归快速排序之后，表中的顺序为：n);Output(L);else printf(排序失败 n);for(i=0;iL.ELenght;i+)/ 将 a里的值给 L.elemen