数据结构大型作业报告

《数据结构大型作业报告》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构大型作业报告班级：信息安全0501学号：012005014109姓名：肖胜鹏2007年8月19日23一．题目：内部排序算法研究内容：（1）设n个关键字均为整数(1≤n≤100000)（2）设计K个内部排序算法(K≥5),每个算法须记录执行所需的时间（3）自动生成多组数据,每组数据含n个整数(正序、逆序、随机分布)（4）执行每个排序算法（5）用图、表格数据分析说明在什么情况下采用什么算法较好;二．数据结构及存储结构存储结构：采用顺序存用数组存储数据。数据结构：ADT{voidInputData(longlist[

2、],longn)操作结果：以用户的意志（正序，逆序或随机）建立待排序数据表。voidOutputData(longlist[],longn)操作结果：输出数据表list[]中的内容。voidInsertSort(longlist[],longn)操作结果：用直接插入排序的方法将list[]中的n个数据按照非递减排列，且输出每趟排序后的结果以及程序运行的时间。voidShellSort(longlist[],longn)操作结果：用希尔排序的方法将list[]中的n个数据按照非递减排列，且输出每趟排序后的结果以及程序运行

3、的时间。voidBubbleSort(longlist[],longn)操作结果：用冒泡排序的方法将list[]中的n个数据按照非递减排列且输出每趟排序后的结果以及程序运行的时间。voidQuickSort(longlist[],longstart,longend)操作结果：用快速排序的方法将list[]中的n个数据按照非递减排列且输出每趟排序后的结果以及程序运行的时间。voidSelectSort(longlist[],longn)操作结果：用选择排序的方法将list[]中的n个数据按照非递减排列且输出每趟排序后的结

4、果以及程序运行的时间。voidMerge(longR[],longlow,longmid,longhigh)操作结果：实现一次归并。voidMergePass(longR[],longlength,longn)操作结果：归并长为length的两个子表，实现一趟归并。23voidMergeSort(longR[],longn)操作结果：用二路归并排序的方法将list[]中的n个数据按照非递减排列且输出每趟排序后的结果以及程序运行的时间。voidMenu(void)操作结果：输出功能菜单。voidclear(void)操作

5、结果：询问用户是否清屏，然后作相应的处理。}ADT。一．主要算法设计思想.(1).直接插入排序函数原型：voidInsertSort(longlist[],longn)；算法思想：假设记录存放在list[0—n]中，list[0--i-1]是已排好序的记录，list[i—n]是未排好序的记录，将list[i]插入到list[0—i-1]之中，使list[0—i]是有序的。插入list[i]的过程就是完成排序中的一趟，随着有序区的不断扩大，使list[0—n-1]全部有序。同时在程序开始时用clock()获得时间，程序结

6、束时再获取时间，两时间值的差就是程序运行的时间。（2）.希尔排序函数原型：voidShellSort(longlist[],longn)；算法思想：把记录按下标的一定增量d分组，对每组记录采用直接插入排序方法进行排序，随着增量逐渐减小，所分成的组包含的记录越来越多，当增量的值减小到1时，整个数据合成为一组，构成一组有序记录，则完成排序，同时在程序开始时用clock()获得时间，程序结束时再获取时间，两时间值的差就是程序运行的时间。（3）冒泡排序函数原型：voidBubbleSort(longlist[],longn)；

7、算法思想：通过相邻元素之间的比较和交换使排序码较大的元素逐渐向序列的尾部移动。冒泡排序的第一趟排序过程：设1

8、longend)算法思想：23通过比较关键字，交换记录，以某个记录为界，将待排序列分成两部分。其中，一部分所有记录的关键字大于等于支点记录的关键字，另一部分所有记录的关键字小于支点记录的关键字。将待排序记录按关键字以支点记录分成两部分的过程，成为一次划分对各部分不断划分，直至每一部分中只剩下一个记录为止，整个序列才能按关键字有序排