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

1、intkeynum;/記錄的數(shù)據(jù)域,只有關(guān)鍵字一項(xiàng)1、實(shí)驗(yàn)?zāi)康?1)復(fù)習(xí)順序查找、二分查找、分塊查找的根本算法及適用場(chǎng)合；(2)掌握哈希查找的根本方法及適用場(chǎng)合,并能在解決實(shí)際問(wèn)題時(shí)靈活應(yīng)用；(3)穩(wěn)固在散列查找時(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)撰寫實(shí)驗(yàn)報(bào)告.4、實(shí)驗(yàn)步驟與源程序?qū)嶒?yàn)步驟本程序共設(shè)計(jì)了五個(gè)函數(shù)來(lái)實(shí)現(xiàn)建表,顯示

2、,查找,插入,刪除這幾個(gè)主要功能,然后設(shè)計(jì)主函數(shù),串接程序,并進(jìn)行調(diào)試,測(cè)試實(shí)驗(yàn)結(jié)果.源代碼#include#include#include#include#include#defineMAXSIZE12/哈希表的最大容量,與所采用的哈希函數(shù)有關(guān)enumBOOLFalse,True;enumHAVEORNOTNULLKEY,HAVEKEY,DELKEY;臉希表元素的三種狀態(tài),沒(méi)有記錄、有記錄、有過(guò)記錄但已被刪除typedefstruct/定義哈希表的結(jié)構(gòu)intelemMAXSIZE;/數(shù)據(jù)元素體HAVEORNOTelemflagMAXSIZE;/元素狀態(tài)標(biāo)志,沒(méi)有記錄、有記錄、有過(guò)記錄但已被刪

3、除intcount;/哈希表中當(dāng)前元素的個(gè)數(shù)HashTable;typedefstructRecord;voidInitialHash(HashTable&);/初始化口口布表voidPrintHash(HashTable);/顯示哈希米中的所有兀素BOOLSearchHash(HashTable,int,int&);/在哈希表中查找兀素BOOLInsertHash(HashTable&,Record);/在哈希表中插入兀素BOOLDeleteHash(HashTable&,Record);/在哈希表中刪除兀素intHash(int);/哈希函數(shù)voidmain

4、()HashTableH;/聲明哈希表 Hcharch,j=y;intposition,n,k;RecordR;BOOLtemp;InitialHash(H);while(j!=n)printf(nt哈希查找: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(%c,&ch);/輸入操作選項(xiàng)switch(ch)case1:printf(n

5、請(qǐng)輸入元素個(gè)數(shù)(10):);for(k=0;kn;k+)printf請(qǐng)輸入第3d 個(gè)整數(shù)：,k+1;scanf(%d,&R.keynum);/輸入要插入的記錄temp=InsertHash(H,R);break;case2:if(H.count)/哈希表不空PrintHash(H);elseprintf(n 散列表為空表！n);break;case3:if(!H.count)printf(n 散列表為空表!n);/哈希表空elseprintf(n 請(qǐng)你輸入要查找元素(int):);scanf(%d,&R.keynum);/輸入待查記錄的關(guān)鍵字temp=SearchHash(H,

6、R.keynum,position);/temp=True:記錄查找成功；temp=False:沒(méi)有找到待查記錄if(temp)printf(n 查找成功該元素位置是%dn,position);elseprintf(n 本散列表沒(méi)有該元素!n);break;break;printf(n 請(qǐng)輸入要插入元素(int):);scanf(%d,&R.keynum);/temp=InsertHash(H,R);case4:if(H.count=MAXSIZE)/哈希表已滿printf(n散列表已經(jīng)滿！n;輸入要插入的記錄/temp=True:記錄插入成功；temp=False:已存在關(guān)鍵字相同的

7、記錄default:j=n;printf(nt 歡送再次使用本程序,再見!n);voidInitialHash(HashTable&H)/inti;H.count=0;for(i=0;i=MAXSIZE)p=p%MAXSIZE;/if(p=p1)returnFalse;/素if(k=H.elemp&H.elemflagp=HAVEKEY)/returnTrue;elsereturnFalse;/inti;for(i=0;iMAXSIZE;i+)/顯示哈希表中記錄所在位置printf(%-4d,i);printf(n);for(i=0;iMAXSIZE;i+)/顯布哈希表中記錄值

8、if(H.elemflagi=HAVEKEY)printf(%-4d,H.elemi);elseprintf(%4c,);printf(ncount:%dn,H.count);/顯示哈希表當(dāng)前記錄數(shù)p 指示插入位置,并返回 False求得哈希地址該位置中填有記錄并且關(guān)鍵字不沖突處理方法：線性探測(cè)再散列循環(huán)搜索整個(gè)表已搜索完,沒(méi)有找到待查元查找成功,p 指示待查元素位置查找不成功/查找不成功時(shí)插入元素 e 到開放定址哈希表 H 中,并返回 True,否那么返回 Falseintp;if(SearchHash(H,e.keynum,p)素returnFalse;elseH.elemflagp 尸

9、HAVEKEY;已有記錄H.elemp=e.keynum;/H.count+;returnTrue;BOOLDeleteHash(HashTable&H,Recorde)/在查找成功時(shí)刪除待刪元素 e,intp;if(!SearchHash(H,e.keynum,p)returnFalse;else并返回 True,否那么返回/H.elemflagp 尸 DELKEY;被刪除H.count-;returnTrue;intHash(intkn)return(kn%11);/表中已有與 e 有相同關(guān)鍵字的元設(shè)置標(biāo)志為 HAVEKEY 表不該位置插入記錄哈希表當(dāng)前長(zhǎng)度加一False表中不存在待刪元素設(shè)置標(biāo)志為 DELKEY 說(shuō)明該元素已哈希表當(dāng)前長(zhǎng)度減一哈希函數(shù)：H(key)=keyMOD115、測(cè)試數(shù)據(jù)與實(shí)驗(yàn)結(jié)果(可以抓圖粘貼)(1)菜單:(3)顯示請(qǐng)輸入菜單號(hào)：2)12345&78101135&7勺:uiint：S(4)查找請(qǐng)輸入菜單號(hào),3青你輸入要查找元素(皿七門堂我成功該元素位置是才(5)插入請(qǐng)輸入菜單號(hào),4胃輸入要插入元素?zé)o素插入成功,(6)刪除請(qǐng)輸入菜單號(hào),5青你輸入要?jiǎng)h除元素Cnt八2刪除成功t6、結(jié)果分析與實(shí)驗(yàn)體會(huì)本次實(shí)驗(yàn)是參考了范例程序,經(jīng)過(guò)自己的改寫,從而實(shí)現(xiàn)要求.先做簡(jiǎn)單的輸出,一步步的再做其*MK二二二找一表示我人盤二