- 1、本文档共13页,可阅读全部内容。
- 2、原创力文档(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
- 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
- 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们。
- 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
- 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
学生实验报告书
实验课程名称应用数据结构
开课学院管理学院
指导教师姓名
学生姓名
学生专业班级
学生学号
2014—2015学年第2学期
1
实验四
实验项目名称综合算法设计实验日期2015年6月17日
实验者专业班级实验类型综合型
一、实验目的、意义
1)掌握查找的含义
2)掌握基本查找操作的算法和实现
3)掌握动态查找算法的实现、应用场合与优缺点
4)能够针对具体问题,灵活选用适宜的查找算法
5)掌握排序的基本概念,对排序的稳定性及排序的时间复杂度有深刻的认识
6)对比折半插入排序和Shell排序的异同
7)掌握选择排序中堆排序的基本思想和算法实现
8)掌握快速排序的基本思想和算法实现
9)了解归并排序算法的基本思想和程序实现
10)了解基数排序算法的基本思想和程序实现
11)掌握Hash排序算法的基本思想和程序实现
在前面实验内容的基础上,根据实际问题选择相应算法。
二、实验基本原理与方法
本实验涉及各类查找和排序算法。
静态查找,折半查找的思想为:设查找表中的元素存放在数组r中,数据元素的下标范围
为[low,high],要查找的关键字值为key,中间元素的下标为mid|_(low+high)/2_|(向下取整),
令key与r[mid]的关键字比较:
1若keyr[mid].key,查找成功,下标为m的记录即为所求,返回mid。
2若keyr[mid].key,所要找的记录只能在左半部分记录中,再对左半部分使用折半查
找法继续进行查找,搜索区间缩小了一半。
3若keyr[mid].key,所要找的记录只能在右半部分记录中,再对右半部分使用折半查
找法继续进行查找,搜索区间缩小了一半。
重复上述过程,直到找到查找表中某一个数据元素的关键字的值等于给定的值key,说明
查找成功;或者出现low的值大于high的情况,说明查找不成功。
动态查找,编程实现一个开放式的高校本科招生最低录取分数线的查询系统,供师生和家
长等查询,高校自愿放入该校的信息,可能随时有高校加入。要求实现的查询功能有:
①查询等于用户给定分数的高校;
②查询大于(或小于)用户给定分数的高校③查询最低录取分数线在用户给定的分数段中
的高校。
直接插入排序:将当前无序区的第一个记录插入到有序区中适当位置。
折半查找法:在有序表中进行,先确定表的中点位置,再通过比较确定下一步查找哪个半
区。
Shell排序:先取定一个小于n的整数d作为第一个增量,把文件的全部记录分成d个组,
11
所有距离为d倍数的记录放在同一个组中,在各组内进行直接插入排序;然后取第二个增量重
1
复上述分组和排序,直至所取的增量d1(dd…dd),即所有记录放在同一组中进行直接
ttt-121
插入排序为止。
堆排序是利用大顶堆(或小顶堆)来选取当前无序区中关键字最大(或最小)的记录实现
2
排序。
快速排序是对冒泡法的改进,其基本思想是:通过一趟排序将待排文件分割成独立的两部
分,其中一部分记录的关键字值均比另一部分记录的关键字小,然后分别对这两部分进行排序,
以达到整个序列有序。
归并的思想:将两个或两个以上的有序表合并成一个有序表。利用归并的思想实现排序,
假设初始的
文档评论(0)