浏览 1996 次
锁定老帖子 主题:哈希表的查找和算法
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
|
|
---|---|
作者 | 正文 |
发表时间:2011-04-19
最后修改:2011-04-19
设有一组关键字{12,11,35,25,22,58},采用哈希函数:H(key)=key%6,采用开放 地址法的二次探测再哈希方法解决冲突,试在0~10的哈希地址空间中对该关键字序列 构造哈希表。 解法: 依题,m=11,二次探测再哈希的下一地址计算公式为 d1=H(key), d2=(d1+i*i)%m, d3=(d1-i*i)%m 其中(i=1,2,3,...) 则有: H(12)=12%6=0 H(11)=11%6=5 H(35)=35%6=5(冲突) H(35)=(5+1*1)%11=6 H(25)=25%6=1 H(22)=22%6=4 H(58)=58%6=4(冲突) H(58)=(4+1*1)%11=5(冲突) H(58)=(4-1*1)%11=3 对应的构造算法实现: #include<iostream> using namespace std; void CrtHash(int a[],int val,int n1,int n2) { int temp=val%n1; //没有冲突 if(a[temp]==0){a[temp]=val;return;} else //发生冲突 { int temp1; for(int j=1;;++j) { temp1=(temp+j*j)%n2; if(a[temp1]==0){a[temp1]=val;return;} temp1=(temp-j*j)%n2; if(a[temp1]==0){a[temp1]=val;return;} } } } int main() { int KEY[6]={12,11,35,25,22,58}; int hashtable[11]; memset(hashtable,0,sizeof(hashtable)); for(int i=0;i<6;++i) { CrtHash(hashtable,KEY[i],6,11); } for(int i=0;i<11;++i) { cout<<hashtable[i]<<" "; } return 0; } 声明:ITeye文章版权属于作者,受法律保护。没有作者书面许可不得转载。
推荐链接
|
|
返回顶楼 | |