数据结构课程设计(各种排序算法的实现)

数据结构课程设计(各种排序算法的实现)

ID:47204822

大小:82.50 KB

页数:8页

时间:2019-08-26

数据结构课程设计(各种排序算法的实现)_第1页
数据结构课程设计(各种排序算法的实现)_第2页
数据结构课程设计(各种排序算法的实现)_第3页
数据结构课程设计(各种排序算法的实现)_第4页
数据结构课程设计(各种排序算法的实现)_第5页
资源描述:

《数据结构课程设计(各种排序算法的实现)》由会员上传分享,免费在线阅读,更多相关内容在应用文档-天天文库

1、.数据结构课程设计报告题目:专业:班级:学号:姓名:指导老师:时间:..一、课程设计题目及所涉及知识点设计题目:排序算法实现知识点:malloc申请连续存储空间、冒泡排序、快速排序、直接插入排序的算法实现、结构体的定义与调用、函数的递归调用二、课程设计思路及算法描述设计思路:1、确定程序要实现的功能即(1)允许用户输入一组数据,任意多个。(2)由用户选择对该组数据进行排序的方法:直接插入排序、冒泡排序、快速排序。并可以查看每趟排序的结果。2、确定程序所需要的功能块,存储结构-结构体,malloc申请存储空间,各功能函数--冒泡排

2、序功能块maopao();、直接插入排序功能块insertsort();、快速排序q_sort();、数据访问功能块traveres();、数据输出功能块liststring();主函数部分main();。3、编写代码具体实现各项功能,并进行调试。算法描述:冒泡排序(BubbleSorting)的基本思想:设待排序n个元素存放在数组a[n]中,无序区范围初始为(a(0),a(1),a(2),...,a[n-1]),冒泡排序方法是在当前无序区内,从最上面的元素a[0]开始,对每两个相邻的元素a[i+1]和a[i](i=0,1,..

3、.,n-1)进行比较,且使值较小的元素换至值较大的元素之上(若a[i]>a[i+1],则a[i]和a[i+1]的值互换),这样经过一趟冒泡排序后,假设最后下移的元素为a[k],则无序区中值较大的几个元素到达下端并从小到大依次存放在a[k+1],a[k+2],...a[n-1]中,这样无序区范围变为(a[0],a[1],a[2],...,a[k])。在当前无序区内进行下一趟冒泡排序。这个过程一直到某一趟排序中不出现元素交换的动作,排序结束。整个排序过程最多执行n-1遍。算法实现:voidBubbleSort(SeqListR)//

4、R(l..n)是待排序的文件,采用自下向上扫描,对R做冒泡排序{inti,j;Booleanexchange;//交换标志for(i=1;i=i;j--)//对当前无序区R[i..n]自下向上扫描if(R[j+1].key

5、换标志置为真}if(!exchange)//本趟排序未发生交换,提前终止算法return;}//endfor(外循环)}//BubbleSort直接插入排序(StraightInsertionSorting)的基本思想:..把n个待排序的元素看成为一个有序表和一个无序表,开始时有序表中只包含一个元素,无序表中包含有n-1个元素,排序过程中每次从无序表中取出第一个元素,将它插入到有序表中的适当位置,使之成为新的有序表,重复n-1次可完成排序过程。把a[i]插入到a[0],a[1],...,a[i-1]之中的具体实施过程为:先把a[

6、i]赋值给变量t,然后将t依次与a[i-1],a[i-2],...进行比较,将比t大的元素右移一个位置,直到发现某个j(0<=j<=i-1),使得a[j]<=t或j为(-1),把t赋值给a[j+1].算法实现:voidinsert_sort(ElemTypea[],intn)//待排序元素用一个数组a表示,数组有n个元素{inti,j;ElemTypet;for(i=1;i=0)&&(t

7、1]=a[j];j--;}//顺序比较和移动a[j+1]=t;}}快速排序算法:在R[low..high]中任选一个记录作为基准(Pivot),以此基准将当前无序区划分为左、右两个较小的子区间R[low..pivotpos-1)和R[pivotpos+1..high],并使左边子区间中所有记录的关键字均小于等于基准记录(不妨记为pivot)的关键字pivot.key,右边的子区间中所有记录的关键字均大于等于pivot.key,而基准记录pivot则位于正确的位置(pivotpos)上,它无须参加后续的排序。算法实现:voidQu

8、ickSort(SeqListR,intlow,inthigh){//对R[low..high]快速排序intpivotpos;//划分后的基准记录的位置if(low

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。