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

1、人郛鞅大學(xué)實驗報告學(xué)院（系）名稱： 計算機(jī)與通信工程學(xué)院姓名* *學(xué)號專業(yè)計算機(jī)科學(xué)與技術(shù)班級2015級*班實驗項目實驗五：查找算法應(yīng)用課程名稱數(shù)據(jù)結(jié)構(gòu)與算法課程代碼0661013實驗時間年 月 日第節(jié)實驗地點7 *考核 標(biāo)準(zhǔn)實驗過程25 分程序運(yùn)行20 分回答問題15 分實驗報告30 分特色 功能5 分考勤違 紀(jì)情況5 分成績成績 欄其它批改意見：教師簽字：考核 內(nèi)容評價在實驗 課堂中的表 現(xiàn)，包括實 驗態(tài)度、編 寫程序過程 等內(nèi)容等。功能完善，功能不全有小錯無法運(yùn)行O正確o基本正確O有提示o無法回答o完整o較完整o般o內(nèi)容極少o無報告o有o無o有o無、實驗?zāi)康膶嶒災(zāi)康模豪斫舛媾判驑洹V

2、L樹的查找、插入、刪除、建立算法的思想及程序?qū)崿F(xiàn)；掌握散列存儲結(jié)構(gòu)的思想，能選擇合適散列函數(shù)，實現(xiàn)不同沖突處理方法的散列表的查找、建立。能運(yùn)用所 學(xué)查找結(jié)構(gòu)與算法等解決實際問題。二、實驗題目與要求1.折半查找算法1）問題描述：從鍵盤讀入一串整數(shù)和一個待查關(guān)鍵字，查找在該整數(shù)串中是否有這個待查關(guān)鍵 字。如果有，輸出它在整數(shù)串中的位置；如果沒有，輸出-12）實驗要求：利用折半查找算法查找用遞歸和非遞歸兩種方式實現(xiàn)折半查找算法3）實現(xiàn)提示：遞歸實現(xiàn)參考書上折半查找算法的實現(xiàn)非遞歸算法利用棧實現(xiàn)2.構(gòu)造二叉排序樹，并進(jìn)行中序遍歷（實驗類型：綜合型）1）問題描述：從鍵盤讀入一串整數(shù)構(gòu)造一棵二叉排序樹，并

3、對得到的二叉排序樹進(jìn)行中序遍歷, 得到有序序列。2）實驗要求： 該二叉排序樹以二叉鏈表存儲3）實現(xiàn)提示：二叉排序樹的構(gòu)成， 可從空的二叉樹開始， 每輸入一個結(jié)點數(shù)據(jù)， 就建立一個新 結(jié) 點插入到當(dāng)前已生成的二叉排序樹中， 所以它的主要操作是二叉排序樹插入運(yùn)算。 在二叉排序樹 中插入新 結(jié)點，只要保證插入后仍符合二叉排序樹的定義即可。3.哈希表查找1）問題描述: 針對某個集體的“人名”構(gòu)造哈希表，解決按“人名”進(jìn)行查找的索引結(jié)構(gòu)。2）實驗要求： 要求表的平均查找長度不超過R（R可以從鍵盤輸入確定），完成相應(yīng)的建表和查表程序。4.拼寫檢查1）問題描述：現(xiàn)在有一些英語單詞需要做拼寫檢查，你的工具是一

4、本詞典。需要檢查的單詞，有的是詞典中的單詞，有的與詞典中的單詞相似，你的任務(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的新記錄。?二叉排序樹，又叫二叉查找樹或二叉搜索樹。它或者是一棵空樹，

5、或者是一棵具有如下特征的非空二叉樹：?1）若它的左子樹非空，貝U左子樹上所有節(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é)點就插

6、入右子樹。對建立好的樹進(jìn)行中序遍歷即可得到有序序列。3、人的姓一般有很大可能性相同，但是人名的第二個字一般是不同的，既然人名示例是拼音形式姑且認(rèn)為第二個字母即為第二個字。將其ASCLL碼模49作為哈希函數(shù)，將各人名分類存在不同的鏈表中，提高查詢效率。算法描述：可以用自然語言、偽代碼或流程圖等方式4、以單詞中字母的數(shù)目為標(biāo)準(zhǔn)將單詞分類，若字母數(shù)想等或相差 詳細(xì)描述），否則根本不相似。則進(jìn)行細(xì)致的比較（下面有1、low = 1,high = nmid =(low+hi結(jié)束2、(1)創(chuàng)建普通二叉樹節(jié)點。(2)輸入要插入的值k。(3)將k插入二叉樹節(jié)點中，若當(dāng)前節(jié)點為空則申請節(jié)點空間并將k存入當(dāng)前節(jié)點

7、的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)的整個鏈表中都找不到此名字則說明待查人名不在名

8、單中，輸出0,否則表明待查人名在名單中，輸出1。4、(1)輸入單詞列表并存入字典中。(2)輸入待查單詞。(3)將待查單詞和字典中的每個單詞做比較。(3)計算字典中單詞列表中每個單詞的長度和待查單詞的長度。分三種情況：若字典中單詞的長度等于待查單詞的長度，將字典中單詞的每個字母和待查單詞的每個字母做比較，若相同的字母數(shù)和單詞長度相同則說明兩單詞完全相同，若或比人名長度少一則說明兩單詞只有一個 字母不同屬于替換一個字母就相同的情況。兩種情況均打印1.若字典中的單詞長度等于待查單詞長度減一，將字典中單詞的每個字母和待查單詞的每個字母作比較，若相同字母數(shù)為字典中單詞的長度，則說明待查單詞與字典中的單詞

9、相似，只是多了一個字母，打印1.若字典中單詞長度等于待查單詞長度加一，將字典中的每個字母和待查單詞的每個字母作比較，若相同字母數(shù)為字典中單詞長度減一，則說明待查單詞與字典中的單詞相似，只是少了一個字母，打印1.其余情況均不相似，打印0.?算法的實現(xiàn)和測試結(jié)果：包括算法運(yùn)行時的輸入、輸出，實驗中出現(xiàn)的問題及解決辦法等D3匚V/1 N D OWSsys te m 3 2c rndn e xe3 212 32請按任意鍵繼續(xù).3 21 3 41請按E意龕繼續(xù).N DC)WSstem32cnnd,exe12 3-1123請按任意鍵繼續(xù).C:VVIN DOWSsystem32cmd ef?abProces

10、s exited after 23. seconds wilh rewrn value 0請按任意權(quán)繼續(xù).” 算法時間復(fù)雜度分析1、O(log2 n).2、最差情況(單枝樹)O(n)一般情況O(log2n)3、? 0(1)?4、?0(m n)? 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é)都會，折半查找之

11、前也聽說過，如何讓查找表變得有序也是讓人頭疼的事。就說 這個散列查找，竟然能達(dá)到0(1)階的查找效率，真讓人感嘆人類的智慧了。做完了圖那章的實驗，感覺這次實驗簡單多了。數(shù)據(jù)結(jié)構(gòu)真的是越來越有趣了，慢慢感受到了編程的 魅力。五、源代碼清單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