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

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、通过综合训练，能够培养学生实际分析问题、解决问题、编程和动手操作等多方面的能力，最终目的是帮助学生系统地掌握数据结构的基本内容，并运用所学的数据结构知识去解决实际问题。其中内容包括数组、链接表、栈和队列、递归、树与森林、图、堆与优先级队列、集合与搜索结构、排序、索引与散列结构等关键字：数据结构；分析；掌握abstract data structure course design, lists the data structure course design as an example, through the comprehensive training, to cultivate stude

3、nts' practical analysis and solve problems in many aspects, programming, and hands-on ability, the ultimate goal is to help students to systematically master the basic content of data structure, and using the data structure of knowledge to solve practical problems. content including array, linke

4、d list, stack and queue, recursion, tree and forest, graph, heap and priority queue, the structure of the collection and search, sorting, indexing and hashing structure, etc keywords: data structure；analysis；master数据结构课程设计-快速排序与归并排序一、 引 言二、 将一组数据运用快速排序与归并排序进行排序，要求使用递归与非递归方法三、 本次课程设运用到了 数组、链接表、栈、递归、排

5、序等结构。四、 在学校机房进行程序设计，编写代码，实现程序的功能二、设计目的与任务1、课程设计目的 1、能够更灵活地应用所学数据结构知识，独立完成问题分析，结合数据结构理论知识，编写程序求解指定问题。 2.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力；4.数据结构课程设计是学习c语言的一个重要过程，通过此次实践，学生对书本上的知识通过上机操作有了更形象的理解，对今后的学习有很大的帮助。 2、课程设计的任务 问题描述: 做一个快速排序与归并排序 三、设计方案1、 需求分析1) 对一组数据进行快速排序和递归排

6、序2) 快速排序：快速排序对气泡排序的一种改进。它的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对两部分记录继续进行排序，以达到整个序列有序。 3) 归并排序：归并排序是又一类不同的排序方法。“归并”的含义是将两个或两个以上的有序表组合成一个新的有序表。无论是顺序存储结构还是链表存储结构，都可在o（m+n)（m,m分别为有序表的长度）的时间量级上实现。利用归并的思想容易实现排序。2、概要设计1) 抽象数据类型(adt)如下：adt sqlint 数据对象：d=a|ai int, i=1,2,n,n0数据关系：r1=<ai

7、-1,ai> | ai-1,ai d,i=2,n 基本操作：int initsqlint(sqlint &l)/构造一个空的线性表 lvoid assignment(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(

8、sqlint &l,int low,int high)/交换顺序表l.element里的值，以枢轴为中心，小的在前，大的在后int quicksort(sqlint &l,int low,int high)/非递归快速排序算法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 &am

9、p;l,int low,int high)/递归归并排序算法2) 存储结构typedef struct int *element; /存储空间基址 int elenght;/当前分配的存储容量个数 sqlint; 3) 过程图3、详细设计本程序中的重要程序段如下，功能是分别实现快速排序与归并排序，并且分别用不同的方法(递归与非递归)，并且判断程序是否正确等( 简要介绍设计中的重要程序段 )快速排序：通过一趟排序将待排序记录分割成独立的两个区间，其中左区间记录的关键字的值均比右区间中记录的关键字的值小，再分别对这两个区间中的记录进行快速排序，以达到整个序列有序为止。1) 重要程序段1/交换顺序表

