課程設(shè)計(jì)報(bào)告--數(shù)據(jù)哈希表應(yīng)用

1、. 蘭州商學(xué)院隴橋?qū)W院 工學(xué)系課程設(shè)計(jì)報(bào)告設(shè) 計(jì) 題 目：數(shù)據(jù)哈希表應(yīng)用 系 別：工學(xué)系 專 業(yè) (方 向)：網(wǎng)絡(luò)工程班 年 級(jí)、 班：2012級(jí)計(jì)算機(jī)科學(xué)與技術(shù) 學(xué) 生 姓 名：李妮 學(xué) 生 學(xué) 號(hào)：20120661116 指 導(dǎo) 教 師：王萬玉 2013年 12 月 24 日目錄二、需求分析：1三、算法思想：1四、概要設(shè)計(jì)：2五系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)2六、總結(jié)3七、附件（代碼、部分圖表）4；哈希表應(yīng)用一、問題描述哈希表應(yīng)用設(shè)計(jì)：設(shè)哈希表長為13，用除留余數(shù)法構(gòu)造一個(gè)哈希函數(shù)，以開放定址法中的線性探測再散列法作為解決沖突的方法，編程實(shí)現(xiàn)哈希表的查找、插入、刪除、顯示和退出系統(tǒng)的算法。二、需求分析：

2、1、功能需求用戶能夠自定義輸入數(shù)據(jù)，存入哈希表里；用戶能夠?qū)Ξ?dāng)前哈希表進(jìn)行管理。操作內(nèi)容包括：顯示當(dāng)前哈希表、查詢某個(gè)數(shù)據(jù)、插入某個(gè)數(shù)據(jù)、刪除表中某個(gè)數(shù)據(jù)、退出該系統(tǒng)。程序有良好的交互界面，有操作提示和出錯(cuò)提示，方便用戶使用和進(jìn)出入程序。2、程序約束哈希表的散列方法為除留余數(shù)法，處理沖突的辦法為線性探測在散列。使用C/C+語言編寫，程序模塊化設(shè)計(jì)。程序可實(shí)現(xiàn)用戶與計(jì)算機(jī)的交互過程。在計(jì)算機(jī)顯示提示信息后，可由用戶鍵入運(yùn)算命令以實(shí)現(xiàn)對(duì)應(yīng)的功能，包含表的建立、數(shù)據(jù)的查找、插入、刪除、顯示、退出等功能。本程序旨在實(shí)現(xiàn)哈希函數(shù)的構(gòu)造與處理存儲(chǔ)沖突，因而指定哈希表存儲(chǔ)的數(shù)據(jù)類型為簡單的整型數(shù)字，在實(shí)用性

3、上還有所欠缺。但根據(jù)用戶需求的變化，可以對(duì)程序的基本數(shù)據(jù)類型進(jìn)行改造，以實(shí)現(xiàn)更為豐富的功能，進(jìn)而體現(xiàn)哈希表在查找數(shù)據(jù)時(shí)的優(yōu)越性。三、算法思想：在設(shè)定哈希表的抽象數(shù)據(jù)類型時(shí)，要有查找數(shù)據(jù)元素的操作。另外，插入操作和刪除操作也要用到查找數(shù)據(jù)元素操作，以查看該數(shù)據(jù)元素是否存在，因此可以設(shè)計(jì)查找元素操作包括插入和刪除操作的查找。因此，查找操作就有兩種情況：一種情況是插入操作時(shí)尋找空閑單元的查找；另一種情況是在查找和刪除操作時(shí)尋找該元素是否在哈希表中已存在的查找。插入操作時(shí)尋找空閑單元查找的特征是哈希表中不存在該對(duì)象，設(shè)計(jì)此時(shí)查找函數(shù)返回該空閑單元位置的“正”值；查找和刪除操作時(shí)尋找該元素是否在哈希表中

