哈希表實(shí)驗(yàn)報(bào)告

1、實(shí)習(xí)報(bào)告題目：設(shè)計(jì)一個(gè)哈希表，完成相應(yīng)的建表和查表程序2016.12.04班級(jí)： 1503013 姓名：李睿元 學(xué)號(hào)：完成日期：一、需求分析1. 假設(shè)人名為中國(guó)人名的漢語(yǔ)拼音形式；2. 待填入哈希表的姓名共有30 個(gè)，去平均查找長(zhǎng)度的上限為 2 ；3. 哈希函數(shù)用除留余數(shù)法構(gòu)造，用偽隨機(jī)探測(cè)再散列法處理沖突；4. 取讀者周圍較熟悉的 30 個(gè)人的姓名。二、概要設(shè)計(jì)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/ 隨機(jī)數(shù)值（ define MAX 30/ 人數(shù)（ define hashlen 61/ 哈希表長(zhǎng)2. 主要函數(shù)的實(shí)現(xiàn)：（ 1）哈希函數(shù)：int Hash（int key）（ 2）關(guān)鍵字獲得：int GetKey（char str）（ 3）文件流中讀取姓名：void GetName（NodeList &L,int i,FILE* fp）（ 4）哈希表的初始化：void InitialHashTable（HashTable &

3、amp;ht）（ 5）偽隨機(jī)探測(cè)序列的生成：void CreatConfilctArray（int n）（ 6）哈希表的生成：void CreatHashTable(HashTable &ht,NodeList L,int* n)（ 7)哈希表的查詢：void SearchHashTable(HashTable ht,int* n,char get_name)三、詳細(xì)設(shè)計(jì)#include <stdio.h>#include <stdlib.h>#include <string.h># define P 61/ 隨機(jī)數(shù)值# define MAX 30/

4、 人數(shù)# define hashlen 61/ 哈希表長(zhǎng)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(" 請(qǐng)以拼音形式輸入第 %d 個(gè)姓名 :",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表內(nèi)存儲(chǔ)位置: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表內(nèi)存儲(chǔ)位置:i+;void SearchHashTable(HashTable ht,int* n,char get_name)/printf(" 請(qǐng)輸入要查詢的姓名： ");/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(" 表中未找到無(wú)此人！ n");break;else if(hth.key=k)printf("已找到 s,表內(nèi)存儲(chǔ)位置：dn",get_name,h);break;elsep+;h=np;*/if(=NULL)printf(" 表中未找到無(wú)此人！ n");break;else if(strcmp(,get_name)=0)printf("已找到 s,表內(nèi)存儲(chǔ)位置：d,查找次數(shù)：dn",get_name,h,s_time);break;elsep+;

10、h=(t+np)%hashlen;s_time+;int main()/ printf(" 請(qǐng)輸入建表所需的三十個(gè)人名！ 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(" 請(qǐng)輸入要查找的人名(輸入“* ”表示結(jié)束程序):");scanf("%s",get_name);printf(" 關(guān)鍵字： %d ",GetKey(get_name);if(strcmp(get_name,"*")=0)break;SearchHashTable(ht,rand_n,g

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

14、uyazhou keyfi； 393表內(nèi)存儲(chǔ)位器39 taosiji keytti 755表內(nèi)布僧位置：23 hahu iey§! 422表內(nèi)存儲(chǔ)位翼士 56 along keyUi 529去為存儲(chǔ)住置：41 abao Key值：403表內(nèi)存儲(chǔ)位置：37 hukun Ht；“ 555表內(nèi)審港住再二47 vangkjn kcy（|； 763表內(nèi)存儲(chǔ)位置；2 weiwei ks*值：BSC蓑內(nèi)存桶位置:20 haojie key值：624表內(nèi)方福位置：14哈希恚建表無(wú)屬鬲輸入要查找的父名（榆人雙i表示結(jié)束程序）;即駐un753已找到4此kun,關(guān)內(nèi)存楮住望2,查冊(cè)次數(shù)：9 請(qǐng)輸入要查找的

15、人名（輸入"*"表示結(jié)束程序）rhicjie之糖字. 624已找到hao如.表內(nèi)存儲(chǔ)位置，14.查找次數(shù)T 胃輸入要杳找的人名（輸入小樣"表示結(jié)束程序工九口3： 隹遑李，616 F,找到lanh*,表內(nèi)存儲(chǔ)位置：6,杳找就數(shù)：1 請(qǐng)輸入方查找的人名（輸入“*”表示結(jié)束程序）:hahahaha 艮藤宇：804表中未找到無(wú)此大！請(qǐng)輸入要查找的人名（輔人“杵*”表示結(jié)束程序）;*Process exited after IE. 06 seconds with return value 0六、測(cè)試數(shù)據(jù)1 .挑選表中已有的十個(gè)姓名進(jìn)行測(cè)試(xiaoli,zhuangshua

16、ngshuang,laobai,lujia,xiaohei,huyazhou,abao,haojie,taosiji,wangkun )府 Dtt6&JX.4ha ihta b I e, exe X哈希表建表無(wú)成_二_一二二一一請(qǐng)輸入要查找的人名（輸A表示結(jié)束程序）：工iwHi理 G駁已找到xii,表內(nèi)存餡位置 3&,查找次數(shù);1 謂也A要直找的人空!輸入表不結(jié)束程.序？:產(chǎn)叫i呼至忸langstm3期， 關(guān)廷宇！ 1945己找到whiLian瑜Liangshumg,表內(nèi)存儲(chǔ)位置；54,直找次數(shù)：1 請(qǐng)輸入要查找的人名輸入力表不結(jié)束程序）ilaobai 關(guān)醬；616已找到必必力

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

