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

1、歹EASTCHINAINSTITUTEOFTECHNOLOGY數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告哈希表問題姓名：鄭健專業(yè)：信息管理與信息系統(tǒng)班級：083221學(xué)號：08322126指導(dǎo)老師：劉自強(qiáng)設(shè)計(jì)時(shí)間：2010年5月7日二，設(shè)計(jì)要求與分析2.1 課程設(shè)計(jì)要求22.2 程序分析2三，數(shù)據(jù)結(jié)構(gòu)選擇與概要設(shè)計(jì)1 數(shù)據(jù)結(jié)構(gòu)選擇31 Hash函數(shù)流程圖4-9四，設(shè)計(jì)算法建立節(jié)點(diǎn)10哈希函數(shù)的定義10哈希查找11程序測試11五，使用說明與測試結(jié)果使用說明11主菜單截圖12添加記錄截圖12查找截圖13散列結(jié)果截圖13清空記錄截圖14六，程序源代碼及實(shí)驗(yàn)心得源代碼14-18實(shí)驗(yàn)心得19計(jì)評分表20本設(shè)計(jì)主要要求分別以電

2、話號碼和用戶名為關(guān)鍵字建立哈希表，并實(shí)現(xiàn)查找功能。所以本設(shè)計(jì)的核心問題是如何解決散列的問題，由于結(jié)點(diǎn)的個(gè)數(shù)無法確認(rèn)，并且如果采用線性探測法散列算法，刪除結(jié)點(diǎn)會引起“信息丟失”的問題。所以采用鏈地址法散列算法。采用鏈地址法，當(dāng)出現(xiàn)同義詞沖突時(shí)，使用鏈表結(jié)構(gòu)把同義詞鏈接在一起。首先，解決的是定義鏈表結(jié)點(diǎn)，在鏈接地址法中，每個(gè)結(jié)點(diǎn)對應(yīng)一個(gè)鏈表結(jié)點(diǎn)，它由三個(gè)域組成，而由于該程序需要分別用電話號碼和用戶名為關(guān)鍵字建立哈希表，所以該鏈表結(jié)點(diǎn)它是由四個(gè)域組成,name8、num11和address20都是char浮點(diǎn)型采用鏈地址法，其中的所有同義詞構(gòu)成一個(gè)單鏈表，再由一個(gè)表頭結(jié)點(diǎn)指向這個(gè)單鏈表的第一個(gè)結(jié)點(diǎn)。

3、這些表頭結(jié)點(diǎn)組成一個(gè)一維數(shù)組，即哈希二，設(shè)計(jì)要求與分析課程設(shè)計(jì)要求設(shè)計(jì)哈希表實(shí)現(xiàn)電話號碼查詢系統(tǒng)。設(shè)計(jì)程序完成以下要求：(1)設(shè)每個(gè)記錄有下列數(shù)據(jù)項(xiàng)：電話號碼、用戶名、地址；(2)從鍵盤輸入各記錄，分別以電話號碼和用戶名為關(guān)鍵字建立哈希表；(3)采用再哈希法解決沖突；(4)查找并顯示給定電話號碼的記錄；(5)查找并顯示給定用戶的記錄。程序分析具體思路為：(1)對于以號碼為關(guān)鍵字的散列函數(shù)，是將十一個(gè)數(shù)字全部相加，然后對20求余。得到的數(shù)作為地址。對于以用戶名為關(guān)鍵字的散列函數(shù)，是將所有字母的ASCLL碼值相加，然后對20求余。(2)要添加用戶信息，即要有實(shí)現(xiàn)添加結(jié)點(diǎn)的功能的函數(shù)，所以要設(shè)計(jì)一個(gè)

4、必須包括一個(gè)輸入結(jié)點(diǎn)信息、添加結(jié)點(diǎn)的函數(shù)；(3)要實(shí)現(xiàn)查找函數(shù)，則必須包括一個(gè)查找結(jié)點(diǎn)的函數(shù)；另外還有一個(gè)必不可少的就是運(yùn)行之后要有一個(gè)主菜單，即要設(shè)計(jì)一個(gè)主函數(shù)(main()。(4)測試數(shù)據(jù)的選擇最后，程序完成后要對程序進(jìn)行編譯調(diào)試，執(zhí)行后要選擇數(shù)據(jù)進(jìn)行測試，這里選擇的測試數(shù)據(jù)為：.姓名：鄭?。浑娫挘?234567;地址：江西九江；.姓名：吳任；電話：2345678;地址：江西南昌；.姓名：黃鑫；電話：3456789;地址：江西上饒；三，數(shù)據(jù)結(jié)構(gòu)選擇與概要設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)選擇本設(shè)計(jì)涉及到的數(shù)據(jù)結(jié)構(gòu)為：哈希表。要求輸入電話號碼、用戶名、地址三個(gè)信息，并要求分別以電話號碼和用戶名為關(guān)鍵字進(jìn)行查找，所

