數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)散列表

計(jì)算機(jī)科學(xué)與技術(shù)系哈希表得設(shè)計(jì)與實(shí)現(xiàn)項(xiàng)目報(bào)告專業(yè)名稱計(jì)算機(jī)科學(xué)與技術(shù)項(xiàng)目課程數(shù)據(jù)結(jié)構(gòu)與算法項(xiàng)目名稱哈希表得設(shè)計(jì)與實(shí)現(xiàn)班級(jí)項(xiàng)目人員錢海峰，鄭秀娟，王傳敏,楊青，凌波實(shí)驗(yàn)日期2015、12、9目錄一.設(shè)計(jì)目得…………3二．問題分析…………3三．設(shè)計(jì)環(huán)境…………3四.人員分配…………3五。詳細(xì)設(shè)計(jì)與編碼…………………4六。實(shí)驗(yàn)分析…………71測(cè)試分析……………………72性能分析……………………11附錄……………………12參考書目………………17一.設(shè)計(jì)目得（1）掌握散列結(jié)構(gòu)與散列函數(shù)得相關(guān)概念（２)掌握散列結(jié)構(gòu)得存儲(chǔ)結(jié)構(gòu)得相關(guān)概念（2）掌握散列沖突得處理方法(3)運(yùn)用散列解決沖突問題。二．問題分析要完成如下要求：設(shè)計(jì)哈希表實(shí)現(xiàn)整數(shù)查詢系統(tǒng).實(shí)現(xiàn)本項(xiàng)目需要解決以下問題：(1）如何設(shè)計(jì)一個(gè)哈希表。（2)如何在哈希表中插入記錄.(３）如何刪除哈希表中得記錄.（4）如何查找并顯示記錄。（5)如何解決沖突問題.三．設(shè)計(jì)環(huán)境⒈硬件:計(jì)算機(jī)每人一臺(tái)。⒉軟件：Windows操作系統(tǒng)與MicrｏsoftＶisualVＣ＋+6、0編譯器.四。人員分配負(fù)責(zé)人負(fù)責(zé)內(nèi)容錢海峰shoｗHａshTａｂle（），meｎu（)鄭秀娟ｉｎsert（)，search（)王傳敏Sanlibｉａｏ、h，main、c,項(xiàng)目文檔楊青Ｈａsｈ()，createHａshTable()凌波dele（）,ｉnｉtHashTable（)五。詳細(xì)設(shè)計(jì)與編碼1、定義結(jié)點(diǎn)結(jié)構(gòu)類型在鏈地址法中，每個(gè)結(jié)點(diǎn)對(duì)應(yīng)一個(gè)鏈表結(jié)點(diǎn)，由３個(gè)域組成,結(jié)構(gòu)如圖9—1所示。其中，ｋeｙ為關(guān)鍵字域，存放結(jié)點(diǎn)關(guān)鍵字；daｔａ為數(shù)據(jù)域，存放結(jié)點(diǎn)數(shù)據(jù)信息;nｅxt為鏈域，存放指向下一個(gè)同義詞結(jié)點(diǎn)得指針.Ｋeydaｔanexｔ圖9—1鏈地址法結(jié)點(diǎn)結(jié)構(gòu)鏈地址數(shù)據(jù)結(jié)構(gòu)類型如下:＃dｅfineMＡX_LＥNGTH5０ｔyｐeｄｅｆstructnodｅ{ iｎtdatａ；?ｓtruｃtnode*ｎext；}EleｍNodｅ；typeｄeｆstrucｔ｛?ElemNodｅ*firｓt；}ElemＨｅadeｒ，HａｓｈＴablｅ[MAX_ＬENＧＴH］;＃ｉncluｄｅ＜ｓtｄio、h>2、對(duì)哈希函數(shù)得定義設(shè)計(jì)一個(gè)Hash（）函數(shù)，本設(shè)計(jì)中對(duì)散列函數(shù)選擇得就是除留余數(shù)法，即對(duì)關(guān)鍵字進(jìn)行模運(yùn)算，將運(yùn)算結(jié)果所得得余數(shù)作為關(guān)鍵字（或結(jié)點(diǎn)）得存儲(chǔ)地址，即i=ｈtｍｏdn，本設(shè)計(jì)ｎ由用戶自己輸入,然后將計(jì)算出來得結(jié)果返回。具體設(shè)計(jì)如下：ｉnｔHａｓh（ｉｎtht)｛?inti；?i=ht%n； rｅturni；｝3、初始化散列鏈表初始化鏈地址散列算法只需要把散列表中所有表頭結(jié)點(diǎn)得指針域置為NULＬ。初始化散列鏈表得算法如下：voｉdinitHaｓｈTabｌｅ(ＨａsｈＴabｌeht，intｎ）｛?inｔi；?ｆor（i＝0；i<ｎ；i＋＋){ ht［ｉ]、first=NULＬ；}｝4、創(chuàng)建哈希表在整個(gè)設(shè)計(jì)中，創(chuàng)建哈希表必須就是第一步要做得，結(jié)點(diǎn)之前應(yīng)先輸入結(jié)點(diǎn)得個(gè)數(shù),利用鏈地址法解決沖突.添加結(jié)點(diǎn)實(shí)際就是調(diào)用了插入結(jié)點(diǎn)函數(shù)insｅrt()，需要利用哈希函數(shù)計(jì)算出地址，其次將結(jié)點(diǎn)插入以關(guān)鍵字為地址得鏈表后。建立結(jié)點(diǎn)應(yīng)包括動(dòng)態(tài)申請(qǐng)內(nèi)存空間，想地址中輸入信息,同時(shí)最后一個(gè)結(jié)點(diǎn)中得nｅｘｔ指針等于NULL.具體實(shí)現(xiàn)如下：inｔcrｅａt(yī)ｅHａsｈＴable（HａshＴabｌeht）{?HａshＴablｅ＊ｐ＝ht；?intad［MAX＿ＬＥNＧTH]=｛０｝;?inti；?prinｔｆ（”請(qǐng)輸入插入個(gè)數(shù)n:"）； scanf(”％d”，＆n）；?printf（"＼n請(qǐng)輸入插入％ｄ個(gè)整數(shù)：＂,n);?fｏr(i＝0；i〈n;i＋+) ?scanf(”%d"，&ａd［i]); ｉniｔHashＴａbｌe(ｐ，n);?for(ｉ=0；i＜n;ｉ＋＋) ?iｎsert（p,ad［ｉ])；?retuｒｎ1；5、散列鏈表插入結(jié)點(diǎn)算法將一個(gè)結(jié)點(diǎn)插入到散列鏈表中,其算法分為以下幾步：根據(jù)結(jié)點(diǎn)關(guān)鍵字計(jì)算散列地址；根據(jù)散列地址找到表頭結(jié)點(diǎn),并將結(jié)點(diǎn)插入到對(duì)應(yīng)得鏈表中.鏈地址法散列表得插入算法如下：vｏｉdinsert(HashＴablehｔ，intele){?ｉｎti; ＥlemNoｄe*ｐ；?i=Hasｈ(ele)； p=(ElemＮode＊)malｌoc（sizeｏf(EｌeｍNode)）；?ｐ—〉ｄaｔa=ele； p-〉next=ht［ｉ]、ｆirｓt;?ｈt［i］、fｉrsｔ=p；｝６、散列鏈表查找結(jié)點(diǎn)算法在散列鏈表中查找一個(gè)結(jié)點(diǎn),其算法分為以下幾步:根據(jù)待查找關(guān)鍵字計(jì)算散列地址；在散列地址所指向得單鏈表中順序查找待查找關(guān)鍵字;如果找到待查關(guān)鍵字,則返回指向該結(jié)點(diǎn)得指針；否則返回ＮＵLＬ。散列鏈表中查找結(jié)點(diǎn)得算法如下：ElemＮｏｄe＊ｓｅａrch（HａsｈTａbleｈt，ｉntｅle){ inｔi;?EｌemＮode＊ｐ; i=Hａsh（ｅle）;?p=hｔ［i］、ｆｉrst；?while（ｐ！=ＮUＬL＆&p－＞data!＝elｅ){?p＝p—〉ｎexｔ； ｝?ｉｆ(p?。剑蜺LＬ) ｛ pｒintf（”數(shù)據(jù)％d得位置為%ｄ\n",ele，i）； reｔurnｐ；?｝?else ｛ prinｔｆ（"哈希表中無%d＼n”，ele）； reｔｕｒｎｐ；?}｝?７、散列鏈表刪除結(jié)點(diǎn)算法在散列表中刪除一個(gè)結(jié)點(diǎn),其算法分為兩步：查找要?jiǎng)h除得結(jié)點(diǎn)；如果找到則刪除，否則顯示提示信息.在散列表中刪除一個(gè)結(jié)點(diǎn)得算法如下：voｉddelｅ（HａｓhTａbｌeht，ｉntelｅ）{//刪除指定數(shù)據(jù) ｉｎti；?ＥlemＮoｄe*ｐ,*q;?i=Hash(ele)； p=ht［i］、ｆirst; if(p==ＮULL）{ ?pｒｉntf（＂ｅｒrｏrｏccurred！"）； } if(p—>data==ele）{? ｈt［i]、first＝p—>neｘt；?}?else｛ ?q=ｐ－＞nｅxt； ?wｈilｅ（ｑ！=ＮULＬ&&ｑ—>data！=elｅ){???ｐ=q；?? ｑ=ｑ—＞nｅxt;??}??if(q==NＵLL）｛ printｆ（”ｅrrｏroccurred?。?；? ｝? ｅlse｛ ?ｐ－〉nexｔ=q-＞next； frｅｅ（q)； ｝ }｝六。實(shí)驗(yàn)分析１、測(cè)試分析（1)建立哈希表（2)插入一個(gè)結(jié)點(diǎn)并顯示：查找結(jié)點(diǎn):在哈希表中沒有3這個(gè)數(shù),會(huì)輸出一行提示信息。刪除一個(gè)結(jié)點(diǎn)并顯示:2、性能分析散列法本質(zhì)上就是一種通過關(guān)鍵字直接計(jì)算存儲(chǔ)地址得方法。在理想情況下，散列函數(shù)可以把結(jié)點(diǎn)均勻地分布在散列表中，不發(fā)生沖突，則查找過程無需比較，其時(shí)間復(fù)雜度O（1)。但在實(shí)際使用過程中，為了將范圍廣泛得關(guān)鍵字映射到一組連續(xù)得存儲(chǔ)空間,往往會(huì)發(fā)生同義詞沖突,這時(shí)就需要進(jìn)行關(guān)鍵字比較. 能夠把關(guān)鍵字盡可能均勻地分布到散列表中得函數(shù)就是“好"得散列函數(shù)。好得散列函數(shù)可以有效地降低沖突得得發(fā)生，從而提高查找性能。但好得散列函數(shù)與關(guān)鍵字得數(shù)字特征有關(guān)，因此不存在對(duì)任何結(jié)點(diǎn)都好得散列函數(shù).?對(duì)于同一種散列函數(shù),采用不同得沖突處理方法將產(chǎn)生不同得效果,例如線性探測(cè)法容易導(dǎo)致“二次聚集”，而拉鏈法可以從根本上杜絕二次聚集，從而提高查找性能。不過也會(huì)“浪費(fèi)”一部分散列表得空間。附錄＊***＊*＊＊＊***＊**＊*＊＊＊＊＊＊*＊**＊程序源代碼＊＊＊＊＊＊*＊**＊＊＊＊＊**＊＊＊*＊****＊＊＊*＊*＊//頭文件sanlｉbiａo、ｈ#inｃlｕde<stdio、h＞#include<sｔｄlｉb、h＞#deｆineMAＸ_LENGTＨ50typedefsｔruｃｔnode｛?iｎｔdata;?ｓtrｕctnodｅ＊ｎeｘt;}ElｅmNodｅ；typeｄefstruct｛?EｌｅmＮoｄｅ＊firsｔ;｝EｌemHeaｄer，HaｓhTablｅ[MAＸ＿LEＮＧＴH］;ｉntn;//存儲(chǔ)哈希表長(zhǎng)度vｏidｉｎｉtHashTable（HashTaｂleht,inｔn)；ｖoiｄinserｔ(HashTａbleht，iｎtｅlｅ）；EｌemNode*seaｒch（HashＴablｅhｔ,iｎteｌe);voiｄdｅｌe（ＨａshTableht,intele）；ｉntHash（ｉntht）；ｉｎｔｃｒeatｅHaｓｈTaｂｌe（HａshＴａblｅｈt）；voｉdshｏwHａshTａble（HaｓhＴableht)；ｖoidmｅnu（ＨashTaｂlehｔ);//菜單//功能函數(shù)sａnｌibiａo、ｃ＃iｎcｌudｅ＂sanlibｉao、ｈ"voidinitHashＴable（HashTａbleht，intｎ){／/初始化 inti；?foｒ（i＝0;i〈n;i++）｛ ?ht［ｉ］、first=NUＬL；?}｝voidｉnsｅrt（HａshTableht，intelｅ)｛//插入 intｉ； ElemNodｅ*p; i=Haｓh（ｅlｅ); p=(ElemNode*）malｌoｃ（sｉzeof（ElemNodｅ）)；// p－>key=ｅle； p->data＝eｌｅ； ｐ—〉nexｔ=ht［i］、ｆirst； ht[i］、ｆｉｒsｔ=p；｝EｌｅｍNoｄe*search（HasｈTaｂｌｅht,inｔｅｌｅ）{//查找 inti;?EｌemＮode＊p；?i=Hａｓh（ｅle)；?ｐ=ht[i］、firｓt;?while(p！＝NULL&&p-〉datａ!＝elｅ){ ?p=p－＞next； }?ｉf(p?。絅ULL） ｛ pｒｉntf（"數(shù)據(jù)％d得位置為％d＼n＂，ｅｌe，i）;? returnp；?｝?ｅlse?｛??prｉｎtf("哈希表中無％ｄ＼n＂，ｅlｅ);??retｕrnp; }｝?voｉddelｅ（HasｈTableht，intｅle）｛//刪除指定數(shù)據(jù) inti;?ElemＮode*ｐ，＊q;?ｉ=Hａsh（ｅle)； p=ht［i]、first； iｆ(p==NUＬL）{ ?priｎtｆ（"erｒorocｃurｒed!”)；?}?if（p—>ｄata＝=eｌe）{ ｈt［i］、firｓt＝p->neｘt; ｝?ｅlse{??q＝p—〉ｎeｘt; wｈiｌe（q！=NULL＆＆q-＞data?。絜le）｛ ?p=q；???q=q—＞next; ｝??ｉf（q=＝NULL)｛?? ｐｒintｆ（”erroroccuｒrｅd!")； ?｝ eｌｓｅ{? ?p—>ｎext=q->nｅxt； ? frｅe(cuò)（ｑ)；??｝ }｝intHash(ｉntｈt)｛//哈希函數(shù)?inti；?i＝hｔ%n; returｎｉ；｝inｔｃrｅaｔｅＨasｈTablｅ(HashTableｈt）／／創(chuàng)建哈希表｛?HashTablｅ*p=ht; inｔａd［MＡX_LENGTH］=｛0};?inti；?pｒiｎtf（"請(qǐng)輸入插入個(gè)數(shù)ｎ:");?sｃaｎf（”％d"，＆n)； printf（”\n請(qǐng)輸入插入%d個(gè)整數(shù):＂,n);?ｆor（i=0；i<n；i++)??scａnf(＂％ｄ＂,＆ad[i]）； ｉｎiｔHａshTablｅ（p,n）；?for(ｉ=0;i<ｎ；i++） ?ｉnsｅrt(ｐ,ad［i]);?ｒeｔurn1;｝vｏｉdｓhowHashTable（ＨashTableht）//顯示哈希表｛?ｉnti；?ＥlemＮode*p；?／/ｉ＝Ｈaｓh（elｅ)； for（i=0；i〈n；ｉ++)?｛ p＝ht［i］、fｉｒｓt；??iｆ(p!=ＮULＬ）ｐrintf（＂位置%d上得數(shù)據(jù):"，i）; whilｅ(p！=NULL） ?{ ?ｐriｎtf（"%ｄ"，p－＞datａ）;? ｐ=p-＞next; ?} if（ht[ｉ］、firｓt!=ＮUＬＬ)printf（＂\n＂）; }}voidmeｎｕ（HasｈTableht)｛?inｔp,ｈ；//p菜單選擇;?do?｛//??system（＂clｓ”）；/／清屏 prｉｎtf("★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆\n”）； priｎｔｆ（”☆★☆★\n”)； pｒintf(＂★☆＊*＊＊＊＊＊***＊＊＊＊?dú)g迎來到哈希表系統(tǒng)!*＊＊＊*****＊＊***＊★☆\n")；? printf("☆★合肥學(xué)院?? ☆★\n"）；? pｒintf（”★☆計(jì)算機(jī)科學(xué)與技術(shù)★☆\n”);??pｒiｎtf(”☆★錢海峰,鄭秀娟，王傳敏,楊青，凌波☆★\n”);? ｐｒintf（＂☆★☆★＼n”）； ?pｒintf("☆★※※※※※※※☆★\ｎ"）；??printｆ（＂★☆※菜單※★☆\n”）;? prinｔf（"☆★※※※※※※※☆★\n”）；? ｐｒintｆ（”☆★☆★\n”）； ?priｎtf（”★☆**＊＊**＊＊*＊*＊*＊（1）-——?jiǎng)?chuàng)建哈希表＊*＊****＊＊＊＊*＊＊*＊＊＊★☆\n"）； ?pｒiｎtf（＂☆★＊＊＊＊＊*＊*＊＊＊**＊（2）—－—查找*＊*＊＊＊＊＊＊＊***＊＊＊**★☆\n”）； printf("★☆＊＊＊＊＊＊*＊*＊＊***(3)——－刪除*＊*＊＊*＊***＊*＊＊**＊＊★☆\n”）；? ｐriｎｔf（”☆★＊＊**＊＊＊*＊**＊＊*（４)—--插入 ＊*＊＊＊***＊＊*＊＊＊＊**＊★☆\n”）；??prｉｎtf(”★☆*＊＊＊＊＊*****＊＊*(5)—-—輸出哈希表＊*＊*＊＊＊＊＊＊＊＊**＊***★☆＼n");??ｐｒintf("☆★＊＊＊*＊*＊＊＊*＊＊**(0）--—退出＊*＊＊＊＊*＊*＊*＊*＊*＊＊＊☆★＼n”）；??ｐrintf（＂★☆＊＊＊＊＊＊＊＊****＊＊＊**＊*＊＊*＊**＊＊＊**＊*＊＊＊＊＊＊***＊＊＊