18、找次數(shù)：1 請(qǐng)輸入要杳找的人名（輸入氣料”表示結(jié)束程序）:taciFi ji 關(guān)聆 755已找到tagiji,表內(nèi)存儲(chǔ)位置.2當(dāng)查找次教：1 請(qǐng)輸入要查找的人名（輸入氣鏟'表示結(jié)束程序）:哂mgkun 關(guān)鏈字：763已找到陶ngk皿 表內(nèi)希信格置：2,善樂(lè)次數(shù):9 請(qǐng)輸入要查找的人名（輸入“林”表示結(jié)束程序）：*'recess exited after 37* 49 seconds with return value 0：41abao V 日 y值; 403表內(nèi)存儲(chǔ)位真:37 hukun key值; 555表內(nèi)存儲(chǔ)位置；47 wanjkuii key值： 763表內(nèi)存儲(chǔ)位置i

19、Z vaiwsi koyfii 65C表內(nèi)存福住置一20 haoj i s ksyfi> S24表內(nèi)薦席位置 14along keyla： 52g P Dr1 .fQrsXha c Ha b I e. ev &X與上方的哈希表進(jìn)行對(duì)比完全匹配。右名名名名名主 藺哈希表建表完成輸入要查找的人名（輸入*產(chǎn)表示結(jié)束程序）iaoli 地字：G4G匕北至表廣I百茵空置：3G,直技次數(shù)、二輸入要查捕的人名（輸入"比料"表7F結(jié)束程序）：zhuangshuar.gshuang 鍵字：1940已找到whuwn葬himigshuMng,表內(nèi)存儲(chǔ)位置：54,查找次數(shù)：1 請(qǐng)輸入要

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

21、氣*戶表示結(jié)束程序）也犯近 入 624 Bhaojie,表內(nèi)薦襦應(yīng)望14,杳我次數(shù);1 清輸入要查找的人名（輸入“*4'表示結(jié)束程序）：tao=iji, ffWQ名名名名along keyll： bZU：41abao 4eyii ： 403表內(nèi)存儲(chǔ)位置：37 hukun key值；555商為存儲(chǔ)位置；47 vangk'jn keyfi： 7E3表內(nèi)存儲(chǔ)但置：2 vrelvel teyfi： S50表內(nèi)存儲(chǔ)便置；20 haojie key值：&24表內(nèi)存精位置：14哈希表建表完成情輸入要查找的人名（輸入J”戶表示結(jié)束程序）：xi«li 關(guān)童字：646已找到xiH

22、,表內(nèi)存儲(chǔ)應(yīng)置：36,查找次數(shù)U 情輸入要查找的人名【輸入“*”表示結(jié)束程的：Ehuangshuangshuing 關(guān)鍵字；1946已找到zhumgshu&n耳shumF，表內(nèi)存儲(chǔ)隹置;E4.查找次數(shù)：1 著輸入要查找的人名（輸A仃3表示結(jié)束程序）:1二川記鍵字i 1臼匕找到laohwi,莪內(nèi)存儲(chǔ)位置卜吼查找次數(shù);1請(qǐng)輸入要查找的人名（輸入F*產(chǎn)表示結(jié)束程序）rlujia 隹腌字，522已找到1旬匕 袤內(nèi)存儲(chǔ)位置，西 查找次數(shù)J 請(qǐng)輸入要杳找的人名（揄入“林”表示結(jié)耒程序）: Tii achei關(guān)林字：M3已找到油anhRi.古內(nèi)存儲(chǔ)位置 1L杳指次數(shù)：1請(qǐng)輸入賽杳找的人名（輸入表示結(jié)束程序）:huyazhou 美鬼宅893已找在Jhup箍hou.表內(nèi)在隔起置339,番也次數(shù):1 請(qǐng)輸入要查找的人名（輸入產(chǎn)