哈希表实验报告15936.doc

《哈希表实验报告15936.doc》由会员分享，可在线阅读，更多相关《哈希表实验报告15936.doc（14页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

2、hashtablechar name;int key;int conflict_time;HashTablehashlen；（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） 伪

3、随机探测序列的生成：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。hinclude #include string。hdefine P 61/随机数值 #define MAX 30/人数 define hashlen 61/哈希表长 typedef struct Nodechar name2

4、0;int key； Node，NodeListMAX；typedef struct hashtablechar* name；int key；int conflict_time;HashTablehashlen；int Hash（int key)return keyP; 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”，Li。name)；Li。key=Get

5、Key(Li.name）； /fscanf(fp,”%s”,Li。name)；Li。key=GetKey（Li。name)；/printf（n”）；void InitialHashTable(HashTable &ht)int n=0;while（nhashlen)htn.conflict_time=0；htn.name=NULL;htn。key=0；n+；void CreatConfilctArray（int n）/n=（int*)malloc（50*sizeof（int）)； int i=0，j=0；while（i50）ni=rand（）（hashlen+1）;for（;ji；j+）if（

6、ni=nj)j=0；ni=rand(）（hashlen+1）;continue;i+；void CreatHashTable(HashTable &ht,NodeList L，int n）/CreatConfilctArray(n）；int i=0；int t；while（iMAX）t=Hash（Li。key)；if(htt。conflict_time=0）htt。name=Li。name；htt.conflict_time+；htt。key=Li。key；printf（”姓名：s key值：d 表内存储位置:%dn,Li。name，Li。key，t）；elseint m=0；int d=（t

7、+nm）hashlen; while（htd。conflict_time！=0）htd。conflict_time+；m+；d=（t+nm）hashlen；htd。name=Li。name；htd。conflict_time+;htd。key=Li。key；printf(姓名：s key值:d 表内存储位置：%dn，Li。name，Li。key,d）；i+； void SearchHashTable（HashTable ht,int n，char get_name）/printf(请输入要查询的姓名：”）;/char get_name20；int p=-1;int s_time=1；/scan

8、f（”s”，get_name)；int h，k;int t；k=GetKey(get_name）;t=h=Hash（k）；while（1)/if（hth。conflict_time=0hth.key!=k）printf（”表中未找到无此人!n”）； break;else if（hth。key=k）printf(”已找到%s，表内存储位置:dn，get_name，h)；break;elsep+；h=np;/if(hth。name=NULL)printf(表中未找到无此人！n); break；else if（strcmp（hth.name,get_name）=0）printf(”已找到s,表内存储

9、位置:d，查找次数：%dn,get_name，h,s_time);break；elsep+;h=(t+np）%hashlen;s_time+；int main（）/printf（”请输入建表所需的三十个人名!n）；int i，j;NodeList L;HashTable ht；InitialHashTable（ht）；char get_name20=0;int rand_n50;CreatConfilctArray（rand_n）；FILE fp;fp=fopen（”name。txt,”r）;for（i=0；i30；i+）GetName（L,i,fp）；fclose（fp）;CreatHash

10、Table（ht,L,rand_n）;printf（n)；printf(-哈希表建表完成-”)；printf(”n）;while（1）get_name20=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的选择很

11、重要，经过分析后的选择是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)