課程設計--《哈希表的操作》設計報告

上傳人：奔*** IP屬地：河北更新時間：2024-03-01 格式：doc 頁數：15 大?。?88.00KB 人氣指數：12 舉報 版權申訴

已閱讀1頁，還剩14頁未讀，繼續(xù)免費閱讀

版權說明：本文檔由用戶提供并上傳，收益歸屬內容提供方，若內容存在侵權，請進行舉報或認領

文檔簡介

1、　　《哈希表的操作》設計報告　　一目的　　通過此次課程設計，讓學生充分掌握對哈希表的有關操作，例如除留余數法的運用，處理沖突的三個辦法：線性探測再散列，二次探測再散列，連地址法等。加深學生對于哈希表這種獨特存儲方式（區(qū)別于線性存儲和鏈式存儲）的理解，和幾種算法之間的優(yōu)越性的體會。 </p&

2、gt;　　二需求分析　　1、功能需求　?、伲脩裟軌蜃远x輸入單詞，存入哈希表里；　　②．用戶能夠對當前哈希表進行管理。操作內容包括：查看當前哈希表、搜索某個單詞、插入任意單詞、刪除表中某個單詞、查看當前表的平均

3、搜索長度、置空當前哈希表。　　③．程序有良好的交互界面，有操作提示和出錯提示，方便用戶使用和進出入程序。　　2、程序約束　?、伲１淼纳⒘蟹椒槌粲鄶捣?，處理沖突的辦法為線性探測在散列。　?、冢褂肅/C++語言編寫，程序模塊化設

4、計。　　三概要設計　　1、模塊設計　　程序分為主程序模塊和哈希表類定義模塊，主程序存放在main.app中，哈希表類存放在HashTable.h頭文件中。　　①．主程序模塊&

5、lt;/b>　　用于數據和DOS用戶界面的初始化，主函數mai()內部定義子函數function()，調用哈希表類中的各個功能函數。　?、冢１眍惗x　　Calculate(string s) 單詞key值計算函數，類友元<

6、;/p>　　形參s傳送輸入的單詞。由于單詞為string型，不方便直接拿來參與取余數計算，故用計算函數求出一個key來，同時可以減少沖突（字母相同的單詞key有可能不同）。　　FindPos(int key,string value) 地址查找函數，類成員　　key傳送計算出的單詞的關鍵值，value傳送輸入的單詞，下同

7、。此函數為查找、插入、刪除等函數提供地址搜索服務。　　Search(int key,string value) 查找函數，類成員　　Insert(string value) 插入函數，類成員　　Remove(int key,string value) 刪除函數

8、，類成員　　makeEmpty() 置空哈希表函數，類成員　　getInfo(int address) 獲取某個地址中元素的信息，類成員　　形參address是哈希表中某元素的地址（數組下標），通過key % divitor

9、得到　　getSize(HashTable HT) 獲取哈希表存儲情況，類友員　　ASL(HashTable HT) 平均查找長度計算函數，類友元　　四詳細設計<b&g

10、t;　　1、主要功能實現(xiàn)　?、伲侄x：#define DefaultSize 30 數組最大容量　　divitor 取余除數，設為29（≤30的最大質數）　?、冢畣卧~key計算：</p

11、>　　int Calculate(string s){　　//key計算函數：word前5個字符的ASCII碼 + 單詞長度　　//不足5個字符的word，用所有字符的ASCII碼 + 單詞長度　　int k=0,len; 　　len=s.le

12、ngth();　　if(len<5){　　for(unsigned int i=0;i<s.length();i++) k+=(int)s[i]; }　　else{　　for(int i=0;i<=4;i++) k+

13、=(int)s[i]; }　　k+=len;　　return k;　　} 　?、郏刂凡檎遥?lt;/b>&l

