《数据结构课程设计快速排序和归并排序》由会员分享，可在线阅读，更多相关《数据结构课程设计快速排序和归并排序（27页珍藏版）》请在金锄头文库上搜索。
1、XX 学院信息科学与工程系课程设计说明书课 程 名 称: 数据结构 课 程 代 码: 题 目: 快速排序与归并排序 年级/专业/班: 学 生 姓 名: 奉 XX 学 号: 14400000001440000000 指 导 教 师: 易 开 题 时 间: 2015 年 12 月 30 日完 成 时 间: 2016 年 1 月 10 日1目目 录录摘 要.1一、引 言.3二、设计目的与任务.31、课程设计目的.32、课程设计的任务.3三、设计方案.31、需求分析.32、概要设计.43、详细设计.54、程序清单.13四、调试分析与体会.19五、运行结果.20六、结 论.24七、致 谢.24八、参考文
2、献.25摘摘 要要数据结构课程设计，列举了数据结构课程设计实例，通过综合训练，能够培养学生实际分析问题、解决问题、编程和动手操作等多方面的能力，最终目的是帮助学生系统地掌握数据结构的基本内容，并运用所学的数据结构知识去解决实际问题。其中内容包括数组、链接表、栈和队列、递归、树与森林、图、堆与优先级队列、集合与搜索结构、排序、索引与散列结构等关键字关键字：数据结构；分析；掌握Abstract 2Data structure course design, lists the data structure course design as an example, through the compre
3、hensive training, to cultivate students 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.
4、 Content including array, linked 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；master3数据结构数据结构课程设计课程设计-快速排序与归并排序快速排序与归并排序一、引引 言言二、 将一组数据运用快速
5、排序与归并排序进行排序，要求使用递归与非递归方法三、本次课程设运用到了 数组、链接表、栈、递归、排序等结构。四、 在学校机房进行程序设计，编写代码，实现程序的功能二、设计目的与任务1、课程设计目的、课程设计目的 1、能够更灵活地应用所学数据结构知识，独立完成问题分析，结合数据结构理论知识，编写程序求解指定问题。 2.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力；4.数据结构课程设计是学习 C 语言的一个重要过程，通过此次实践，学生对书本上的知识通过上机操作有了更形象的理解，对今后的学习有很大的帮助。 2、
6、课程设计的任务、课程设计的任务 问题描述: 做一个快速排序与归并排序 三、设计方案三、设计方案1、需求分析需求分析1)对一组数据进行快速排序和递归排序2)快速排序：快速排序对气泡排序的一种改进。它的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对两部分记录继续进行排序，以达到整个序列有序。 3)归并排序：归并排序是又一类不同的排序方法。 “归并”的含义是将两个或两个以上的有序表组合成一个新的有序表。无论是顺序存储结构还是链表存储结构，都可在 O（m+n)（m,m 分别为有序表的长度）的时间量级上实现。利4用归并的思想容易实现排序
7、。2、概要设计、概要设计1) 抽象数据类型(ADT)如下：ADTADT SqLintSqLint 数据对象数据对象：D=a|ai int, i=1,2,n,n0 数据关系数据关系：R1= | ai-1,ai D,i=2,n 基本操作：基本操作：int InitSqlint(SqLint /存储空间基址 int ELenght;/当前分配的存储容量个数 SqLint; 3)过程图53、详细设计、详细设计本程序中的重要程序段如下，功能是分别实现快速排序与归并排序，并且分别用不同的方法(递归与非递归)，并且判断程序是否正确等( 简要介绍设计中的重要程序段 )快速排序：快速排序：通过一趟排序将待排序记
8、录分割成独立的两个区间，其中左区间记录的关键字的值均比右区通过一趟排序将待排序记录分割成独立的两个区间，其中左区间记录的关键字的值均比右区间中记录的关键字的值小，再分别对这两个区间中的记间中记录的关键字的值小，再分别对这两个区间中的记录录进进行行快快速速排排序序，以以达达到到整整个个序序列列有有序序为为止止。1)重要程序段 1/交换顺序表 L.element 里的值，以枢轴为中心，小的在前，大的在后 6int Partition(SqLint /将第一个元素给 piovt 作为枢轴 while(low!=high)/从表中的两端交替地向中间扫描 while(low=pivot) high-;/
9、一路将后端的值进行 扫描，直到找到比枢轴小的值为止 L.elementlow=L.elementhigh;/将比枢轴小的值移到低端 while(low=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.stacksize+=STACKINCREMENT;*S.top+=e;return OK;/Push/出栈 Status Pop(SqStack e=*-S.top;return OK;/Top3)重要程序段 3/非递归快速排序算法 int QuickSort(SqLint /定义一个栈 S int p,l,h;/p 记录枢轴的位置，l 记录子串首元素位置，h l 记录子串尾元素位置InitStack(S); /初始化栈 8if(lowlow)/取枢轴前子串的首尾位置入栈 Push(S,low);Push(S,p-1);if(p+1l)/取枢轴前子串的首尾位置入栈 Push(S,l);Push(S,p-1);if(p+1L.elemen
