哈希表实验报告

1、实习报告题目：设计一个哈希表，完成相应的建表和查表程序、需求分析 完成日期：1503013班级：姓名：李睿元学号:人名为中国人名的汉语拼音形式；2. 待填入哈希表的姓名共有30个，去平均查找长度的上限为2；3. 哈希函数用除留余数法构造，用伪随机探测再散列法处理冲突；4. 取读者周围较熟悉的30个人的姓名。二、概要设计1. 抽象数据类型的定义：(1) 人名数据表：typedef struct Nodechar name20;int key;)Node,NodeListMAX;(2) 哈希表：typedef struct hashtablechar* name;int key;int conf

2、Ii ct_t i me;HashTabIehash Ien;(3) 变虽：#def ine P 61主要函数的实现：(1) 哈希函数：int Hash(int key)(2) 关键字获得：int GetKey(char str)(3) 文件流中读取姓名：void GetName(NodeList &L, int i,FILE* fp)(4) 哈希表的初始化：void InitiaIHashTabIe (HashTabIe &ht)(5) 伪随机探测序列的生成：void CreatConfilctArray(int n)(6) 哈希表的生成：void CreatHashTabIe(HashTa

3、bIe &ht.NodeList L. int* n)(7) 哈希表的查询：void SearchHashTabIe(HashTabIe ht. int* n. char get_name)三、详细设计#include #include #include #define P 61ame);Li key=GetKey(Li. name); /fscanf (fp. %s. Li name);Li.key二GetKey(Li. name);onfIi ct_t i meO;htn. name二NULL;htn. key二0:n卄：void CreatConfilctArray(int n)ey);

4、i f(htt conf Ii ct_t ime=0)htt name二Li name;ht t conf Iict_t i me+;ht t.key=Li.key;%dn. Li. name. Li. key, t);表内存储位萱：%d 值：key%s 姓名：抽潼晴龙 else int mO; int d= (t+nm)%hashIen;while(htd. conf Iict_t ime!=0)htd conf Iict_t i me+;m+;d= (t+nm)%hashIen;ht d name二Li name;ht d conf I ict_t i me+;htd key=Li.key

5、;轴;I晴龙 姓名：%s key 值：%d 表内存储位置:%dn.Li. name. Li, key. d); i卄；)void SearchHashTabIe(HashTabIe ht irrt* n. char get_name)onfIict_t ime二二0&hth. key!=k)抽潼晴龙表中未找到无此人！ n);break： else if(hth. key二二k)抽潼晴龙，表内存储位直：%S已找到%dn, get_name. h) ; break;)elseP+；h=np;*/if (=NULL)表中未找到无此人！抽潼晴彦 n);break; else if(st

6、rcmp(hth name get_name)二二0)已找到抽潼晴龙纶s: %dn. get_name, h, s_t i me);查找次数%d表内存储位直:八break; else P卄；h= (t+np)%hashIen; s_t i me+;)int ma i n ()哈希表可以在理想情况下不经过任何比较，一次存取就能得到所查记录；2. 除留余数法对于p的选择很重要，经过分析后的选择是p为小于等于m的最大素数，最终 选择了 61;3. 伪随机探测再散列相较于线性探测再散列或二次探测再散能有效的防止二次堆积。四、用户手册1. 本程序的运行环境为Windows操作系统，执行文件为；2. 本程序的输入的名字存储在文件中；.程序进入后已经完成哈希表的构建并进行展示，用户只需进行相应的查找；3.五、测试数据1. 挑选表中已有的十个姓名进行测试(xiaoli, zhuangshuangshuang Iaobai, luj ia. xiaohei,huyazhou,abao.haoj ie. taosi j