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

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

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