哈希表实验报告

实习报告题目：设计一个哈希表，完成相应的建表和查表程序班级：1503013姓名：李睿元学号：15030130073完成日期：2016.12.04一、需求分析1.假设人名为中国人名的汉语拼音形式；2.待填入哈希表的姓名共有30个，去平均查找长度的上限为2；3.哈希函数用除留余数法构造，用伪随机探测再散列法处理冲突；4.取读者周围较熟悉的30个人的姓名。二、概要设计1.抽象数据类型的定义：（1）人名数据表：typedefstructNode{charname[20];intkey;}Node,NodeList[MAX];（2）哈希表：typedefstructhashtable{char*name;intkey;intconflict_time;}HashTable[hashlen];（3）变量：#defineP61//随机数值#defineMAX30//人数#definehashlen61//哈希表长2.主要函数的实现：（1）哈希函数：intHash(intkey)（2）关键字获得：intGetKey(charstr[])（3）文件流中读取姓名：voidGetName(NodeList&L,inti,FILE*fp)（4）哈希表的初始化：voidInitialHashTable(HashTable&ht)（5）伪随机探测序列的生成：voidCreatConfilctArray(intn[])（6）哈希表的生成：voidCreatHashTable(HashTable&ht,NodeListL,int*n)（7）哈希表的查询：voidSearchHashTable(HashTableht,int*n,charget_name[])三、详细设计#includestdio.h#includestdlib.h#includestring.h#defineP61//随机数值#defineMAX30//人数#definehashlen61//哈希表长typedefstructNode{charname[20];intkey;}Node,NodeList[MAX];typedefstructhashtable{char*name;intkey;intconflict_time;}HashTable[hashlen];intHash(intkey){returnkey%P;}intGetKey(charstr[]){intt=0;char*s=str;while(*s){t+=*s;s++;}returnt;}voidGetName(NodeList&L,inti,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);}voidInitialHashTable(HashTable&ht){intn=0;while(nhashlen){ht[n].conflict_time=0;ht[n].name=NULL;ht[n].key=0;n++;}}voidCreatConfilctArray(intn[]){//n=(int*)malloc(50*sizeof(int));inti=0,j=0;while(i50){n[i]=rand()%(hashlen+1);for(;ji;j++){if(n[i]==n[j]){j=0;n[i]=rand()%(hashlen+1);continue;}}i++;}}voidCreatHashTable(HashTable&ht,NodeListL,int*n){//CreatConfilctArray(n);inti=0;intt;while(iMAX){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(姓名：%skey值：%d表内存储位置：%d\n,L[i].name,L[i].key,t);}else{intm=0;intd=(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(姓名：%skey值：%d表内存储位置：%d\n,L[i].name,L[i].key,d);}i++;}}voidSearchHashTable(HashTableht,int*n,charget_name[]){//printf(请输入要查询的姓名：);//charget_name[20];intp=-1;ints_time=1;//scanf(%s,get_name);inth,k;intt;k=GetKey(get_name);t=h=Hash(k);while(1){/*if(ht[h].conflict_time==0&&ht[h].key!=k){printf(表中未找到无此人！\n);break;}elseif(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;}elseif(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++;}}}intmain(){//printf(请输入建表所需的三十个人名！\n);inti,j;NodeListL;HashTableht;InitialHashTable(ht);charget_name[20]={0};intrand_n[50];CreatConfilctArray(rand_n);FILE*fp;fp=fopen(name.txt,r);for(i=0;i30;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);}return0;}四、调试分析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）