課程設(shè)計(jì)--《哈希表的操作》設(shè)計(jì)報(bào)告

上傳人：奔*** IP屬地：河北更新時(shí)間：2024-03-01 格式：doc 頁數(shù)：15 大小：488.00KB 人氣指數(shù)：12 舉報(bào) 版權(quán)申訴

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

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡介

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

2、gt;　　二需求分析　　1、功能需求　　①．用戶能夠自定義輸入單詞，存入哈希表里；　?、冢脩裟軌?qū)Ξ?dāng)前哈希表進(jìn)行管理。操作內(nèi)容包括：查看當(dāng)前哈希表、搜索某個(gè)單詞、插入任意單詞、刪除表中某個(gè)單詞、查看當(dāng)前表的平均

3、搜索長度、置空當(dāng)前哈希表。　?、郏绦蛴辛己玫慕换ソ缑?，有操作提示和出錯(cuò)提示，方便用戶使用和進(jìn)出入程序。　　2、程序約束　?、伲１淼纳⒘蟹椒槌粲鄶?shù)法，處理沖突的辦法為線性探測(cè)在散列。　　②．使用C/C++語言編寫，程序模塊化設(shè)

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

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

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

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

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

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

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

11、>　　int Calculate(string s){　　//key計(jì)算函數(shù)：word前5個(gè)字符的ASCII碼 + 單詞長度　　//不足5個(gè)字符的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{ 　　//搜索一個(gè)散列表中關(guān)鍵碼與key匹配的元素，搜索成功，則函數(shù)返回改元素的位置　　//否則返回插入點(diǎn)（如果有足夠空間的話）　　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++; } //當(dāng)做循環(huán)表處理，找出下一個(gè)空地址　　}while (j != address); 　　return j; //轉(zhuǎn)一圈回到起點(diǎn)，表已

17、滿，失敗　　} //t1在這個(gè)函數(shù)體里面增加的量△t1為某一元素探查的次數(shù)　?、埽阉?、插入、刪除函數(shù)相同結(jié)構(gòu)：　　Type Name(type1 paramater1, type2 paramater2){　　//調(diào)用FindPos（type1 paramater1,

18、type2 paramater2）　　//檢查FindPos返回值，并對(duì)此作出相應(yīng)判斷　　//根據(jù)以上內(nèi)容作出處理　　//返回　　}

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

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

21、表長， t2的計(jì)算如下：　　2、流程圖　　五調(diào)試分析　　1、本次課程設(shè)計(jì)采用的是除留余數(shù)法構(gòu)造了哈希表，除數(shù)的選擇很重要。如果選得不好，會(huì)造成很多沖突，浪費(fèi)時(shí)間和空間代價(jià)。例如，本次設(shè)計(jì)的哈希表最大長度為30，余數(shù)如果取得較小，例

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

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

24、　　1.單詞輸入　　2.表內(nèi)存儲(chǔ)情況　　3.輸入完畢立即測(cè)試ASL的情況　　4查找測(cè)試　　5. 插

25、入刪除測(cè)試　　測(cè)試結(jié)果：沒有發(fā)現(xiàn)錯(cuò)誤。　　七用戶使用說明　　1、功能使用說明　?、伲檎n表：查看當(dāng)前哈希表的存儲(chǔ)情況　　②．搜索：

26、輸入一個(gè)單詞，查詢表內(nèi)的情況。不支持key查詢，因?yàn)橄嗤膋ey可能有不同的單詞對(duì)應(yīng)，例如”pa”和”le”，key都是211。　　③．插入：輸入單詞，插入到哈希表中。插入后會(huì)立即顯示插入元素的情況。　?、埽畡h除：輸入單詞，在表中搜索，如果存在則刪除，不存在則提示不存在或者已刪除。不支持輸入key進(jìn)行刪除，原因同②。暫時(shí)不支持直接輸入地址進(jìn)行刪除。<

