数据结构实验（C语言）：折半查找、哈希查找
文章参考过网上的内容如有侵权请联系#includestdio.h#includestdlib.h#defineHASHSIZE 12#defineNULLKEY -32768typedefstruct{int*elem;//数据元素储存空间基址建表示按实际长度分配0号单元留空intlength;//表长度}SSTable,HashTable;/*typedef struct { int *elem; //数据元素存储基址动态分配数组 int count1; //当前数据元素个数 }HashTable;*/intmHASHSIZE;intSearch_Seq(SSTable ST,intkey){//在顺序表ST中顺序查找其关键字等于key的数据元素。若找到//则函数值该元素在表中的位置否则为0ST.elem[0]key;//哨兵inti;for(iST.length;ST.elem[i]!key;--i);//从后往前找returni;//找不到时,i为0}intSearch_Bin(SSTable ST,intkey){//在有序表ST中折半查找其关键字等于key的数据元素。若找到则函数值为//该元素在表中的位置否则为0intlow1;inthighST.length;//置区间初值while(lowhigh){intmid(lowhigh)/2;if(ST.elem[mid]key)returnmid;//找到待查找元素elseif(ST.elem[mid]key)highmid-1;//继续在前半区间进行查找elselowmid1;//继续在后半区间进行查找}return0;//顺序表中不存在待查找元素}//初始化散列表intInitHashTable(HashTable*H){inti;H-lengthm;H-elem(int*)malloc(m*sizeof(int));for(i0;im;i)H-elem[i]NULLKEY;return1;}voidInitSSTable(SSTableST){ST.lengthm;ST.elem(int*)malloc((m1)*sizeof(int));}//散列函数intHash(intkey){returnkey%m;}//插入关键字进入散列表voidInsertHash(HashTable*H,intkey){intaddrHash(key);while(H-elem[addr]!NULLKEY)addr(addr1)%m;H-elem[addr]key;}//散列表查找关键字intSearchHash(HashTable H,intkey,int*addr){*addrHash(key);while(H.elem[*addr]!key){*addr(*addr1)%m;if(H.elem[*addr]NULLKEY||*addrHash(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(i0;im;i){InsertHash(H,a[i]);St.elem[i1]a[i];printf(%d ,a[i]);}St.lengthm;printf(\n);printf(---菜单---\n);printf(1:顺序查找2折半查找3哈希查找\n);intn;while(1){printf(选择查找方式\n);scanf(%d,n);switch(n){case3:{printf(插入之后的哈希表为\n);for(i0;im;i)printf(%d,,H.elem[i]);intaddr,j;jSearchHash(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;}}}}
)
