哈希表实验报告

题目：设计一个哈希表，完成相应的建表和查表程序

班级：1503013 姓名：李睿元 学号：15030130073 完成日期：2016.12.04

一、需求分析

  1. 假设人名为中国人名的汉语拼音形式；

  2. 待填入哈希表的姓名共有30个，去平均查找长度的上限为2；

  3. 哈希函数用除留余数法构造，用伪随机探测再散列法处理冲突；

  4. 取读者周围较熟悉的30个人的姓名。

二、概要设计

  1. 抽象数据类型的定义：

（1）人名数据表：

（2）哈希表：

typedef struct hashtable

{

}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

#include

#include

#define P 61//随机数值 

#define MAX 30//人数 

#define hashlen 61//哈希表长 

typedef struct Node

{

}Node,NodeList[MAX];

typedef struct hashtable

{

}HashTable[hashlen];

int Hash(int key)

{

} 

int GetKey(char str[])

{

} 

void GetName(NodeList &L,int i,FILE* fp)

{

/* 请以拼音形式输入第%d个姓名:",i);

}

void InitialHashTable(HashTable &ht)

{

}

void CreatConfilctArray(int n[])

{

//

}

void CreatHashTable(HashTable &ht,NodeList L,int* n)

{

//

   姓名：%s key值：%d 表内存储位置：%d\\n",L[i].name,L[i].key,t);

   姓名：%s key值：%d 表内存储位置：%d\\n",L[i].name,L[i].key,d);

     i++;                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                

}

void SearchHashTable(HashTable ht,int* n,char get_name[])

{

 请输入要查询的姓名：");

//

   表中未找到无此人！\\n"); 

   已找到%s，表内存储位置：%d\\n",get_name,h);

   表中未找到无此人！\\n"); 

   已找到%s，表内存储位置：%d，查找次数:%d\\n",get_name,h,s_time);

}

int main()

{

// 请输入建表所需的三十个人名！\\n");

    fp=fopen("name.txt

 哈希表建表完成-------------");

  请输入要查找的人名(输入“***”表示结束程序):");

  关键字：%d ",GetKey(get_name));

}

四、调试分析

  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）