另一方面，实验目的1 .掌握查找表、动态查找表、静态查找表和平均查找长度的概念。
2、掌握线性表中的顺序检索和折半检索的方法。
3、学习快速冷风函数的构建方法、碰撞处理机理及快速冷风表的检索。
二、实验内容和要求1 .静态查找表技术根据顺序搜索算法和折半搜索算法的特点，对以下两个查找表选择合适的算法，设计完整的c源程序。 然后完成问题：
表1查找{ 8、15、19、26、33、41、47、52、64、90}，key=41
查找表2:{ 12，76，29，15，62，35，33，89，48，20 }，查找密钥=35
查找key=41的算法：折半搜索算法比较次数： 3
寻找key=35的算法：逐次检索算法比较次数： 5
顺序查找算法实现代码# include bits/stdc.h # definemax _ num 100 usingnamespacestd； 类型索引键类型； 类型def struct { keytype key； }ElemType； typedef struct { elemtype elem [ max _ num ]； int length； } ss表； intseq_search(sstableST，KeyType key ) { int i； ST.elem[0].key=key； for(I=ST.Length； ST.elem[i].key！=key； I----； 返回I； }int main () { SSTable ST； 关键型密钥； int n，I； ST.length=0； printf ('请输入查找表元素的数量：')； scanf('%d '，n )； printf (查找表输入：(n )； while(n-- ) Scanf('%d '，ST.elem[ST.length ].key )； printf('n输入搜索元素：')； Scanf('%d '，tkey )； I=seq_search(ST，tkey )； if(I==0) printf('n未找到此元素n '； elseprintf('n在查找表中为%d '，ST.length 1-i )； 返回0； }折半搜索算法的实现代码# include bits/stdc.h # definemax _ num 100 usingnamespacestd； 类型索引键类型； 类型def struct { keytype key； }ElemType； typedef struct { elemtype elem [ max _ num ]； int length； } ss表； intHLDDS_search(sstableST，int key ) { int low，high，mid； low=0； high=ST.length； wile(low=high ) {mid=) lowhigh )/2； if(key==ST.Elem[mid].key )返回mid； elseif(keyst.elem[mid].key ) high=mid-1； else low=mid 1； }返回- 1； }int main () { SSTable ST； 关键型密钥； int n，I； ST.length=0； printf ('请输入查找表元素的数量：')； scanf('%d '，n )； printf (查找表输入：(n )； while(n-- ) Scanf('%d '，ST.elem[ST.length ].key )； printf('n输入搜索元素：')； Scanf('%d '，tkey )； I=HLDDS_search(ST，tkey )； if(I==-1 ) printf ) (n未找到此元素n )； ELSEprintf('n在查找表中为%d '，i 1)； 返回0； ) 2、采用快速冷风表结构和查询/*开放地址法构建快速冷风表(/# include stdio.h # include malloc.h # define maxsize 25 # definep 13 # defineo k1 # ) /*关键字值*/int标志； /*是否存储元素*/}El
emType;typedef struct { ElemType data[MAXSIZE]; int count; /*元素个数*/ int sizeindex; /*当前迅速的冷风表容量*/}HashTable;int d1[15]={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14}; /*线性探测序列*/int d2[15]={0,1,-1,2*2,-2*2,3*3,-3*3,4*4,-4*4,5*5,-5*5,6*6,-6*6,7*7,-7*7}; /*二次探测序列*/void dataset(int ds[],int *len);int InsertHash(HashTable *H,int e,int d[]);int CreateHash(HashTable *H,int ds[],int len,int d[]);int SearchHash(HashTable *H, int e,int d[]);void menu();/*输入查找表*/void dataset(int ds[],int *len){ int n,m; n=0; printf("n查找表输入："); while(scanf("%d",&m)==1){ /*以输入一个非整数作为结束*/ ds[n]=m; n++; } *len=n;}/*计算迅速的冷风地址，插入迅速的冷风表*/int InsertHash(HashTable *H,int e,int d[]){ int k,i=1; k=e%P; while(H->data[k].flag==TRUE||k<0){ k=(e%P+d[i])%MAXSIZE;i++; if(i>=15) return ERROR; } H->data[k].key=e; H->data[k].flag=TRUE; H->count++; return OK;}/*构造迅速的冷风表*/int CreateHash(HashTable *H,int ds[],int len,int d[]){ int i; for(i=0;i<len;i++){ if(SearchHash(H,ds[i],d)!=-1) return DUPLICATE; InsertHash(H,ds[i],d); if(H->count>=MAXSIZE) return ERROR; } return OK;}/*初始化迅速的冷风表*/void InitHash(HashTable *H){ int i; for(i=0;i<MAXSIZE;i++){ H->data[i].key=0; H->data[i].flag=FALSE; }}/*在迅速的冷风表中查找*/int SearchHash(HashTable *H, int e,int d[]){ int k,i=1; k=e%P; while(H->data[k].key!=e){ k=(e%P+d[i])%MAXSIZE;i++; if(i>=15) return -1; } return k;}/*演示菜单*/void menu(){ int choice;int *p; HashTable h; h.count=0;h.sizeindex=MAXSIZE; int a[MAXSIZE]={0}; int i,n,e; dataset(a,&n); /*建立查找表*/ getchar(); printf("n"); do{ printf("n----迅速的冷风查找演示----n"); printf("n1.线性探测构造迅速的冷风表n"); printf("n2.二分探测构造迅速的冷风表n"); printf("n3.退出n"); printf("n输入选择："); scanf("%d",&choice); if(choice==1) p=d1; else if(choice==2) p=d2; else return; InitHash(&h); /*初始化迅速的冷风表*/ if(!(i=CreateHash(&h,a,n,p))) /*构造迅速的冷风表*/ printf("n迅速的冷风表构造失败！n"); else if(i==DUPLICATE) printf("n迅速的冷风表具有重复关键字！n"); else{ printf("n迅速的冷风表：n"); for(i=0;i<h.sizeindex;i++) printf("%3d",h.data[i].key); printf("nn迅速的冷风查找n输入要查找的key值："); getchar(); scanf("%d",&e); if((i=SearchHash(&h,e,p))==-1) printf("n%d未找到n",e); else printf("n%d在迅速的冷风表中下标为%dn",e,i); } getchar(); }while(1);}int main(){ menu(); return 0;}输入查找表为：19 14 23 1 68 20 84 27 55 11 10 79（注意以输入一个非整数结束）。
运行结果：
1)线性探测散列：
int d1[15]={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14};
迅速的冷风表形态：
84在迅速的冷风表中的位置:8
2）二次探测散列：
int d2[15]={0,1,-1,22,-22,33,-33,44,-44,55,-55,66,-66,77,-77};
迅速的冷风表形态：
84在迅速的冷风表中的位置：5