14、t;p>　　int HashTable::FindPos(int key,string value) const{ 　　//搜索一個散列表中關鍵碼與key匹配的元素，搜索成功，則函數返回改元素的位置　　//否則返回插入點（如果有足夠空間的話）　　int address= key % divit

15、or;　　int j = address;　　do{　　if(info[j]==Empty || (info[j]==Active && ht[j]==value)){ t1++;return j;} //找到

16、　else { j=(j+1) % TableSize; t1++; } //當做循環(huán)表處理，找出下一個空地址　　}while (j != address); 　　return j; //轉一圈回到起點，表已

17、滿，失敗　　} //t1在這個函數體里面增加的量△t1為某一元素探查的次數　　④．搜索、插入、刪除函數相同結構：　　Type Name(type1 paramater1, type2 paramater2){　　//調用FindPos（type1 paramater1,

18、type2 paramater2）　　//檢查FindPos返回值，并對此作出相應判斷　　//根據以上內容作出處理　　//返回　　}

19、⑤．ASL設計：　　第一步：設立全局變量t1,t2，分別代表成功和不成功的ASL公式的分子。　　第二步：在FindPos處設立一個監(jiān)聽變量t，每次查找t自加1，直到查找到合適地址。t的增量△t就是這個元素的查找次數。　　第三步：在Insert處用t監(jiān)聽，插入成功t不變，失敗則t自減1。<

20、/p>　　第四步：在Remove處用t監(jiān)聽，首先將t賦值給一個中間變量temp，經過FindPos地址查找后，t的增量△t=t-temp。刪除這個元素，意味著這個元素的t要減去這元素的查找次數，即t-2*(t-temp)。　　ASLsucc = t1 / 輸入單詞的個數（或已用地址的數量）　　ASLunsucc = t2 /

21、表長， t2的計算如下：　　2、流程圖　　五調試分析　　1、本次課程設計采用的是除留余數法構造了哈希表，除數的選擇很重要。如果選得不好，會造成很多沖突，浪費時間和空間代價。例如，本次設計的哈希表最大長度為30，余數如果取得較小，例

22、如23,17等，相比起最接近30的29來說，會使得一部分元素容易形成堆積，平均搜索長度變大，而且取余的時間也會更長。　　2、本次設計處理沖突采用了線性探測再散列的辦法。相比起同時閉散列方法的二次探測再散列來說，優(yōu)點在于功能簡單易操作性；缺點是當數據量逐漸加大時，前者的平均查找長度會逐漸比后者大。　　3、做為閉散列方法處理沖突問題，不能像連地址法那樣的開放

23、地址法一樣，隨意的用物理刪除方法刪除表里的元素。否則容易引起搜索鏈的中斷，使得該元素后面發(fā)生沖突的元素無法查找到，造成程序和實際情況有誤。　　4、在概要設計的階段發(fā)現(xiàn)，無論是搜索、插入還是刪除，首先都要對元素進行尋址操作，因此獨立設立一個尋址函數FindPos，供以上三個函數共用，以減少代碼的重復。　　六測試結果

24、　　1.單詞輸入　　2.表內存儲情況　　3.輸入完畢立即測試ASL的情況　　4查找測試　　5. 插

25、入刪除測試　　測試結果：沒有發(fā)現(xiàn)錯誤。　　七用戶使用說明　　1、功能使用說明　?、伲檎n表：查看當前哈希表的存儲情況　?、冢阉鳎?/p>

26、輸入一個單詞，查詢表內的情況。不支持key查詢，因為相同的key可能有不同的單詞對應，例如”pa”和”le”，key都是211。　?、郏迦耄狠斎雴卧~，插入到哈希表中。插入后會立即顯示插入元素的情況。　?、埽畡h除：輸入單詞，在表中搜索，如果存在則刪除，不存在則提示不存在或者已刪除。不支持輸入key進行刪除，原因同②。暫時不支持直接輸入地址進行刪除。<

27、;/p>　　⑤．顯示ASL：查看當前表中的ASL值。　　⑥．置空表：將當前表初始化為一張空表。　　2、注意事項　　本次設計重點在對哈希表的處理上，沒有對選擇界面進行很有效的出錯處理，請勿在輸入數字時輸入其他字符，以免出現(xiàn)死循環(huán)等錯誤。</p&

28、gt;　　八課程設計總結　　1、目的達成百分比　　通過此次的課程設計，我已經基本了解并掌握了哈希表的基本操作方法，對常用的散列方法（如：除留余數法）、處理沖突的方法（如：線性探測和二次探測）有了更深的認識和體會，對開散列法（鏈地址法）也有了進一步的了解。

29、此次課程設計目的達成的百分比我給自己評定在75%~85%。　　2、心得體會　?、伲敬蔚恼n程設計并不是很難，都是課上所講解過的基本內容。容易出錯的地方應該是一些細節(jié)方面。比如ASL的計算，機器并沒有人腦那么靈活，會過濾掉插入和刪除所帶來的影響，所以在插入或者刪除時要特別注意ASL值得變化，防止結果有誤。</p&

30、gt;　?、冢敬握n程設計可以用動態(tài)數組來代替目前的靜態(tài)數組，達到更實用的效果。還可以將現(xiàn)在的類寫成模板類形式，為以后各種元素類型的哈希表提供類模板。　　附件：　　1、源代碼　　①．頭文件hashtable.h<

31、;/p>　　#include <iostream>　　using namespace std;　　#define Active 1　　#define Empty 0　　#define Deleted -1&l

32、t;p>　　const int DefaultSize = 30;　　//enum KindOfStatus {Active ,Empty ,Deleted};　　int t1,t2; //t1:每個已有元素的探查次數的總和 t2:每個新元素查找可用地址的次數總和（t/time）　　class H

33、ashTable{　　public:　　HashTable(const int d,int sz=DefaultSize); //構造函數聲明　　bool Search(int key,string value); //搜索<

34、/p>　　int Insert(string value); //插入　　bool Remove(int key,string value); //刪除　　void makeEmpty();

35、 //置空　　void getInfo(int address); //一開始是用的友元的，但是不知道為什么訪問Private總是報錯　　friend int Calculate(string s); //計算每個單詞的key值

36、　　friend void getSize(HashTable HT); //獲取當前深度和最大深度　　friend void ASL(HashTable HT);　　private: 　　int divitor;

37、 //哈希表的除數　　int CurrentSize,TableSize; //當前深度以及表的容量　　string ht[DefaultSize]; //哈希表存儲數組<p

38、>　　int info[DefaultSize]; //狀態(tài)數組　　int FindPos(int key,string value) const; //散列函數：計算初始的散列地址　　};　　Ha

39、shTable::HashTable(int d, int sz){ //構造函數　　divitor = d;　　TableSize = sz; CurrentSize = 0;　　//ht = new string [TableSize];

40、 //開辟散列數組空間　　//info = new KindOfStatus[TableSize]; //開辟標志數組空間，標志是每個元素的屬性（Active,Empty,Delected）　　for(int i=0;i<TableSize;i++) {　　ht[i] = '

41、 '; info[i] = Empty; }　　}　　/**使用線性探測法搜索 **/　　int HashTable::FindPos(int key,string value) const{ 　　//搜索一個散

42、列表中關鍵碼與key匹配的元素，搜索成功，則函數返回改元素的位置　　//否則返回插入點（如果有足夠空間的話）　　int address= key % divitor;　　int j = address;　　do{

43、　　if(info[j]==Empty||info[j]==Deleted||(info[j]==Active&&ht[j]==value)){t1++;return j;} //找到　　else { j=(j+1) % TableSize; t1++; } //當做循環(huán)表處

44、理，找出下一個空地址　　}while (j != address); 　　return j; //轉一圈回到起點，表已滿，失敗　　} //t1在這個函數體里面增加的量δt1為

45、某一元素探查的次數　　bool HashTable::Search(int key,string value){　　//使用線性探測在哈希表ht（每個地址容納一個元素）中搜索word。如果word在表中存在，　　//則函數返回true，并用引用參數value返回找到的元素；如果word不在表中，則返回false。

46、　　int temp=t1;　　int i = FindPos(key,value);　　if(value == ht[i]) {cout<<"此單詞在 "<<i<<" 位置";t1=temp;return true;}

47、;　　else {t1=temp;return false;}　　}　　int Calculate(string s){　　//key計算函數：word前5個字符的ASCII碼 + 單詞長度　　//不足5個字符的

48、word，用所有字符的ASCII碼 + 單詞長度　　int k=0,len; 　　len=s.length();　　if(len<5){　　for(unsigned int i=0;i<s.length();i++) k+=(int)s[i]; }</p

49、>　　else{　　for(int i=0;i<=4;i++) k+=(int)s[i]; }　　k+=len;　　return k;<

50、p>　　}　　int HashTable::Insert(string value){　　//在ht表中搜索value。若找到則不再插入；若未找到，但表已滿，也不再插入，并返回false。　　//若找到的位置標志是Empty或Deleted,不論是表是否已滿都插入，返回

51、true。　　int key = Calculate(value); //計算函數：抽取關鍵碼　　int i = FindPos(key,value); //地址計算　　int flag=0;<p

52、>　　do{　　if(info[i] != Active){ //該地址未被存放，存放新元素　　ht[i] = value; info[i] = Active;　　getInfo(i);<p&g

53、t;　　CurrentSize++; 　　flag = 1; break; }　　if(info[i] == Active && ht[i] == value)　　{ cout<<"表中已有此元素，不用在插入！"<<endl; flag = -1;t1-

54、-;break;}　　if(info[i] == Active && ht[i] !=value) i++;　　}while(i<TableSize);　　if(i>=TableSize) { cout<<"表已滿，不能插入！"<<endl

55、; t1--;}　　return flag;　　}　　bool HashTable::Remove(int key ,string value){　　//在ht表中刪除元素word,若表中找不到word,或雖然找到word，但它已經邏

56、輯刪除過　　//則返回false，否則在表中刪除元素word,返回true，并在引用參數value中得到它　　int temp=t1;　　int i = FindPos(key,value);　　if(info[i] == Active && ht[i]

57、== value){ //找到要刪元素，且是活動元素　　info[i] = Deleted; CurrentSize--; //做刪除標志，并不是真正的物理刪除　　cout<<"元素已被刪除"<<endl;　　getInfo(i

58、);　　t1=t1-2*(t1-temp); //t1-temp為這個元素的探查次數（δt1）　　return true; //刪除成功　　}</p&

59、gt;　　else { cout<<"找不到這個元素或者這個元素已經被刪除過。"<<endl;t1=temp;return false; } //刪除失敗,t1不變　　}　　void HashTable::makeEmpty(){

60、　　for(int i=0;i<TableSize;i++) { ht[i] = " ";info[i] = Empty;}　　CurrentSize = 0;　　t1=0;　　cout<<"散列表已被置空

61、"<<endl;　　}　　void getSize(HashTable HT){　　if(HT.CurrentSize>=0 && HT.TableSize>=0){　　cout<

62、;<"CurrentSize: "<<HT.CurrentSize<<endl;　　cout<<"TableSize: "<<HT.TableSize<<endl;　　}

63、　　}　　void HashTable::getInfo(int a){　　cout<<"HT["<<a<<"]= "; 　　cout<<" "<<ht[a

64、]<<"\t"; //HT[a]=value　　if(info[a] == Empty)　　cout<<"Empty"<<endl;　　if(info[a] == Active){<

65、;/p>　　cout<<"Active"<<" ";　　cout<<"key: "<<Calculate(ht[a])<<endl;}　　if(info[a] == Deleted)