10、l.element里的值，以枢轴为中心，小的在前，大的在后 int partition(sqlint &l,int low,int high)int pivot=l.elementlow;/将第一个元素给piovt作为枢轴 while(low!=high)/从表中的两端交替地向中间扫描 while(low<high&&l.elementhigh>=pivot) high-;/一路将后端的值进行 扫描，直到找到比枢轴小的值为止 l.elementlow=l.elementhigh;/将比枢轴小的值移到低端 while(low<high&&

11、l.elementlow<=pivot) low+;/一路将后端的值进行 扫描，直到找到比枢轴大的值为止 l.elementhigh=l.elementlow; /将比枢轴大的值移到高端 l.elementlow=pivot;/枢轴记录到位 return low;/返回枢轴位置 2) 重要程序段2/栈的运用typedef structselemtype *base;/在栈构造之前和销毁之后，base的值为null selemtype *top;/栈顶指针 int stacksize;/当前已分配的存储空间，以元素为单位 sqstack;/栈的初始化 status initstack(sq

12、stack &s)/构造一个空栈s s.base=(selemtype *)malloc(stack_init_size*sizeof(selemtype);if(!s.base) return error;/分配存储空间失败 s.top=s.base;s.stacksize=stack_init_size;return ok;/initstack/入栈 status push(sqstack &s,selemtype e)/插入元素e为新的栈顶元素 if(s.top-s.base>=s.stacksize)/栈满，追加存储空间 s.base=(selemtype *)r

13、ealloc(s.base,(s.stacksize+stackincrement)*sizeof(selemtype);if(!s.base) return error;/存储分配失败 s.top=s.base+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.t

14、op;return ok;/top3) 重要程序段3/非递归快速排序算法 int quicksort(sqlint &l,int low,int high)/采用快速排序的方法对l.element进行升序排序/利用栈，保存每一个待排序子串的首尾元素下标，下一次while循环时取出这个范围，/对这段子序列进行partition操作sqstack s;/定义一个栈 s int p,l,h;/p 记录枢轴的位置，l记录子串首元素位置，h l记录子串尾元素位置initstack(s);/初始化栈 if(low<high)p=partition(l,low,high);/进行第一次 par

15、tition if(p-1>low)/取枢轴前子串的首尾位置入栈 push(s,low);push(s,p-1);if(p+1<high)/取枢轴后子串的首尾位置入栈 push(s,p+1);push(s,high);while(s.base!=s.top)/判断栈是否为空， pop(s,h);/取一个待排序的子串首尾位置 pop(s,l);p=partition(l,l,h);/将待排序的子串进行 partition if(p-1>l)/取枢轴前子串的首尾位置入栈 push(s,l);push(s,p-1);if(p+1<h)/取枢轴后子串的首尾位置入栈 push(s

16、,p+1);push(s,h);free(s.base); /释放 s.bese的空间 return 1;/排序成功返回14) 重要程序段4/递归快速排序算法 int rquicksort(sqlint &l,int low,int high)/采用快速排序的方法对l.element进行升序排序/运用递归的方法，对串进行排序， int p; /p 用来记录枢轴的位置 if(low<high) /判断 长度是否大于1 p=partition(l,low,high);/将串 l.elementlow.,high一分为二 rquicksort(l,low,p-1);/对底子表进行递归排

17、序 rquicksort(l,p+1,high);/对底子表进行递归排序 return 1;/排序成功返回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记录高端最前位置，

18、k 用来记录temp元素个数 int *temp; temp=(int *)malloc(l.elenght*sizeof(int);/给temp 分配存储空间 if(!temp) printf("分配空间失败n"); return ;/存储分配失败 k=0;/赋值第一个位置 while(i<=mid&&j<=high)/将底端和高端进行相比，大的和放到temp，直到有一个没有元素为止 if(l.elementi>l.elementj)tempk+=l.elementi+;else tempk+=l.elementj+;while(i<

19、;=mid)/判断底端是否有值，有则赋值给temp tempk+=l.elementi+;while(j<=high)/判断高端是否有值，有则赋值给temp tempk+=l.elementj+;for(i=low,j=0;i<=high;j+,i+)/把temp里的值给l.element l.elementi=tempj;free(temp);/释放temp 2) 重要程序段2/非递归归并排序算法 int mergesort(sqlint &l)/采用归并排序的方法对l.element进行降序排序/将一个数组 对半分为两个子串，并且这两个子串是 有序的。/再将两个 有序的

