實(shí)驗(yàn)五查找算法應(yīng)用

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

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

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

4、是詞典中的單詞，有的與詞典中的單詞相似，你的任務(wù)是發(fā)現(xiàn)這兩種情況。單詞 A 與單詞 B 相 似的情況有三種： 刪除單詞 A 的一個(gè)字母后得到單詞 B； 用任意一個(gè)字母替換單詞 A 的一個(gè)字母后得到單詞 B； 在單詞 A 的任意位置增加一個(gè)字母后得到單詞 B。 2）實(shí)驗(yàn)要求：發(fā)現(xiàn)詞典中與給定單詞相同或相似的單詞。 實(shí)驗(yàn)過程與實(shí)驗(yàn)結(jié)果 應(yīng)包括如下主要內(nèi)容：Ø 數(shù)據(jù)結(jié)構(gòu)定義Ø 數(shù)表的查找方法通常適用于動(dòng)態(tài)集合。動(dòng)態(tài)集合的特點(diǎn)是集合結(jié)構(gòu)本身在查找過程中動(dòng)態(tài)生成，即對(duì)于給定值k，若集合中存在關(guān)鍵字等于k的記錄，則查找成功，否則插入關(guān)鍵字為k的新記錄。Ø 二叉排序樹，又叫二叉

5、查找樹或二叉搜索樹。它或者是一棵空樹，或者是一棵具有如下特征的非空二叉樹：Ø 1）若它的左子樹非空，則左子樹上所有節(jié)點(diǎn)的關(guān)鍵字均小于根節(jié)點(diǎn)的關(guān)鍵字。Ø 2）若它的右子樹非空，則右子樹上所有節(jié)點(diǎn)的關(guān)鍵字均大于根節(jié)點(diǎn)的關(guān)鍵字。Ø 3）左、右子樹也分別是二叉排序樹。Ø 平衡二叉樹的定義是：若一棵二叉排序樹中每個(gè)節(jié)點(diǎn)的左、右子樹的高度之差的絕對(duì)值不超過1，則稱這樣的二叉排序樹為平衡二叉樹。Ø 算法設(shè)計(jì)思路簡(jiǎn)介Ø 1、Ø 數(shù)據(jù)有序，用折半查找法，通過即可快速找到關(guān)鍵字。Ø 2、Ø 二叉樹表實(shí)際上就是個(gè)二叉樹，就像建

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

7、、開始輸入ai,keyi = 1,2,3,nlow = 1,high = nmid = (low+high)/2mid = key? = high = mid-1k < amid? 是 否low = mid+1 low <= high? 是 否return midreturn -1輸出mid輸出-1結(jié)束2、(1)創(chuàng)建普通二叉樹節(jié)點(diǎn)。(2)輸入要插入的值k。(3)將k插入二叉樹節(jié)點(diǎn)中，若當(dāng)前節(jié)點(diǎn)為空則申請(qǐng)節(jié)點(diǎn)空間并將k存入當(dāng)前節(jié)點(diǎn)的data域中，令其左右子樹均為空;若當(dāng)前節(jié)點(diǎn)不為空且k小于當(dāng)前節(jié)點(diǎn)的data值，則將k存入當(dāng)前節(jié)點(diǎn)的左子樹中去，若當(dāng)前節(jié)點(diǎn)不為空且k大于當(dāng)前節(jié)點(diǎn)的data

8、值，則將k存入當(dāng)前節(jié)點(diǎn)的右子樹中去。 (4)中序遍歷此二叉樹。3、Ø (1)錄入人名。Ø (2)以人名的第二個(gè)字母的ASCLL碼模49（所用數(shù)組空間為50），得到的數(shù)作為下標(biāo)，將此人名存入相應(yīng)的鄰接表中。Ø (3)輸入待查人名。Ø (4)以人名的第二個(gè)字母的ASCLL碼模49得到的數(shù)字為下標(biāo)找到相應(yīng)的鏈表，若鏈表為空則表明待查人名不在名單中，輸出0；若不為空，則與鏈表中的每一個(gè)名字做比較，入股在下標(biāo)對(duì)應(yīng)的整個(gè)鏈表中都找不到此名字則說明待查人名不在名單中，輸出0，否則表明待查人名在名單中，輸出1。4、(1)輸入單詞列表并存入字典中。(2)輸入待查單詞。(3

9、)將待查單詞和字典中的每個(gè)單詞做比較。(3)計(jì)算字典中單詞列表中每個(gè)單詞的長(zhǎng)度和待查單詞的長(zhǎng)度。分三種情況： 若字典中單詞的長(zhǎng)度等于待查單詞的長(zhǎng)度，將字典中單詞的每個(gè)字母和待查單詞的每個(gè)字母做比較，若相同的字母數(shù)和單詞長(zhǎng)度相同則說明兩單詞完全相同，若或比人名長(zhǎng)度少一則說明兩單詞只有一個(gè)字母不同屬于替換一個(gè)字母就相同的情況。兩種情況均打印1.若字典中的單詞長(zhǎng)度等于待查單詞長(zhǎng)度減一，將字典中單詞的每個(gè)字母和待查單詞的每個(gè)字母作比較，若相同字母數(shù)為字典中單詞的長(zhǎng)度，則說明待查單詞與字典中的單詞相似，只是多了一個(gè)字母，打印1.若字典中單詞長(zhǎng)度等于待查單詞長(zhǎng)度加一，將字典中的每個(gè)字母和待查單詞的每個(gè)字母

