數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)9哈希查找

1、 算法設(shè)計(jì)與分析 實(shí)驗(yàn)報(bào)告 - 8 -1、 實(shí)驗(yàn)?zāi)康模?) 復(fù)習(xí)順序查找、二分查找、分塊查找的基本算法及適用場(chǎng)合；（2) 掌握哈希查找的基本方法及適用場(chǎng)合，并能在解決實(shí)際問(wèn)題時(shí)靈活應(yīng)用；（3) 鞏固在散列查找時(shí)解決沖突的方法及特點(diǎn)。2、 實(shí)驗(yàn)內(nèi)容（1) 哈希表查找的實(shí)現(xiàn)（用線性探測(cè)法解決沖突）；（2) 能對(duì)哈希表進(jìn)行插入和查找。3、 實(shí)驗(yàn)要求（1) 分析算法思想，利用C（C+）語(yǔ)言完成程序設(shè)計(jì)。（2) 上機(jī)調(diào)試通過(guò)實(shí)驗(yàn)程序。（3) 輸入數(shù)據(jù)，進(jìn)行哈希插入和查找。（4) 給出具體的算法分析，包括時(shí)間復(fù)雜度和空間復(fù)雜度等。（5) 撰寫(xiě)實(shí)驗(yàn)報(bào)告。4、 實(shí)驗(yàn)步驟與源程序 實(shí)驗(yàn)步驟本程序共設(shè)計(jì)了五個(gè)函數(shù)

2、來(lái)實(shí)現(xiàn)建表，顯示，查找，插入，刪除這幾個(gè)主要功能，然后設(shè)計(jì)主函數(shù)，串接程序，并進(jìn)行調(diào)試，測(cè)試實(shí)驗(yàn)結(jié)果。 源代碼#include <dos.h>#include <conio.h>#include <math.h>#include <stdio.h>#include <stdlib.h>#define MAXSIZE 12 /哈希表的最大容量，與所采用的哈希函數(shù)有關(guān)enum BOOLFalse,True;enum HAVEORNOTNULLKEY,HAVEKEY,DELKEY; /哈希表元素的三種狀態(tài)，沒(méi)有記錄、有記錄、有過(guò)記錄但已被刪

3、除typedef struct /定義哈希表的結(jié)構(gòu) int elemMAXSIZE; /數(shù)據(jù)元素體 HAVEORNOT elemflagMAXSIZE; / 元素狀態(tài)標(biāo)志，沒(méi)有記錄、有記錄、有過(guò)記錄但已被刪除 int count; / 哈希表中當(dāng)前元素的個(gè)數(shù) HashTable;typedef struct int keynum; / 記錄的數(shù)據(jù)域，只有關(guān)鍵字一項(xiàng)Record;void InitialHash(HashTable&); / 初始化哈希表void PrintHash(HashTable); / 顯示哈希表中的所有元素BOOL SearchHash(HashTable,in

4、t,int&); / 在哈希表中查找元素BOOL InsertHash(HashTable&,Record); / 在哈希表中插入元素BOOL DeleteHash(HashTable&,Record); / 在哈希表中刪除元素int Hash(int); / 哈希函數(shù)void main() HashTable H; / 聲明哈希表H char ch,j='y' int position,n,k; Record R; BOOL temp; InitialHash(H); while(j!='n') printf("nt 哈 希

5、查 找 "); printf("nt*"); printf("nt* 1-建 表 *"); printf("nt* 2-顯 示 *"); printf("nt* 3-查 找 *"); printf("nt* 4-插 入 *"); printf("nt* 5-刪 除 *"); printf("nt* 0-退 出 *"); printf("nt*"); printf("nnt請(qǐng)輸入菜單號(hào)："); scanf(&

6、quot; %c",&ch); / 輸入操作選項(xiàng) switch(ch) case '1':printf("n請(qǐng)輸入元素個(gè)數(shù)(<10): "); scanf("%d",&n); printf("n"); for( k=0;k<n;k+) printf("請(qǐng)輸入第%3d個(gè)整數(shù): ",k+1);scanf("%d",&R.keynum); / 輸入要插入的記錄 temp=InsertHash(H,R); ; break; case '

7、;2':if(H.count) / 哈希表不空 PrintHash(H); else printf("n散列表為空表!n"); break; case '3':if(!H.count) printf("n散列表為空表!n"); / 哈希表空 else printf("n請(qǐng)你輸入要查找元素(int) :"); scanf("%d",&R.keynum); / 輸入待查記錄的關(guān)鍵字 temp=SearchHash(H,R.keynum,position); / temp=True:記錄查

8、找成功；temp=False:沒(méi)有找到待查記錄 if(temp) printf("n查找成功該元素位置是 %dn",position); else printf("n本散列表沒(méi)有該元素!n"); break; case '4':if(H.count=MAXSIZE) / 哈希表已滿 printf("n散列表已經(jīng)滿!n"); break; printf("n請(qǐng)輸入要插入元素(int):"); scanf("%d",&R.keynum); / 輸入要插入的記錄 temp=In

9、sertHash(H,R); / temp=True:記錄插入成功；temp=False:已存在關(guān)鍵字相同的記錄 if(temp) printf("n元素插入成功!n"); else printf("n元素插入失敗，相同元素本散列表已經(jīng)存在!n"); break; case '5':printf("n請(qǐng)你輸入 要?jiǎng)h除元素(int):"); scanf("%d",&R.keynum); / 輸入要?jiǎng)h除記錄的關(guān)鍵字 temp=DeleteHash(H,R); / temp=True:記錄刪除成功

