數(shù)據(jù)結(jié)構(gòu)與算法-散列表查找操作實驗

1、廣州XX學(xué)院數(shù)據(jù)結(jié)構(gòu)與算法實驗報告專業(yè)班級姓 名實驗名稱計科181實驗日期2019.12.10XX學(xué) 號20181533實驗6.散列表查找操作指導(dǎo)教師曾岫成 績一、實驗?zāi)康? .熟悉散列查找方法和特點。2 .掌握散列查找解決沖突的方法。3 .用C語言完成算法和程序設(shè)計并上機調(diào)試通過；4 .撰寫實驗報告，給出算法思路或流程圖和具體實現(xiàn)（源程序）、算法分 析結(jié)果（包括時間復(fù)雜度、空間復(fù)雜度以及算法優(yōu)化設(shè)想）、輸入數(shù)據(jù)及程序運 行結(jié)果（必要時給出多種可能的輸入數(shù)據(jù)和運行結(jié)果）。二、實驗要求1、程序要求包含頭文件以及 main函數(shù)2、實驗中所設(shè)計的函數(shù)（算法）需要滿足實驗的要求3、程序的編譯、運行要成

2、功通過4、運行的結(jié)果正確，且有相應(yīng)的提示三、實驗環(huán)境WIND7 VC+6.0或C與C+程序設(shè)計學(xué)習(xí)與實驗系統(tǒng)四、實驗內(nèi)容1 .閉散列表查找的實現(xiàn)2 .開散列表查找的實現(xiàn)五、源代碼及算法分析1 .閉散列表查找的實現(xiàn)假定的最大存儲單元數(shù)*/ 以整型為元素類型*/定義散列表數(shù)組*/#include "stdio.h"#define MAXSIZE 20/*typedef int keytype;/*typedef keytype HTableMAXSIZE; /*/*用線性探測再散列法處理沖突建立散列表*/void creHT（HTable HT,int m,int p） /*創(chuàng)

3、建長度為 m的散列表,p 為除留余數(shù)中的除數(shù)*/ int i,n=0; keytype x;for(i=0;i<m;i+) HTi=-1;/*printf("Input datas(-1:End):"); scanf("%d",&x);while(x!=-1) n+;if(n>m) break; /* n i=x%p;/*while(HTi!=-1)/*i=(i+1)%m;HTi=x;/*scanf("%d",&x);/* 輸出散列表*/void list(HTable HT,int m) /* int i

4、;for(i=0;i<m;i+) printf("%5d",i);printf("n");for(i=0;i<m;i+) printf("%5d",HTi);printf("n");初始化散列表*/記錄散列表中的元素個數(shù)*/計算散列地址*/線性探測*/將元素存入空閑單元*/輸出長度為m的散列表*/在長度為m的散列表中取地址*/找到 */沒找到*/* 查找算法*/int search(HTable HT,int m,keytype x,int p)/* 查找關(guān)鍵字為x 的元素 */ int i,j;i=x

5、%p;/*j=i;while(HTj!=-1) if(HTj=x) return j; /*j=(j+1)%m;if(j=i) break;/*return -1;/* 計算查找成功時的平均查找長度*/float ASLsucc(HTable HT,int m,int p) /* 計算查找成功時的平均查找長度 */ int i,j,n,s=0;for(i=0,n=m;i<m;i+)/*查找成功的可能性有n 種 */ if(HTi=-1) n-;continue;/*j=HTi%p;s+=(m+i-j+1)%m;/*次數(shù)，并進行累加*/return (float)s/n;/* 計算查找失敗

6、時的平均查找長度*/float ASLfail(HTable HT,int m,int p) /*度 */ int i,j,k,s=0;for(i=0;i<p;i+)/* k=0;j=i;while(HTj!=-1) k+;j=(j+1)%m;if(j=i) break;/*況 */s+=k;/* k并進行累加*/return (float)s/p;main() HTable HT;int m=9,p=9;keytype key;creHT(HT,m,p);/*列函數(shù)的余數(shù)為9。以【例7.8】為例 */list(HT,m);/*printf("n"); scanf(&

7、quot;%d",&key);/*printf("%dn",search(HT,m,key,p); /* printf("%6.2fn",ASLsucc(HT,m,p); /*長度*/printf("%6.2fn",ASLfail(HT,m,p); /*長度*/2開散列表查找的實現(xiàn)統(tǒng)計散列表中的元素個數(shù)*/計算成功查找HTi 的比較計算查找失敗時的平均查找長查找失敗的可能性有p 種 */當(dāng)元素填滿整個空間時的情為查找失敗時的比較次數(shù)，建立散列表，長度為9，散輸出散列表*/輸入查找元素*/輸出查找結(jié)果*/輸出查找成功時

8、的平均查找輸出查找失敗時的平均查找#include "stdio.h"/*typedef int keytype; typedef struct node keytype data;struct node *next;slink;/*/* 用拉鏈法處理沖突建立散列表*/void creHT(slink *HT,int m,int p) /*數(shù) */ int i; keytype x; slink *s; for(i=0;i<m;i+)HTi=NULL;/*printf("Input datas(-1:End):"); scanf("%d&

9、quot;,&x);while(x!=-1) i=x%p;/*s=(slink *)malloc(sizeof(slink); s->data=x;/*s->next=HTi; HTi=s;/*scanf("%d",&x);/* 輸出散列表*/void list(slink *HT,int m) /* int i;slink *q;for(i=0;i<m;i+) printf("%5d=> ",i);q=HTi;while(q) printf("%5d ",q->data); q=q-&g

10、t;next; printf("n");關(guān)鍵字類型*/鏈表結(jié)點類型*/建立表長為m的散列表,p為除散列表初始化*/計算散列地址*/生成結(jié)點*/用首插法插入結(jié)點*/輸出散列表，m是表長*/* 查找算法*/int search(slink *HT,int p,keytype x) /* 在散列表中查找指定元素，p 為除數(shù) */ slink *q;int i;i=x%p;/*計算散列地址*/q=HTi;while(q)/* if(q->data=x) return i; /* q=q->next;return -1;/*/* 計算查找成功時的平均查找長度*/float

11、 ASLsucc(slink *HT,int p) /*找長度 ,p 為除數(shù) */ int i,n=0,k,s=0; slink *q;for(i=0;i<p;i+) k=0;q=HTi;while(q) s+=+k;/*加 */n+;/*q=q->next;return (float)s/n;/* 計算查找失敗時的平均查找長度*/float ASLfail(slink *HT,int p) /*長度 ,p 為除數(shù) */ int i,n=0; slink *q;for(i=0;i<p;i+) q=HTi; while(q) n+;/* n次數(shù) */q=q->next;return (float)n/p;在相應(yīng)鏈表中查找*/找到 */沒找到 */計算查找成功時的平均查計算比較次數(shù)，并進行累統(tǒng)計表中的元素個數(shù)*/計算查找失敗時的平均查找既是元素個數(shù)，也是比較main() slink *HT9;int m=9,p=9;keytype key;creHT(HT,m,p);/*為例 */list(HT,m);/*scanf("%d",&key);/*printf("%dn",search(HT,p,key); /*printf(