哈希表的設(shè)計與實現(xiàn)

/合肥學院計算機科學和技術(shù)系課程設(shè)計報告2007～2008學年第2學期課程數(shù)據(jù)結(jié)構(gòu)和算法課程設(shè)計名稱哈希表的設(shè)計和實現(xiàn)學生姓名學號0604011026專業(yè)班級06計科(1)指導老師2008年9月課程設(shè)計題目:（哈希表的設(shè)計和實現(xiàn)的問題）設(shè)計哈希表實現(xiàn)電話號碼查詢系統(tǒng)。設(shè)計程序完成以下要求：（1）設(shè)每個記錄有下列數(shù)據(jù)項：電話號碼、用戶名、地址；（2）從鍵盤輸入各記錄，分別以電話號碼和用戶名為關(guān)鍵字建立哈希表；（3）接受再哈希法解決沖突；（4）查找并顯示給定電話號碼的記錄；（5）查找并顯示給定用戶的記錄。問題分析和任務(wù)定義問題分析 要完成如下要求：設(shè)計哈希表實現(xiàn)電話號碼查詢系統(tǒng)。實現(xiàn)本程序須要解決以下幾個問題：如何設(shè)計一個結(jié)點使該結(jié)點包括電話號碼、用戶名、地址。如何分別以電話號碼和用戶名為關(guān)鍵字建立哈希表。如何利用再哈希法解決沖突。如何實現(xiàn)用哈希法查找并顯示給定電話號碼的記錄。如何查找并顯示給定用戶的記錄。任務(wù)定義由問題分析知，本設(shè)計主要要求分別以電話號碼和用戶名為關(guān)鍵字建立哈希表，并實現(xiàn)查找功能。所以本設(shè)計的核心問題是如何解決散列的問題，亦即設(shè)計一個良好的哈希表。由于結(jié)點的個數(shù)無法確認，并且假如接受線性探測法散列算法，刪除結(jié)點會引起“信息丟失”的問題。所以接受鏈地址法散列算法。接受鏈地址法，當出現(xiàn)同義詞沖突時，運用鏈表結(jié)構(gòu)把同義詞鏈接在一起，即同義詞的存儲地址不是散列表中其他的空地址。首先，解決的是定義鏈表結(jié)點，在鏈地址法中，每個結(jié)點對應(yīng)一個鏈表結(jié)點，它由三個域組成，而由于該程序須要分別用電話號碼和用戶名為關(guān)鍵字建立哈希表，所以該鏈表結(jié)點它是由四個域組成.name[8]、num[11]和address[20]都是char浮點型，輸入輸出都只能是浮點型的。接受鏈地址法，其中的全部同義詞構(gòu)成一個單鏈表，再由一個表頭結(jié)點指向這個單鏈表的第一個結(jié)點。這些表頭結(jié)點組成一個一維數(shù)組，即哈希表。數(shù)組元素的下標對應(yīng)由散列函數(shù)求出的散列地址。拉鏈法處理沖突的散列表結(jié)構(gòu)：

