哈希表實驗報告

1、實習報告題目：設計一個哈希表，完成相應的建表和查表程序2016.12.04班級： 1503013 姓名：李睿元 學號：完成日期：一、需求分析1. 假設人名為中國人名的漢語拼音形式；2. 待填入哈希表的姓名共有30 個，去平均查找長度的上限為 2 ；3. 哈希函數(shù)用除留余數(shù)法構造，用偽隨機探測再散列法處理沖突；4. 取讀者周圍較熟悉的 30 個人的姓名。二、概要設計1. 抽象數(shù)據(jù)類型的定義：（ 1）人名數(shù)據(jù)表：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/ 隨機數(shù)值（ define MAX 30/ 人數(shù)（ define hashlen 61/ 哈希表長2. 主要函數(shù)的實現(xiàn)：（ 1）哈希函數(shù)：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/ 隨機數(shù)值# define MAX 30/

4、 人數(shù)# 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,查找次數(shù)：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. 哈希表可以在理想情況下不經(jīng)過任何比較，一次存取就能得到所查記錄；2. 除留余數(shù)法對于p 的選擇很重要，經(jīng)過分析后的選擇是p 為小于等于m 的最大素數(shù)，最終選擇了 61 ；3. 偽隨機探測再散列相較于線性探測再散列或二次探測再散能有效的防止二次堆積。五、用戶手冊1. 本程序的運行環(huán)境為 Windows 操作系統(tǒng)，執(zhí)行文件為 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.程序進入后已經(jīng)完成哈希表的構建并進行展示，用戶只需進行相應的查找;D ;我的宜揩人5 Him b I。q " 口一詣名名名名名名名名名mjiahao k日y但：E4b表網(wǎng)存儲"直：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,查冊次數(shù)：9 請輸入要查找的

15、人名（輸入"*"表示結束程序）rhicjie之糖字. 624已找到hao如.表內存儲位置，14.查找次數(shù)T 胃輸入要杳找的人名（輸入小樣"表示結束程序工九口3： 隹遑李，616 F,找到lanh*,表內存儲位置：6,杳找就數(shù)：1 請輸入方查找的人名（輸入“*”表示結束程序）:hahahaha 艮藤宇：804表中未找到無此大！請輸入要查找的人名（輔人“杵*”表示結束程序）;*Process exited after IE. 06 seconds with return value 0六、測試數(shù)據(jù)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&,查找次數(shù);1 謂也A要直找的人空!輸入表不結束程.序？:產(chǎn)叫i呼至忸langstm3期， 關廷宇！ 1945己找到whiLian瑜Liangshumg,表內存儲位置；54,直找次數(shù)：1 請輸入要查找的人名輸入力表不結束程序）ilaobai 關醬；616已找到必必力

17、，表內存儲位置,6查找次數(shù) 請輸入要查找的人名（輸入"表示結束程序）;lu加關腕君S33已找到卬電，表內存儲位置 45,查揶次數(shù)：1 請輸入要查找的人名（輸入J+戶表示結束程序）：宣逅而氧 舞字；743已找到="he。表內存儲位置111,查找瀏K” 請輸入要查找的人名（輸入表示結束程序）;huy顯hou 關金字，w92已找到huyazhou,我內存儲位置,科查找次數(shù);1 請輸入要查找的人名（輸入小林”表示結束程序）：介 美燧字 403已找到ab皿表內存鐳位置37*查或次數(shù)：1 請輸入要查找的人名（輸入樣法結耒程序）：桂3運 美潸字：624已找到臉:詁.表內存儲位置：14.查

18、找次數(shù)：1 請輸入要杳找的人名（輸入氣料”表示結束程序）:taciFi ji 關聆 755已找到tagiji,表內存儲位置.2當查找次教：1 請輸入要查找的人名（輸入氣鏟'表示結束程序）:哂mgkun 關鏈字：763已找到陶ngk皿 表內希信格置：2,善樂次數(shù):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與上方的哈希表進行對比完全匹配。右名名名名名主 藺哈希表建表完成輸入要查找的人名（輸入*產(chǎn)表示結束程序）iaoli 地字：G4G匕北至表廣I百茵空置：3G,直技次數(shù)、二輸入要查捕的人名（輸入"比料"表7F結束程序）：zhuangshuar.gshuang 鍵字：1940已找到whuwn葬himigshuMng,表內存儲位置：54,查找次數(shù)：1 請輸入要

20、查找的人名（軸入“ *產(chǎn)表不結束林序J;心口出 爭字 616已找到1羽此城，表內存儲位置, 0直戰(zhàn)次數(shù)二L 清輸入要查找的人名常人“串神”表示結束程序）：lujia 廷字：533已找到之，表內存儲位置：器，直找次敷：1 青輸入要查找的人名（輸入“田”表示結束程序）： xiadhei關健宇：743日找到表內存儲位置；1L查找軟數(shù)門 清輸入要查找國人名（輸入氣/"我示結束程序”huy口工hou 八度字四三匕找到hu?事工hmi,寺內存儲泣瓦 迪 善裝次數(shù)：1 清輸入要查找的人名獺入.杪產(chǎn)表示結束程序）：近二 褲字：403已找到丁里,裝內存儲位置：戶,二找字數(shù)：1 清輸入要查找的人名（輸入

21、氣*戶表示結束程序）也犯近 入 624 Bhaojie,表內薦襦應望14,杳我次數(shù);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,查找次數(shù)U 情輸入要查找的人名【輸入“*”表示結束程的：Ehuangshuangshuing 關鍵字；1946已找到zhumgshu&n耳shumF，表內存儲隹置;E4.查找次數(shù)：1 著輸入要查找的人名（輸A仃3表示結束程序）:1二川記鍵字i 1臼匕找到laohwi,莪內存儲位置卜吼查找次數(shù);1請輸入要查找的人名（輸入F*產(chǎn)表示結束程序）rlujia 隹腌字，522已找到1旬匕 袤內存儲位置，西 查找次數(shù)J 請輸入要杳找的人名（揄入“林”表示結耒程序）: Tii achei關林字：M3已找到油anhRi.古內存儲位置 1L杳指次數(shù)：1請輸入賽杳找的人名（輸入表示結束程序）:huyazhou 美鬼宅893已找在Jhup箍hou.表內在隔起置339,番也次數(shù):1 請輸入要查找的人名（輸入產(chǎn)