實驗五： 查找算法應(yīng)用.doc

《實驗五： 查找算法應(yīng)用.doc》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

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

2、除、建立算法的思想及程序?qū)崿F(xiàn)；掌握散列存儲結(jié)構(gòu)的思想，能選擇合適散列函數(shù)，實現(xià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)造二叉排序樹，并進行中序遍歷（實驗類型：綜合型）1）問題描述：從鍵盤讀入一串整數(shù)構(gòu)造一棵二叉排序樹，并對得到的

3、二叉排序樹進行中序遍歷，得到有序序列。2）實驗要求：該二叉排序樹以二叉鏈表存儲3）實現(xiàn)提示：二叉排序樹的構(gòu)成，可從空的二叉樹開始，每輸入一個結(jié)點數(shù)據(jù)，就建立一個新結(jié)點插入到當前已生成的二叉排序樹中，所以它的主要操作是二叉排序樹插入運算。在二叉排序樹中插入新結(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)包括如下主要容：?數(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、?二叉樹表實際上就是個二叉樹，就像建立一個普通的二叉樹一樣建立樹，只是在插入節(jié)點的時候要和當前節(jié)點的值比較，若當前節(jié)點為空則插入當前節(jié)點；否則，若小于當前值則插入左子樹大于當前節(jié)點就插入右子樹。對建

6、立好的樹進行中序遍歷即可得到有序序列。?3、?人的姓一般有很大可能性相同，但是人名的第二個字一般是不同的，既然人名示例是拼音形式姑且認為第二個字母即為第二個字。將其ASCLL碼模49作為哈希函數(shù)，將各人名分類存在不同的鏈表中，提高查詢效率。?算法描述：可以用自然語言、偽代碼或流程圖等方式4、以單詞中字母的數(shù)目為標準將單詞分類，若字母數(shù)想等或相差一則進行細致的比較（下面有詳細描述），否則根本不相似。1、開始輸入a[i],keyi=1,2,3,…,nlow=1,high=nmid=(low+high)/2mid=key?=≠high=mid-1k

7、<=high?是否returnmidreturn-1輸出mid輸出-1結(jié)束2、(1)創(chuàng)建普通二叉樹節(jié)點。(2)輸入要插入的值k。(3)將k插入二叉樹節(jié)點中，若當前節(jié)點為空則申請節(jié)點空間并將k存入當前節(jié)點的data域中，令其左右子樹均為空;若當前節(jié)點不為空且k小于當前節(jié)點的data值，則將k存入當前節(jié)點的左子樹中去，若當前節(jié)點不為空且k大于當前節(jié)點的data值，則將k存入當前節(jié)點的右子樹中去。(4)中序遍歷此二叉樹。3、?(1)錄入人名。?(2)