哈希表实验报告

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

2、shtablechar* 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 &

3、amp;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/

4、 人数# define hashlen 61/ 哈希表长typedef struct Nodechar name20;int key;Node,NodeListMAX;typedef struct hashtablechar* name;int key;int conflict_time;HashTablehashlen;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

5、* fp)/* printf(" 请以拼音形式输入第 %d 个姓名 :",i);scanf("%s",L);Li.key=GetKey(L); */ fscanf(fp,"%s",L);Li.key=GetKey(L); /printf("n");void InitialHashTable(HashTable &ht)int n=0;while(n<hashlen) htn.conflict_time=0;=NULL;htn.key=0;

6、 n+;void CreatConfilctArray(int n)/ n=(int*)malloc(50*sizeof(int);int i=0,j=0;while(i<50) ni=rand()%(hashlen+1);for(;j<i;j+) if(ni=nj)j=0;ni=rand()%(hashlen+1); continue; i+;void CreatHashTable(HashTable &ht,NodeList L,int* n) / CreatConfilctArray(n);%dn",L,Li.key,t);%dn",L

7、,Li.key,d);int i=0;int t;while(i<MAX)t=Hash(Li.key);if(htt.conflict_time=0)=L;htt.conflict_time+;htt.key=Li.key;printf("姓名：s key值：d表内存储位置:elseint m=0;int d=(t+nm)%hashlen;while(htd.conflict_time!=0)htd.conflict_time+;m+;d=(t+nm)%hashlen;=L;htd.conflict_time+

8、;htd.key=Li.key;printf("姓名：s key值：%d表内存储位置:i+;void SearchHashTable(HashTable ht,int* n,char get_name)/printf(" 请输入要查询的姓名： ");/char get_name20;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(hth.conflict_time=0&&h

9、th.key!=k)printf(" 表中未找到无此人！ n");break;else if(hth.key=k)printf("已找到 s,表内存储位置：dn",get_name,h);break;elsep+;h=np;*/if(=NULL)printf(" 表中未找到无此人！ n");break;else if(strcmp(,get_name)=0)printf("已找到 s,表内存储位置：d,查找次数：dn",get_name,h,s_time);break;elsep+;

10、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;i<30;i+)GetName(L,i,fp);fclose(fp);CreatHashTable

11、(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,g

12、et_name);return 0;四、调试分析1. 哈希表可以在理想情况下不经过任何比较，一次存取就能得到所查记录；2. 除留余数法对于p 的选择很重要，经过分析后的选择是p 为小于等于m 的最大素数，最终选择了 61 ；3. 伪随机探测再散列相较于线性探测再散列或二次探测再散能有效的防止二次堆积。五、用户手册1. 本程序的运行环境为 Windows 操作系统，执行文件为 hashtable.exe ；2. 本程序的输入的名字存储在name.txt 文件中； name.&Mx -白季*一 U X文年叱 Milk flraiO) =Eh? 0斯壮IM用力n 诅 acmrig 匚用；启r

13、i萼glr 引ri g rbr遍曜 vtLsrrwB i subln：." - ： -da fill LaobHiWFU ml 3f £jng ilatiyu 耳1汕Mi iiLahfd Luji 白 二 hi 嘛。 yuhaa 皿的西 ha jim hahia if：. 小用巾h-o huv-aEhou tfliTSljl Nhu along abas hukun3.程序进入后已经完成哈希表的构建并进行展示，用户只需进行相应的查找;D ;我的宜揩人5 Him b I。q " 口一诣名名名名名名名名名mjiahao k日y但：E4b表网存储"直：53 h

14、uyazhou keyfi； 393表内存储位器39 taosiji keytti 755表内布僧位置：23 hahu iey§! 422表内存储位翼士 56 along keyUi 529去为存储住置：41 abao Key值：403表内存储位置：37 hukun Ht；“ 555表内审港住再二47 vangkjn kcy（|； 763表内存储位置；2 weiwei ks*值：BSC蓑内存桶位置:20 haojie key值：624表内方福位置：14哈希恚建表无属鬲输入要查找的父名（榆人双i表示结束程序）;即驻un753已找到4此kun,关内存楮住望2,查册次数：9 请输入要查找的

15、人名（输入"*"表示结束程序）rhicjie之糖字. 624已找到hao如.表内存储位置，14.查找次数T 胃输入要杳找的人名（输入小样"表示结束程序工九口3： 隹遑李，616 F,找到lanh*,表内存储位置：6,杳找就数：1 请输入方查找的人名（输入“*”表示结束程序）:hahahaha 艮藤宇：804表中未找到无此大！请输入要查找的人名（辅人“杵*”表示结束程序）;*Process exited after IE. 06 seconds with return value 0六、测试数据1 .挑选表中已有的十个姓名进行测试(xiaoli,zhuangshua

