实验五： 查找算法应用.doc

《实验五： 查找算法应用.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验报告学院（系）名称：计算机与通信工程学院**学号********专业计算机科学与技术班级2015级*班实验项目实验五：查找算法应用课程名称数据结构与算法课程代码0661013实验时间年月日第节实验地点7-***考核标准实验过程25分程序运行20分回答问题15分实验报告30分特色功能5分考勤违纪情况5分成绩成绩栏其它批改意见:教师签字：考核容评价在实验课堂中的表现，包括实验态度、编写程序过程等容等。□功能完善,□功能不全□有小错□无法运行○正确○基本正确○有提示○无法回答○完整○较完整○一般○容极少○无报告○有○无○有○无一、实验目的实验目的：理解二叉排序树、AVL树的查找、插入、删

2、除、建立算法的思想及程序实现；掌握散列存储结构的思想，能选择合适散列函数，实现不同冲突处理方法的散列表的查找、建立。能运用所学查找结构与算法等解决实际问题。二、实验题目与要求1.折半查找算法1）问题描述：从键盘读入一串整数和一个待查关键字，查找在该整数串中是否有这个待查关键字。如果有，输出它在整数串中的位置；如果没有，输出-12）实验要求：①利用折半查找算法查找②用递归和非递归两种方式实现折半查找算法3)实现提示：①递归实现参考书上折半查找算法的实现②非递归算法利用栈实现2.构造二叉排序树，并进行中序遍历（实验类型：综合型）1）问题描述：从键盘读入一串整数构造一棵二叉排序树，并对得到的

3、二叉排序树进行中序遍历，得到有序序列。2）实验要求：该二叉排序树以二叉链表存储3）实现提示：二叉排序树的构成，可从空的二叉树开始，每输入一个结点数据，就建立一个新结点插入到当前已生成的二叉排序树中，所以它的主要操作是二叉排序树插入运算。在二叉排序树中插入新结点，只要保证插入后仍符合二叉排序树的定义即可。3．哈希表查找1）问题描述：针对某个集体的“人名”构造哈希表，解决按“人名”进行查找的索引结构。2）实验要求：要求表的平均查找长度不超过R（R可以从键盘输入确定），完成相应的建表和查表程序。4.拼写检查1）问题描述：现在有一些英语单词需要做拼写检查，你的工具是一本词典。需要检查的单词，有

4、的是词典中的单词，有的与词典中的单词相似，你的任务是发现这两种情况。单词A与单词B相似的情况有三种：①删除单词A的一个字母后得到单词B；②用任意一个字母替换单词A的一个字母后得到单词B；③在单词A的任意位置增加一个字母后得到单词B。2）实验要求：发现词典中与给定单词相同或相似的单词。实验过程与实验结果应包括如下主要容：Ø数据结构定义Ø数表的查找方法通常适用于动态集合。动态集合的特点是集合结构本身在查找过程中动态生成，即对于给定值k，若集合中存在关键字等于k的记录，则查找成功，否则插入关键字为k的新记录。Ø二叉排序树，又叫二叉查找树或二叉搜索树。它或者是一棵空树，或者是一棵具有如下特征的

5、非空二叉树：Ø1）若它的左子树非空，则左子树上所有节点的关键字均小于根节点的关键字。Ø2）若它的右子树非空，则右子树上所有节点的关键字均大于根节点的关键字。Ø3）左、右子树也分别是二叉排序树。Ø平衡二叉树的定义是：若一棵二叉排序树中每个节点的左、右子树的高度之差的绝对值不超过1，则称这样的二叉排序树为平衡二叉树。Ø算法设计思路简介Ø1、Ø数据有序，用折半查找法，通过即可快速找到关键字。Ø2、Ø二叉树表实际上就是个二叉树，就像建立一个普通的二叉树一样建立树，只是在插入节点的时候要和当前节点的值比较，若当前节点为空则插入当前节点；否则，若小于当前值则插入左子树大于当前节点就插入右子树。对建

6、立好的树进行中序遍历即可得到有序序列。Ø3、Ø人的姓一般有很大可能性相同，但是人名的第二个字一般是不同的，既然人名示例是拼音形式姑且认为第二个字母即为第二个字。将其ASCLL码模49作为哈希函数，将各人名分类存在不同的链表中，提高查询效率。Ø算法描述：可以用自然语言、伪代码或流程图等方式4、以单词中字母的数目为标准将单词分类，若字母数想等或相差一则进行细致的比较（下面有详细描述），否则根本不相似。1、开始输入a[i],keyi=1,2,3,…,nlow=1,high=nmid=(low+high)/2mid=key?=≠high=mid-1k

7、<=high?是否returnmidreturn-1输出mid输出-1结束2、(1)创建普通二叉树节点。(2)输入要插入的值k。(3)将k插入二叉树节点中，若当前节点为空则申请节点空间并将k存入当前节点的data域中，令其左右子树均为空;若当前节点不为空且k小于当前节点的data值，则将k存入当前节点的左子树中去，若当前节点不为空且k大于当前节点的data值，则将k存入当前节点的右子树中去。(4)中序遍历此二叉树。3、Ø(1)录入人名。Ø(2)