4、已存在的特征是哈希表中已存在該數(shù)據(jù)元素，設(shè)計(jì)此時(shí)查找函數(shù)返回該數(shù)據(jù)單元位置的“負(fù)”值。進(jìn)而執(zhí)行后續(xù)操作。為了區(qū)分哈希表中每一個(gè)表元素的當(dāng)前狀態(tài)，為每一個(gè)表元素設(shè)置一個(gè)“標(biāo)志”定為tag。tag=0表示該元素為空；tag=1表示該元素以存放有數(shù)據(jù)元素；tag=-1表示該元素中存放的數(shù)據(jù)元素已被刪除。判斷當(dāng)tag為0或-1時(shí)都可以進(jìn)行插入操作。四、概要設(shè)計(jì)：哈希表抽象數(shù)據(jù)類型的定義：ADT HashTable 數(shù)據(jù)對(duì)象：D=ai|aiElemSet, i=1,2,.n, n0 數(shù)據(jù)關(guān)系：R1=|ai-1D, i=1,2,.n 基本操作：Initiate( &h ) 操作結(jié)果：構(gòu)造一個(gè)空的哈希表h。

5、SearchHash( h, x, p ) 初始條件：哈希表h已存在；p為除留余數(shù)法中除數(shù)，由用戶指定。 操作結(jié)果：查找表中元素與指定數(shù)據(jù)x比較。元素已存在時(shí)返回其所在位置的負(fù)數(shù)下標(biāo)、不存在時(shí)返回其位置的正數(shù)下標(biāo)、遍歷哈希表后未查找到時(shí)返回表長。Insert( &h, x, p ) 初始條件：哈希表h已存在。 操作結(jié)果：查找操作后插入元素x至哈希表。若元素已存在或哈希表已滿時(shí)插入操作失敗，返回值為0。Delete(&h, x, p ) 初始條件：哈希表h已存在。 操作結(jié)果：查找操作后從哈希表中刪除元素x。若元素不在表中時(shí)刪除操作失敗，返回值為0。Print( h ) 初始條件：哈希表h已存在。

6、 操作結(jié)果：顯示哈希表中元素及存儲(chǔ)狀態(tài)。五系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)int Hash(T key); /計(jì)算哈希地址void Collision(int &s);/沖突,計(jì)算下一個(gè)地址int Search(T key,int &s);/哈希查找int Insert(ElemType e);/元素插入int Delete(ElemType e); /元素刪除void Display(); /顯示哈希表template int LHSearch:Insert(ElemType e)/插入元素int s;if(count=size) printf(表滿，不能插入!n); return UNSUCCESS;el

7、se s=Hash(e.key); int f; f=Search(e.key,s); if(f) /表中已有和e的關(guān)鍵字相同的元素,不進(jìn)行插入操作 printf(該元素已存在，不能插入!n); return UNSUCCESS; else HTs.key=e.key; printf(插入成功!n); count+; return SUCCESS; 1、本次課程設(shè)計(jì)采用的是除留余數(shù)法構(gòu)造了哈希表，除數(shù)的選擇很重要。如果選得不好，會(huì)造成很多沖突，浪費(fèi)時(shí)間和空間代價(jià)。例如，本次設(shè)計(jì)的哈希表最大長度為11，余數(shù)如果取得較小，會(huì)使得一部分元素容易形成堆積，平均搜索長度變大，而且取余的時(shí)間也會(huì)更長。2、

8、本次設(shè)計(jì)處理沖突采用了線性探測再散列的辦法。相比起同時(shí)閉散列方法的二次探測再散列來說，優(yōu)點(diǎn)在于功能簡單易操作性；缺點(diǎn)是當(dāng)數(shù)據(jù)量逐漸加大時(shí)，前者的平均查找長度會(huì)逐漸比后者大。六、總結(jié)哈希表作為一種存儲(chǔ)與查找的優(yōu)化方式，通過把關(guān)鍵碼值映射到數(shù)表中一個(gè)位置來訪問數(shù)據(jù)，以加快查找速度。在日常生活中，哈希函數(shù)的應(yīng)用也是隨處可見。當(dāng)今十分流行的P2P數(shù)據(jù)傳輸技術(shù)中一系列的壓縮、打包以及積分標(biāo)準(zhǔn)都應(yīng)用到了hash算法設(shè)置?？梢娎霉：瘮?shù)用途之廣。本次程序設(shè)計(jì)中利用“除留余數(shù)法”構(gòu)造哈希函數(shù)，并用“開放定址法”中的“線性探測再散列”方式處理沖突，選取較為簡單的整型數(shù)字作為存儲(chǔ)數(shù)據(jù)。通過此次實(shí)驗(yàn)，我對(duì)哈希表抽

