哈希表實驗報告

1、1. 實驗目的：掌握HASHg的建立和查表技術。2. 實驗內容 ：1. 編寫函數(shù)實現(xiàn)線性探查HASH表的插入和查找算法。2. 編寫主函數(shù)完成以下功能：3. 定義一個長度為128的HASH表；4. 隨機產生120個0255之間的不重復的偽隨機整數(shù)，依次插入到HASH表中；HASH函數(shù)為 H(k)= k*0.618 mod 127；5. 查找存在的和不存在的關鍵字；6. 編寫函數(shù)，統(tǒng)計該HASH表的平均查找長度；7. 變換關鍵字個數(shù)，觀察平均查找長度的變化；8. 變換HASH函數(shù)，觀察平均查找長度的變化；9. 編寫函數(shù)實現(xiàn)HASH表的刪除算法。3. 實驗步驟1. 運行已經給出的代碼：產生隨機數(shù)和查

2、找功能已經實現(xiàn)。2. 編寫統(tǒng)計哈希表平均查找長度的函數(shù)。int asl(int keys, int n)/計算平均查找長度ASL并返回結果。參照find函數(shù)。int i,h,ASL=0;for(i=0;iKeyNum;i+)n=1;/n 用來記錄查找長度h=hash(keysi);while(HashTableh.key!=-1)&(HashTableh.key!=keysi)n+;h=(h+1)%M;ASL=ASL+n;/把查找長度累加起來ASL=ASL/KeyNum;/計算平均查找長度return ASL;3. 編寫選作的哈希表的刪除算法。根據(jù)給出的關鍵字 h 在表中查找，不符合則用-1標

3、記key即不進行操作，找到則用999標記Key即 刪除。void del(int k)/HASH 表的刪除int h;h=hash(k);while(HashTableh.key!=-1)&(HashTableh.key!=k)h=(h+1)%M;/查找關鍵字k else HashTableh.key=999; / 找到 k 后，用 999 標記if(HashTableh.key=-1); /沒有發(fā)現(xiàn)k，不進行操作同時需要在主函數(shù)中添加刪除功能的顯示， 為了顯示刪除后的變化， 將刪 除后的表打印出來。while(ch_=y) / 刪除關鍵字_flushall();printf(Enter th

4、e key you want to delete:);scanf(%d, &key);/ 輸入要刪除的關鍵字del(key);printf(continue to delete?y/n );_flushall();輸出刪除關鍵字后的哈希表ch_=getchar();printf(Deleted HashTable:n);/for(i=0; iM; i+) printf(%d ,HashTablei);printf(n);4. 程序清單#include #include #include #define M 130 /Hash 表長度#define KeyNum 130 / 關鍵字個數(shù)struc

5、t element int key;int otherterm;typedef struct element DATATYPE;DATATYPE HashTableM;int hash(int k) return (int)(k*0.618)%127);int h;h=hash(k);while(HashTableh.key!=-1) h=(h+1)%M;HashTableh.key=k;int find(int k) /HASH表的查找相關算法。int h;h=hash(k);while(HashTableh.key!=-1)&(HashTableh.key!=k) h=(h+1)%M;if

6、(HashTableh.otherterm=1) return -1;else if(HashTableh.key=-1) return -1;else return h;int Delete(int k) /HASH 表的刪除相關算法。int h;h=find(k);if(h!=-1)HashTableh.otherterm=1;return 1;else return 0;void create_random(int ran, int N, int n) / 產生 n 個 0R-1 范圍的不重復隨機整數(shù)，存入 ran 數(shù)組中int i,j,r;int *sz; / 初始化隨機數(shù)種子sran

7、d(unsigned)time(NULL); / 產生 0R-1 范圍的 n 個數(shù)，存入數(shù)組 sz 中產生 n 個隨機數(shù)sz=(int *)malloc(N*sizeof(int);for(i=0;iN;i+) szi=i; / for(i=0;in;i+) r=rand()%(N-i);rani=szr;for(j=r;jN;j+) szj=szj+1;free(sz);float asl(int keys, int n) /計算平均查找長度ASL并返回結果。參照find函數(shù)。int i,count,h;float average,sum=0.0;for(i=0;in;i+) count=1

8、;h=hash(keysi);while(HashTableh.key!=keysi) h=(h+1)%M;count+;sum+=count;average=sum/n;return average;void main() / 主函數(shù)int i,h,key,t,e;char ch=y;int keysKeyNum;for(i=0; iM; i+) HashTablei.key=-1;create_random(keys, 256, KeyNum);printf(Keys:n);for(i=0; iKeyNum; i+) printf(%d ,keysi);printf(nHash Table

9、:n);for(i=0; iKeyNum; i+) insert(keysi);for(i=0; iM; i+) printf(%d ,HashTablei);printf(n);printf(ASL=%.2fn,asl(keys, KeyNum);while(ch=y) printf(* * * * * * * * * * * n);printf（1. 查找關鍵字位置 2. 刪除關鍵字 n）;printf(* * * * * * * * * * * n);_flushall();scanf(%d,&t);switch(t) case 1: printf(Enter a key: );scanf(%d, &key);h=find(key);if (h=-1) printf(Can not found key %d.n,key);else printf(Key %d is in location %dn,key,h);break;case 2: printf(Enter a key: );scanf(%d, &key);e=Delete(key);if