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

1、哈希表查找的設(shè)計(jì)一.問題描述：哈希表查找的設(shè)計(jì)：設(shè)哈希表長(zhǎng)為 20,用除留余數(shù)法構(gòu)造一個(gè)哈希函數(shù)，以開放定址法 中的線性探測(cè)再散列法作為解決沖突的方法，編程實(shí)現(xiàn)哈希表查找、插入和建立算法。二.需求分析：程序可實(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ù)類型為簡(jiǎn) 單的整型數(shù)字，在實(shí)用性上還有所欠缺。但根據(jù)用戶需求的變化，可以對(duì)程序的基本數(shù)據(jù)類 型進(jìn)行改造，以實(shí)現(xiàn)更為豐富的功能，進(jìn)而體現(xiàn)哈希表在查找數(shù)據(jù)時(shí)的優(yōu)越性。三.算法思想：在設(shè)定哈希表的抽

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

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

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

5、哈希表。ADT HashTable2 .程序模塊：Hash.h頭文件，包含哈希表抽象數(shù)據(jù)類型。Hash.cpp主程序，為哈希表操作面板。五.程序代碼：Hash.h 文件#include<malloc.h>#include<iostream.h>#include<iomanip.h>#include<process.h>#include<ctype.h>#define TableSize 20哈希表長(zhǎng) 20#define SUCCESS 1typedef int Status;typedef struct定義元素關(guān)鍵字類型int key

6、;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)前存儲(chǔ)量HashItem tableTableSize;int currentSize;當(dāng)前哈希表存儲(chǔ)量HashTable;Status Initiate(HashTable *h)初始化操作int i;for(i=0; i<TableSi

7、ze; 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ù)法定哈希地址，主程序中定義一不大于表長(zhǎng)的素?cái)?shù)pint j=i;while(h.tablej.tag=1 && h.tablej.elem.key!=x.key)/沖突時(shí)j=(j+1)%TableSize;/開放定址法，線性探

8、測(cè)再散列，求出新位置jif(j=i)cout<<"哈希表中未查找到"<<x.key<<endl;return TableSize;/全表遍歷后未搜索到所給元素，返回表長(zhǎng)if(h.tablej.tag=1)/元素已存在時(shí)返回其位置的負(fù)數(shù)下標(biāo)cout<<”該元素在哈希表的第"<<j<<"位"<<endl; return -j;else/元素不存在時(shí)返回其位置的下標(biāo)cout<<"哈希表中未查找至U "<<x.key<&

9、lt;endl; return j;Status Insert(HashTable *h, Elemtype x, int p)插入元素操作int i=SearchHash(*h, x, p);/ 先調(diào)用查找操作if(i<0)/元素已存在時(shí)，插入失敗cout<<x.key<<"元素已存在，無法再錄入，操作失?。?"<<endl<<endl;return UNSUCCESS;elseif(i!=TableSize && (*h).tablei.tag!=1) /哈希表有剩余空間時(shí)，進(jìn)行插入操作(*h).ta

10、blei.elem.key=x.key;/插入元素(*h).tablei.tag=1;/tag標(biāo)志置為1資料./表存儲(chǔ)量加1(*h).currentSize+;cout<<”錄入成功！ "<<endl<<endl;return SUCCESS;elseif(i=TableSize)哈希表已滿時(shí)，插入失敗cout<<"哈希表已滿，無法再插入"<<x.key<<”,操作失敗！ "<<endl<<endl;return UNSUCCESS;Status Delete

11、(HashTable *h, Elemtype x, int p)/先調(diào)用查找操作刪除元素操作int i=SearchHash(*h, x, p);if(i<=0)/查找成功，元素存在時(shí)，進(jìn)行刪除操作(*h).table-i.elem.key=NULL;/單元值設(shè)為NULL(*h).table-i.tag=-1;/tag標(biāo)志置為-1(*h).currentSize-;/表存儲(chǔ)量減1cout<<"刪除成功！ "<<endl;return SUCCESS;elsecout<<"刪除失敗！ "<<endl;

