实验五-查找算法应用

,.实验报告学院（系）名称：计算机与通信工程学院姓名 * * 学号 ********班级 2015级*班 实验项目 实验五：课程名称 数据结构与算法实验时间年月日第节考核实验过程程序运行回答问题实验报告标准25分20分15分30分成绩栏

专业计算机科学与技术查找算法应用课程代码0661013实验地点7-***特色考勤违成绩功能纪情况5分5分其它批改意见:评价在实验

□功能完善, ○正确

○完整课堂中的表考核现，包括实

□功能不全 ○基本正确

○较完整

○有 ○有内容 验态度、编写程序过程

□有小错 ○有提示

○一般

○无 ○无等内容等。

□无法运行 ○无法回答

○内容极少○无报告教师签字：,.一、实验目的实验目的：理解二叉排序树、AVL树的查找、插入、删除、建立算法的思想及程序实现；掌握散列谢谢阅读存储结构的思想，能选择合适散列函数，实现不同冲突处理方法的散列表的查找、建立。能运用所精品文档放心下载学查找结构与算法等解决实际问题。二、实验题目与要求1.折半查找算法1）问题描述：从键盘读入一串整数和一个待查关键字，查找在该整数串中是否有这个待查关键谢谢阅读字。如果有，输出它在整数串中的位置；如果没有，输出-1谢谢阅读2）实验要求：①利用折半查找算法查找②用递归和非递归两种方式实现折半查找算法精品文档放心下载实现提示：①递归实现参考书上折半查找算法的实现②非递归算法利用栈实现精品文档放心下载2.构造二叉排序树，并进行中序遍历（实验类型：综合型）精品文档放心下载1）问题描述：从键盘读入一串整数构造一棵二叉排序树，并对得到的二叉排序树进行中序遍历，感谢阅读得到有序序列。2）实验要求：该二叉排序树以二叉链表存储3）实现提示：二叉排序树的构成，可从空的二叉树开始，每输入一个结点数据，就建立一个新结精品文档放心下载点插入到当前已生成的二叉排序树中，所以它的主要操作是二叉排序树插入运算。在二叉排序树中插入新精品文档放心下载结点，只要保证插入后仍符合二叉排序树的定义即可。3．哈希表查找1）问题描述：针对某个集体的“人名”构造哈希表，解决按“人名”进行查找的索引结构。感谢阅读2）实验要求：要求表的平均查找长度不超过R（R可以从键盘输入确定），完成相应的建表和查谢谢阅读表程序。拼写检查,.1）问题描述：现在有一些英语单词需要做拼写检查，你的工具是一本词典。需要检查的单词，有精品文档放心下载的是词典中的单词，有的与词典中的单词相似，你的任务是发现这两种情况。单词A与单词B相似的感谢阅读情况有三种：①删除单词A的一个字母后得到单词B；②用任意一个字母替换单词A的一个字母精品文档放心下载后得到单词B；③在单词A的任意位置增加一个字母后得到单词B。感谢阅读2）实验要求：发现词典中与给定单词相同或相似的单词。谢谢阅读实验过程与实验结果应包括如下主要内容：➢ 数据结构定义➢ 数表的查找方法通常适用于动态集合。动态集合的特点是集合结构本身在查找过程中动谢谢阅读态生成，即对于给定值k，若集合中存在关键字等于k的记录，则查找成功，否则插入关键精品文档放心下载字为k的新记录。➢

