实现哈希表的构造和查找算法,要求:用除留余数法构造哈希函数,分别采用二次探测再散列、链地址法解决冲突。
// // Created by CHAO on 2021-12-19. // //实现哈希表的构造和查找算法,要求:用除留余数法构造哈希函数,分别采用二次探测再散列、链地址法解决冲突。 #include#include #include typedef struct node { int key; struct node *next; } keytype; typedef struct { keytype elem[100]; int length; //当前的长度 int size; //哈希表的总长 } Hashtable; int a=0,b=0; int twohash(int i, int wei) //二级探测处理冲突 { if (i % 2 != 0) wei += pow(++a, 2); else wei -= pow(++b, 2); return wei; } int hash(Hashtable h, int key) //放入数据无冲突 { return key%(h.size); } void creat(Hashtable *h) { int key, t, p; printf("请输入哈希表的长度和数据的长度:n"); scanf("%d%d", &h->size, &h->length); for (int i = 0; i < h->size; i++) //初始化将哈希表中的关键字都置为-1,代表此存储位为空 h->elem[i].key = 0; printf("请输入数据:n"); for (int j = 0; j < h->length; j++) { scanf("%d", &key); p = hash(*h, key); if (h->elem[p].key == 0) h->elem[p].key = key; //放入数据无冲突 else //二级探测解决 { int count = 1;//记录探测次数,1 -1 4 -4 t = p; //当前下标 while (h->elem[p].key != 0 && h->elem[p].key != key) //当前下标有元素且不等于key { p = twohash(count, t); count++; if (p >= h->size) //超过下标继续循环 { p = p % h->size; } if (p < 0) { //小于下标 p += h->size; } } a = b = 0; h->elem[p].key = key; } } } void createlink(Hashtable *h) { //领接表形式 int key, t, p; printf("请输入哈希表的长度和数据的长度:n"); scanf("%d%d", &h->size, &h->length); for (int i = 0; i < h->size; i++) // { h->elem[i].key = 0; h->elem[i].next=NULL; } printf("请输入数据:n"); for (int j = 0; j < h->length; j++) { scanf("%d", &key); p = key%h->size; if (h->elem[p].key==0) h->elem[p].key = key; //放入数据无冲突 else { if ( h->elem[p].key != key) { keytype *xin = h->elem[p].next; keytype *new = (keytype *) malloc(sizeof(keytype)); new->key = key; new->next = NULL; if (xin == NULL) //第二个元素 h->elem[p].next=new; else { while (xin->next != NULL) xin = xin->next; xin->next = new; } } } } } 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); } void printhashlink(Hashtable *h) //打印 { int qq=0; for (int i = 0; i < h->size; i++) { printf("%-4.2d%d ",qq++, h->elem[i].key); keytype *pp=h->elem[i].next; while (pp!=NULL){ printf("%d ",pp->key); pp=pp->next; } printf("n"); } } int SearchHash(Hashtable H,int k){ //二级探测写法寻找 int p,i=0,t=0; p=hash(H,k); //求位置 t=p; while(H.elem[p].key!=0&&(k!=H.elem[p].key)) //该地址中有记录且关键字不同 { p=twohash(i,t); // 用二次探测法求的下一个探测的地址 i++; } if(k==H.elem[p].key) return p; else return 0; } int searchlink(Hashtable H,int key){ //领接表写法 int p=0; p=hash(H,key); //求位 if(H.elem[p].key==key) return p; else //该地址中有记录且关键字不同 { keytype *xin=H.elem[p].next; while(xin!=NULL) { if(xin->key==key) //循环判断 return p; xin=xin->next; } } return 0; } int main() { int key,c; int choice=0; printf("请选择探索的类型,(1为二次探测,2为链探测)n"); scanf("%d",&choice); if(choice==1) { Hashtable t; creat(&t); printf("输出哈希表:nn"); printhash(&t); printf("n"); printf("n请输入要查找记录的关键字:"); scanf("%d",&key); c=SearchHash(t,key); if(c==0) printf("没有找到该记录!n"); else printf("该记录的位置是:%dn",c); return 0; } else if(choice==2) { Hashtable s; createlink(&s); printhashlink(&s); printf("n请输入要查找记录的关键字:"); scanf("%d", &key); getchar(); c = searchlink(s, key); if (c == 0) printf("没有找到该记录!n"); else printf("该记录的位置是:%dn", c); return 0; } }
1.先输入需要哪种方法解决冲突,然后会调用函数根据不同的方法创建哈希表,后输入需要查找的数据,这时就会直接用对应的探测方法查找。要注意输入的格式,下面给出一组输入:
探测方式:1
哈希表长度及数据个数:13 5
数据:1 2 12 13 25
查找的值:25
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)