2 changzhigangnj changzhigangnj 于 2014.03.17 19:46 提问

哈希查找程序中的几个问题

本人新手,接触到哈希查找,有几个问题看不懂,希望大家指点迷津,多谢。

#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");
}

  1. 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);//输出位置
}

Csdn user default icon
上传中...
上传图片
插入图片