實現哈希表的構造和查找算法，要求：用除留余數法構造哈希函數，分別用一次探測再散列、二次探測再散列解決沖突。

#include<stdio.h> #include<stdlib.h> #include<math.h> /*typedef struct {ElemType *elem;int count;int sizeindex; }HashTable;*/ typedef struct{int key; }keytype;typedef struct { keytype elem[100];int length; /*當前的長度*/int size; /*哈希表的總長*/ }hashtable; int a=0,b=0,select; int hash2(int i,int t) { if(i%2==0)t=t+pow(++a,2);elset=t-pow(++b,2);return t; } int hash1(int i,int t) { i++;t=i;return t; } int hash(hashtable h,int k) {return k%(h.size); } void creat(hashtable *h) { int i,j,key,t,p;printf("請輸入哈希表的長度，和表中的記錄長:");scanf("%d%d",&h->size,&h->length);printf("請選擇：\n1。采用線性探測再散列處理沖突\n2。采用二次探測再散列處理沖突"); scanf("%d",&select);for(i=0;i<h->size;i++)//初始化將哈希表中的關鍵字都置為-1，代表此存儲位子為空 h->elem[i].key=-1;printf("input data:\n");for(j=0;j<h->length;j++){ scanf("%d",&key);p=hash(*h,key);if(h->elem[p].key==-1)h->elem[p].key=key;else{ i=0;t=p;while(h->elem[p].key!=-1&&h->elem[p].key!=key&&i<h->size/2){ if(select==2){p=hash2(i,t);i++;}else if(select==1){p=hash1(i,t);i++;}}a=b=0; //此紀錄找到儲存位置，將a，b參數置0，為下一個記錄沖突做準備 h->elem[p].key=key;}} } int SearchHash(hashtable H,int k){int p,i=0,t=0;p=hash(H,k); //求得Hash的地址 while(H.elem[p].key!=-1&&(k!=H.elem[p].key))//該地址中有記錄，并且關鍵字不相等 {if(select==2){p=hash2(i,t); // 用二次探測法求的下一個探測的地址 i++; }else if(select==1){p=hash1(i,t); // 用二次探測法求的下一個探測的地址 i++;}}if(k==H.elem[p].key)return p;elsereturn -1;}void printhash(hashtable *h){ int i;for(i=0;i<h->size;i++)printf("%-4.2d",i);printf("\n");for(i=0;i<2*h->size;i++)printf("--");printf("\n");for(i=0;i<h->size;i++)printf("%-4.2d",h->elem[i].key);} int main(){ hashtable t;int i,key,key1,c;creat(&t);printf("顯示哈希表:\n\n");printhash(&t);printf("\n\n當前哈希表記錄長為:%d\n",t.length);printf("\n請輸入要查找記錄的關鍵字:");scanf("%d",&key);c=SearchHash(t,key);if(c!=-1)printf("該記錄的位子是:%d\n",c);elseprintf("沒有找到該記錄!\n");return 0;}

測試結果如下：

請輸入哈希表的長度，和表中的記錄長:30 10 請選擇： 1。采用線性探測再散列處理沖突 2。采用二次探測再散列處理沖突2 input data: 12 13 14 56 25 35 36 38 37 12 顯示哈希表:00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 ------------------------------------------------------------------------------------------------------------------------ -01 -01 -01 -01 -01 35 36 37 38 -01 -01 -01 12 13 14 -01 -01 -01 -01 -01 -01 -01 -01 -01 -01 25 56 -01 -01 -01 當前哈希表記錄長為:10請輸入要查找記錄的關鍵字:14 該記錄的位子是:14

?

總結

以上是生活随笔為你收集整理的哈希表的构造和查找算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。