实验七 查找技术的编程实现 实验报告

《实验七 查找技术的编程实现 实验报告》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、HUBEIUNIVERSITYOFAUTOMOTIVETECHNOLOGY数据结构这里一定填写清楚自己选择的实验层次。（基础、提高或者挑战）实验报告实验项目实验七实验类别提高篇学生姓名朱忠栋学生学号20120231515完成日期2014-12-30指导教师付勇智实验成绩评阅日期评阅教师HUBEIUNIVERSITYOFAUTOMOTIVETECHNOLOGY数据结构这里一定填写清楚自己选择的实验层次。（基础、提高或者挑战）实验报告实验项目实验七实验类别提高篇学生姓名朱忠栋学生学号20120231515完成日期2014-12-30指导教师付勇智实验成绩评阅日期评阅教师实验七查找技术的编程实现【

2、实验目的】查找技术的编程实现要求：查找技术的编程实现（2学时，综合型），掌握查找技术的编程实现，可以实现一种，也可以实现多种。也鼓励学生利用基本操作进行一些应用的程序设计。【实验性质】综合性实验，其综合性体现在本实验的内容具有的实际应用价值，多种数据结构的综合应用，各种具有代表性的算法设计和程序实现。（学时数：2H）【实验内容】1.顺序、二分等查找程序设计。2.鼓励学生实现哈希法等查找程序设计。只要是本章讨论的查找技术都可以作为编程的内容。3.鼓励将多种方法进行同时编程进行对比。【注意事项】1.开发语言：使用C。2.可以自己增加其他功能。【实验分析、说明过程】本次实验提高篇主要考查查找技术的

3、编程实现，掌握查找技术的编程实现。//运用除留余数法作为哈希函数及差值解决法解决哈希冲突解决法、设计哈希表。*/程序构思：//依除留余数法将数据存储至哈希表中，发生哈希冲突时以差值解决法解决。//除留余数法://Address=Key%Array_Size//差值解决法：//New_Address=(Old_Address+Offset)%Array_Siae///数据查找时，同时也先用除留余数法运算出数据地址，//若找不到运用差值法找出下一个数据地址，直到数据全查找完为止。【思考问题】1．查找的效率主要是什么操作体现的？答：查找运算的主要操作是关键字的比较，所以通常把查找过程中对关键字需要

4、执行的平均比较次数（也称平均查找长度）作为衡量一个查找算法效率的标准。2. 二分法的优缺点分析？答：优点：高效缺点：二分法虽然有较高的查找速度，但是只能查有序表，而排序也是一种很浪费时间的运算，而且二分法查找只适合顺序存储结构，为保持表的有序性，在进行插入和删除操作时都必须移动大量的结点。3. 哪些查找算法可以用递归实现？答：二叉查找树的查找，二叉查找树的插入4. 哈希查找法的特点和优点？最终取消了数据比较的基本操作吗？答：取消了数据比较的基本操作特点：通过对关键字值进行某种运算来确定待查记录的存放地址。但是，由于关键字的取值范围往往大于允许的地址范围，不可避免的会发生冲突，而使查找时间增加

5、，但是只要能构造出均匀的哈希函数，并能较好地处理冲突，哈希法是十分有效的。优点：在查找过程中可以不进行数据的比较，因此，其查找时间与表中记录的个数无关，当所选择的的哈希函数能得到均匀的地址分布时，其查找效率比其他的几种查找方法都要高。5. 举出查找的应用范例？答：二叉树的平衡【实验小结】(总结本次实验的重难点及心得、体会、收获)对于本次实验，我认为基础篇较为简单，我已经能够很快的做出来了。而对于提高篇，虽说有些难度，但是经过不断地参考书本，以及参考网上的相关实验和相应的程序，经过不断的修改与反思终于成功的完成本次实验。通过本次实验我知道了无论想要做成任何事情必须经过反复的钻研与试探，对我以后

6、的工作和学习都有所帮助。同时经过本次实验我了解查找技术的编程实现，掌握查找技术的编程实现；而且还有哈希法的相关知识以及它的具体运用方法和场合。【附录-实验代码】#include#define Max 6#define HashMax 5int Data[Max]={12,160,219,522,725,9997}; //数据数组int HashTab[HashMax];int Counter=1;                           //计数器int Hash_Mod(int Key)                    //哈希函数之除留余数法{    

7、return (Key%5);                      //返回，键值除以哈希表大小取余数}int Collision_Offset(int Address)        //差值哈希冲突解决法 {    int offset=3;                        //设差值为3    return ((Address+offset)%5);         //返回，旧地址