12、return UNSUCCESS;Status Print(HashTable h)打印表操作cout<<endl<<"哈希表序數(shù)存儲(chǔ)情況存儲(chǔ)元素"<<endl;for(int i=0;i<TableSize;i+)cout<<setw(4)<<i<<setw(10)<<h.tablei.tag<<setw(10)<<h.tablei.elem.key<<endl;cout<<endl<<”表中非空元素個(gè)數(shù)："<

13、;<h.currentSize<<endl<<endl;return SUCCESS;Status Clear(HashTable *h)置空表操作for(int i=0;i<TableSize;i+)(*h).tablei.tag=0; (*h).tablei.elem.key=NULL;(*h).currentSize=NULL;cout<<"哈希表已全部置空！ "<<endl;return SUCCESS;Hash.cpp 文件int main()cout<<endl<<"*

14、 HashTable Test File*"<<endl<<endl;HashTable h;Initiate(&h);int prime;cout<<”請(qǐng)輸入一個(gè)小于20的質(zhì)數(shù)：" cin>>prime;char choice;while(1)cout<<""<<endl;cout<<"按a輸出哈希表"<<endl;cout<<”按b查找指定元素在表中的位置"<<endl;cout<<

15、”按 c 錄入元素"<<endl;cout<<”按 d 刪除元素"<<endl;cout<<"按e清空哈希表"<<endl;cout<<"按 其他鍵 退出"<<endl<<endl<<"請(qǐng)選擇："cin>>choice;cout<<" "<<endl;switch(choice)case'a': Print(h); break;case&

16、#39;b': cout<<"請(qǐng)輸入需要查找的元素的值："Elemtype a;cin>>a.key;SearchHash(h,a,prime);break;case'c': cout<<”請(qǐng)輸入需要輸入的元素個(gè)數(shù)(120)："int n,i;cin>>n;Elemtype *pi=0;pi=(Elemtype*)malloc(n*sizeof(Elemtype);cout<<"請(qǐng)依次輸入"<<n<<"個(gè)元素的值："&

17、lt;<endl;for(i=0;i<n;i+) cin>>pii.key; Insert(&h,pii,prime);break;case'd': cout<<”請(qǐng)輸入需要?jiǎng)h除的元素的值："Elemtype c;cin>>c.key;Delete(&h,c,prime);break;case'e': Clear(&h); break; default:return 0;六.運(yùn)行結(jié)果：程序運(yùn)行，先按要求輸入一小于20的質(zhì)數(shù)作為除留余數(shù)法的除數(shù)因子?，F(xiàn)取 7。p：3 &0d

18、3tH,普要彼甯1電面、H ashTa ble De bughash.exe"* Hashi able Test File *-*«*«*»*請(qǐng)輸入一個(gè)小于2陰的質(zhì)數(shù):7顯示主面板，選擇錄入數(shù)據(jù)。kmmnkmwm Nas)11 able Test File*»»*(»*I輸入一個(gè)小于狗的質(zhì)數(shù)：7出找人除空鍵 輯一錄粵地 a bC口e苴.先輸入本次需要錄入數(shù)據(jù)的個(gè)數(shù)，現(xiàn)取 5。再依次錄入數(shù)據(jù)，現(xiàn)輸入 326,547,233,145,985讖纏天酷版數(shù)哈希表序數(shù)存儲(chǔ)情況存儲(chǔ)元素003 1547 1233 。 1326 1145 19S5 00 00326哈希表中未查找到326錄入成功！&47哈希表中未查找到S47桌人成功!233哈希表中未查找到23m錄入成功！145哈希表中未查找到145錄入成功！985哈希表中未查找到會(huì)5錄入成功！選擇輸出哈希表，并顯示當(dāng)前表中存儲(chǔ)元素個(gè)數(shù)。默認(rèn)未存儲(chǔ)的單元“存儲(chǔ)元素”為0,可以從“存儲(chǔ)情況”9 0 12 3 411111表中非空元素個(gè)數(shù);一欄判斷存儲(chǔ)元素為“ 0”還是為“空”選擇查找指定元素在表中的位置。輸入已存在的元素“233”與不存在的元