哈希表查找的設(shè)計

1、哈希表查找的設(shè)計一問題描述：哈希表查找的設(shè)計：設(shè)哈希表長為20，用除留余數(shù)法構(gòu)造一個哈希函數(shù)，以開放定址法中的線性探測再散列法作為解決沖突的方法，編程實現(xiàn)哈希表查找、插入和建立算法。2 需求分析：程序可實現(xiàn)用戶與計算機的交互過程。在計算機顯示提示信息后，可由用戶鍵入運算命令以實現(xiàn)對應(yīng)的功能，包含數(shù)據(jù)的錄入、查找、刪除、顯示等功能。本程序旨在實現(xiàn)哈希函數(shù)的構(gòu)造與處理存儲沖突，因而指定哈希表存儲的數(shù)據(jù)類型為簡單的整型數(shù)字，在實用性上還有所欠缺。但根據(jù)用戶需求的變化，可以對程序的基本數(shù)據(jù)類型進(jìn)行改造，以實現(xiàn)更為豐富的功能，進(jìn)而體現(xiàn)哈希表在查找數(shù)據(jù)時的優(yōu)越性。3 算法思想：在設(shè)定哈希表的抽象數(shù)據(jù)類型時

2、，要有查找數(shù)據(jù)元素的操作。另外，插入操作和刪除操作也要用到查找數(shù)據(jù)元素操作，以查看該數(shù)據(jù)元素是否存在，因此可以設(shè)計查找元素操作包括插入和刪除操作的查找。因此，查找操作就有兩種情況：一種情況是插入操作時尋找空閑單元的查找；另一種情況是在查找和刪除操作時尋找該元素是否在哈希表中已存在的查找。插入操作時尋找空閑單元查找的特征是哈希表中不存在該對象，設(shè)計此時查找函數(shù)返回該空閑單元位置的“正”值；查找和刪除操作時尋找該元素是否在哈希表中已存在的特征是哈希表中已存在該數(shù)據(jù)元素，設(shè)計此時查找函數(shù)返回該數(shù)據(jù)單元位置的“負(fù)”值。進(jìn)而執(zhí)行后續(xù)操作。為了區(qū)分哈希表中每一個表元素的當(dāng)前狀態(tài)，為每一個表元素設(shè)置一個“標(biāo)

3、志”定為tag。tag=0表示該元素為空；tag=1表示該元素以存放有數(shù)據(jù)元素；tag=-1表示該元素中存放的數(shù)據(jù)元素已被刪除。判斷當(dāng)tag為0或-1時都可以進(jìn)行插入操作。4 概要設(shè)計：1. 哈希表抽象數(shù)據(jù)類型的定義：ADT HashTable 數(shù)據(jù)對象：D=ai|aiElemSet, i=1,2,.n, n0 數(shù)據(jù)關(guān)系：R1=<ai-1,ai>|ai-1D, i=1,2,.n 基本操作：Initiate( &h ) 操作結(jié)果：構(gòu)造一個空的哈希表h。SearchHash( h, x, p ) 初始條件：哈希表h已存在；p為除留余數(shù)法中除數(shù)，由用戶指定。 操作結(jié)果：查找表中元

4、素與指定數(shù)據(jù)x比較。元素已存在時返回其所在位置的負(fù)數(shù)下標(biāo)、不存在時返回其位置的正數(shù)下標(biāo)、遍歷哈希表后未查找到時返回表長。Insert( &h, x, p ) 初始條件：哈希表h已存在。 操作結(jié)果：查找操作后插入元素x至哈希表。若元素已存在或哈希表已滿時插入操作失敗，返回值為0。Delete(&h, x, p ) 初始條件：哈希表h已存在。 操作結(jié)果：查找操作后從哈希表中刪除元素x。若元素不在表中時刪除操作失敗，返回值為0。Print( h ) 初始條件：哈希表h已存在。 操作結(jié)果：顯示哈希表中元素及存儲狀態(tài)。Clear( &h ) 初始條件：哈希表h已存在。 操作結(jié)果：

5、清空哈希表。ADT HashTable2. 程序模塊：Hash.h頭文件，包含哈希表抽象數(shù)據(jù)類型。Hash.cpp主程序，為哈希表操作面板。 5 程序代碼：Hash.h文件 #include<malloc.h> #include<iostream.h> #include<iomanip.h> #include<process.h> #include<ctype.h> #define TableSize 20 /哈希表長20 #define SUCCESS 1 #define UNSUCCESS 0 typedef int Status

6、; typedef struct /定義元素關(guān)鍵字類型 int key; Elemtype; typedef struct /定義哈希表中基本單元,包含數(shù)據(jù)與標(biāo)志兩部分 Elemtype elem; /數(shù)據(jù)部分,存放關(guān)鍵字 int tag; /標(biāo)志部分,tag=0表示表單元為空, /tag=1表示表單元已存放數(shù)據(jù)元素, /tag=-1表示表單元中存放的數(shù)據(jù)已被刪除 HashItem; typedef struct /定義哈希表,包含表單元數(shù)組與當(dāng)前存儲量 HashItem tableTableSize; int currentSize; /當(dāng)前哈希表存儲量 HashTable; Status