9、象數(shù)據(jù)類型的定義以及構(gòu)造方法有了初步的認(rèn)識(shí)和了解，也為今后編寫更復(fù)雜的應(yīng)用程序提供了新的思想方法與實(shí)現(xiàn)基礎(chǔ)。七、附件（代碼、部分圖表）#include#define SUCCESS 1;#define UNSUCCESS 0;#define NULLKEY -1;#define TableLength 13;#define p 13; / H(key)=key % p typedef int T;template struct ElemTypeT key;/關(guān)鍵字;template class LHSearchprivate:ElemType *HT; /開放定址哈希表int count; /

10、當(dāng)前數(shù)據(jù)元素個(gè)數(shù)int size; /哈希表長度public:LHSearch(); / LHSearch(); / void InitHashTable(int n);/ int Hash(T key); /計(jì)算哈希地址void Collision(int &s);/沖突,計(jì)算下一個(gè)地址int Search(T key,int &s);/哈希查找int Insert(ElemType e);/元素插入int Delete(ElemType e); /元素刪除void Display(); /顯示哈希表;template LHSearch:LHSearch()HT=NULL;size=0;co

11、unt=0;template LHSearch:LHSearch() delete HT;count=0;template int LHSearch:Hash(T key) /由哈希函數(shù)求哈希地址return key%p;template void LHSearch:Collision(int &s)/開放定址法解決沖突s=s+;template int LHSearch:Search(T key,int &s)/查找，找到返回/int s;s=Hash(key);while(HTs.key!=-1) & (key!=HTs.key) Collision(s);if(HTs.key=key)

12、return 1;else return 0;template int LHSearch:Insert(ElemType e)/插入元素int s;if(count=size) printf(表滿，不能插入!n); return UNSUCCESS;else s=Hash(e.key); int f; f=Search(e.key,s); if(f) /表中已有和e的關(guān)鍵字相同的元素,不進(jìn)行插入操作 printf(該元素已存在，不能插入!n); return UNSUCCESS; else HTs.key=e.key; printf(插入成功!n); count+; return SUCCES

13、S; template int LHSearch:Delete(ElemType e)/刪除元素int s;if(count=NULL) printf(表空，不能刪除!n); return UNSUCCESS;else s=Hash(e.key); int f; if(f) HTs.key=e.key; printf(刪除成功!n); count-; return SUCCESS; /表中已有和e的關(guān)鍵字相同的元素,不進(jìn)行插入操作 else printf(該元素不存在，不能刪除!n); return UNSUCCESS; templatevoid LHSearch:InitHashTable(

14、int n)size=n;HT=new ElemTypesize;for(int i=0;isize;i+) /初始化，把哈希表置空 HTi.key=NULLKEY;templatevoid LHSearch:Display()for(int i=0;isize;i+) printf(%dn,i); if(HTi.key!=-1) printf(%dn,HTi.key); else printf(t); printf(n);void main()int m;T key;int s=0;ElemType e;LHSearch a;printf(輸入相應(yīng)代碼，必須先創(chuàng)建哈希表n);do print

15、f (t|=|tn); printf (t| |tn); printf (t| 哈希表應(yīng)用 |tn); printf (t| |tn); printf (t|=|tn); printf (ntt【1】-建立!t【2】-插入!t【3】-刪除!n);printf (ntt【4】-查找!t【5】-顯示!t【6】-退出!n); printf (請(qǐng)選擇操作:); scanf(%d,&m); switch(m) case 1:/創(chuàng)建查找表 printf(請(qǐng)輸入表容量：n); scanf(%d,&m); a.InitHashTable(m); printf(依次輸入表元素，-1結(jié)束:n); for(scanf(%d,&e.key) ;e.key!=-1;scanf(%d,&e.key) a.Insert(e); break; case 2: /插入元素 printf(輸入要插入的元素:n); scanf(%d,&e.key); a.Insert(e); break; case 3: /刪除元素 prin