实验五-查找算法应用

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

2、L树的查找、插入、删除、建立算法的思想及程序实现；掌握散列存储结构的思想，能选择合适散列函数，实现不同冲突处理方法的散列表的查找、建立。能运用所 学查找结构与算法等解决实际问题。二、实验题目与要求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）若它的左子树非空，贝U左子树上所有节点的关键字均小于根节点的关键字。?2）若它的右子树非空，则右子树上所有节点的关键字均大于根节点的关键字。?3）左、右子树也分别是二叉排序树。?平衡二叉树的定义是：若一棵二叉排序树中每个节点的左、右子树的高度之差的绝对值不超过1，则称这样的二叉排序树为平衡二叉树。?算法设计思路简介1、数据有序，用折半查找法，通过即可快速找到关键字。2、二叉树表实际上就是个二叉树，就像建立一个普通的二叉树一样建立树，只是在插入节点的 时候要和当前节点的值比较，若当前节点为空则插入当前节点；否则，若小于当前值则插入 左子树大于当前节点就插

6、入右子树。对建立好的树进行中序遍历即可得到有序序列。3、人的姓一般有很大可能性相同，但是人名的第二个字一般是不同的，既然人名示例是拼音形式姑且认为第二个字母即为第二个字。将其ASCLL码模49作为哈希函数，将各人名分类存在不同的链表中，提高查询效率。算法描述：可以用自然语言、伪代码或流程图等方式4、以单词中字母的数目为标准将单词分类，若字母数想等或相差 详细描述），否则根本不相似。则进行细致的比较（下面有1、low = 1,high = nmid =(low+hi结束2、(1)创建普通二叉树节点。(2)输入要插入的值k。(3)将k插入二叉树节点中，若当前节点为空则申请节点空间并将k存入当前节点

7、的data域中，令其左右子树均为空；若当前节点不为空且k小于当前节点的data值，则将k存入当前节点的左子树中去，若 当前节点不为空且k大于当前节点的data值，则将k存入当前节点的右子树中去。(4)中序遍历此二叉树。3、?(1)录入人名。?(2)以人名的第二个字母的ASCLL码模49(所用数组空间为50)，得到的数作为下标，将此人名存入相应的邻接表中。?(3)输入待查人名。?(4)以人名的第二个字母的ASCLL码模49得到的数字为下标找到相应的链表，若链表为空则表明待查人名不在名单中，输出0;若不为空，则与链表中的每一个名字做比较，入股在下标对应的整个链表中都找不到此名字则说明待查人名不在名

8、单中，输出0,否则表明待查人名在名单中，输出1。4、(1)输入单词列表并存入字典中。(2)输入待查单词。(3)将待查单词和字典中的每个单词做比较。(3)计算字典中单词列表中每个单词的长度和待查单词的长度。分三种情况：若字典中单词的长度等于待查单词的长度，将字典中单词的每个字母和待查单词的每个字母做比较，若相同的字母数和单词长度相同则说明两单词完全相同，若或比人名长度少一则说明两单词只有一个 字母不同属于替换一个字母就相同的情况。两种情况均打印1.若字典中的单词长度等于待查单词长度减一，将字典中单词的每个字母和待查单词的每个字母作比较，若相同字母数为字典中单词的长度，则说明待查单词与字典中的单词

9、相似，只是多了一个字母，打印1.若字典中单词长度等于待查单词长度加一，将字典中的每个字母和待查单词的每个字母作比较，若相同字母数为字典中单词长度减一，则说明待查单词与字典中的单词相似，只是少了一个字母，打印1.其余情况均不相似，打印0.?算法的实现和测试结果：包括算法运行时的输入、输出，实验中出现的问题及解决办法等D3匚V/1 N D OWSsys te m 3 2c rndn e xe3 212 32请按任意键继续.3 21 3 41请按E意龛继续.N DC)WSstem32cnnd,exe12 3-1123请按任意键继续.C:VVIN DOWSsystem32cmd ef?abProces

