實驗五-查找算法應(yīng)用

,.實驗報告學(xué)院（系）名稱：計算機(jī)與通信工程學(xué)院姓名 * * 學(xué)號 ********班級 2015級*班 實驗項目 實驗五：課程名稱 數(shù)據(jù)結(jié)構(gòu)與算法實驗時間年月日第節(jié)考核實驗過程程序運行回答問題實驗報告標(biāo)準(zhǔn)25分20分15分30分成績欄

專業(yè)計算機(jī)科學(xué)與技術(shù)查找算法應(yīng)用課程代碼0661013實驗地點7-***特色考勤違成績功能紀(jì)情況5分5分其它批改意見:評價在實驗

□功能完善, ○正確

○完整課堂中的表考核現(xiàn)，包括實

□功能不全 ○基本正確

○較完整

○有 ○有內(nèi)容 驗態(tài)度、編寫程序過程

□有小錯 ○有提示

○一般

○無 ○無等內(nèi)容等。

□無法運行 ○無法回答

○內(nèi)容極少○無報告教師簽字：,.一、實驗?zāi)康膶嶒災(zāi)康模豪斫舛媾判驑?、AVL樹的查找、插入、刪除、建立算法的思想及程序?qū)崿F(xiàn)；掌握散列謝謝閱讀存儲結(jié)構(gòu)的思想，能選擇合適散列函數(shù)，實現(xiàn)不同沖突處理方法的散列表的查找、建立。能運用所精品文檔放心下載學(xué)查找結(jié)構(gòu)與算法等解決實際問題。二、實驗題目與要求1.折半查找算法1）問題描述：從鍵盤讀入一串整數(shù)和一個待查關(guān)鍵字，查找在該整數(shù)串中是否有這個待查關(guān)鍵謝謝閱讀字。如果有，輸出它在整數(shù)串中的位置；如果沒有，輸出-1謝謝閱讀2）實驗要求：①利用折半查找算法查找②用遞歸和非遞歸兩種方式實現(xiàn)折半查找算法精品文檔放心下載實現(xiàn)提示：①遞歸實現(xiàn)參考書上折半查找算法的實現(xiàn)②非遞歸算法利用棧實現(xiàn)精品文檔放心下載2.構(gòu)造二叉排序樹，并進(jìn)行中序遍歷（實驗類型：綜合型）精品文檔放心下載1）問題描述：從鍵盤讀入一串整數(shù)構(gòu)造一棵二叉排序樹，并對得到的二叉排序樹進(jìn)行中序遍歷，感謝閱讀得到有序序列。2）實驗要求：該二叉排序樹以二叉鏈表存儲3）實現(xiàn)提示：二叉排序樹的構(gòu)成，可從空的二叉樹開始，每輸入一個結(jié)點數(shù)據(jù)，就建立一個新結(jié)精品文檔放心下載點插入到當(dāng)前已生成的二叉排序樹中，所以它的主要操作是二叉排序樹插入運算。在二叉排序樹中插入新精品文檔放心下載結(jié)點，只要保證插入后仍符合二叉排序樹的定義即可。3．哈希表查找1）問題描述：針對某個集體的“人名”構(gòu)造哈希表，解決按“人名”進(jìn)行查找的索引結(jié)構(gòu)。感謝閱讀2）實驗要求：要求表的平均查找長度不超過R（R可以從鍵盤輸入確定），完成相應(yīng)的建表和查謝謝閱讀表程序。拼寫檢查,.1）問題描述：現(xiàn)在有一些英語單詞需要做拼寫檢查，你的工具是一本詞典。需要檢查的單詞，有精品文檔放心下載的是詞典中的單詞，有的與詞典中的單詞相似，你的任務(wù)是發(fā)現(xiàn)這兩種情況。單詞A與單詞B相似的感謝閱讀情況有三種：①刪除單詞A的一個字母后得到單詞B；②用任意一個字母替換單詞A的一個字母精品文檔放心下載后得到單詞B；③在單詞A的任意位置增加一個字母后得到單詞B。感謝閱讀2）實驗要求：發(fā)現(xiàn)詞典中與給定單詞相同或相似的單詞。謝謝閱讀實驗過程與實驗結(jié)果應(yīng)包括如下主要內(nèi)容：? 數(shù)據(jù)結(jié)構(gòu)定義? 數(shù)表的查找方法通常適用于動態(tài)集合。動態(tài)集合的特點是集合結(jié)構(gòu)本身在查找過程中動謝謝閱讀態(tài)生成，即對于給定值k，若集合中存在關(guān)鍵字等于k的記錄，則查找成功，否則插入關(guān)鍵精品文檔放心下載字為k的新記錄。?

