《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)五哈希表

1、實(shí)驗(yàn)五 查找實(shí)驗(yàn)?zāi)康? ） 掌握哈希表的構(gòu)造和查找過程及其算法設(shè)計；2 ） 掌握哈希表的平均查找長度的計算。實(shí)驗(yàn)內(nèi)容編寫程序，實(shí)現(xiàn)哈希表的相關(guān)運(yùn)算，并完成以下功能：建立關(guān)鍵字序列（ 16， 74， 60， 43， 54， 90 ， 46， 31， 29， 88 ， 77）對應(yīng)的哈希表A0.12 ，哈希函數(shù)為 H（k）=k%13 ，并采用開放地址法中的線性探測法解決沖突。要求輸出構(gòu)造的哈希表。在上述哈希表中查找關(guān)鍵字為29 的記錄，輸出其位置和比較次數(shù)；在上述哈希表中刪除關(guān)鍵字為77 的記錄，再將其插入。輸出上述哈希表查找成功時的平均查找長度。設(shè)計思路及程序代碼（包括程序結(jié)構(gòu)（即函數(shù)調(diào)用關(guān)系）

2、、算法功能描述或流程圖、程序代碼）#include#define MaxSize 100#define NULLKEY -1#define DELKEY -2typedef int KeyType;typedef char *InfoType;typedef structKeyType key;InfoType data;int count;HashData;typedef HashData HashTableMaxSize;void InsertHT(HashTable ha,int&n,KeyType k,int p)/將關(guān)鍵字 k 插入到哈希表中int i,adr;adr=k%p;if(

3、haadr.key=NULLKEY|haadr.key=DELKEY)/xj 可以直接放在哈希表中 haadr.key=k;haadr.count=1;elsei=1;doadr=(adr+1)%p;i+;while(haadr.key!=NULLKEY&haadr.key!=DELKEY);haadr.key=k;haadr.count=i;n+;void CreateHT(HashTable ha,KeyType x,int n,int m,int p)/創(chuàng)建哈希表int i,n1=0;for(i=0;im;i+)/ 哈希表置初值hai.key=NULLKEY;hai.count=0;fo

4、r(i=0;in;i+)InsertHT(ha,n1,xi,p);int SearchHT(HashTable ha,int p,KeyType k)/ 在哈希表中查找關(guān)鍵字kint i=0,adr;adr=k%p;while(haadr.key!=NULLKEY&haadr.key!=k)i+;/ 采用線性探查找下一個地址adr=(adr+1)%p;if(haadr.key=k)/ 查找成功return adr;else return -1;/ 查找失敗int DeleteHT(HashTable ha,int p,int k,int &n)/ 刪除哈希表中的關(guān)鍵字 int adr;adr=

5、SearchHT(ha,p,k);if(adr!=-1)/ 在哈希表中找到該關(guān)鍵字haadr.key=DELKEY;n-;/ 哈希表的長度減1return 1;else/ 在哈希表中未找到該關(guān)鍵字return 0;void DispHT(HashTable ha,int n,int m)/ 輸出哈希表float avg=0;int i;printf( 哈希表的地址:t);for(i=0;im;i+)printf(%3d,i);printf(n);printf( 哈希表的關(guān)鍵字為 :t);for(i=0;im;i+)if(hai.key=NULLKEY|hai.key=DELKEY) print

6、f( );elseprintf(%3d,hai.key);printf(n);void ASL(HashTable ha,int n,int m,int p)/求平均查找長度int i;int succ=0,unsucc=0;for(i=0;im;i+)if(hai.key!=NULLKEY)succ+=hai.count;/ 累計成功時的總關(guān)鍵字比較次數(shù)printf( 成功情況下ASL(%d)=%gn,n,succ*1.0/n);int main()int x=16,74,60,43,54,90,46,31,29,88,77;int n=11,m=13,p=13,i,k=29;HashTab

7、le ha;printf(1)n);CreateHT(ha,x,n,m,p);/ 構(gòu)造哈希表printf(n);DispHT(ha,n,m);/ 輸出哈希表printf(2)n);printf( 查找關(guān)鍵字 29 的記錄 :n);i=SearchHT(ha,p,k);if(i!=-1)printf(ha%d.key=%dn,i,k);printf( 查找關(guān)鍵字 29 的比較次數(shù)為 :%dn,i);elseprintf( 未找到 %dn,k);printf(3)n);k=77;printf( 刪除關(guān)鍵字 %d:n,k);DeleteHT(ha,p,k,n);DispHT(ha,n,m);/ 輸出

8、哈希表i=SearchHT(ha,p,k);if(i!=-1)printf(ha%d.key=%dn,i,k);elseprintf( 未找到 %dn,k);printf( 將刪除的關(guān)鍵字 77 重新插入 :n,k);/ 重新插入關(guān)鍵字77InsertHT(ha,n,k,p);DispHT(ha,n,m);printf(4)n);printf( 查找成功的平均長度為 :n);ASL(ha,n,m,p);return 0;測試結(jié)果(程序運(yùn)行結(jié)果采用截圖的方式打印)* ,L:Debug5555xxe,哈希表的地址：0122哈箝泰的美鎮(zhèn)宇為二77（2J怪找關(guān)鍵字29的記大m.b. key=29國我關(guān)鍵字加的匕減不圾為不 刪除關(guān)鍵字可哈髭表的加圻：（：1 2 3哈花表的關(guān)鍵字為： 未找于m杼刪除的關(guān)鍵字在重新氏74 5 6 754 16 43 31a29g i o n is 46 60 74 eesoq ID 11 1254 16 必 3129 4a 74 3哈春表的地西： L 哈希表的關(guān)鍵字力：3 g 10