10、s exited after 23. seconds wilh rewrn value 0请按任意權继续.” 算法时间复杂度分析1、O(log2 n).2、最差情况(单枝树)O(n)一般情况O(log2n)3、? 0(1)?4、?0(m n)? m:字典中的单词数? n:待查单词数四、收获与体会之前只知道查找这回事，以为以现在计算机的性能查找已经变得很方便了。跟戴老师学习了查找之后 才发现大数据的可怕，无论多少条记录我们都希望在几秒内完成。那么在短时间内计算机性能无法大幅度 提高的前提下就要考虑查找的算法了(其实就算计算机性能再好，优化算法也能提高查找效率)。顺序查找肯定是不学都会，折半查找之

11、前也听说过，如何让查找表变得有序也是让人头疼的事。就说 这个散列查找，竟然能达到0(1)阶的查找效率，真让人感叹人类的智慧了。做完了图那章的实验，感觉这次实验简单多了。数据结构真的是越来越有趣了，慢慢感受到了编程的 魅力。五、源代码清单1、#inelude using namespace std;int binarysearch( int array , int Key, int N)int low = 1;int high = N;int mid;while (low = high)2、mid = (low+high)/2;/cout mid: mid en dl;if (array mid

12、 = Key) return mid;else if (Key n;cin key;for (int i = 1;i ai;result = bin arysearch(a,key ,n);cout result;return 0;#include using namespace std;int count = 0;int N = 0;typedef struct BitNodeint data;struct BitNode *lchild,*rchild;BitNode,*BitTree;void insert(BitTree &T, int k)if(T = NULL)T = (B

13、itNode*)malloc( sizeof (BitNode);T-data = k;T-lchild = T-rchild = NULL;else if(k data) insert(T-lchild,k);else if(k T-data) insert(T-rchild,k);else if(k = T-data) insert(T-lchild,k);void InOrder(BitNode *T)if(T = NULL) return ;InO rder (T-lchild);cout data;cou nt+;/cout N = N endl;/cout cou nt = cou

14、 nt en dl;if(cou nt N)cout rchild);int main()BitNode *root;root = NULL;int a20 = 0;for (int j = 0;j aj;N+;if(aj = -1)N-;break ;int i = 0;while (ai != -1)in sert(root,ai);i+；/cout haha en dl;InO rder(root);cou nt = 0;N = 0;return 0;3、#include #include using namespace std; typedef struct Hashchar data

15、50;struct Hash *next;Hash;typedef structint data;struct Hash *next;FirstHash30;int main()int n ,q;int cou nts;cin n;cin q;char name5050;char check name5050;FirstHash *h;h = (FirstHash*)malloc( sizeof (FirstHash50);for (int i = 0;i data = i;hi- next = NULL;for (int i = 0;i n amei;/cout n amei1 = n am

16、ei1 en dl; counts = ( int )namei1 % 49;/cout cou nts = cou nts data, namei);/cout data: data n ext = hcou nts-n ext;hcou nts-n ext = hash;/以上I?程?序?问没o题?afor (int i = 0;i check namei;for (int i = 0;i next = NULL)cout 0 n ext;while (temp!= NULL & strcmp(temp-data,checknamei)temp = temp-n ext;if (t

17、emp = NULL)cout 0 en dl;!= 0)elsecout 1 en dl;return 0;4、#in cludeusing n amespace std;char Dic5050;char Check5050;in t getLe ngth(char array)得到单词的长度int i = 0;while(arrayi != 0)i+;return i;int research(char array1,char array2)字典，待查词汇 ，字典中的某个单词与某个待查单词是否相似int count1 = 0;int count2 = 0;int simble = 0;c

18、ountl = getLe ngth(arrayl);count2 = getLe ngth(array2);/cout co untl = countl en dl;/cout co unt2 = count2 en dl;if(cou nt1 = cou nt2) /单词长度相等，替换任一字母simble = 0;int i = 0;while(i = coun t1-1)return 1;elsereturn 0;else if(cou nt1 = cou nt2-1)比字典长度长1simble = 0;int i = 0,j = 0;while( j count2 & i = coun t1)return 1;elsereturn 0;else if(cou nt1 = cou nt2+1)比字典长度短1int i = 0,j = 0;simble = 0;while(i count1 & j = coun t1-1)return 1;elsereturn 0;elsereturn 0;int mai n()i