本人新手,接触到哈希查找,有几个问题看不懂,希望大家指点迷津,多谢。
#include"stdio.h"
#include"malloc.h"
//定义查找的节点元素
typedef struct
{
int num;
char name[20];
}ElemType;
//定义哈希表
typedef struct
{
ElemType *elem;
int count;
int sizeindex;
}HashTable;
//定义哈希函数
int Hash(int num)
{
int p;
p=num%5;
return p;
}
//创建哈希表
void InitHash(HashTable *H)
{
int i;
int MAX=sizeof(HashTable);
H->elem=(ElemType *)malloc(MAX*sizeof(ElemType));
H->count=0;
H->sizeindex=MAX;
for(i=0;i<MAX;i++)
H->elem[i].num=0; //初始化,是SearHash()函数能够判断到底有没有元素在里面
}
//定义查找函数
int SearHash(HashTable H,int key,int p)
{
int c=0;
*p=Hash(key);
while(H.elem[*p].num!=key&&H.elem[*p].num!=0)//通过二次探测再散列解决冲突
{
c=c+1;
if(c%2==1)
*p=*p+(c+1)(c+1)/4;
else
*p=*p-(c*c)/4;
}
if(H.elem[*p].num==key)
return 1;
else
return 0;
}
//插入函数
//如果查找不到就插入元素
void InsertHash(HashTable *H,ElemType e)
{
int p;
SearHash(*H,e.num,&p);
H->elem[p]=e;
++H->count;
}
//主函数
void main()
{
HashTable H;
int p,key,i;
ElemType e;
InitHash(&H);
for(i=0;i<3;i++) //输入3个元素
{
loop:printf("输入第%d个学生学号\n",i+1);
scanf("%d",&e.num); //输入学号
if(!SearHash(H,e.num,&p))
{
printf("输入第%d个学生名字\n",i+1);
scanf("%s",e.name); //输入名字
InsertHash(&H,e); //插入元素
}
else
{
printf("该学号已经存在\n");//否则就表示元素的学号已经存在
goto loop;//跳到loop处
}
}
printf("请输入您要查找的学生学号:\n");
scanf("%d",&key);//输入要查找的学号
if(SearHash(H,key,&p))//能查找成功
{
printf("查找成功!学生的姓名是%s\n\n",H.elem[p].name);//输出名字
printf("学生所在表中的位置是%d\n\n",p);//输出位置
}
else
printf("查找失败!您要找的学生不存在\n\n");
}
- List item 这是一本讲算法的书中关于哈希查找算法的例子 有几个问题:
1.定义哈希表的结构体中,elem是一个指向结构体变量ElemType的指针,并不是数组,但是为什么会在后面的代码中出现像 H->elem[i].num=0;这样的语句?
2.定义哈希表的结构体中 count和sizeindex表示什么?
3.创建哈希表函数中的MAX是什么东西?
4.查找函数这段代码看不懂,关于c和p的处理是什么意思?
while(H.elem[*p].num!=key&&H.elem[*p].num!=0)//通过二次探测再散列解决冲突
{
c=c+1;
if(c%2==1)
*p=*p+(c+1)*(c+1)/4;
else
*p=*p-(c*c)/4;
}
if(H.elem[*p].num==key)
return 1;
else
return 0;
5.插入函数中的p是什么?不需要初始化?
void InsertHash(HashTable *H,ElemType e)
{
int p;
SearHash(*H,e.num,&p);
H->elem[p]=e;
++H->count;
}
6.主函数中,p好像也没有初始化,但是可以使用p输出学生的名字和位置?
if(SearHash(H,key,&p))//能查找成功
{
printf("查找成功!学生的姓名是%s\n\n",H.elem[p].name);//输出名字
printf("学生所在表中的位置是%d\n\n",p);//输出位置
}