20、子串 合并 为 一个有序的数组。int i,j,low,mid,high;/i 记录每次子序列比较的步长， j 记录在 temp中记录存放的个数, low 记录/ 子串的 最前端位置， mid 记录子串的中间位置，high 记录最后端位置 for(i=1;i<l.elenght;i*=2)/记录并控制每一步 步长 for(low=0;low<l.elenght-i;low=high) /记录并控制每一次步数 mid=low+i;/中间位置 high=mid+i;/最后端位置 if(high>l.elenght)/判断high 是否比总元素个数大 high=l.elenght;

21、merge(l,low,mid-1,high-1);/把 结构体l 子串最底端，中间端的前一个，最高端给merge return 1; /归并排序成功 返回 1 3) 重要程序段3/递归归并排序算法 int rmergesort(sqlint &l,int low,int high)/采用归并排序的方法对l.element进行降序排序/将一个数组 对半分为两个子串，并且这两个子串是 有序的。 /再将两个 有序的子串 合并 为 一个有序的数组。 int mid;/记录中间位置 if(low<high)/判断 长度是否大于1 mid=(low+high)/2;/将l.elementl

22、ow，high分为l.elementlow.mid和l.elementmid+1.high rmergesort(l,low,mid);/递归将l.elementlow.mid归并为有序的 l.elementlow.mid rmergesort(l,mid+1,high);/递归将l.elementmid+1.high归并为有序的 l.elementmid+1.high merge(l,low,mid,high);/把 结构体l 子串最底端，中间端的前一个，最高端给mergereturn 1;/归并排序成功 返回 1 主函数与排序函数的调用void sort()sqlint l; /定义一个结

23、构体 l int *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(!a) printf("分配空间失败n"); re

