




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認(rèn)領(lǐng)
文檔簡介
1、實驗報告學(xué)院(系)名稱:計算機與通信工程學(xué)院姓名* *學(xué)號* *專業(yè)計算機科學(xué)與技術(shù)班級2015級*班實驗項目實驗五: 查找算法應(yīng)用 課程名稱數(shù)據(jù)結(jié)構(gòu)與算法課程代碼0661013實驗時間年 月 日第節(jié)實驗地點7-*考核標(biāo)準(zhǔn)實驗過程25分程序運行20分回答問題15分實驗報告30分特色功能5分考勤違紀(jì)情況5分成績成績欄其它批改意見: 教師簽字:考核內(nèi)容評價在實驗課堂中的表現(xiàn),包括實驗態(tài)度、編寫程序過程等內(nèi)容等。功能完善, 功能不全有小錯無法運行正確基本正確有提示無法回答完整較完整一般內(nèi)容極少無報告有無有無 一、實驗?zāi)康膶嶒災(zāi)康模豪斫舛媾判驑洹VL 樹的查找、插入、刪除、建立算法的思想及程序?qū)崿F(xiàn)
2、;掌握散列存儲結(jié)構(gòu)的思想,能選擇合適散列函數(shù),實現(xiàn)不同沖突處理方法的散列表的查找、建立。能運用所學(xué)查找結(jié)構(gòu)與算法等解決實際問題。二、實驗題目與要求1.折半查找算法 1)問題描述:從鍵盤讀入一串整數(shù)和一個待查關(guān)鍵字,查找在該整數(shù)串中是否有這個待查關(guān)鍵 字。如果有,輸出它在整數(shù)串中的位置;如果沒有,輸出-1 2)實驗要求: 利用折半查找算法查找 用遞歸和非遞歸兩種方式實現(xiàn)折半查找算法 3) 實現(xiàn)提示: 遞歸實現(xiàn)參考書上折半查找算法的實現(xiàn) 非遞歸算法利用棧實現(xiàn) 2.構(gòu)造二叉排序樹,并進行中序遍歷(實驗類型:綜合型) 1)問題描述:從鍵盤讀入一串整數(shù)構(gòu)造一棵二叉排序樹,并對得到的二叉排序樹進行中序遍歷
3、, 得到有序序列。 2)實驗要求:該二叉排序樹以二叉鏈表存儲 3)實現(xiàn)提示:二叉排序樹的構(gòu)成,可從空的二叉樹開始,每輸入一個結(jié)點數(shù)據(jù),就建立一個新 結(jié)點插入到當(dāng)前已生成的二叉排序樹中,所以它的主要操作是二叉排序樹插入運算。在二叉排序樹 中插入新結(jié)點,只要保證插入后仍符合二叉排序樹的定義即可。 3哈希表查找 1)問題描述:針對某個集體的“人名”構(gòu)造哈希表,解決按“人名”進行查找的索引結(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)若它的左子樹非空,則左子樹上所有節(jié)點的關(guān)鍵字均小于根節(jié)點的關(guān)鍵字。Ø 2)若它的右子樹非空,則右子樹上所有節(jié)點的關(guān)鍵字均大于根節(jié)點的關(guān)鍵字。Ø 3)左、右子樹也分別是二叉排序樹。Ø 平衡二叉樹的定義是:若一棵二叉排序樹中每個節(jié)點的左、右子樹的高度之差的絕對值不超過1,則稱這樣的二叉排序樹為平衡二叉樹。Ø 算法設(shè)計思路簡介Ø 1、Ø 數(shù)據(jù)有序,用折半查找法,通過即可快速找到關(guān)鍵字。Ø 2、Ø 二叉樹表實際上就是個二叉樹,就像建
6、立一個普通的二叉樹一樣建立樹,只是在插入節(jié)點的時候要和當(dāng)前節(jié)點的值比較,若當(dāng)前節(jié)點為空則插入當(dāng)前節(jié)點;否則,若小于當(dāng)前值則插入左子樹大于當(dāng)前節(jié)點就插入右子樹。對建立好的樹進行中序遍歷即可得到有序序列。Ø 3、Ø 人的姓一般有很大可能性相同,但是人名的第二個字一般是不同的,既然人名示例是拼音形式姑且認(rèn)為第二個字母即為第二個字。將其ASCLL碼模49作為哈希函數(shù),將各人名分類存在不同的鏈表中,提高查詢效率。Ø 算法描述:可以用自然語言、偽代碼或流程圖等方式4、以單詞中字母的數(shù)目為標(biāo)準(zhǔn)將單詞分類,若字母數(shù)想等或相差一則進行細致的比較(下面有詳細描述),否則根本不相似。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é)點。(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
8、值,則將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
9、)將待查單詞和字典中的每個單詞做比較。(3)計算字典中單詞列表中每個單詞的長度和待查單詞的長度。分三種情況: 若字典中單詞的長度等于待查單詞的長度,將字典中單詞的每個字母和待查單詞的每個字母做比較,若相同的字母數(shù)和單詞長度相同則說明兩單詞完全相同,若或比人名長度少一則說明兩單詞只有一個字母不同屬于替換一個字母就相同的情況。兩種情況均打印1.若字典中的單詞長度等于待查單詞長度減一,將字典中單詞的每個字母和待查單詞的每個字母作比較,若相同字母數(shù)為字典中單詞的長度,則說明待查單詞與字典中的單詞相似,只是多了一個字母,打印1.若字典中單詞長度等于待查單詞長度加一,將字典中的每個字母和待查單詞的每個字母
10、作比較,若相同字母數(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、
11、Ø O(mn)Ø m:字典中的單詞數(shù)Ø n:待查單詞數(shù)四、收獲與體會之前只知道查找這回事,以為以現(xiàn)在計算機的性能查找已經(jīng)變得很方便了。跟戴老師學(xué)習(xí)了查找之后才發(fā)現(xiàn)大數(shù)據(jù)的可怕,無論多少條記錄我們都希望在幾秒內(nèi)完成。那么在短時間內(nèi)計算機性能無法大幅度提高的前提下就要考慮查找的算法了(其實就算計算機性能再好,優(yōu)化算法也能提高查找效率)。順序查找肯定是不學(xué)都會,折半查找之前也聽說過,如何讓查找表變得有序也是讓人頭疼的事。就說這個散列查找,竟然能達到O(1)階的查找效率,真讓人感嘆人類的智慧了。做完了圖那章的實驗,感覺這次實驗簡單多了。數(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)/得到單詞的長度 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
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 2025光伏發(fā)電系統(tǒng)采購合同
- 2025混凝土工程施工合同范本
- 2025節(jié)能服務(wù)合同模板
- 2025高空建筑外墻清潔保養(yǎng)合同
- 2025授權(quán)印刷合同范本
- 2025冰箱銷售正規(guī)合同范本
- 2025存量房屋租賃合同范本
- 2025維修倉庫租賃合同范本
- 2025合同意向書合同意向書的法律效力
- 2025辦公室裝修水電施工合同范本 辦公室水電施工合同格式
- GB/T 4008-2024錳硅合金
- 中國肺血栓栓塞診治與預(yù)防指南解讀專家講座
- 2024急性腦梗死溶栓規(guī)范診治指南(附缺血性腦卒中急診急救專家共識總結(jié)歸納表格)
- 《鴻門宴》公開課一等獎創(chuàng)新教學(xué)設(shè)計 統(tǒng)編版高中語文必修下冊
- DZ∕T 0202-2020 礦產(chǎn)地質(zhì)勘查規(guī)范 鋁土礦(正式版)
- 二年級三位數(shù)加減法豎式計算
- 安全生產(chǎn)投入臺賬(模板)
- 清華大學(xué)領(lǐng)軍計劃語文試題強基計劃
- 醫(yī)療欠款欠條范本
- 母親節(jié)健康科普知識
- 《奧爾夫音樂教學(xué)法》課程標(biāo)準(zhǔn)
評論
0/150
提交評論