二叉排序树，又叫二叉查找树或二叉搜索树。它或者是一棵空树，或者是一棵具有如下特征的非空二叉树：感谢阅读1）若它的左子树非空，则左子树上所有节点的关键字均小于根节点的关键字。精品文档放心下载2）若它的右子树非空，则右子树上所有节点的关键字均大于根节点的关键字。谢谢阅读3）左、右子树也分别是二叉排序树。平衡二叉树的定义是：若一棵二叉排序树中每个节点的左、右子树的高度之差的绝对值不超过1，则称这样的二叉排序树为平衡二叉树。感谢阅读算法设计思路简介1、数据有序，用折半查找法，通过即可快速找到关键字。2、二叉树表实际上就是个二叉树，就像建立一个普通的二叉树一样建立树，只是在插入节点的时候要和当前节点的值比较，若当前节点为空则插入当前节点；否则，若小于当前值则插入左子树大于当前节点就插入右子树。对建立好的树进行中序遍历即可得到有序序列。谢谢阅读3、人的姓一般有很大可能性相同，但是人名的第二个字一般是不同的，既然人名示例是拼音形式姑且认为第二个字母即为第二个字。将其ASCLL码模49作为哈希函数，将各人名分类存谢谢阅读,.在不同的链表中，提高查询效率。算法描述：可以用自然语言、伪代码或流程图等方式4、以单词中字母的数目为标准将单词分类，若字母数想等或相差一则进行细致的比较（下面有精品文档放心下载详细描述），否则根本不相似。1、开始输入a[i],keyi=1,2,3,…,nlow=1,high=nmid=(low+high)/2,.=mid=key?≠是k<a[mid]? high=mid-1否low=mid+1是low<=high?否return-1 returnmid输出-1 输出mid,.结束2、(1)创建普通二叉树节点。(2)输入要插入的值k。(3)将k插入二叉树节点中，若当前节点为空则申请节点空间并将k存入当前节点的data域中，令其感谢阅读左右子树均为空;若当前节点不为空且k小于当前节点的data值，则将k存入当前节点的左子树中去，若感谢阅读当前节点不为空且k大于当前节点的data值，则将k存入当前节点的右子树中去。精品文档放心下载(4)中序遍历此二叉树。3、(1)录入人名。(2)以人名的第二个字母的ASCLL码模49（所用数组空间为50），得到的数作为下标，将此人名存入相应的邻接表中。精品文档放心下载(3)输入待查人名。(4)以人名的第二个字母的ASCLL码模49得到的数字为下标找到相应的链表，若链表为空则表明待查人名不在名单中，输出0；若不为空，则与链表中的每一个名字做比较，入股在下标对应的整个链表中都找不到此名字则说明待查人名不在名单中，输出0，否则表明待查人名在名单中，输出1。感谢阅读4、(1)输入单词列表并存入字典中。(2)输入待查单词。(3)将待查单词和字典中的每个单词做比较。(3)计算字典中单词列表中每个单词的长度和待查单词的长度。分三种情况：感谢阅读若字典中单词的长度等于待查单词的长度，将字典中单词的每个字母和待查单词的每个字母做比感谢阅读较，若相同的字母数和单词长度相同则说明两单词完全相同，若或比人名长度少一则说明两单词只有一个谢谢阅读字母不同属于替换一个字母就相同的情况。两种情况均打印1.精品文档放心下载若字典中的单词长度等于待查单词长度减一，将字典中单词的每个字母和待查单词的每个字母作精品文档放心下载比较，若相同字母数为字典中单词的长度，则说明待查单词与字典中的单词相似，只是多了一个字母，打感谢阅读1.若字典中单词长度等于待查单词长度加一，将字典中的每个字母和待查单词的每个字母作比较，谢谢阅读若相同字母数为字典中单词长度减一，则说明待查单词与字典中的单词相似，只是少了一个字母，打印1.感谢阅读其余情况均不相似，打印0.➢ 算法的实现和测试结果：包括算法运行时的输入、输出，实验中出现的问题及解决办法等感谢阅读1、➢➢2、➢➢3、➢4、➢➢ 算法时间复杂度分析1、O(log2n).2、最差情况（单枝树）O(n)一般情况O(log2n),.3、O(1)4、O(mn)m:字典中的单词数n:待查单词数四、收获与体会之前只知道查找这回事，以为以现在计算机的性能查找已经变得很方便了。跟戴老师学习了查找之后谢谢阅读才发现大数据的可怕，无论多少条记录我们都希望在几秒内完成。那么在短时间内计算机性能无法大幅度精品文档放心下载提高的前提下就要考虑查找的算法了(其实就算计算机性能再好，优化算法也能提高查找效率)。谢谢阅读顺序查找肯定是不学都会，折半查找之前也听说过，如何让查找表变得有序也是让人头疼的事。就说谢谢阅读这个散列查找，竟然能达到O(1)阶的查找效率，真让人感叹人类的智慧了。感谢阅读做完了图那章的实验，感觉这次实验简单多了。数据结构真的是越来越有趣了，慢慢感受到了编程的精品文档放心下载魅力。五、源代码清单1、#include<iostream>usingnamespacestd;intbinarysearch(intarray[],intKey,intN)谢谢阅读{intlow=1;inthigh=N;intmid;while(low<=high),.{mid=(low+high)/2;//cout<<"mid:"<<mid<<endl;谢谢阅读if(array[mid]==Key)returnmid;精品文档放心下载elseif(Key<array[mid])high=mid-1;elselow=mid+1;}return-1;}intmain(){inta[20]={0};intn,key,result;cin>>n;cin>>key;for(inti=1;i<=n;i++)cin>>a[i];result=binarysearch(a,key,n);谢谢阅读cout<<result;return0;}2、#include<iostream>,.usingnamespacestd;intcount=0;intN=0;typedefstructBitNode{intdata;structBitNode*lchild,*rchild;精品文档放心下载}BitNode,*BitTree;voidinsert(BitTree&T,intk)感谢阅读{if(T==NULL){=(BitNode*)malloc(sizeof(BitNode));T->data=k;感谢阅读T->lchild=T->rchild=NULL;感谢阅读}elseif(k<T->data)insert(T->lchild,k);精品文档放心下载elseif(k>T->data)insert(T->rchild,k);精品文档放心下载elseif(k==T->data)insert(T->lchild,k);感谢阅读}voidInOrder(BitNode*T){if(T==NULL)return;InOrder(T->lchild);,.cout<<T->data;count++;//cout<<"N="<<N<<endl;精品文档放心下载//cout<<"count="<<count<<endl;谢谢阅读if(count<N)cout<<"";InOrder(T->rchild);}intmain(){BitNode*root;root=NULL;inta[20]={0};for(intj=0;j<20;j++){cin>>a[j];N++;if(a[j]==-1){N--;break;}}inti=0;,.while(a[i]!=-1){insert(root,a[i]);i++;}//cout<<"haha"<<endl;InOrder(root);count=0;N=0;return0;}3、#include<iostream>#include<cstring>usingnamespacestd;typedefstructHash{chardata[50];structHash*next;}Hash;typedefstruct{intdata;structHash*next;,.}FirstHash[30];intmain(){intn,q;intcounts;cin>>n;cin>>q;charname[50][50];charcheckname[50][50];FirstHash*h;h=(FirstHash*)malloc(sizeof(FirstHash[50]));精品文档放心下载for(inti=0;i<50;i++){h[i]->data=i;h[i]->next=NULL;}for(inti=0;i<n;i++){cin>>name[i];//cout<<"name[i][1]="<<name[i][1]<<endl;感谢阅读counts=(int)name[i][1]%49;精品文档放心下载//cout<<"counts="<<counts<<endl;感谢阅读Hash*hash=(Hash*)malloc(sizeof(Hash));感谢阅读,.strcpy(hash->data,name[i]);谢谢阅读//cout<<"hash->data:"<<hash->data<<endl;谢谢阅读hash->next=h[counts]->next;感谢阅读h[counts]->next=hash;}//以°?上¦?程¨¬序¨°没?问¨º题¬afor(inti=0;i<q;i++){cin>>checkname[i];}for(inti=0;i<q;i++){counts=(int)checkname[i][1]%49;感谢阅读if(h[counts]->next==NULL)感谢阅读cout<<0<<endl;else{Hash*temp=h[counts]->next;感谢阅读while(temp!=NULL&&strcmp(temp->data,checkname[i])!=0)精品文档放心下载{temp=temp->next;}if(temp==NULL)cout<<0<<endl;,.elsecout<<1<<endl;}}return0;}4、#include<iostream>usingnamespacestd;charDic[50][50];charCheck[50][50];intgetLength(chararray[])//得到单词的长度感谢阅读{inti=0;while(array[i]!='\0'){i++;}returni;}intresearch(chararray1[],chararray2[])//字典,待查词汇，字典中的某个单词与某个待查单词是否相似精品文档放心下载{intcount1=0;,.intcount2=0;intsimble=0;count1=getLength(array1);感谢阅读count2=getLength(array2);精品文档放心下载// cout<<"count1="<<count1<<endl;谢谢阅读// cout<<"count2="<<count2<<endl;感谢阅读if(count1==count2)//单词长度相等，替换任一字母谢谢阅读{simble=0;inti=0;while(i<count1){if(array1[i]==array2[i])感谢阅读simble++;i++;}if(simble>=count1-1)return1;elsereturn0;}elseif(count1==count2-1)//比字典长度长1谢谢阅读{simble=0;,.inti=0,j=0;while(j<count2&&i<count