24、turn ;/存储分配失败 for(i=0;i<l.elenght;i+)/将l.element里的值给a ai=l.elementi;printf("nn此时表里的数据顺序依次为：n");output(l);printf("n升序快速排序过程：（非递归）"); if(quicksort(l,0,l.elenght-1) /判断是否进行非递归快速排序成功，成功则输出表中的有序序列 printf("n经过非递归快速排序之后，表中的顺序为：n"); output(l); else printf("排序失败n");

25、 for(i=0;i<l.elenght;i+)/将 a 里的值给l.element l.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;i<

26、;l.elenght;i+)/将 a 里的值给l.element l.elementi=ai;printf("nn此时表里的数据顺序依次为：n");output(l);printf("n降序归并排序过程：（非递归）");if(mergesort(l)/判断是否进行非递归归并排序成功，成功则输出表中的有序序列printf("n经过非递归归并排序之后，表中的顺序为：n");output(l);else printf("排序失败n");for(i=0;i<l.elenght;i+)/将 a 里的值给l.elemen

27、t l.elementi=ai;printf("nn此时表里的数据顺序依次为：n");output(l);printf("n降序归并排序过程：（递归）");if(rmergesort(l,0,l.elenght-1)/判断是否进行递归归并排序成功，成功则输出表中的有序序列printf("n经过递归归并排序之后，表中的顺序为：n");output(l);else printf("排序失败n");/主函数 int main()sort();return 0;4、程序清单#include<stdio.h>#i

28、nclude<stdlib.h>#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 int *element; /存储空间基址 int elenght;/当前分配的存储容量个数 sqlint;/构造一个空的线性表 l int initsqlint(sqlint &

29、;l)l.element=(int *)malloc(l.elenght*sizeof(int); /分配存储空间 if(!l.element) return 0;/检查分配是否成功，分配失败返回0 return 1;/分配成功则返回1 /initsqlint/给表l.element 赋值 void assignment(sqlint &l)int i;printf("请输入%d个整形数据作为元素n",l.elenght);for(i=0;i<l.elenght;i+)/给表 l.element从键盘上输入进行逐个赋值 scanf("%d"

30、,&l.elementi);/输出表里的 l.elenght个元素 void output(sqlint l)int i;for(i=0;i<l.elenght;i+)/将表 l. element从第一个开始输出 l.elenght个到显示器 printf("%d ",l.elementi);typedef structselemtype *base;/在栈构造之前和销毁之后，base的值为null selemtype *top;/栈顶指针 int stacksize;/当前已分配的存储空间，以元素为单位 sqstack;/栈的初始化 status inits

31、tack(sqstack &s)/构造一个空栈s s.base=(selemtype *)malloc(stack_init_size*sizeof(selemtype);if(!s.base) return error;/分配存储空间失败 s.top=s.base;s.stacksize=stack_init_size;return ok;/initstack/入栈 status push(sqstack &s,selemtype e)/插入元素e为新的栈顶元素 if(s.top-s.base>=s.stacksize)/栈满，追加存储空间 s.base=(selemt

32、ype *)realloc(s.base,(s.stacksize+stackincrement)*sizeof(selemtype);if(!s.base) return error;/存储分配失败 s.top=s.base+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;

33、e=*-s.top;return ok;/top/交换顺序表l.element里的值，以枢轴为中心，小的在前，大的在后 int partition(sqlint &l,int low,int high)/交换顺序表l.element里的值，以第一个（low的位置)做为枢轴值，首先往前取值与枢轴比较，/如大于枢轴则取它前一个继续与枢轴比较，如果还是大于枢轴，再往前取，直到取到比枢轴小，/当值比枢轴小时，把它放到low的位置，然后取low位置的值与枢轴比较，小于枢轴时，取下一个/继续比较，大于枢轴时，比它放到high的位置，然后再取high位置的值，进时比较，大于枢轴时/取它的前一个继续比

34、较，以些类堆，直到low等于gigh为止，int pivot=l.elementlow;/将第一个元素给piovt作为枢轴 while(low!=high)/从表中的两端交替地向中间扫描 while(low<high&&l.elementhigh>=pivot) high-;/一路将后端的值进行 扫描，直到/找到比枢轴小的值为止 l.elementlow=l.elementhigh;/将比枢轴小的值移到低端 while(low<high&&l.elementlow<=pivot) low+;/一路将后端的值进行 扫描，直到/找到比枢轴大的

35、值为止 l.elementhigh=l.elementlow; /将比枢轴大的值移到高端 l.elementlow=pivot;/枢轴记录到们 printf("n");output(l);return low;/返回枢轴位置 /非递归快速排序算法 int quicksort(sqlint &l,int low,int high)/采用快速排序的方法对l.element进行升序排序/利用栈，保存每一个待排序子串的首尾元素下标，下一次while循环时取出这个范围，/对这段子序列进行partition操作sqstack s;/定义一个栈 s int p,l,h;/p 记录

36、枢轴的位置，l记录子串首元素位置，h l记录子串尾元素位置initstack(s);/初始化栈 if(low<high)p=partition(l,low,high);/进行第一次 partition if(p-1>low)/取枢轴前子串的首尾位置入栈 push(s,low);push(s,p-1);if(p+1<high)/取枢轴后子串的首尾位置入栈 push(s,p+1);push(s,high);while(s.base!=s.top)/判断栈是否为空， pop(s,h);/取一个待排序的子串首尾位置 pop(s,l);p=partition(l,l,h);/将待排序的

37、子串进行 partition if(p-1>l)/取枢轴前子串的首尾位置入栈 push(s,l);push(s,p-1);if(p+1<h)/取枢轴后子串的首尾位置入栈 push(s,p+1);push(s,h);free(s.base); /释放 s.bese的空间 return 1;/排序成功返回1/递归快速排序算法 int rquicksort(sqlint &l,int low,int high)/采用快速排序的方法对l.element进行升序排序/运用递归的方法，对串进行排序， int p; /p 用来记录枢轴的位置 if(low<high) /判断 长度是

38、否大于1 p=partition(l,low,high);/将串 l.elementlow.,high一分为二 rquicksort(l,low,p-1);/对底子表进行递归排序 rquicksort(l,p+1,high);/对底子表进行递归排序 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记录底端最前位置，

39、j记录高端最前位置，k 用来记录temp元素个数 int *temp; temp=(int *)malloc(l.elenght*sizeof(int);/给temp 分配存储空间 if(!temp) printf("分配空间失败n"); return ;/存储分配失败 k=0;/赋值第一个位置 while(i<=mid&&j<=high)/将底端和高端进行相比，大的和放到temp，直到有一个没有元素为止 if(l.elementi>l.elementj)tempk+=l.elementi+;else tempk+=l.elementj+;

40、while(i<=mid)/判断底端是否有值，有则赋值给temp tempk+=l.elementi+;while(j<=high)/判断高端是否有值，有则赋值给temp tempk+=l.elementj+;for(i=low,j=0;i<=high;j+,i+)/把temp里的值给l.element l.elementi=tempj;free(temp);/释放temp printf("n");output(l);/非递归归并排序算法 int mergesort(sqlint &l)/采用归并排序的方法对l.element进行降序排序/将一个数

41、组 对半分为两个子串，并且这两个子串是 有序的。/再将两个 有序的子串 合并 为 一个有序的数组。int i,j,low,mid,high;/i 记录每次子序列比较的步长， j 记录在 temp中记录存放的个数, low 记录/ 子串的 最前端位置， mid 记录子串的中间位置，high 记录最后端位置 for(i=1;i<l.elenght;i*=2)/记录并控制每一步 步长 for(low=0;low<l.elenght-i;low=high) /记录并控制每一次步数 mid=low+i;/中间位置 high=mid+i;/最后端位置 if(high>l.elenght)

42、/判断high 是否比总元素个数大 high=l.elenght;merge(l,low,mid-1,high-1);/把 结构体l 子串最底端，中间端的前一个，最高端给merge return 1; /归并排序成功 返回 1 /递归归并排序算法 int rmergesort(sqlint &l,int low,int high)/采用归并排序的方法对l.element进行降序排序/将一个数组 对半分为两个子串，并且这两个子串是 有序的。 /再将两个 有序的子串 合并 为 一个有序的数组。 int mid;/记录中间位置 if(low<high)/判断 长度是否大于1 mid=(

43、low+high)/2;/将l.elementlow，high分为l.elementlow.mid和l.elementmid+1.high rmergesort(l,low,mid);/递归将l.elementlow.mid归并为有序的 l.elementlow.mid rmergesort(l,mid+1,high);/递归将l.elementmid+1.high归并为有序的 l.elementmid+1.high merge(l,low,mid,high);/把 结构体l 子串最底端，中间端的前一个，最高端给mergereturn 1;/归并排序成功 返回 1 void sort()sql

44、int l; /定义一个结构体 l int *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(!a) printf("分配空间失

45、败n"); return ;/存储分配失败 for(i=0;i<l.elenght;i+)/将l.element里的值给a ai=l.elementi;printf("nn此时表里的数据顺序依次为：n");output(l);printf("n升序快速排序过程：（非递归）"); if(quicksort(l,0,l.elenght-1) /判断是否进行非递归快速排序成功，成功则输出表中的有序序列 printf("n经过非递归快速排序之后，表中的顺序为：n"); output(l); else printf("

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

47、 for(i=0;i<l.elenght;i+)/将 a 里的值给l.element l.elementi=ai;printf("nn此时表里的数据顺序依次为：n");output(l);printf("n降序归并排序过程：（非递归）");if(mergesort(l)/判断是否进行非递归归并排序成功，成功则输出表中的有序序列printf("n经过非递归归并排序之后，表中的顺序为：n");output(l);else printf("排序失败n");for(i=0;i<l.elenght;i+)/将 a 里的值给l.element l.elementi=ai;printf("nn此时表里的数据顺序依次为：n");output(l);printf("n降序归并排序过程：（递归）");if(rmergesort(l,0,l.elenght-1)/判断是否进行递归归并排序成功，成功则输出表中的有序序列printf("n经过递归归并排序之后，表中的顺序为：n");output(l);else printf("排序失败n");/主函数 int main()sort();return 0;四、调试分析与体会经过调试