10、；temp=False:待刪記錄不存在 if(temp) printf("n刪除成功!n"); else printf("n刪除元素不在散列表中!n"); break; default: j='n' printf("nt歡迎再次使用本程序，再見(jiàn)!n");void InitialHash(HashTable &H) / 哈希表初始化 int i; H.count=0; for(i=0;i<MAXSIZE;i+) H.elemflagi=NULLKEY;void PrintHash(HashTable H)

11、/ 顯示哈希表所有元素及其所在位置 int i; for(i=0;i<MAXSIZE;i+) / 顯示哈希表中記錄所在位置 printf("%-4d",i); printf("n"); for(i=0;i<MAXSIZE;i+) / 顯示哈希表中記錄值 if(H.elemflagi=HAVEKEY) printf("%-4d",H.elemi); else printf("%4c",' '); printf("ncount:%dn",H.count); / 顯示哈希表

12、當(dāng)前記錄數(shù)BOOL SearchHash(HashTable H,int k,int &p) / 在開(kāi)放定址哈希表H中查找關(guān)鍵字為k的數(shù)據(jù)元素，若查找成功，以p指示 / 待查數(shù)據(jù)元素在表中的位置，并返回True；否則，以p指示插入位置，并返回False int p1; p1=p=Hash(k); / 求得哈希地址 while(H.elemflagp=HAVEKEY&&k!=H.elemp) / 該位置中填有記錄并且關(guān)鍵字不相等 p+; / 沖突處理方法：線性探測(cè)再散列 if(p>=MAXSIZE) p=p%MAXSIZE; / 循環(huán)搜索 if(p=p1) retu

13、rn False; / 整個(gè)表已搜索完，沒(méi)有找到待查元素 if(k=H.elemp&&H.elemflagp=HAVEKEY) / 查找成功，p指示待查元素位置 return True; else return False; / 查找不成功 BOOL InsertHash(HashTable &H,Record e) / 查找不成功時(shí)插入元素e到開(kāi)放定址哈希表H中，并返回True，否則返回False int p; if(SearchHash(H,e.keynum,p) / 表中已有與e有相同關(guān)鍵字的元素 return False; else H.elemflagp=HA

14、VEKEY; / 設(shè)置標(biāo)志為HAVEKEY，表示該位置已有記錄 H.elemp=e.keynum; / 插入記錄 H.count+; / 哈希表當(dāng)前長(zhǎng)度加一 return True; BOOL DeleteHash(HashTable &H,Record e) / 在查找成功時(shí)刪除待刪元素e，并返回True，否則返回False int p; if(!SearchHash(H,e.keynum,p) / 表中不存在待刪元素 return False; else H.elemflagp=DELKEY; / 設(shè)置標(biāo)志為DELKEY，表明該元素已被刪除 H.count-; / 哈希表當(dāng)前長(zhǎng)度減一 return True; int Hash(int kn) return (kn%11); / 哈