哈希表實(shí)驗(yàn)報(bào)告

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

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

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

4、e key you want to delete:);scanf(%d, &key);/ 輸入要?jiǎng)h除的關(guān)鍵字del(key);printf(continue to delete?y/n );_flushall();輸出刪除關(guān)鍵字后的哈希表ch_=getchar();printf(Deleted HashTable:n);/for(i=0; iM; i+) printf(%d ,HashTablei);printf(n);4. 程序清單#include #include #include #define M 130 /Hash 表長(zhǎng)度#define KeyNum 130 / 關(guān)鍵字個(gè)數(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表的查找相關(guān)算法。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 表的刪除相關(guān)算法。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) / 產(chǎn)生 n 個(gè) 0R-1 范圍的不重復(fù)隨機(jī)整數(shù)，存入 ran 數(shù)組中int i,j,r;int *sz; / 初始化隨機(jī)數(shù)種子sran

7、d(unsigned)time(NULL); / 產(chǎn)生 0R-1 范圍的 n 個(gè)數(shù)，存入數(shù)組 sz 中產(chǎn)生 n 個(gè)隨機(jī)數(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) /計(jì)算平均查找長(zhǎng)度ASL并返回結(jié)果。參照f(shuō)ind函數(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. 查找關(guān)鍵字位置 2. 刪除關(guān)鍵字 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