1、1、實驗目的(2)上機調試通過實驗程序。(3)輸入數據，進行哈希插入和查找。(1) 復習順序查找、二分查找、分塊查找的基本算法及適用場合；(2) 掌握哈希查找的基本方法及適用場合，并能在解決實際問題時靈活應用;(3) 鞏固在散列查找時解決沖突的方法及特點。實驗內容(1) 哈希表查找的實現(用線性探測法解決沖突)(2) 能對哈希表進行插入和查找。實驗要求(1)分析算法思想，利用C( C+ )語言完成程序設計。(4)給出具體的算法分析，包括時間復雜度和空間復雜度等。(5)撰寫實驗報告。實驗步驟與源程序實驗步驟本程序共設計了五個函數來實現建表，顯示，查找，插入，刪除這幾個主要功能，然后設計主函數，串

2、接程序，并進行調試，測試實驗結果。源代碼#in elude #in elude #in elude #in clude J #i nclude #define MAXSIZE 12/哈希表的最大容量，與所采用的哈希函數有關enum BOOLFalse,True;enum HAVEORNOTNULLKEY,HAVEKEY,DELKEY;/ 哈希表元素的三種狀態(tài)，沒有記錄、有記錄、有過記錄但已被刪除typ edef struct/定義哈希表的結構 int elemMAXSIZE;/數據元素體HAVEORNOT elemflagMAXSIZE;/元素狀態(tài)標志，沒有記錄、有記錄、有過記錄但已被刪除in

3、t count;/哈希表中當前元素的個數HashT able;typ edef struct int keynum;/記錄的數據域，只有關鍵字一項Record;void Ini tialHash(HashTable &);/初始化哈希表void Prin tHash(HashTable);/顯示哈希表中的所有兀素BOOL SearchHash(HashTable,i nt,i nt&);/在哈希表中查找元素BOOL In sertHash(HashTable&, Record);/在哈希表中插入元素BOOL DeleteHash(HashTable&, Record);/在哈希表中刪除元素/哈

4、希函數int Hash(i nt);void main()/聲明哈希表H HashTable H;char ch,j=y;int po siti on,n,k;Record R;BOOL temp;Ini tialHash(H);while( j!=n)prin tf(nt哈希查找);printf(nt*);prin tf(nt*1-建*H*Hprin tf(nt*prin tf(nt*3-查*Hprin tf(nt*4插*Hprin tf(nt*5-刪*Hprin tf(nt*0 退*Hprintf(nt*);prin tf（nnt請輸入菜單號：）;sea nf(” c,&ch);/輸入操作

5、選項switch(ch)case 1:printf(n請輸入元素個數(10):);scan f(%d, &n);prin tf(n);for( k=O;k n; k+) printf（請輸入第3d個整數：,k+1）;sca nf(%d,&R.key nu m);/輸入要插入的記錄temp=ln sertHash(H,R);break;case 2:if(H.cou nt)/哈希表不空Prin tHash(H);elseprintf（n 散列表為空表！n）;break;case 3:if(!H.cou nt)printf(n 散列表為空表！n);/哈希表空elseprin tf(n請你輸入要查找

6、元素(int):”);scan f(%d,&R.key nu m);/輸入待查記錄的關鍵字temp=SearchHash(H,R.ke ynum,p ositi on);/ temp=True:記錄查找成功； temp=False:沒有找到待查記錄if(te mp)prin tf(n查找成功該元素位置是%dn, positio n);elseprin tf(n本散列表沒有該元素！n);/哈希表已滿break;case 4:if(H.cou nt=MAXSIZE) printf(n 散列表已經滿!n);break;prin tf(n請輸入要插入元素(in t):);sca nf(%d,&R.ke

7、y nu m);/輸入要插入的記錄temp=ln sertHash(H,R);/ tem p=True:記錄插入成功；temp=False:已存在關鍵字相同的記錄if(te mp)printf（n元素插入成功！n）;elseprintf（”n元素插入失敗，相同元素本散列表已經存在!n）;break;case 5:printf（n請你輸入要刪除元素（int）:）;sea nf(%d,&R.key nu m);/輸入要刪除記錄的關鍵字tem p=DeleteHash(H,R);/ temp=True:記錄刪除成功；tem p=False:待刪記錄不存在if(te mp)elseprin tf(n刪

8、除成功!n）;prin tf(n刪除元素不在散列表中!n）;break;default: j= n：prin tf（nt歡迎再次使用本程序，再見!n）;void Ini tialHash(HashT able &H)/哈希表初始化int i;H.co un t=0;for(i=0;iMAXSIZE;i+)H.elemflagi=NULLKEY;void Prin tHash(HashTable H)/顯示哈希表所有元素及其所在位int i;for(i=0;iMAXSIZE;i+)/顯示哈希表中記錄所在位置prin tf(%-4d,i);prin tf(n);for(i=0;i=MAXSIZE)

9、p=p %MAXSIZE;/循環(huán)搜索if(p=p1)retur nFalse;/整個表已搜索完，沒有找到待查元if(k=H.elem p&H.elemflag p=HAVEKEY)/查找成功，P指示待查元素位return True;else/查找不成功/表中已有與e有相同關鍵字的元 H.elemflag p=HAVEKEY;/設置標志為 HAVEKEY，表示該retur n False;BOOL In sertHash(HashTable & H,Record e) /查找不成功時插入元素e到開放定址哈希表 H中，并返回True，否則返回Falseint p;if(SearchHash(H,e

10、.ke ynum,p)return False;else位置已有記錄H.elem p=e.ke ynum;/插入記錄H.co un t+;/哈希表當前長度加一return True;BOOL DeleteHash(HashTable & H,Record e) II在查找成功時刪除待刪元素e,并返回True，否則返回False/表中不存在待刪元素int p;if(!SearchHash(H,e.key num,p)return False;else H.elemflag p=DELKEY;II設置標志為DELKEY，表明該元素已被刪除H.co un t-;II哈希表當前長度減一return True;int Hash(i nt kn) return (k n%11);II 哈希函數：H(key)=key MOD 11測試數據與實驗結果（可以抓圖粘貼）(1)菜單:請輸入元素個10= 5菁第第第12 3 4 5(3)顯示請輸入菜單號;B 1234535678101167號(4)查找請輸入菜單號=3情你輸入要查找元素wt：3查找成功該元素位置是3(5)插入請輸入菜單號.4請輸入要插入元素元素插人成功!(6)刪除請輸入菜單號