16、ngshuang,laobai,lujia,xiaohei,huyazhou,abao,haojie,taosiji,wangkun )府 Dtt6&JX.4ha ihta b I e, exe X哈希表建表无成_二_一二二一一请输入要查找的人名（输A表示结束程序）：工iwHi理 G驳已找到xii,表内存馅位置 3&,查找次数;1 谓也A要直找的人空!输入表不结束程.序？:产叫i呼至忸langstm3期， 关廷宇！ 1945己找到whiLian瑜Liangshumg,表内存储位置；54,直找次数：1 请输入要查找的人名输入力表不结束程序）ilaobai 关酱；616已找到必必力

17、，表内存储位置,6查找次数 请输入要查找的人名（输入"表示结束程序）;lu加关腕君S33已找到卬电，表内存储位置 45,查揶次数：1 请输入要查找的人名（输入J+户表示结束程序）：宣逅而氧 舞字；743已找到="he。表内存储位置111,查找浏K” 请输入要查找的人名（输入表示结束程序）;huy显hou 关金字，w92已找到huyazhou,我内存储位置,科查找次数;1 请输入要查找的人名（输入小林”表示结束程序）：介 美燧字 403已找到ab皿表内存镭位置37*查或次数：1 请输入要查找的人名（输入样法结耒程序）：桂3运 美潸字：624已找到脸:诂.表内存储位置：14.查

18、找次数：1 请输入要杳找的人名（输入气料”表示结束程序）:taciFi ji 关聆 755已找到tagiji,表内存储位置.2当查找次教：1 请输入要查找的人名（输入气铲'表示结束程序）:哂mgkun 关链字：763已找到陶ngk皿 表内希信格置：2,善乐次数:9 请输入要查找的人名（输入“林”表示结束程序）：*'recess exited after 37* 49 seconds with return value 0：41abao V 日 y值; 403表内存储位真:37 hukun key值; 555表内存储位置；47 wanjkuii key值： 763表内存储位置i

19、Z vaiwsi koyfii 65C表内存福住置一20 haoj i s ksyfi> S24表内荐席位置 14along keyla： 52g P Dr1 .fQrsXha c Ha b I e. ev &X与上方的哈希表进行对比完全匹配。右名名名名名主 蔺哈希表建表完成输入要查找的人名（输入*产表示结束程序）iaoli 地字：G4G匕北至表广I百茵空置：3G,直技次数、二输入要查捕的人名（输入"比料"表7F结束程序）：zhuangshuar.gshuang 键字：1940已找到whuwn葬himigshuMng,表内存储位置：54,查找次数：1 请输入要

20、查找的人名（轴入“ *产表不结束林序J;心口出 争字 616已找到1羽此城，表内存储位置, 0直战次数二L 清输入要查找的人名常人“串神”表示结束程序）：lujia 廷字：533已找到之，表内存储位置：器，直找次敷：1 青输入要查找的人名（输入“田”表示结束程序）： xiadhei关健宇：743日找到表内存储位置；1L查找软数门 清输入要查找国人名（输入气/"我示结束程序”huy口工hou 八度字四三匕找到hu?事工hmi,寺内存储泣瓦 迪 善装次数：1 清输入要查找的人名獭入.杪产表示结束程序）：近二 裤字：403已找到丁里,装内存储位置：户,二找字数：1 清输入要查找的人名（输入

21、气*户表示结束程序）也犯近 入 624 Bhaojie,表内荐襦应望14,杳我次数;1 清输入要查找的人名（输入“*4'表示结束程序）：tao=iji, ffWQ名名名名along keyll： bZU：41abao 4eyii ： 403表内存储位置：37 hukun key值；555商为存储位置；47 vangk'jn keyfi： 7E3表内存储但置：2 vrelvel teyfi： S50表内存储便置；20 haojie key值：&24表内存精位置：14哈希表建表完成情输入要查找的人名（输入J”户表示结束程序）：xi«li 关童字：646已找到xiH

22、,表内存储应置：36,查找次数U 情输入要查找的人名【输入“*”表示结束程的：Ehuangshuangshuing 关键字；1946已找到zhumgshu&n耳shumF，表内存储隹置;E4.查找次数：1 着输入要查找的人名（输A仃3表示结束程序）:1二川记键字i 1臼匕找到laohwi,莪内存储位置卜吼查找次数;1请输入要查找的人名（输入F*产表示结束程序）rlujia 隹腌字，522已找到1旬匕 袤内存储位置，西 查找次数J 请输入要杳找的人名（揄入“林”表示结耒程序）: Tii achei关林字：M3已找到油anhRi.古内存储位置 1L杳指次数：1请输入赛杳找的人名（输入表示结束程序）:huyazhou 美鬼宅893已找在Jhup箍hou.表内在隔起置339,番也次数:1 请输入要查找的人名（输入产