66、　　cout<<"Deleted"<<endl;　　}　　void ASL(HashTable HT){　　int i=0,j=0;　　t2=0;

67、 //重置t2　　do{ i=j; //外層循環(huán)控制數組的下標　　do{　　if(HT.info[i] != Active) {t2

68、++;break;} //沒有活動的元素，表明可以插入，使用了一次查找次數，t+1　　else {t2++;i++;} } //找不到空地址，t自加　　while(i<HT.TableSize); j++ ;} //內存循環(huán)結束，j自加，進行下一個元素的計算<

69、/p>　　while(j<HT.TableSize); 　　cout<<"ASLsucc:"<<t1<<"/"<<HT.CurrentSize<<"\t";</p

70、>　　cout<<"ASLunsucc:"<<t2<<"/"<<HT.TableSize<<endl; //最后t的值是所有元素查找不成功次數的總和　　}　　②．主程序hash_main.

71、cpp　　#include <string>　　#include "HashTable.h"　　HashTable HT(29,DefaultSize); // 此處還可以用try...catch語句來捕捉初始化時產生的未知錯誤<

72、p>　　string word; // 輸入的單詞　　void function(){　　cout<<"接下來你想要做什么？"<<endl;　　cout<<"1、查看表 2、搜索 3

73、、插入 4、刪除 5、顯示ASL 6、置空當前表其他：退出"<<endl;　　int c;　　cin>>c;　　switch(c){　　case 1: for

