数据结构实验（C语言）：折半查找、哈希查找

文章参考过网上的内容，如有侵权，请联系

#include<stdio.h>#include<stdlib.h>#defineHASHSIZE 12#defineNULLKEY -32768typedefstruct{int*elem;//数据元素储存空间基址，建表示按实际长度分配，0号单元留空intlength;//表长度}SSTable,HashTable;/*typedef struct { int *elem; //数据元素存储基址，动态分配数组 int count1; //当前数据元素个数 }HashTable;*/intm=HASHSIZE;intSearch_Seq(SSTable ST,intkey){//在顺序表ST中顺序查找其关键字等于key的数据元素。若找到//则函数值该元素在表中的位置，否则为0ST.elem[0]=key;//哨兵inti;for(i=ST.length;ST.elem[i]!=key;--i);//从后往前找returni;//找不到时,i为0}intSearch_Bin(SSTable ST,intkey){//在有序表ST中折半查找其关键字等于key的数据元素。若找到，则函数值为//该元素在表中的位置，否则为0intlow=1;inthigh=ST.length;//置区间初值while(low<=high){intmid=(low+high)/2;if(ST.elem[mid]==key)returnmid;//找到待查找元素elseif(ST.elem[mid]>key)high=mid-1;//继续在前半区间进行查找elselow=mid+1;//继续在后半区间进行查找}return0;//顺序表中不存在待查找元素}//初始化散列表intInitHashTable(HashTable*H){inti;H->length=m;H->elem=(int*)malloc(m*sizeof(int));for(i=0;i<m;i++)H->elem[i]=NULLKEY;return1;}voidInitSSTable(SSTable&ST){ST.length=m;ST.elem=(int*)malloc((m+1)*sizeof(int));}//散列函数intHash(intkey){returnkey%m;}//插入关键字进入散列表voidInsertHash(HashTable*H,intkey){intaddr=Hash(key);while(H->elem[addr]!=NULLKEY)addr=(addr+1)%m;H->elem[addr]=key;}//散列表查找关键字intSearchHash(HashTable H,intkey,int*addr){*addr=Hash(key);while(H.elem[*addr]!=key){*addr=(*addr+1)%m;if(H.elem[*addr]==NULLKEY||*addr==Hash(key)){return-1;}}return*addr;}intmain(){SSTable St;InitSSTable(St);inta[12]={12,16,22,25,34,42,48,57,68,71,72,85};HashTable H;inti;InitHashTable(&H);printf("被查找数组\n");for(i=0;i<m;i++){InsertHash(&H,a[i]);St.elem[i+1]=a[i];printf("%d ",a[i]);}St.length=m;printf("\n");printf("---菜单---\n");printf("1:顺序查找；2：折半查找；3：哈希查找\n");intn;while(1){printf("选择查找方式\n");scanf("%d",&n);switch(n){case3:{printf("插入之后的哈希表为：\n");for(i=0;i<m;i++)printf("%d,",H.elem[i]);intaddr,j;j=SearchHash(H,a[5],&addr);printf("搜索到a[5]的地址是：%d\n",j);break;}case1:{printf("查找22\n");printf("元素位置：%d\n",Search_Seq(St,22));break;}case2:{printf("查找16\n");printf("元素位置：%d\n",Search_Bin(St,16));break;}}}}