网站建设的技巧,设计型网站,广西网站建设价格多少,服务器做网站有什么好处实现哈希表的构造和查找算法#xff0c;要求#xff1a;用除留余数法构造哈希函数#xff0c;分别用一次探测再散列、二次探测再散列解决冲突。 #includestdio.h
#includestdlib.h
#includemath.h
/*typedef struct {ElemType *elem;int count;int …实现哈希表的构造和查找算法要求用除留余数法构造哈希函数分别用一次探测再散列、二次探测再散列解决冲突。 #includestdio.h
#includestdlib.h
#includemath.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 a0,b0,select;
int hash2(int i,int t)
{ if(i%20)ttpow(a,2);elsett-pow(b,2);return t;
}
int hash1(int i,int t)
{
i;ti;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(i0;ih-size;i)//初始化将哈希表中的关键字都置为-1代表此存储位子为空 h-elem[i].key-1;printf(input data:\n);for(j0;jh-length;j){ scanf(%d,key);phash(*h,key);if(h-elem[p].key-1)h-elem[p].keykey;else{ i0;tp;while(h-elem[p].key!-1h-elem[p].key!keyih-size/2){ if(select2){phash2(i,t);i;}else if(select1){phash1(i,t);i;}}ab0; //此纪录找到储存位置将ab参数置0为下一个记录冲突做准备 h-elem[p].keykey;}}
}
int SearchHash(hashtable H,int k){int p,i0,t0;phash(H,k); //求得Hash的地址 while(H.elem[p].key!-1(k!H.elem[p].key))//该地址中有记录并且关键字不相等 {if(select2){phash2(i,t); // 用二次探测法求的下一个探测的地址 i; }else if(select1){phash1(i,t); // 用二次探测法求的下一个探测的地址 i;}}if(kH.elem[p].key)return p;elsereturn -1;}void printhash(hashtable *h){ int i;for(i0;ih-size;i)printf(%-4.2d,i);printf(\n);for(i0;i2*h-size;i)printf(--);printf(\n);for(i0;ih-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);cSearchHash(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