74、(int i=0;i<DefaultSize;i++) HT.getInfo(i);break;　　case 2: cout<<"請輸入你要查找的單詞:\t"; cin>>word;　　if(HT.Search(Calculate(word),word)==true)<p&g

75、t;　　cout<<endl;　　else cout<<"表中沒有這個單詞."<<endl;　　break;　　case 3: cout<<"請輸入您要插入的單詞:\t"; cin>

76、>word;　　HT.Insert(word); break;　　case 4: cout<<"請輸入你想要刪除的單詞:\t"; cin>>word;　　HT.Remove(Calculate(word),word);break; <

77、p>　　case 5: ASL(HT);break;　　case 6: HT.makeEmpty();break;　　default: exit(0); }　　}　　void main()

78、;　　{　　cout<<"哈希表數組初始化完畢！"<<endl;　　int i=0,j=0;　　for(int i=0;i<DefaultSize;i++) HT.getInfo(i);

79、;　　getSize(HT);　　cout<<endl<<"請輸入單詞。"<<endl;　　cout<<"注意：數組最大容量為"<<DefaultSize<<endl;　　cout<<&qu

80、ot;你想輸入幾個單詞？"<<endl;　　int count=0; 　　do{　　cin>>count;　　if(count<=0)</p&g

81、t;　　cout<<"你的輸入有誤！請再次輸入："<<endl;　　if(count>DefaultSize) 　　cout<<"你輸入的數超過了最大容量！請正確輸入："<<endl;&

82、lt;p>　　}　　while(count>DefaultSize||count<=0);　　for(int i=1;i<=count;i++){　　cout<<"第"<<i<<"個:

83、";　　cin>>word;　　if(HT.Insert( word )==-1) i--; //輸入有誤，后退一步再輸入一次　　}　　do{ function();} while(1>0);</

眾賞文庫> 全部分類> 畢業(yè)設計

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網頁內容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內容本身不做任何修改或編輯，并不能對任何下載內容負責。
6. 下載文件中如有侵權或不適當內容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

課程設計--《哈希表的操作》設計報告

文檔簡介

溫馨提示

最新文檔

評論

課程設計--《哈希表的操作》設計報告

文檔簡介

溫馨提示

最新文檔

評論

免費下載