3、主程序分析本題目最主要的要求是設(shè)計散列函數(shù)，本程序須要設(shè)計兩個散列函數(shù)才能解決問題，程序須要分別為以電話號碼和用戶名為關(guān)鍵字建立哈希表。所以要分別以用戶名、號碼為關(guān)鍵字建立兩個散列函數(shù)，詳細思路為：對于以號碼為關(guān)鍵字的散列函數(shù)，是將十一個數(shù)字全部相加，然后對20求余。得到的數(shù)作為地址。對于以用戶名為關(guān)鍵字的散列函數(shù)，是將全部字母的ASCLL碼值相加，然后對20求余。要添加用戶信息，即要有實現(xiàn)添加結(jié)點的功能的函數(shù)，所以要設(shè)計一個必需包括一個輸入結(jié)點信息、添加結(jié)點的函數(shù)；要實現(xiàn)查找函數(shù)，則必需包括一個查找結(jié)點的函數(shù)；另外還有一個必不行少的就是運行之后要有一個主菜單，即要設(shè)計一個主函數(shù)（main()）。4、測試數(shù)據(jù)的選擇最終，程序完成后要對程序進行編譯調(diào)試，執(zhí)行后要選擇數(shù)據(jù)進行測試，這里選擇的測試數(shù)據(jù)為：1、姓名：張三電話號碼：地址：合肥2、姓名：Jack電話號碼：地址：Shanghai三、概要設(shè)計和數(shù)據(jù)結(jié)構(gòu)選擇本設(shè)計涉及到的數(shù)據(jù)結(jié)構(gòu)為：哈希表。要求輸入電話號碼、用戶名、地址三個信息，并要求分別以電話號碼和用戶名為關(guān)鍵字進行查找，所以本問題要用到兩個哈希函數(shù)，進行哈希查找。在鏈地址法中，每個結(jié)點對應(yīng)一個鏈表結(jié)點，它由三個域組成，而由于該程序須要分別用電話號碼和用戶名為關(guān)鍵字建立哈希表，所以該鏈表結(jié)點它是由四個域組成，鏈地址法結(jié)點結(jié)構(gòu)如圖：name[8]num[11]address[20]next其中name[8]和num[11]是分別為以電話號碼和用戶名為關(guān)鍵字域，存放關(guān)鍵字（key）；address[20](data)為結(jié)點的數(shù)據(jù)域，用來存儲用戶的地址。Next指針是用來指向下一個結(jié)點的地址。主要算法的流程圖如下：以號碼為關(guān)鍵字的Hash()函數(shù)流程圖取整型num[2]賦給key結(jié)束Key=key%20Key=key+(int)num[i]i++i從3起先取num[i]!=0開始取整型num[2]賦給key結(jié)束Key=key%20Key=key+(int)num[i]i++i從3起先取num[i]!=0開始以姓名為關(guān)鍵字的Hash()函數(shù)流程圖取整型name[0]賦給key2結(jié)束Key2=key%20Key2+=name[i]i++i從0起先取name[i]不為空開始取整型name[0]賦給key2結(jié)束Key2=key%20Key2+=name[i]i++i從0起先取name[i]不為空開始添加結(jié)點信息流程圖:利用用戶名為關(guān)鍵字插入拉鏈法處理沖突調(diào)用hash()函數(shù)調(diào)用hash()函數(shù)Newname指向newphoneNewphone=input()結(jié)束申請新的結(jié)點newphone,newname即新的號碼和名字起先申請專利起先利用用戶名為關(guān)鍵字插入拉鏈法處理沖突調(diào)用hash()函數(shù)調(diào)用hash()函數(shù)Newname指向newphoneNewphone=input()結(jié)束申請新的結(jié)點newphone,newname即新的號碼和名字起先按姓名查找流程圖:q不為空結(jié)束輸出無記錄輸出相應(yīng)記錄q=q->nextq不為空調(diào)用hash()函數(shù)中新結(jié)點q指向phone[key]->next起先q不為空結(jié)束輸出無記錄輸出相應(yīng)記錄q=q->nextq不為空調(diào)用hash()函數(shù)中新結(jié)點q指向phone[key]->next起先按號碼查找流程圖:起先調(diào)用hash2()函數(shù)中新結(jié)點q指向phone[key]->nextq不為空q=q->nextq不為空輸出無記錄輸出相應(yīng)記錄結(jié)束起先調(diào)用hash2()函數(shù)中新結(jié)點q指向phone[key]->nextq不為空q=q->nextq不為空輸出無記錄輸出相應(yīng)記錄結(jié)束主程序流程圖開開始Main()初始化散列鏈表（1）并為其動態(tài)支配內(nèi)存空間初始化散列鏈表（2）并為其動態(tài)支配內(nèi)存空間Menu（）主菜單輸入選擇選擇1選６選7查找號碼find()查找用戶find2()輸出結(jié)果輸出結(jié)果選擇2選擇0選擇3選擇4選擇5進行姓名散列l(wèi)ist2()姓名散列結(jié)果添加記錄apend()退出系統(tǒng)return0進行號碼散列l(wèi)ist()清空creat();creat2()列表已清空號碼散列結(jié)果結(jié)束四、詳細設(shè)計和編碼首先定義結(jié)點結(jié)構(gòu)體類型，在鏈地址法中，每個結(jié)點對應(yīng)一個鏈表結(jié)點，它由三個域組成，而由于該程序須要分別用電話號碼和用戶名為關(guān)鍵字建立哈希表，所以該鏈表結(jié)點它是由四個域組成，鏈地址法結(jié)點結(jié)構(gòu)如圖：name[8]num[11]address[20]next其中name[8]和num[11]是分別為以電話號碼和用戶名為關(guān)鍵字域（key），存放關(guān)鍵字；address[20]為結(jié)點的數(shù)據(jù)域(data)，用來存儲用戶的地址信息。next指針是用來指向下一個結(jié)點的地址。unsignedintkey和unsignedintkey2分別被定義為電話號碼和用戶名關(guān)鍵字。程序的主要模塊如下：************************程序部分源代碼*************************建立節(jié)點structnode//建節(jié)點{charname[8],address[20];//節(jié)點中要包含用戶名，用戶地址，電話號碼以及指向下一個結(jié)點的指針charnum[11];node*next;};typedefnode*pnode;//typedef可以為一個已有的數(shù)據(jù)類型聲明多個別名，這里為該類型聲明白兩個指針typedefnode*mingzi;node**phone;node**nam;node*a;對哈希函數(shù)的定義本程序要設(shè)計兩個hash（）函數(shù)，分別對應(yīng)電話號碼和用戶名。本設(shè)計中對散列函數(shù)選擇的是除留余數(shù)法，即對關(guān)鍵字進行模運算，將運算結(jié)果所得的余數(shù)作為關(guān)鍵字（或結(jié)點）的存儲地址，即H（key）=keymodp,本設(shè)計中p取20,然后將計算出來的數(shù)作為該結(jié)點的地址賦給key。詳細方法如下：以電話號碼為關(guān)鍵字建立哈希函數(shù)hash(charnum[11])。以用戶名為關(guān)鍵字建立哈希函數(shù)hash2(charname[8])。利用強制類型轉(zhuǎn)換，將用戶名的每一個字母的ASCLL碼值相加并且除以20后的余數(shù)。將計算出來的數(shù)作為該結(jié)點的地址賦給key2。************************程序部分源代碼*************************a)voidhash(charnum[11])//以電話號碼為關(guān)鍵字建立哈希函數(shù){key=(int)num[2];while(num[i]!=NULL){key+=(int)num[i];i++;}key=key%20;}b)voidhash2(charname[8])//以用戶名為關(guān)鍵字建立哈希函數(shù){inti=1;key2=(int)name[0];while(name[i]!=NULL){key2+=(int)name[i];i++;}key2=key2%20;}然后，建立結(jié)點，并添加結(jié)點，利用鏈地址法解決沖突。建立結(jié)點應(yīng)包括動態(tài)申請內(nèi)存空間。向結(jié)點中輸入信息。同時將結(jié)點中的next指針等于null。添加結(jié)點，首先須要利用哈希函數(shù)計算出地址即關(guān)鍵字，其次將該結(jié)點插入以關(guān)鍵字為地址的鏈表后，當然由于分別以用戶名和電話號碼為關(guān)鍵字，所以分兩種狀況，假如以用戶名為關(guān)鍵字則調(diào)用voidhash2(charname[8])函數(shù)，并且將結(jié)點插入對應(yīng)的散列鏈表中，假如以電話號碼為關(guān)鍵字則調(diào)用voidhash(charnum[11])函數(shù)，并且將結(jié)點插入對應(yīng)的散列鏈表中。并且，須要兩個建立散列鏈表的函數(shù)，分別動態(tài)申請確定的空間，用于動態(tài)申請散列鏈表。voidcreate()用來動態(tài)創(chuàng)建以電話號碼為關(guān)鍵字的鏈表數(shù)組，voidcreate2()用來動態(tài)創(chuàng)建以用戶名為關(guān)鍵字的鏈表數(shù)組。************************程序部分源代碼*************************voidcreate()//新建號碼節(jié)點{inti;phone=newpnode[20];//動態(tài)創(chuàng)建對象數(shù)組for(i=0;i<20;i++){phone[i]=newnode;phone[i]->next=NULL;}}voidcreate2()//新建姓名節(jié)點{inti;nam=newmingzi[20];for(i=0;i<20;i++){nam[i]=newnode;nam[i]->next=NULL;}同樣，須要兩個顯示鏈表的函數(shù)，利用for循環(huán)和while語句將表中信息按要求輸出來。3．哈希查找想要實現(xiàn)查找功能，同樣須要兩個查找函數(shù)，無論以用戶名還是以電話號碼為關(guān)鍵字，首先，都須要利用hash函數(shù)來計算出地址。再通過比對，假如是以電話號碼為關(guān)鍵字，比較其電話號碼是否相同，假如相同則輸出該結(jié)點的全部信息，假如以用戶名為關(guān)鍵字，則比較用戶名是否相同，假如相同則輸出該結(jié)點的全部信息。假如找不到和之對應(yīng)相同的，則輸出“無此記錄”。************************程序部分源代碼*************************a)、voidfind(charnum[11])//在以電話號碼為關(guān)鍵字的哈希表中查找用戶信息{ hash(num);node*q=phone[key]->next;while(q!=NULL){if(strcmp(num,q->num)==0)break;q=q->next;}if(q) printf("%s_%s_%s\n",q->name,q->address,q->num);elseprintf("無此記錄\n");}b)、voidfind2(charname[8])//在以用戶名為關(guān)鍵字的哈希表中查找用戶信息{hash2(name);node*q=nam[key2]->next;while(q!=NULL){if(strcmp(name,q->name)==0)break;q=q->next;}if(q) printf("%s_%s_%s\n",q->name,q->address,q->num);elseprintf("無此記錄\n");}主函數(shù)本程序須要創(chuàng)建一個主菜單和一個主函數(shù)，主菜單便于用戶的運用，主函數(shù)中，包括全部功能對應(yīng)的數(shù)值，使之和主菜單相對應(yīng)。主函數(shù)界面設(shè)計如下添加記錄查找記錄姓名散列號碼散列清空記錄退出系統(tǒng)4、程序數(shù)據(jù)測試當程序設(shè)計出來后的測試數(shù)據(jù)為：1、姓名：張三電話號碼：地址：合肥2、姓名：Jack電話號碼：地址：Shanghai首先鍵入0,添加結(jié)點信息,然后按1進行查找,分別進行號碼和姓名查找,最終可在主菜單中，選擇號碼散列和姓名散列,由此查看程序運行結(jié)果。至此，就解決了哈希表的設(shè)計和實現(xiàn)算法可能出現(xiàn)的各種問題，那么依據(jù)以上思路以及對問題的分析和對出現(xiàn)狀況的解決則可以寫出源程序。五、上機調(diào)試1、語法錯誤及修改：程序是分塊寫的,調(diào)試時可以運用分步調(diào)試的方式進行,以便能查找看程序是在哪出錯了。本算法運用了鏈表結(jié)構(gòu)和鏈地址法解決沖突的問題，在以姓名為關(guān)鍵字的哈希表中要留意涉及ASCLL碼的類型轉(zhuǎn)換，要留意輸出不能是“%d”，否則不能輸出結(jié)果。編寫程序時要多留意程序中各種指針的運用，還有各類變量的定義，函數(shù)的運用。這些問題均可以依據(jù)編譯器的警告提示，對應(yīng)的將其解決。2、邏輯問題修改和調(diào)整：鏈表結(jié)構(gòu)方法雖然便利了運行，但是增加了對算法過程的相識難度。在本程序中每一個函數(shù)中都須要涉及到指針的操作。所以須要細致分析函數(shù)中的指針指向。在插入結(jié)點，查找結(jié)點時尤為突出。對于主菜單和主函數(shù)的對應(yīng)，確定要一樣，這樣才能保證運行時不會出錯。 3、時間，空間性能分析：散列法本質(zhì)上是一種通過關(guān)鍵字干脆計算存儲地址的方法。在志向狀況下，散列函數(shù)可以把結(jié)點勻整地分布到散列表中，不發(fā)生沖突，則查找過程無需比較，其時間困難度O（n）=1。但在實際運用過程中，為了將范圍廣泛的關(guān)鍵字映射到一組連續(xù)的存儲空間，往往會發(fā)生同義詞沖突，這時在查找過程中就須要進行關(guān)鍵字比較。因此散列法的查找性能取決于3個因素：散列函數(shù)、沖突處理方法和填充因子。接受鏈地址法，可以從根本上杜絕“二次聚集”的發(fā)生，從而提高散列表的勻整度，提高查找性能，不過也會“奢侈”一部分散列表的空間。當散列函數(shù)和沖突處理方法固定時，散列法的查找性能就取決于散列表的填充因子。填充因子a=表中已有的結(jié)點數(shù)/表的長度。填充因子a標記表的添滿程度。很明顯，a越小則發(fā)生沖突的機會就越?。环粗?，a越大沖突的機會就越大，查找的性能也就越低。哈希表鏈地址法查找成功的平均查找長度SNc=1+a/2。鏈地址法查找不成功的平均查找長度Un滿足：Unc=a+e-a.由以上可以看出，散列表的平均查找長度是填充因子的函數(shù)，和散列表的長度沒有關(guān)系，因此在實際應(yīng)用中，我們應(yīng)當選擇一個適當?shù)奶畛湟蜃?，以便把平均查找長度限制在一個盡量小的范圍內(nèi)。 4、閱歷和體會：本設(shè)計用到的數(shù)據(jù)結(jié)構(gòu)是哈希表，并且要實現(xiàn)查找功能，在剛拿到本問題時，我首先想到的查找方法是依次查找，這就沒有用到哈希表，而本設(shè)計要求必需運用哈希表這一存儲結(jié)構(gòu)，另外本設(shè)計也可以用C++中的類來解決，可以用類來設(shè)計哈希表。六、用戶運用說明 本程序運行過程時帶有提示性語句，由于address[20]、name[8]和num[11]可以看出地址可輸入的最大字符數(shù)是20，姓名可輸入的最大字符數(shù)是8，電話號碼都為11位。在輸入的時候，用戶特別留意電話號碼的位數(shù)。實現(xiàn)添加結(jié)點，將信息從鍵盤輸入，然后依據(jù)屏幕的提示進行操作，由此，本設(shè)計的要求就可以被用戶實現(xiàn)了。七、測試結(jié)果程序主菜單:添加記錄:分別按電話號碼和姓名查找:分別輸出按姓名和號碼散列的結(jié)果:清空記錄:八、參考書目譚浩強，《C語言程序設(shè)計》，北京：清華高校出版社，2005年7月第3版。王昆侖，李紅，《數(shù)據(jù)結(jié)構(gòu)和算法》，中國鐵道出版社，2007年6月第1版。李春葆，數(shù)據(jù)結(jié)構(gòu)題集，北京：清華高校出版社，1992年2月第一版。九、附錄************************程序源代碼**************************#include<stdio.h>#include<string.h>#defineNULL0unsignedintkey;//定義兩個關(guān)鍵字unsignedintkey2;int*p;structnode//建節(jié)點每個結(jié)點包括用戶姓名、地址、電話號碼、以及指向下一個結(jié)點的指針{charname[8],address[20];charnum[11];node*next;};typedefnode*pnode;//typedef可以為一個已有的數(shù)據(jù)類型聲明多個別名，這里為該類型聲明白兩個指針typedefnode*mingzi;node**phone;node**nam;node*a;voidhash(charnum[11])//哈希函數(shù)，以電話號碼為關(guān)鍵字建立哈希函數(shù)//哈希函數(shù)的主旨是將電話號碼的十一位數(shù)字全部加起來{inti=3;key=(int)num[2];while(num[i]!=NULL){key+=(int)num[i];i++;}key=key%20;}voidhash2(charname[8])//哈希函數(shù)以用戶名為關(guān)鍵字建立哈希函數(shù) //利用強制類型轉(zhuǎn)換，將用戶名的每一個字母的ASCLL碼值相加并且除以20后的余數(shù){inti=1;key2=(int)name[0];while(name[i]!=NULL){key2+=(int)name[i];i++;}key2=key2%20;}node*input()//輸入節(jié)點信息，建立結(jié)點，并將結(jié)點的next指針指空{(diào)node*temp;temp=newnode;//new的功能是動態(tài)支配內(nèi)存，語法形式：new類型名T（初值列表temp->next=NULL;printf("請輸入姓名:\n");scanf("%s",temp->name);printf("輸入地址：\n");scanf("%s",temp->address);printf("輸入電話：\n");scanf("%s",temp->num);returntemp;//對于指針類型返回的是地址}intapend()//添加節(jié)點{node*newphone;node*newname;newphone=input();newname=newphone;newphone->next=NULL;newname->next=NULL;hash(newphone->num);//利用哈希函數(shù)計算出對應(yīng)關(guān)鍵字的存儲地址hash2(newname->name);newphone->next=phone[key]->next;//利用電話號碼為關(guān)鍵字插入phone[key]->next=newphone;//是接受鏈地址法，拉鏈法處理沖突的散列表結(jié)構(gòu)newname->next=nam[key2]->next;//利用用戶名為關(guān)鍵字插入nam[key2]->next=newname;return0;}voidcreate()//新建節(jié)點{inti;phone=newpnode[20];//動態(tài)創(chuàng)建對象數(shù)組for(i=0;i<20;i++){phone[i]=newnode;phone[i]->next=NULL;}}voidcreate2()//新建節(jié)點{inti;nam=newmingzi[20];for(i=0;i<20;i++){nam[i]=newnode;nam[i]->next=NULL;}}voidlist()//顯示列表{inti;node*p;for(i=0;i<20;i++){p=phone[i]->next;while(p){ printf("%s_%s_%s\n",p->name,p->address,p->num);p=p->next;}}}voidlist2()//顯示列表{inti;node*p;for(i=0;i<20;i++){p=nam[i]->next;while(p){ printf("%s_%s_%s\n",p->name,p->address,p->num);p=p->next;}}}voidfind(charnum[11])//在以電話號碼為關(guān)鍵字的哈希表中查找用戶信息{hash(num);node*q=phone[key]->next;while(q!=NULL){if(strcmp(num,q->num)==0)break;q=q->next;}if(q) print