给出哈希表用链接地址法处理冲突

软件 2023-12-19

c语言哈希表链地址法问题

结构体的成员x_和y_保存的是什么？

你的

intp=Hash(cell);

找到所项后，因为该项中要有一个链保存一系列元素，所以该链应为一指向hash元素的指针。

判断条件因为该项是否为NULL，若为NULL（地址不冲突），否则冲突，执行的是链表的插入操作，插入到前后首位随你意愿（一般插前边）。

哈希表链地址法中的冲突表是什么？

把数据中的其他的0替换为不可能在数据中出现的数,如-1,99999等,当有哈希地址得到数据时再做一次判断认为9999,-1均为0即可

哈希查找的解决冲突

影响哈希查找效率的一个重要因素是哈希函数本身。当两个不同的数据元素的哈希值相同时，就会发生冲突。为减少发生冲突的可能性，哈希函数应该将数据尽可能分散地映射到哈希表的每一个表项中。解决冲突的方法有以下两种：
(1) 开放地址法
如果两个数据元素的哈希值相同，则在哈希表中为后插入的数据元素另外选择一个表项。
当程序查找哈希表时，如果没有在第一个对应的哈希表项中找到符合查找要求的数据元素，程序就会继续往后查找，直到找到一个符合查找要求的数据元素，或者遇到一个空的表项。
(2) 链地址法
将哈希值相同的数据元素存放在一个链表中，在查找哈希表的过程中，当查找到这个链表时，必须采用线性查找方法。
例3. 6是一个简单的哈希查找算法程序，你可以将它和本章结尾的有关代码一起编译连接成一个可执行程序。
例3．6一个简单的哈希查找算法程序
1: #include
2: #include
3: #include list.h
4: #include hash.h
5:
6: #define HASH_SIZE 1024
7:
8: static listnode_t *hashTable[HASH_SIZE];
9:
10: void insert(const char * s)
11: {
12: listnode_t *ele = newNode((void * ) s)
13: unsigned int h = hash(s) % HASH_SIZE;
14:
15: ele->next = hashTable[h]
16: hashTable[h] = ele;
17: }
18:
19: void print (void)
20: {
21: int h;
22:
23: for (h = 0; h < HASH_SIZE; h++)
24: {
25: listnode_t * lp = hashTalbe[h];
26:
27: if(lp == NULL)
28: continue;
29: printf([%d] , h);
30: while (lp)
31: {
32: printf(\t'%s' , lp->u.str)
33: lp = ip->next;
34: }
35: putchar ('\n');
36: }
37: }
38:
39: const char *search(const char *s)
40: {
39: unsigned int h = hash(s) % HASH_SIZE;
42: listnode_t * lp = hashTable[h];
43:
44: while (lp)
45: {
46: if (! strcmp (s, lp->u.str))
47: return lp->u.str;
48: lp = lp->next;
49: }
50: return NULL;
51: }
请参见：
3. 4 哪一种查找方法最方便?
3．5 哪一种查找方法最快?
3．8 怎样查找链表中的数据?
_____________________________________________
以下是一个简单示例：
#include
#include
using namespace std;
#define m 5 //人数
#define n 10 //哈希表长度
#define q 7 //随机数
struct name{
char *py;
int k;
};
name namelist[n];
struct hash{
char *py;
int k;
int s;
};
hash hashlist[n];
void listname()
{
char *f;
int s0,r,i;
namelist[0].py=as;
namelist[1].py=sa;
namelist[2].py=d;
namelist[3].py=f;
namelist[4].py=g;
for(i=0;i{
s0=0;
f=namelist[i].py;
for(r=0;*(f+r)!='\0';r++)
s0+=*(f+r);
namelist[i].k=s0;
}
}
void creathash()
{
int i;
for(i=0;i{
hashlist[i].py=;
hashlist[i].k=0;
hashlist[i].s=0;
}
for(i=0;i{
int sum=0;
int adr=(namelist[i].k)%q;
int d=adr;
if(hashlist[adr].s==0)
{
hashlist[adr].py=namelist[i].py;
hashlist[adr].k=namelist[i].k;
hashlist[adr].s=1;
}
else
{
while(hashlist[d].k!=0)
{
d=(d+namelist[i].k%5+1)%q;
sum+=1;
}
hashlist[d].py=namelist[i].py;
hashlist[d].k=namelist[i].k;
hashlist[d].s=sum+1;
}
}
}
void find()
{
string nam;
int s0=0,r,sum=1,adr,d;
cout<<请输入姓名的拼音：<cin>>nam;;
for(r=0;r<20;r++)
s0+=nam[r];
adr=s0%q;
d=adr;
if(hashlist[adr].k==s0)
cout<<姓名:<else if(hashlist[adr].k==0)
cout<<无此记录！<else
{
int g=0;
while(g==0)
{
d=(d+s0%5+1)%q;
sum+=1;
if(hashlist[d].k==0)
{
cout<<无此记录！<g=1;
}
if(hashlist[d].k==s0)
{
cout<<姓名:<g=1;
}
}
}
}
void display()
{
int i;
float av=0;
for(i=0;i{
cout<<姓名:<}
for(i=0;i<7;i++)
{
av+=hashlist[i].s;
}
av/=m;
cout<<平均查找长度：=<}
int main()
{
char x;
listname();
creathash();
cout<while(cin>>x){
if(x=='d'){display(); cout<else if(x=='f'){find();cout<else break;
}
return 0;
}