首页 > 编程学习 > 哈希表的应用

哈希表的应用

发布时间:2022/12/7 17:34:42

NO COPYING!

NO COPYING!

NO COPYING!

根据给定的一组整数,建立哈希表。

基本要求:

   (1)设计哈希函数;

      (2)分别采用线性探测再散列法和链地址法解决冲突;

      (3)对哈希表进行查找,输出查找成功和不成功的信息。

测试数据要求:

        建立哈希表时输入的数据可以有相同的值。

//Sinhaeng Hhjian
#include<bits/stdc++.h>
#define MAX 105
#define maxn 10005
using namespace std;
struct Node{int key, val;Node *next;
};int Hash(int x){return x%11;
}Node Hnode[11];
void Hinsert(int key, int val){int temp=Hash(key);while(Hnode[temp].key){temp++;if(temp>10)temp-=11;}Hnode[temp].key=key;Hnode[temp].val=val;
}
int Hfind(int key){int cnt=0, temp=Hash(key);while(Hnode[temp].key!=key){temp++;cnt++;if(temp>10)temp-=11;if(cnt>11)break;}if(cnt>11)	return -1;return temp;
}
void xian(int a[], int n){int x;printf("线性探测再散列法解决冲突:\n");memset(Hnode, 0, sizeof(Hnode));for(int i=1;i<=n;i++)Hinsert(a[i], i);printf("请输入需要查找的元素:");scanf("%d", &x);if(Hfind(x)==-1)printf("此元素不存在!\n\n\n");elseprintf("查找成功,是第%d个元素!\n\n\n", Hnode[Hfind(x)].val);
}Node* hnode[11];
Node* hfind(int key){Node* p=NULL;int temp=Hash(key);for(p=hnode[temp];p;p=p->next)if(p->key==key)return p;return NULL;
}
void hinsert(int key,int val){int temp;Node *p=NULL;if(!(p=hfind(key))){temp=Hash(key);p=(Node *)malloc(sizeof(Node));p->key=key;p->next=hnode[temp];hnode[temp]=p;}p->val=val;
}
void lian(int a[], int n){int x;printf("链地址法解决冲突:\n"); memset(hnode, 0, sizeof(hnode));for(int i=1;i<=n;i++)hinsert(a[i], i);printf("请输入需要查找的元素:");scanf("%d", &x);if(hfind(x))printf("查找成功,是第%d个元素!\n\n\n", hfind(x)->val);elseprintf("此元素不存在!\n\n\n");
}int main(){printf("请输入整数的数量:");int n, a[MAX], x;scanf("%d", &n);printf("请输入整数:\n");for(int i=1;i<=n;i++)scanf("%d", &a[i]);xian(a, n);lian(a, n);return 0;
}
/*
9
22 41 53 33 46 30 13 01 67
*/ 

 


本文链接:https://www.ngui.cc/el/2274589.html
Copyright © 2010-2022 ngui.cc 版权所有 |关于我们| 联系方式| 豫B2-20100000