数据结构实验5查找综合

课程实验报告课程名称数据结构班级实验日期2018/12/07姓名学号实验成绩实验名称实验5：查找综合实验目的及要求实验目的（1） 掌握线性表的查找方法和平均查找长度的计算；（2） 掌握二叉排序树构造、查找、插入和删除的方法及其平均查找长度的计算；（3） 掌握哈希查找的方法及其平均查找长度的计算；（3）比较各种查找方法的查找性能。实验环境Windows7Visualstudio2013自行设计数据结构通讯录（包括电话号码、以电话号码为关键字）完成以下功能：用户名、地址，1建立顺序表，采用顺序查找的方法按照关键字进行查找并显示相应的记录，并显示查找的过程即跟关键字比较的顺序，计算查找成功情况下的平均查找长度。实验内容2对无序的记录按照关键字首先排序，然后采用折半查找的方法对数据按照关键字进行查找，并显示查找的过程即跟关键字比较的顺序，计算查找成功情况下的平均查找长度。3对块内无序、块间有序的数据首先建立索引表，采用分块查找的方法对数据按照关键字进行查找，并显示查找的过程即跟关键字比较的顺序，计算查找成功情况下的平均查找长度。4将数据按照关键字的大小插入到二叉排序树中，在二叉排序树中对数据进行插入、查找、删除等操作，计算查找成功情况下的平均查找长度。5建立散列表，散列函数自行设计，解决冲突的方法可以任选线性探测、二次探测和链地址法中的一种。在散列表中对对数据按照关键字进行查找，并显示查找的过程即跟关键字比较的顺序，计算查找成功情况下的平均查找长度。6根据实验数据分析各种查找方法的优劣及适用范围及查找性能。

算法描述及实验步骤调试过程及实验结果1采用顺序表结构建立用户信息存储结构，然后进行顺序查找，再查找的过程中，添加“cout<<”语句标记查找次数，便于以后进行比较，可以比较得到两种查找方法的不同之处，随后进行排序，排序后进行折半查找，比较得到两种两种查找方法的效率。完成1，2两个小问题。算法描述及实验步骤调试过程及实验结果2对于3,要求输入块间有序的数据进行，建立索引表，然后利用索引表进行查找，用cout语句进行标记查找长度。3建立二叉排序树，然后4个函数进行数据的增删查改操作，cout语句标记查找长度。4建立散列表，采用链地址法进行哈希表的存储，建立哈希函数，进行数据的查找，标记。1建立顺序表，进行顺序查找和排序后的折半查找，进行比较，所查找的信息如下二'rocessexitedwithreturnvalue0斤查找的信息如下;an234522建立索引表，分块查找逋查查查（电话号用马为关键字）123452an23452请输入家庭住址；rhdh6y，所查找的信息如下二'rocessexitedwithreturnvalue0斤查找的信息如下;an234522建立索引表，分块查找逋查查查（电话号用马为关键字）123452an23452请输入你先要查找的关键字：12345说查找的信息如下：name:rghsrthrnumber：1234506position：erygsrrocessexitedwithreturnvalue0ressanykeytocontinue...成功查找:姓名:吁码:住址;姓名:号码:住址，姓名:号蚀住址:姓缶号佃住址;姓名:号码:住址=XE-Ti:住址;ghyt6y123456hsthrtyergserths123459aergasfergsrg123450ugsedgasdgsedrg123451agerthwthzzzzzz123454zzzzzzrgerfe123455awrggger:■■■,成功查找:姓名:吁码:住址;姓名:号码:住址，姓名:号蚀住址:姓缶号佃住址;姓名:号码:住址=XE-Ti:住址;ghyt6y123456hsthrtyergserths123459aergasfergsrg123450ugsedgasdgsedrg123451agerthwthzzzzzz123454zzzzzzrgerfe123455awrggger:■■■,l-fr名码址姓号住■■l-frrfr名玛址姓号住息fen邱言rAKeI:的84Jfr-Xrvi姓名：sdgsedrg号码=123451住址：agerthwthzzzzsz123454zzzzzzrgerfe123455awrggger姓名：ghyt6y号码：123456住址：hsthrty姓名：ergserths号码：123459住址aergas请输入你想查找的（关键字）:123454找名话址3建立排序二叉树，并且进行增删查操作：删除123450数据元素（1）初始化（2）插入一个123454数据（删除123450数据元素哈希表的建立与查找：■1HLMaoqiaat-eibLan^tqiXDe^-CppKo^^ol^Patiiger.e^E!卜辎.k要W标"数:3请输k每爪,•、*，"m情输入娃岳:rfvc谙徜入电话号码:133455诘辎人麻虹住扣"rfvcde清辎入姓料；ertyh请输入电话匕码;123456i舌福K家雁任址；edczhn入姓电:宵邓访输K电厝号码:123459输K室庭住址!wsjcaqq请摘入咯拈存魅的愀排偷3存怕成用3讷输入郁要存找的内容〔电L舌作为美愧字）=123456£4揖腐功!信息加F：名:eTlvh电队12345S往址.：edcTtm^L'tMjesaexitedwithreturnvalue03resaanykeytocontinue...

总结通过这次实验，完全的掌握了数据结构第九章：查找的有关内容，从最开始的建立顺序表进行顺序查找，后来的排序后进行折半查找，然后分块查找，建立排序树表，进行查找，增加，删除等操作，然后是哈希表的建立存储，与查找，最终，用了4个程序完成了着第五次实验的要求，并分析得出各种查找的效率问题，最好的是折半查找，但是需要进行排序，现实生活中大多数是无序的，所以采用哈希存储的最实用！附录(部分实现代码)1折半查找：voidBinSearch(SqList*L,intk){intlow=0,high=L->length-1,mid;intfind=1;while(low<=high){cout<<"进行第"<<find<<"次查找……"<<endl;mid=(low+high)/2;if(k==L->data[mid].number){cout<<"查找成功，所查找的信息如下："<<endl;cout<<L->data[mid].name<<endl;cout<<L->data[mid].number<<endl;cout<<L->data[mid].position<<endl;return;}if(k<L->data[mid].number)high=mid-1;elselow=mid+1;find++;}return;}2分块查找：〃分块查找函数数据表长度 索引表 长度关键字intIdxSearch(SqList*L,intn,IdxTypeindex[],intm,intk){intlow=0,high=n-1,mid,i;intb-n/m;//b是每块中记录数据的个数while(low<-high)〃在索引表中找到索要查找的关键字的位置{mid-(low+high)/2;if(index[mid].key>-k)high-mid-1;elselow=mid+1;} 一i=index[high+1].link;//找出起始下标〃在具体的数据中查找while(i<=index[high+1].link&&L->data[i].number!=k){i++;}〃属于这个块中，小于最大下标if(i<=index[high+1].link+b-1)returni+1;elsereturn0;}3树表查找：BSTNode*Search(BSTNode*bt,intk){if(bt->key=k||bt=NULL){returnbt;}if(bt->key<k){returnSearch(bt->rchild,k);}else{returnSearch(bt->lchild,k);}}4哈希存储查找voidSearch(HashTableha[],intp,KeyTypek){inti=0;intadr;adr=k%p;〃计算哈希数值NodeType*q;q=ha[