5、以本問題要用到兩個(gè)哈希函數(shù)，進(jìn)行哈希查找。在鏈地址法中，每個(gè)結(jié)點(diǎn)對應(yīng)一個(gè)鏈表結(jié)點(diǎn)，它由三個(gè)域組成，而由于該程序需要分別用電話號碼和用戶名為關(guān)鍵字建立哈希表，所以該鏈表結(jié)點(diǎn)它是由四個(gè)域組成，鏈接地址法結(jié)點(diǎn)結(jié)構(gòu)如圖：name8num11address20next其中name8和num11是分別為以電話號碼和用戶名為關(guān)鍵字域，存放關(guān)鍵字(key);address20(data)為結(jié)點(diǎn)的數(shù)據(jù)域，用來存儲用戶的地址。Next指針是用來指向下一個(gè)結(jié)點(diǎn)的地址。3.2Hash函數(shù)流程圖以號碼為關(guān)鍵字的hash函數(shù)流程圖以姓名為關(guān)鍵字的hash函數(shù)流程圖申請新的結(jié)點(diǎn)newphone,newname即新的號碼和名

6、字Newphone=input()Newname指向newphone調(diào)用hash()函數(shù)調(diào)用hash()函數(shù)拉鏈法處理沖突利用用戶名為關(guān)鍵字插入結(jié)束調(diào)用hash()函數(shù)中新結(jié)點(diǎn)q指向phonekey->nextq=q->next輸出無記/輸出相應(yīng)錄/記錄結(jié)束四，設(shè)計(jì)算法建立節(jié)點(diǎn)structnode(charname8,address20;charnum11;node*next;typedefnode*pnode;可以為一個(gè)已有的數(shù)據(jù)類型聲明多個(gè)別名，這里為該類型聲明了兩個(gè)指針typedefnode*mingzi;node*phone;node*nam;node*a;哈希函數(shù)的定義本

7、程序要設(shè)計(jì)兩個(gè)hash()函數(shù)，分別對應(yīng)電話號碼和用戶名。對關(guān)鍵字進(jìn)行模運(yùn)算，將運(yùn)算結(jié)果所得的余數(shù)作為關(guān)鍵字(或結(jié)點(diǎn))的存儲地址，方法如下：以電話號碼為關(guān)鍵字建立哈希函數(shù)hash(charnum11)。以用戶名為關(guān)鍵字建立哈希函數(shù)hash2(charname8)。利用強(qiáng)制類型轉(zhuǎn)換，將用戶名的每一個(gè)字母的ASCLL碼值相加并且除以20后的余數(shù)。將計(jì)算出來的數(shù)作為該結(jié)點(diǎn)的地址賦給key2ovoidhash(charnum11);/以電話號碼為關(guān)鍵字建立哈希函數(shù)哈希函數(shù)的主旨是將電話號碼的十一位數(shù)字全部加起來(inti=3;key=(int)num2;while(numi!=NULL)(key+=(

8、int)numi;i+;)key=key%20;"/利用強(qiáng)制類型轉(zhuǎn)換，將用戶名的每一個(gè)字母的ASCLL碼值相加并且除以20后的余數(shù)voidhash2(charname8);/哈希函數(shù)以用戶名為關(guān)鍵字建立哈希函數(shù)(inti=1;key2=(int)name0;while(namei!=NULL)(key2+=(int)namei;i+;)key2=key2%20;)哈希查找想要實(shí)現(xiàn)查找功能，同樣需要兩個(gè)查找函數(shù)，無論以用戶名還是以電話號碼為關(guān)鍵字，首先，都需要利用hash函數(shù)來計(jì)算出地址。再通過比對，如果是以電話號碼為關(guān)鍵字，比較其電話號碼是否相同，如果相同則輸出該結(jié)點(diǎn)的所有信息，如果

9、以用戶名為關(guān)鍵字，則比較用戶名是否相同，如果相同則輸出該結(jié)點(diǎn)的所有信息。如果找不到與之對應(yīng)相同的，則輸出“無此記錄”。voidfind(charnum11);/在以電話號碼為關(guān)鍵字的哈希表中查找用戶信息(hash(num);node*q=phonekey->next;while(q!=NULL)(if(strcmp(num,q->num)=0)break;q=q->next;if(q)printf("%s_%s_%sn",q->name,q->address,q->num);elseprintf("無此記錄n");vo

10、idfind2(charname8);/在以用戶名為關(guān)鍵字的哈希表中查找用戶信息(hash2(name);node*q=namkey2->next;while(q!=NULL)(if(strcmp(name,q->name)=0)break;q=q->next;)程序測試首先鍵入0,添加結(jié)點(diǎn)信息，然后按1進(jìn)行查找，分別進(jìn)行號碼和姓名查找，最后可在主菜中，選擇號碼散列和姓名散列，由此查看程序運(yùn)行結(jié)果。至此，就解決了哈希表的設(shè)計(jì)與實(shí)現(xiàn)算法可能出現(xiàn)的各種問題，那么根據(jù)以上思路以及對問題的分析和對出現(xiàn)情況的解決則可以寫出源程序。五，使用說明與測試結(jié)果使用說明由于address20、n

11、ame8和num11可以看出地址可輸入的最大字符數(shù)是20,姓名可輸入的最大字符數(shù)是8,電話號碼都為11位。主菜單截圖5.3添加記錄截圖:錄錄列列錄統(tǒng)山江話7記記系(九電56加找名擔(dān)W3八西入？；番一姓口WHS!C:DOCU1EITSODSETTINGSADIISISTRATOK.添加的內(nèi)容:名，俞久地址工工西上儻片人電話:345678C:DOCUlEJiTSAHDSETTIMGSADiniISTRATOR-.76542打_1-息二信g的時(shí)錄錄列列錄統(tǒng)找班記記系查刃加找名碼空出*出健曹_姓口i靜？任綠野B.1.2.B.4.E.Ld5.5散列結(jié)果截圖1口同Ic*C:DOCUIEirSAHDSETT

12、INGSADIIIIISTRATOR.王口錄錄列列錄統(tǒng)咨四百=記記系列邙粵,t加找名斜空出Ld錄錄列列錄Bs散JJ加找名陰空曾耋萼一姓號情狗z-C:WCU1EHTSANDSETTIMGSkADIIHISTRATOR.六，程序源代碼及實(shí)驗(yàn)心得6.1源代碼#include<stdio.h>#include<string.h>#defineNULL0unsignedintkey;unsignedintkey2;int*p;structnodecharname8,address20;charnum11;node*next;typedefnode*pnode;typedefnod

13、e*mingzi;node*phone;node*nam;node*a;voidhash(charnum11)inti=3;key=(int)num2;while(numi!=NULL)key+=(int)numi;i+；key=key%20;voidhash2(charname8)(inti=1;key2=(int)name0;while(namei!=NULL)(key2+=(int)namei;i+;)key2=key2%20;)node*input()(node*temp;temp=newnode;temp->next=NULL;printf("請輸入姓名：n"

14、;);scanf("%s",temp->name);printf("輸入地址：n");scanf("%s",temp->address);printf("輸入電話：n");scanf("%s",temp->num);returntemp;)intapend()node*newphone;node*newname;newphone=input();newname=newphone;newphone->next=NULL;newname->next=NULL;hash(

15、newphone->num);hash2(newname->name);newphone->next=phonekey->next;phonekey->next=newphone;newname->next=namkey2->next;namkey2->next=newname;return0;)voidcreate()(inti;phone=newpnode20;for(i=0;i<20;i+)(phonei=newnode;phonei卜>next=NULL;)voidcreate2()(inti;nam=newmingzi20;

16、for(i=0;i<20;i+)(nami=newnode;nami->next=NULL;)voidlist()(inti;node*p;for(i=0;i<20;i+)(p=phonei->next;while(p)(printf("%s_%s_%sn",p->name,p->address,p->num);p=p->next;)voidlist2()(inti;node*p;for(i=0;i<20;i+)(p=nami->next;while(p)(printf("%s_%s_%sn",

17、p->name,p->address,p->num);p=p->next;)voidfind(charnum11)hash(num);node*q=phonekey->next;while(q!=NULL)if(strcmp(num,q->num)=0)break;q=q->next;)if(q)printf("%s_%s_%sn",q->name,q->address,q->num);elseprintf("無此記錄n");)voidfind2(charname8)hash2(name);no

18、de*q=namkey2->next;while(q!=NULL)if(strcmp(name,q->name)=0)break;q=q->next;)if(q)printf("%s_%s_%sn",q->name,q->address,q->num);elseprintf("無此記錄n");)voidmenu()/菜單printf("0.添加記錄n");printf("1.查找記錄n");printf("2.姓名散列n");printf("3.號碼

19、散列n");printf("4.清空記錄n");printf("5.退出系統(tǒng)n");)intmain()charnum11;charname8;create();create2();intsel;while(1)(menu();scanf("%d",&sel);if(sel=1)(printf("6號碼查詢，7姓名查詢n");intb;scanf("%d",&b);if(b=6)(printf("請輸入電話號碼：n");scanf("%s&

20、quot;,num);printf("輸出查找的信息：n");find(num);else(printf("請輸入姓名：n");scanf("%s",name);printf("輸出查找的信息：n");find2(name);if(sel=2)printf("姓名散列結(jié)果：n");list2();if(sel=0)printf("請輸入要添加的內(nèi)容：n");apend();if(sel=3)printf("號碼散列結(jié)果：n");list();if(sel=4)printf("列表已清空：n");create();create2();if(sel=6)return0;return0;)6.2實(shí)驗(yàn)心得一周的課程設(shè)計(jì)今天結(jié)束