实验五：查找算法的应用.docx

实验报告
学院〔系〕名称：计算机与通信工程学院
某某
**
学号
********
专业
计算机科学与技术
班级
2015级*班
实验项目
实验五：查找算法应用
课程名称
数据结构与算法
课程代码
0661013
实验时间
年月日第节
实验地点
7-***
考核标准
实验过程
25分
程序运行
20分
回答如下问题
15分
实验报告
30分
特色
功能
5分
考勤违纪情况
5分
成绩
成绩栏
其它批改意见:
教师签字：
考核内容
评价在实验课堂中的表现，包括实验态度、编写程序过程等内容等。
□功能完善,
□功能不全
□有小错
□无法运行
○正确
○根本正确
○有提示
○无法回答
○完整
○较完整
○一般
○内容极少
○无报告
○有
○无
○有
○无
一、实验目的
实验目的：理解二叉排序树、AVL 树的查找、插入、删除、建立算法的思想与程序实现；掌握散列
存储结构的思想，能选择适宜散列函数，实现不同冲突处理方法的散列表的查找、建立。能运用所
学查找结构与算法等解决实际问题。
二、实验题目与要求

1〕问题描述：从键盘读入一串整数和一个待查关键字，查找在该整数串中是否有这个待查关键字。如果有，输出它在整数串中的位置；如果没有，输出-1
2〕实验要求：①利用折半查找算法查找②用递归和非递归两种方式实现折半查找算法
3) 实现提示：①递归实现参考书上折半查找算法的实现②非递归算法利用栈实现
，并进展中序遍历〔实验类型：综合型〕
1〕问题描述：从键盘读入一串整数构造一棵二叉排序树，并对得到的二叉排序树进展中序遍历，得到有序序列。
2〕实验要求：该二叉排序树以二叉链表存储
3〕实现提示：二叉排序树的构成，可从空的二叉树开始，每输入一个结点数据，就建立一个新结点插入到当前已生成的二叉排序树中，所以它的主要操作是二叉排序树插入运算。在二叉排序树中插入新结点，只要保证插入后仍符合二叉排序树的定义即可。
3．哈希表查找
1〕问题描述：针对某个集体的“人名〞构造哈希表，解决按“人名〞进展查找的索引结构。
2〕实验要求：要求表的平均查找长度不超过 R〔R 可以从键盘输入确定〕，完成相应的建表和查表程序。
4. 拼写检查
1〕问题描述：现在有一些英语单词需要做拼写检查，你的工具是一本词典。需要检查的单词，有的是词典中的单词，有的与词典中的单词相似，你的任务是发现这两种情况。单词 A 与单词 B 相似的情况有三种：①删除单词 A 的一个字母后得到单词 B；②用任意一个字母替换单词 A 的一个字母后得到单词 B；③在单词 A 的任意位置增加一个字母后得到单词 B。
2〕实验要求：发现词典中与给定单词一样或相似的单词。
实验过程与实验结果
应包括如下主要内容：
数据结构定义
数表的查找方法通常适用于动态集合。动态集合的特点是集合结构本身在查找过程中动态生成，即对于给定值k，假如集合中存在关键字等于k的记录，如此查找成功，否如此插入关键字为k的新记录。
二叉排序树，又叫二叉查找树或二叉搜索树。它或者是一棵空树，或者是一棵具有如下特征的非空二叉树：
1〕假如它的左子树非空，如此左子树上所有节点的关键字均小于根节点的关键字。
2〕假如它的右子树非空，如此右子树上所有节点的关键字均大于根节点的关键字。
3〕左、右子树也分别是二叉排序树。
平衡二叉树的定义是：假如一棵二叉排序树中每个节点的左、右子树的高度之差的绝对值不超过1，如此称这样的二叉排序树为平衡二叉树。
算法设计思路简介
1、
数据有序，用折半查找法，通过即可快速找到关键字。
2、
二叉树表实际上就是个二叉树，就像建立一个普通的二叉树一样建立树，只是在插入节点的时候要和当前节点的值比拟，假如当前节点为空如此插入当前节点；否如此，假如小于当前值如此插入左子树大于当前节点就插入右子树。对建立好的树进展中序遍历即可得到有序序列。
3、
人的姓一般有很大可能性一样，但是人名的第二个字一般是不同的，既然人名示例是拼音形式姑且认为第二个字母即为第二个字。将其ASCLL码模49作为哈希函数，将各人名分类存在不同的链表中，提高查询效率。
算法描述：可以用自然语言、伪代码或流程图等方式
4、
以单词中字母的数目为标准将单词分类，假如字母数想等或相差一如此进展细致的比拟〔下面有详细描述〕，否如此根本不相似。
1、
开始