10、作比較，若相同字母數(shù)為字典中單詞長(zhǎng)度減一，則說明待查單詞與字典中的單詞相似，只是少了一個(gè)字母，打印1.其余情況均不相似，打印0.Ø 算法的實(shí)現(xiàn)和測(cè)試結(jié)果：包括算法運(yùn)行時(shí)的輸入、輸出，實(shí)驗(yàn)中出現(xiàn)的問題及解決辦法等Ø 1、ØØØ 2、ØØØ 3、ØØ 4、ØØ 算法時(shí)間復(fù)雜度分析Ø 1、Ø O(log2n).Ø 2、Ø 最差情況（單枝樹）O(n)Ø 一般情況O(log2n)Ø 3、Ø O(1)Ø 4、

11、Ø O(mn)Ø m:字典中的單詞數(shù)Ø n:待查單詞數(shù)四、收獲與體會(huì)之前只知道查找這回事，以為以現(xiàn)在計(jì)算機(jī)的性能查找已經(jīng)變得很方便了。跟戴老師學(xué)習(xí)了查找之后才發(fā)現(xiàn)大數(shù)據(jù)的可怕，無論多少條記錄我們都希望在幾秒內(nèi)完成。那么在短時(shí)間內(nèi)計(jì)算機(jī)性能無法大幅度提高的前提下就要考慮查找的算法了(其實(shí)就算計(jì)算機(jī)性能再好，優(yōu)化算法也能提高查找效率)。順序查找肯定是不學(xué)都會(huì)，折半查找之前也聽說過，如何讓查找表變得有序也是讓人頭疼的事。就說這個(gè)散列查找，竟然能達(dá)到O(1)階的查找效率，真讓人感嘆人類的智慧了。做完了圖那章的實(shí)驗(yàn)，感覺這次實(shí)驗(yàn)簡(jiǎn)單多了。數(shù)據(jù)結(jié)構(gòu)真的是越來越有趣了，慢慢感受

12、到了編程的魅力。五、源代碼清單 1、#include<iostream>using namespace std;int binarysearch(int array,int Key,int N)int low = 1;int high = N;int mid;while(low <= high)mid = (low+high)/2;/cout << "mid:" << mid << endl;if(arraymid = Key) return mid;else if(Key < arraymid)high = mi

13、d-1;else low = mid+1;return -1;int main()int a20 = 0;int n,key,result;cin >> n;cin >> key;for(int i = 1;i <=n;i+)cin >> ai;result = binarysearch(a,key,n);cout << result;return 0;2、#include<iostream>using namespace std;int count = 0;int N = 0;typedef struct BitNodeint

14、 data;struct BitNode *lchild,*rchild;BitNode,*BitTree;void insert(BitTree &T,int k)if(T = NULL)T = (BitNode*)malloc(sizeof(BitNode);T->data = k;T->lchild = T->rchild = NULL;else if(k < T->data) insert(T->lchild,k);else if(k > T->data) insert(T->rchild,k);else if(k = T-

15、>data) insert(T->lchild,k);void InOrder(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 << " "InO

16、rder(T->rchild);int main()BitNode *root;root = NULL;int a20 = 0;for(int j = 0;j < 20;j+)cin >> aj;N+;if(aj = -1)N-;break;int i = 0;while(ai != -1)insert(root,ai);i+;/cout << "haha" << endl;InOrder(root);count = 0;N = 0;return 0;3、#include<iostream>#include<

17、cstring>using namespace std;typedef struct Hashchar data50;struct Hash *next;Hash;typedef structint data;struct Hash *next;FirstHash30;int main()int n,q;int counts;cin >> n;cin >> q;char name5050;char checkname5050;FirstHash *h;h = (FirstHash*)malloc(sizeof(FirstHash50);for(int i = 0;

18、i < 50;i+)hi->data = i;hi->next = NULL;for(int i = 0;i < n;i+)cin >> namei;/cout << "namei1 = " << namei1 << endl;counts = (int)namei1 % 49;/cout << "counts = " << counts << endl;Hash *hash = (Hash*)malloc(sizeof(Hash);strcpy(

19、hash->data,namei);/cout << "hash->data:" << hash->data << endl;hash->next = hcounts->next;hcounts->next = hash;/以°?上¦?程¨¬序¨°沒?問¨º題¬afor(int i = 0;i < q;i+)cin >>checknamei;for(int i = 0;i < q;i+)co

20、unts = (int)checknamei1 % 49;if(hcounts->next = NULL)cout << 0 << endl;elseHash *temp = hcounts->next;while(temp!= NULL && strcmp(temp->data,checknamei) != 0)temp = temp->next;if(temp = NULL)cout << 0 << endl;elsecout << 1 << endl;return 0;4、#i

21、nclude<iostream>using namespace std;char Dic5050;char Check5050;int getLength(char array)/得到單詞的長(zhǎng)度 int i = 0;while(arrayi != '0')i+;return i;int research(char array1,char array2)/字典,待查詞匯 ，字典中的某個(gè)單詞與某個(gè)待查單詞是否相似 int count1 = 0;int count2 = 0;int simble = 0;count1 = getLength(array1);count2

22、= getLength(array2);/cout << "count1 = " << count1 << endl;/cout << "count2 = " << count2 << endl;if(count1 = count2)/單詞長(zhǎng)度相等，替換任一字母 simble = 0;int i = 0;while(i < count1)if(array1i = array2i)simble+;i+;if(simble >= count1-1)return 1;elsereturn 0;else if(count1 = count2-1)/比字典長(zhǎng)度長(zhǎng)1 simble = 0;int i = 0,j = 0;while(j