1、實驗報告學院（系）名稱：計算機與通信工程學院姓名* *學號* *專業計算機科學與技術班級2015級*班實驗項目實驗五： 查找算法應用 課程名稱數據結構與算法課程代碼0661013實驗時間年 月 日第節實驗地點7-*考核標準實驗過程25分程序運行20分回答問題15分實驗報告30分特色功能5分考勤違紀情況5分成績成績欄其它批改意見: 教師簽字：考核內容評價在實驗課堂中的表現，包括實驗態度、編寫程序過程等內容等。功能完善, 功能不全有小錯無法運行正確基本正確有提示無法回答完整較完整一般內容極少無報告有無有無 一、實驗目的實驗目的：理解二叉排序樹、AVL 樹的查找、插入、刪除、建立算法的思想及程序實現

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

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

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

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

6、立一個普通的二叉樹一樣建立樹，只是在插入節點的時候要和當前節點的值比較，若當前節點為空則插入當前節點；否則，若小于當前值則插入左子樹大于當前節點就插入右子樹。對建立好的樹進行中序遍歷即可得到有序序列。Ø 3、Ø 人的姓一般有很大可能性相同，但是人名的第二個字一般是不同的，既然人名示例是拼音形式姑且認為第二個字母即為第二個字。將其ASCLL碼模49作為哈希函數，將各人名分類存在不同的鏈表中，提高查詢效率。Ø 算法描述：可以用自然語言、偽代碼或流程圖等方式4、以單詞中字母的數目為標準將單詞分類，若字母數想等或相差一則進行細致的比較（下面有詳細描述），否則根本不相似。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結束2、(1)創建普通二叉樹節點。(2)輸入要插入的值k。(3)將k插入二叉樹節點中，若當前節點為空則申請節點空間并將k存入當前節點的data域中，令其左右子樹均為空;若當前節點不為空且k小于當前節點的data值，則將k存入當前節點的左子樹中去，若當前節點不為空且k大于當前節點的data

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

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

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

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

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)/得到單詞的長度 int i = 0;while(arrayi != '0')i+;return i;int research(char array1,char array2)/字典,待查詞匯 ，字典中的某個單詞與某個待查單詞是否相似 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)/單詞長度相等，替換任一字母 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)/比字典長度長1 simble = 0;int i = 0,j = 0;while(j