27、;/p>　?、荩@示ASL：查看當(dāng)前表中的ASL值。　?、蓿每毡恚簩?dāng)前表初始化為一張空表。　　2、注意事項(xiàng)　　本次設(shè)計(jì)重點(diǎn)在對(duì)哈希表的處理上，沒有對(duì)選擇界面進(jìn)行很有效的出錯(cuò)處理，請(qǐng)勿在輸入數(shù)字時(shí)輸入其他字符，以免出現(xiàn)死循環(huán)等錯(cuò)誤。</p&

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

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

30、gt;　?、冢敬握n程設(shè)計(jì)可以用動(dòng)態(tài)數(shù)組來代替目前的靜態(tài)數(shù)組，達(dá)到更實(shí)用的效果。還可以將現(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:每個(gè)已有元素的探查次數(shù)的總和 t2:每個(gè)新元素查找可用地址的次數(shù)總和（t/time）　　class H

33、ashTable{　　public:　　HashTable(const int d,int sz=DefaultSize); //構(gòu)造函數(shù)聲明　　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總是報(bào)錯(cuò)　　friend int Calculate(string s); //計(jì)算每個(gè)單詞的key值

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

37、 //哈希表的除數(shù)　　int CurrentSize,TableSize; //當(dāng)前深度以及表的容量　　string ht[DefaultSize]; //哈希表存儲(chǔ)數(shù)組<p

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

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

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

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

42、列表中關(guān)鍵碼與key匹配的元素，搜索成功，則函數(shù)返回改元素的位置　　//否則返回插入點(diǎn)（如果有足夠空間的話）　　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++; } //當(dāng)做循環(huán)表處

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

45、某一元素探查的次數(shù)　　bool HashTable::Search(int key,string value){　　//使用線性探測(cè)在哈希表ht（每個(gè)地址容納一個(gè)元素）中搜索word。如果word在表中存在，　　//則函數(shù)返回true，并用引用參數(shù)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計(jì)算函數(shù)：word前5個(gè)字符的ASCII碼 + 單詞長度　　//不足5個(gè)字符的

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。　　//若找到的位置標(biāo)志是Empty或Deleted,不論是表是否已滿都插入，返回

51、true。　　int key = Calculate(value); //計(jì)算函數(shù)：抽取關(guān)鍵碼　　int i = FindPos(key,value); //地址計(jì)算　　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，但它已經(jīng)邏

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

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

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

59、gt;　　else { cout<<"找不到這個(gè)元素或者這個(gè)元素已經(jīng)被刪除過。"<<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)控制數(shù)組的下標(biāo)　　do{　　if(HT.info[i] != Active) {t2

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

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

70、>　　cout<<"ASLunsucc:"<<t2<<"/"<<HT.TableSize<<endl; //最后t的值是所有元素查找不成功次數(shù)的總和　　}　?、冢鞒绦騢ash_main.

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

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

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

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

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

76、>word;　　HT.Insert(word); break;　　case 4: cout<<"請(qǐng)輸入你想要?jiǎng)h除的單詞:\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<<"哈希表數(shù)組初始化完畢！"<<endl;　　int i=0,j=0;　　for(int i=0;i<DefaultSize;i++) HT.getInfo(i);

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

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

81、t;　　cout<<"你的輸入有誤！請(qǐng)?jiān)俅屋斎耄?quot;<<endl;　　if(count>DefaultSize) 　　cout<<"你輸入的數(shù)超過了最大容量！請(qǐng)正確輸入："<<endl;&

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

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

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

溫馨提示

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

課程設(shè)計(jì)--《哈希表的操作》設(shè)計(jì)報(bào)告

文檔簡介

溫馨提示

最新文檔

評(píng)論

課程設(shè)計(jì)--《哈希表的操作》設(shè)計(jì)報(bào)告

文檔簡介

溫馨提示

最新文檔

評(píng)論

免費(fèi)下載