二叉排序樹，又叫二叉查找樹或二叉搜索樹。它或者是一棵空樹，或者是一棵具有如下特征的非空二叉樹：感謝閱讀1）若它的左子樹非空，則左子樹上所有節(jié)點的關(guān)鍵字均小于根節(jié)點的關(guān)鍵字。精品文檔放心下載2）若它的右子樹非空，則右子樹上所有節(jié)點的關(guān)鍵字均大于根節(jié)點的關(guān)鍵字。謝謝閱讀3）左、右子樹也分別是二叉排序樹。平衡二叉樹的定義是：若一棵二叉排序樹中每個節(jié)點的左、右子樹的高度之差的絕對值不超過1，則稱這樣的二叉排序樹為平衡二叉樹。感謝閱讀算法設(shè)計思路簡介1、數(shù)據(jù)有序，用折半查找法，通過即可快速找到關(guān)鍵字。2、二叉樹表實際上就是個二叉樹，就像建立一個普通的二叉樹一樣建立樹，只是在插入節(jié)點的時候要和當(dāng)前節(jié)點的值比較，若當(dāng)前節(jié)點為空則插入當(dāng)前節(jié)點；否則，若小于當(dāng)前值則插入左子樹大于當(dāng)前節(jié)點就插入右子樹。對建立好的樹進(jìn)行中序遍歷即可得到有序序列。謝謝閱讀3、人的姓一般有很大可能性相同，但是人名的第二個字一般是不同的，既然人名示例是拼音形式姑且認(rèn)為第二個字母即為第二個字。將其ASCLL碼模49作為哈希函數(shù)，將各人名分類存謝謝閱讀,.在不同的鏈表中，提高查詢效率。算法描述：可以用自然語言、偽代碼或流程圖等方式4、以單詞中字母的數(shù)目為標(biāo)準(zhǔn)將單詞分類，若字母數(shù)想等或相差一則進(jìn)行細(xì)致的比較（下面有精品文檔放心下載詳細(xì)描述），否則根本不相似。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,.結(jié)束2、(1)創(chuàng)建普通二叉樹節(jié)點。(2)輸入要插入的值k。(3)將k插入二叉樹節(jié)點中，若當(dāng)前節(jié)點為空則申請節(jié)點空間并將k存入當(dāng)前節(jié)點的data域中，令其感謝閱讀左右子樹均為空;若當(dāng)前節(jié)點不為空且k小于當(dāng)前節(jié)點的data值，則將k存入當(dāng)前節(jié)點的左子樹中去，若感謝閱讀當(dāng)前節(jié)點不為空且k大于當(dāng)前節(jié)點的data值，則將k存入當(dāng)前節(jié)點的右子樹中去。精品文檔放心下載(4)中序遍歷此二叉樹。3、(1)錄入人名。(2)以人名的第二個字母的ASCLL碼模49（所用數(shù)組空間為50），得到的數(shù)作為下標(biāo)，將此人名存入相應(yīng)的鄰接表中。精品文檔放心下載(3)輸入待查人名。(4)以人名的第二個字母的ASCLL碼模49得到的數(shù)字為下標(biāo)找到相應(yīng)的鏈表，若鏈表為空則表明待查人名不在名單中，輸出0；若不為空，則與鏈表中的每一個名字做比較，入股在下標(biāo)對應(yīng)的整個鏈表中都找不到此名字則說明待查人名不在名單中，輸出0，否則表明待查人名在名單中，輸出1。感謝閱讀4、(1)輸入單詞列表并存入字典中。(2)輸入待查單詞。(3)將待查單詞和字典中的每個單詞做比較。(3)計算字典中單詞列表中每個單詞的長度和待查單詞的長度。分三種情況：感謝閱讀若字典中單詞的長度等于待查單詞的長度，將字典中單詞的每個字母和待查單詞的每個字母做比感謝閱讀較，若相同的字母數(shù)和單詞長度相同則說明兩單詞完全相同，若或比人名長度少一則說明兩單詞只有一個謝謝閱讀字母不同屬于替換一個字母就相同的情況。兩種情況均打印1.精品文檔放心下載若字典中的單詞長度等于待查單詞長度減一，將字典中單詞的每個字母和待查單詞的每個字母作精品文檔放心下載比較，若相同字母數(shù)為字典中單詞的長度，則說明待查單詞與字典中的單詞相似，只是多了一個字母，打感謝閱讀1.若字典中單詞長度等于待查單詞長度加一，將字典中的每個字母和待查單詞的每個字母作比較，謝謝閱讀若相同字母數(shù)為字典中單詞長度減一，則說明待查單詞與字典中的單詞相似，只是少了一個字母，打印1.感謝閱讀其余情況均不相似，打印0.? 算法的實現(xiàn)和測試結(jié)果：包括算法運行時的輸入、輸出，實驗中出現(xiàn)的問題及解決辦法等感謝閱讀1、??2、??3、?4、?? 算法時間復(fù)雜度分析1、O(log2n).2、最差情況（單枝樹）O(n)一般情況O(log2n),.3、O(1)4、O(mn)m:字典中的單詞數(shù)n:待查單詞數(shù)四、收獲與體會之前只知道查找這回事，以為以現(xiàn)在計算機(jī)的性能查找已經(jīng)變得很方便了。跟戴老師學(xué)習(xí)了查找之后謝謝閱讀才發(fā)現(xiàn)大數(shù)據(jù)的可怕，無論多少條記錄我們都希望在幾秒內(nèi)完成。那么在短時間內(nèi)計算機(jī)性能無法大幅度精品文檔放心下載提高的前提下就要考慮查找的算法了(其實就算計算機(jī)性能再好，優(yōu)化算法也能提高查找效率)。謝謝閱讀順序查找肯定是不學(xué)都會，折半查找之前也聽說過，如何讓查找表變得有序也是讓人頭疼的事。就說謝謝閱讀這個散列查找，竟然能達(dá)到O(1)階的查找效率，真讓人感嘆人類的智慧了。感謝閱讀做完了圖那章的實驗，感覺這次實驗簡單多了。數(shù)據(jù)結(jié)構(gòu)真的是越來越有趣了，慢慢感受到了編程的精品文檔放心下載魅力。五、源代碼清單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;}//以°?上|?程¨?序¨°沒?問¨o題?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