哈希表实验报告
实习报告 题目：设计一个哈希表，完成相应的建表和查表程序 班级：1503013 姓名：李睿元 学号：15030130073 完成日期：2016.12.04
一、 需求分析
1. 假设人名为中国人名的汉语拼音形式；
2. 待填入哈希表的姓名共有 30 个，去平均查找长度的上限为 2；
3. 哈希函数用除留余数法构造，用伪随机探测再散列法处理冲突；
4. 取读者周围较熟悉的 30 个人的姓名。
二、 概要设计
1. 抽象数据类型的定义：
（1）人名数据表：
typedef struct Node
{
char name[20];
int key;
}Node,NodeList[MAX];
（2）哈希表：
typedef struct hashtable {
char* name;
int key;
int conflict_time; }HashTable[hashlen]; （3）变量：
#define P 61//随机数值
#define MAX 30//人数
#define hashlen 61//哈希表长
2. 主要函数的实现：
（1）哈希函数：
int Hash(int key) （2）关键字获得：
int GetKey(char str[])
（3）文件流中读取姓名：
void GetName(NodeList &L,int i,FILE* fp) （4）哈希表的初始化：
void InitialHashTable(HashTable &ht) （5）伪随机探测序列的生成：
void CreatConfilctArray(int n[]) （6）哈希表的生成：
void CreatHashTable(HashTable &ht,NodeList L,int* n) （7）哈希表的查询：
void SearchHashTable(HashTable ht,int* n,char get_name[]) 三、 详细设计 #include <stdio.h> #include <stdlib.h> #include <string.h>
#define P 61//随机数值
#define MAX 30//人数
#define hashlen 61//哈希表长
typedef struct Node {
char name[20];
int key;
}Node,NodeList[MAX]; typedef struct hashtable {
char* name;
int key;
int conflict_time; }HashTable[hashlen];
int Hash(int key) {
return key%P;
}
int GetKey(char str[]) {
int t=0;
char *s=str;
while(*s)
{
t += *s;
s++;
}
return t;
}
void GetName(NodeList &L,int i,FILE* fp) { /* printf("请以拼音形式输入第%d 个姓名:",i);
scanf("%s",L[i].name);
L[i].key=GetKey(L[i].name); */
fscanf(fp,"%s",L[i].name);
L[i].key=GetKey(L[i].name);
//printf("\n"); }
void InitialHashTable(HashTable &ht) {
int n=0;
while(n<hashlen)
{
ht[n].conflict_time=0;
ht[n].name=NULL;
ht[n].key=0;
n++;
} }
void CreatConfilctArray(int n[]) { // n=(int*)malloc(50*sizeof(int));
int i=0,j=0;
while(i<50)
{
n[i]=rand()%(hashlen+1);
for(;j<i;j++)
{
if(n[i]==n[j])
{
j=0;
n[i]=rand()%(hashlen+1);
continue;
}
}
i++;
} }
void CreatHashTable(HashTable &ht,NodeList L,int* n) { // CreatConfilctArray(n);
int i=0;
int t;
while(i<MAX)
{
t=Hash(L[i].key);
if(ht[t].conflict_time==0)
{
ht[t].name=L[i].name;
ht[t].conflict_time++;
ht[t].key=L[i].key;
printf("姓名：%s key 值：%d 表内存储位置：%d\n",L[i].name,L[i].key,t);
}
else
{
int m=0;
int d=(t+n[m])%hashlen;
while(ht[d].conflict_time!=0)
{
ht[d].conflict_time++;
m++;
d=(t+n[m])%hashlen;
}
ht[d].name=L[i].name;
ht[d].conflict_time++;
ht[d].key=L[i].key;
printf("姓名：%s key 值：%d 表内存储位置：%d\n",L[i].name,L[i].key,d);
}
i++;
} }
void SearchHashTable(HashTable ht,int* n,char get_name[]) {
//printf("请输入要查询的姓名：");
//char get_name[20];
int p=-1;
int s_time=1;
// scanf("%s",get_name);
int h,k;
int t;
k=GetKey(get_name);
t=h=Hash(k);
while(1)
{
/*if(ht[h].conflict_time==0&&ht[h].key!=k)
{
printf("表中未找到无此人！\n");
break;
}
else if(ht[h].key==k)
{
printf("已找到%s，表内存储位置：%d\n",get_name,h);
break;
}
else
{
p++;
h=n[p];
}*/
if(ht[h].name==NULL)
{
printf("表中未找到无此人！\n");
break;
}
else if(strcmp(ht[h].name,get_name)==0)
{
printf("已找到%s，表内存储位置：%d，查找次数:%d\n",get_name,h,s_time);
break;
}
else
{
p++;
h=(t+n[p])%hashlen;
s_time++;
}
} }
int main()
{ // printf("请输入建表所需的三十个人名！\n");
int i,j;
NodeList L;
HashTable ht;
InitialHashTable(ht);
char get_name[20]={0};
int rand_n[50];
CreatConfilctArray(rand_n);
FILE* fp;
fp=fopen("name.txt","r");
for(i=0;i<30;i++)
{
GetName(L,i,fp);
}
fclose(fp);
CreatHashTable(ht,L,rand_n);
printf("\n");
printf("--------------哈希表建表完成-------------");
printf("\n");
while(1)
{
get_name[20]={0};
printf("请输入要查找的人名(输入“***”表示结束程序):");
scanf("%s",get_name);
printf("关键字：%d ",GetKey(get_name));
if(strcmp(get_name,"***")==0)
break;
SearchHashTable(ht,rand_n,get_name);
}
return 0; } 四、 调试分析
1. 哈希表可以在理想情况下不经过任何比较，一次存取就能得到所查记录；
2. 除留余数法对于 p 的选择很重要，经过分析后的选择是 p 为小于等于 m 的最大素数，最终选择了 61；
3. 伪随机探测再散列相较于线性探测再散列或二次探测再散能有效的防止二次堆积。
五、 用户手册
1. 本程序的运行环境为 Windows 操作系统，执行文件为 hashtable.exe；
2. 本程序的输入的名字存储在 name.txt 文件中；
3.
程序进入后已经完成哈希表的构建并进行展示，用户只需进行相应的查找；
六、 测试数据
1. 挑选表中已有的十个姓名进行测试 （xiaoli,zhuangshuangshuang,laobai,lujia,xiaohei,huyazhou,abao,haojie,taosiji,wangkun）
与上方的哈希表进行对比完全匹配。
2. 选择 5 个没有在表中的名字进行查表操作：
（lovetianqi,tianjiejie,jiwang,beijing,heheda）