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

1、intkeynum;/記錄的數(shù)據(jù)域,只有關(guān)鍵字一項1、實驗?zāi)康?1)復(fù)習(xí)順序查找、二分查找、分塊查找的根本算法及適用場合；(2)掌握哈希查找的根本方法及適用場合,并能在解決實際問題時靈活應(yīng)用；(3)穩(wěn)固在散列查找時解決沖突的方法及特點.2、實驗內(nèi)容(1)哈希表查找的實現(xiàn)(用線性探測法解決沖突)；(2)能對哈希表進(jìn)行插入和查找.3、實驗要求(1)分析算法思想,利用 C(C+)語言完成程序設(shè)計.(2)上機調(diào)試通過實驗程序.(3)輸入數(shù)據(jù),進(jìn)行哈希插入和查找.(4)給出具體的算法分析,包括時間復(fù)雜度和空間復(fù)雜度等.(5)撰寫實驗報告.4、實驗步驟與源程序?qū)嶒灢襟E本程序共設(shè)計了五個函數(shù)來實現(xiàn)建表,顯示

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

3、除intcount;/哈希表中當(dāng)前元素的個數(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 請輸入菜單號：);scanf(%c,&ch);/輸入操作選項switch(ch)case1:printf(n

5、請輸入元素個數(shù)(10):);for(k=0;kn;k+)printf請輸入第3d 個整數(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 請你輸入要查找元素(int):);scanf(%d,&R.keynum);/輸入待查記錄的關(guān)鍵字temp=SearchHash(H,

6、R.keynum,position);/temp=True:記錄查找成功；temp=False:沒有找到待查記錄if(temp)printf(n 查找成功該元素位置是%dn,position);elseprintf(n 本散列表沒有該元素!n);break;break;printf(n 請輸入要插入元素(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)鍵字不沖突處理方法：線性探測再散列循環(huán)搜索整個表已搜索完,沒有找到待查元查找成功,p 指示待查元素位置查找不成功/查找不成功時插入元素 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)/在查找成功時刪除待刪元素 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)前長度加一False表中不存在待刪元素設(shè)置標(biāo)志為 DELKEY 說明該元素已哈希表當(dāng)前長度減一哈希函數(shù)：H(key)=keyMOD115、測試數(shù)據(jù)與實驗結(jié)果(可以抓圖粘貼)(1)菜單:(3)顯示請輸入菜單號：2)12345&78101135&7勺:uiint：S(4)查找請輸入菜單號,3青你輸入要查找元素(皿七門堂我成功該元素位置是才(5)插入請輸入菜單號,4胃輸入要插入元素?zé)o素插入成功,(6)刪除請輸入菜單號,5青你輸入要刪除元素Cnt八2刪除成功t6、結(jié)果分析與實驗體會本次實驗是參考了范例程序,經(jīng)過自己的改寫,從而實現(xiàn)要求.先做簡單的輸出,一步步的再做其*MK二二二找一表示我人盤二