課程實驗報告課程名稱數(shù)據(jù)結構班級實驗日期2018/12/07姓名學號實驗成績實驗名稱實驗5：查找綜合實驗目的及要求實驗目的（1） 掌握線性表的查找方法和平均查找長度的計算；（2） 掌握二叉排序樹構造、查找、插入和刪除的方法及其平均查找長度的計算；（3） 掌握哈希查找的方法及其平均查找長度的計算；（3）比較各種查找方法的查找性能。實驗環(huán)境Windows7Visualstudio2013自行設計數(shù)據(jù)結構通訊錄（包括電話號碼、以電話號碼為關鍵字）完成以下功能：用戶名、地址，1建立順序表，采用順序查找的方法按照關鍵字進行查找并顯示相應的記錄，并顯示查找的過程即跟關鍵字比較的順序，計算查找成功情況下的平均查找長度。實驗內(nèi)容2對無序的記錄按照關鍵字首先排序，然后采用折半查找的方法對數(shù)據(jù)按照關鍵字進行查找，并顯示查找的過程即跟關鍵字比較的順序，計算查找成功情況下的平均查找長度。3對塊內(nèi)無序、塊間有序的數(shù)據(jù)首先建立索引表，采用分塊查找的方法對數(shù)據(jù)按照關鍵字進行查找，并顯示查找的過程即跟關鍵字比較的順序，計算查找成功情況下的平均查找長度。4將數(shù)據(jù)按照關鍵字的大小插入到二叉排序樹中，在二叉排序樹中對數(shù)據(jù)進行插入、查找、刪除等操作，計算查找成功情況下的平均查找長度。5建立散列表，散列函數(shù)自行設計，解決沖突的方法可以任選線性探測、二次探測和鏈地址法中的一種。在散列表中對對數(shù)據(jù)按照關鍵字進行查找，并顯示查找的過程即跟關鍵字比較的順序，計算查找成功情況下的平均查找長度。6根據(jù)實驗數(shù)據(jù)分析各種查找方法的優(yōu)劣及適用范圍及查找性能。

算法描述及實驗步驟調(diào)試過程及實驗結果1采用順序表結構建立用戶信息存儲結構，然后進行順序查找，再查找的過程中，添加“cout<<”語句標記查找次數(shù)，便于以后進行比較，可以比較得到兩種查找方法的不同之處，隨后進行排序，排序后進行折半查找，比較得到兩種兩種查找方法的效率。完成1，2兩個小問題。算法描述及實驗步驟調(diào)試過程及實驗結果2對于3,要求輸入塊間有序的數(shù)據(jù)進行，建立索引表，然后利用索引表進行查找，用cout語句進行標記查找長度。3建立二叉排序樹，然后4個函數(shù)進行數(shù)據(jù)的增刪查改操作，cout語句標記查找長度。4建立散列表，采用鏈地址法進行哈希表的存儲，建立哈希函數(shù)，進行數(shù)據(jù)的查找，標記。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數(shù)據(jù)元素（1）初始化（2）插入一個123454數(shù)據(jù)（刪除123450數(shù)據(jù)元素哈希表的建立與查找：■1HLMaoqiaat-eibLan^tqiXDe^-CppKo^^ol^Patiiger.e^E!卜輜.k要W標"數(shù):3請輸k每爪,?、*，"m情輸入娃岳:rfvc諳徜入電話號碼:133455詰輜人麻虹住扣"rfvcde清輜入姓料；ertyh請輸入電話匕碼;123456i舌福K家雁任址；edczhn入姓電:宵鄧訪輸K電厝號碼:123459輸K室庭住址!wsjcaqq請摘入咯拈存魅的愀排偷3存怕成用3訥輸入郁要存找的內(nèi)容〔電L舌作為美愧字）=123456￡4揖腐功!信息加F：名:eTlvh電隊12345S往址.：edcTtm^L'tMjesaexitedwithreturnvalue03resaanykeytocontinue...

總結通過這次實驗，完全的掌握了數(shù)據(jù)結構第九章：查找的有關內(nèi)容，從最開始的建立順序表進行順序查找，后來的排序后進行折半查找，然后分塊查找，建立排序樹表，進行查找，增加，刪除等操作，然后是哈希表的建立存儲，與查找，最終，用了4個程序完成了著第五次實驗的要求，并分析得出各種查找的效率問題，最好的是折半查找，但是需要進行排序，現(xiàn)實生活中大多數(shù)是無序的，所以采用哈希存儲的最實用！附錄(部分實現(xiàn)代碼)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分塊查找：〃分塊查找函數(shù)數(shù)據(jù)表長度 索引表 長度關鍵字intIdxSearch(SqList*L,intn,IdxTypeindex[],intm,intk){intlow=0,high=n-1,mid,i;intb-n/m;//b是每塊中記錄數(shù)據(jù)的個數(shù)while(low<-high)〃在索引表中找到索要查找的關鍵字的位置{mid-(low+high)/2;if(index[mid].key>-k)high-mid-1;elselow=mid+1;} 一i=index[high+1].link;//找出起始下標〃在具體的數(shù)據(jù)中查找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;〃計算哈希數(shù)值NodeType*q;q=ha[