7、Initiate(HashTable *h) /初始化操作 int i; for(i=0; i<TableSize; i+) (*h).tablei.tag=0; /tag標(biāo)志置為0(*h).tablei.elem.key=NULL; /空單元默認(rèn)值設(shè)為NULL (*h).currentSize=0; return SUCCESS; int SearchHash(HashTable h, Elemtype x, int p) /查找元素操作 int i=x.key%p; /除留余數(shù)法定哈希地址,主程序中定義一不大于表長的素數(shù)p int j=i; while(h.tablej.tag=1

8、&& h.tablej.elem.key!=x.key) /沖突時 j=(j+1)%TableSize; /開放定址法,線性探測再散列,求出新位置j if(j=i) cout<<"哈希表中未查找到"<<x.key<<endl;return TableSize; /全表遍歷后未搜索到所給元素,返回表長 if(h.tablej.tag=1) /元素已存在時返回其位置的負(fù)數(shù)下標(biāo)cout<<"該元素在哈希表的第"<<j<<"位"<<endl;

9、return -j; else /元素不存在時返回其位置的下標(biāo)cout<<"哈希表中未查找到"<<x.key<<endl; return j; Status Insert(HashTable *h, Elemtype x, int p) /插入元素操作 int i=SearchHash(*h, x, p); /先調(diào)用查找操作 if(i<0) /元素已存在時,插入失敗cout<<x.key<<"元素已存在,無法再錄入,操作失?。?quot;<<endl<<endl; retur

10、n UNSUCCESS; else if(i!=TableSize && (*h).tablei.tag!=1) /哈希表有剩余空間時,進(jìn)行插入操作 (*h).tablei.elem.key=x.key; /插入元素 (*h).tablei.tag=1; /tag標(biāo)志置為1 (*h).currentSize+; /表存儲量加1 cout<<"錄入成功！"<<endl<<endl; return SUCCESS; else if(i=TableSize) /哈希表已滿時,插入失敗 cout<<"哈希表已

11、滿,無法再插入"<<x.key<<"，操作失敗！"<<endl<<endl; return UNSUCCESS; Status Delete(HashTable *h, Elemtype x, int p) /刪除元素操作 int i=SearchHash(*h, x, p); /先調(diào)用查找操作 if(i<=0) /查找成功,元素存在時,進(jìn)行刪除操作 (*h).table-i.elem.key=NULL; /單元值設(shè)為NULL (*h).table-i.tag=-1; /tag標(biāo)志置為-1 (*h).curre

12、ntSize-; /表存儲量減1 cout<<"刪除成功！"<<endl; return SUCCESS; else cout<<"刪除失??！"<<endl; return UNSUCCESS; Status Print(HashTable h) /打印表操作 cout<<endl<<"哈希表序數(shù) 存儲情況 存儲元素"<<endl; for(int i=0;i<TableSize;i+) cout<<setw(4)<<i&

13、lt;<setw(10)<<h.tablei.tag<<setw(10)<<h.tablei.elem.key<<endl; cout<<endl<<"表中非空元素個數(shù)："<<h.currentSize<<endl<<endl; return SUCCESS; Status Clear(HashTable *h) /置空表操作 for(int i=0;i<TableSize;i+) (*h).tablei.tag=0; (*h).tablei.elem.k

14、ey=NULL; (*h).currentSize=NULL; cout<<"哈希表已全部置空！"<<endl; return SUCCESS; Hash.cpp文件int main( ) cout<<endl<<"* HashTable Test File*"<<endl<<endl; HashTable h; Initiate(&h); int prime; cout<<"請輸入一個小于20的質(zhì)數(shù)：" cin>>prime; c

15、har choice; while(1) cout<<""<<endl; cout<<"按 a 輸出哈希表"<<endl; cout<<"按 b 查找指定元素在表中的位置"<<endl; cout<<"按 c 錄入元素"<<endl; cout<<"按 d 刪除元素"<<endl; cout<<"按 e 清空哈希表"<<endl; c

16、out<<"按 其他鍵 退出"<<endl<<endl<<"請選擇：" cin>>choice; cout<<""<<endl; switch(choice) case'a': Print(h); break;case'b': cout<<"請輸入需要查找的元素的值："Elemtype a;cin>>a.key;SearchHash(h,a,prime);break;case&

17、#39;c':cout<<"請輸入需要輸入的元素個數(shù)(120)："int n,i;cin>>n;Elemtype *pi=0;pi=(Elemtype*)malloc(n*sizeof(Elemtype);cout<<"請依次輸入"<<n<<"個元素的值："<<endl;for(i=0;i<n;i+) cin>>pii.key; Insert(&h,pii,prime);break;case'd':cout<

18、<"請輸入需要刪除的元素的值："Elemtype c;cin>>c.key;Delete(&h,c,prime);break;case'e': Clear(&h); break; default:return 0; 6 運行結(jié)果： 程序運行，先按要求輸入一小于20的質(zhì)數(shù)作為除留余數(shù)法的除數(shù)因子?，F(xiàn)取7。 顯示主面板，選擇錄入數(shù)據(jù)。 先輸入本次需要錄入數(shù)據(jù)的個數(shù)，現(xiàn)取5。再依次錄入數(shù)據(jù)，現(xiàn)輸入326,547,233,145,985。 選擇輸出哈希表，并顯示當(dāng)前表中存儲元素個數(shù)。默認(rèn)未存儲的單元“存儲元素”為0，可以從“存儲情況”一欄判斷存儲元素為“0”還是為“空”。 選擇查找指定元素在表中的位置。輸入已存在的元素“233”與不存在的元素“14”，顯示如下： 再次選擇錄入數(shù)據(jù)。分別輸入已存在的元素“233”與不存在的元素“14”，顯示如下： 選擇刪除數(shù)據(jù)。分別刪除已存在的元素“985”與不存在的元素“211”，顯示如下： 再次選擇輸出哈希表。經(jīng)過上述操作后，哈希表現(xiàn)存儲狀態(tài)如下：其中新增元素14存儲在哈希表第0位，刪除元素