數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)---哈希表的設(shè)計(jì)與實(shí)現(xiàn)

1、<p>　　課程名稱：數(shù)據(jù)結(jié)構(gòu) </p><p><b>　　XXXXXXXX</b></p><p>　　本科學(xué)生課程設(shè)計(jì)（論文）</p><p>　　題 目 哈希表的設(shè)計(jì)與實(shí)現(xiàn) </p><p>　　姓 名 XXX </p

2、><p>　　學(xué) 號(hào) XXXXXXXXXXXX </p><p>　　學(xué) 部 計(jì)算機(jī)科學(xué)與技術(shù) </p><p>　　專業(yè)、年級(jí) 計(jì)算機(jī)科學(xué)與技術(shù) 大二 </p><p>　　指 導(dǎo) 教 師 XX </p>

3、;<p>　　2010 年 11月 28日</p><p><b>　　摘 要</b></p><p>　　隨著信息技術(shù)的發(fā)展，關(guān)于各種程序中的數(shù)據(jù)結(jié)構(gòu)也是層出不窮，對(duì)于項(xiàng)目某一方面的計(jì)算或者是某一方面的研究，出現(xiàn)了專門的數(shù)據(jù)結(jié)構(gòu)，哈希表就是其中之一，哈希表作為另類的一種數(shù)據(jù)結(jié)構(gòu)，其作用也是區(qū)別于其它同類的數(shù)據(jù)結(jié)構(gòu)的，它是由兩部分組成的：鍵(key)和

4、值，通過鍵可以迅速的查找到你需要的值。常見的構(gòu)造哈希函數(shù)的方法有直接定址法 除留余數(shù)法 平方取中法 數(shù)字分析法等。一般創(chuàng)建哈希表時(shí)可能會(huì)出現(xiàn)很多的沖突，常用的處理沖突的方法為開放定址法 再哈希法 鏈地址法 建立一個(gè)公共溢出區(qū)。</p><p>　　關(guān)鍵詞: 數(shù)據(jù)結(jié)構(gòu)；哈希表；鍵(key)；</p><p><b>　　目 錄</b></p><p&

5、gt;　　第1章前言與系統(tǒng)實(shí)現(xiàn)2</p><p><b>　　1.1前言2</b></p><p><b>　　1.2系統(tǒng)實(shí)現(xiàn)3</b></p><p>　　1.2.1 開發(fā)環(huán)境3</p><p>　　1.2.2 Visual C++環(huán)境的安裝3</p><p&g

6、t;　　第2章 系統(tǒng)功能分析4</p><p>　　2.1 系統(tǒng)功能需求分析4</p><p>　　2.2 任務(wù)定義4</p><p>　　第3章 總體設(shè)計(jì)5</p><p>　　3.1系統(tǒng)數(shù)據(jù)結(jié)構(gòu)5</p><p>　　3.2主要算法流程圖6</p><p>　　3.2.1

7、 以姓名為關(guān)鍵字的CreateHashList()函數(shù)流程圖6</p><p>　　3.2.2 哈希表查找算法流程圖7</p><p>　　3.2.3主程序流程圖8</p><p>　　第4章 詳細(xì)設(shè)計(jì)和編碼9</p><p>　　4.1節(jié)點(diǎn)的建立9</p><p>　　4.2 對(duì)哈希函數(shù)的定義9<

8、;/p><p>　　4.3 創(chuàng)建哈希表算法、代碼如下所示:10</p><p>　　4.3.1 算法10</p><p>　　4.3.2代碼10</p><p>　　4.4哈希查找11</p><p>　　4.5顯示哈希表14</p><p>　　4.6主菜單設(shè)計(jì)16</p>

9、<p>　　4.7 主函數(shù)設(shè)計(jì)16</p><p>　　第5章 程序運(yùn)行測試19</p><p>　　5.1程序主界面19</p><p>　　5.2哈希表初始化19</p><p>　　5.3按姓名查找記錄21</p><p>　　5.4顯示哈希表全部記錄22</p><

10、p><b>　　總結(jié)23</b></p><p><b>　　參考文獻(xiàn)24</b></p><p><b>　　前言與系統(tǒng)實(shí)現(xiàn)</b></p><p><b>　　1.1前言</b></p><p>　　在信息化時(shí)代的今天，計(jì)算機(jī)技術(shù)已經(jīng)是發(fā)展到

11、一個(gè)很可觀的地步了，特別是面向窗口的操作系統(tǒng)的出現(xiàn)，使得程序設(shè)計(jì)更加的容易了。在過去計(jì)算機(jī)內(nèi)存容量小，CPU計(jì)算速度慢，關(guān)于程序設(shè)計(jì)中的數(shù)據(jù)結(jié)構(gòu)也因此提出來很多的關(guān)于解決這方面的問題。哈希表就是其中之一，哈希表是一個(gè)由關(guān)鍵字與值組成的特殊的一種數(shù)據(jù)結(jié)構(gòu)。它的出現(xiàn)主要是為了解決在結(jié)構(gòu)中查找記錄時(shí)需要進(jìn)行一系列和關(guān)鍵字的比較,這一類查找方法是建立在“比較”的基礎(chǔ)上的，在順序等的查找中，查找的效率是依賴于查找過程中所比較的次數(shù)。</p&

12、gt;<p>　　理想的情況是希望不經(jīng)過任何的比較一次存取便能得到所查記錄，那就必須在記錄的存儲(chǔ)位置和它的關(guān)鍵字之間建立一個(gè)確定的對(duì)應(yīng)關(guān)系，使得每個(gè)關(guān)鍵字和結(jié)構(gòu)中一個(gè)唯一的存儲(chǔ)位置相對(duì)應(yīng)。因而在查找時(shí)只要根據(jù)這個(gè)對(duì)應(yīng)關(guān)系找到給定的值的像。若結(jié)構(gòu)中存在關(guān)鍵字和該值相等的記錄，則所要查找的數(shù)就必定就是這個(gè)所查找到的記錄。</p><p>　　哈希函數(shù)是建立哈希表的一個(gè)重要的成員，它的構(gòu)造方法分為以下幾種

13、：</p><p>　　直接定址法、數(shù)字分析法、平方取中法、折疊法、除留余數(shù)法、隨機(jī)數(shù)法。</p><p>　　本程序中主要用的是除余取留法,除留取余法主要是取關(guān)鍵字被某個(gè)不大于哈希表表長m的數(shù)p出后所得余數(shù)為哈希地址即:H(key)=key MOD p, p<=m，這是一種最簡單，也是一種最常用的構(gòu)造函數(shù)的方法，它不僅可以對(duì)關(guān)鍵字直接取模，也可在折疊、平方中等運(yùn)算之后取模。<

14、/p><p>　　在哈希表的建立中，很容易出現(xiàn)同義詞，這些同義詞的出現(xiàn)也導(dǎo)致了建立哈希表時(shí)沖突的出現(xiàn)，如果不解決這些沖突那么建立好的哈希表與預(yù)料的哈希表不同。關(guān)于處理沖突的方法主要有：開放定址法、再哈希法、鏈地址法。本程序中主要用的就是鏈地址法萊解決沖突的。</p><p><b>　　1.2系統(tǒng)實(shí)現(xiàn)</b></p><p>　　本程序是在Vc++

15、6.0環(huán)境下編寫 測試運(yùn)行的。</p><p>　　1.2.1 開發(fā)環(huán)境</p><p>　　表1-1列出了系統(tǒng)硬件配置，表6-2列出了系統(tǒng)軟件配置。</p><p>　　表1.1 組裝臺(tái)式機(jī)配置</p><p><b>　　表1.2 軟件環(huán)境</b></p><p>　　1.2.2 Visu

16、al C++環(huán)境的安裝</p><p>　　在計(jì)算機(jī)中安裝Visual C++安裝程序，Visual C++應(yīng)用程序的開發(fā)主要有兩種模式，一種是WIN API方式，另一種則是MFC方式，傳統(tǒng)的WIN API開發(fā)方式比較繁瑣，而MFC則是對(duì)WIN API再次封裝，所以MFC相對(duì)于WIN API開發(fā)更具備效率優(yōu)勢。本軟件中因?yàn)槌绦蛑饕菫榱藢?shí)現(xiàn)某個(gè)算法所以這里沒有用到MFC。</p><p>

17、　　第2章 系統(tǒng)功能分析</p><p>　　2.1 系統(tǒng)功能需求分析</p><p>　　實(shí)現(xiàn)本程序需要解決以下幾個(gè)問題：</p><p>　　1. 設(shè)計(jì)一個(gè)結(jié)點(diǎn)使該結(jié)點(diǎn)包括電話號(hào)碼、用戶名、QQ等結(jié)點(diǎn)信息。</p><p>　　2. 利用用戶名為關(guān)鍵字建立哈希表，哈希函數(shù)用除留余數(shù)法構(gòu)照。</p><p>　　

18、3. 利用鏈表法處理沖突問題。</p><p>　　4. 實(shí)現(xiàn)用哈希法查找并顯示給定姓名的記錄。</p><p>　　5. 顯示哈希表中的全部記錄。</p><p><b>　　2.2 任務(wù)定義</b></p><p>　　由功能需求分析知，本設(shè)計(jì)主要要求以用戶名為關(guān)鍵字建立哈希表，并實(shí)現(xiàn)查找功能。所以本設(shè)計(jì)的核心問題

19、是如何解決散列的問題，亦即設(shè)計(jì)一個(gè)良好的哈希表。根據(jù)題目的要求采用鏈地址法散列算法。當(dāng)出現(xiàn)同義詞沖突時(shí)，使用鏈表結(jié)構(gòu)把同義詞鏈接在一起，即同義詞的存儲(chǔ)地址不是散列表中其他的空地址。</p><p>　　首先，解決的是定義鏈表結(jié)點(diǎn)，在鏈地址法中，每個(gè)結(jié)點(diǎn)對(duì)應(yīng)一個(gè)鏈表結(jié)點(diǎn)，它由六個(gè)域組成，而由于該程序需要用用戶名為關(guān)鍵字建立哈希表，所以該鏈表結(jié)點(diǎn)它是char strName[20];char strClass[20]

20、;char strPhone[11];char strqq[10]; int num; char strAddress 六個(gè)數(shù)據(jù)域和struct Name *next 一個(gè)地址域組成。</p><p>　　構(gòu)造哈希表的函數(shù)主要是用除留取余法來構(gòu)造哈希函數(shù)的。</p><p>　　沖突的解決采用鏈地址法，具體的實(shí)現(xiàn)思想是，所有同義詞構(gòu)成一個(gè)單鏈表，再由一個(gè)表頭結(jié)點(diǎn)指向這個(gè)單鏈表的第一個(gè)結(jié)點(diǎn)。

21、這些表頭結(jié)點(diǎn)組成一個(gè)一維數(shù)組，即哈希表。數(shù)組元素的下標(biāo)對(duì)應(yīng)由散列函數(shù)求出的散列地址。</p><p><b>　　第3章 總體設(shè)計(jì)</b></p><p><b>　　3.1系統(tǒng)數(shù)據(jù)結(jié)構(gòu)</b></p><p>　　本設(shè)計(jì)涉及到的數(shù)據(jù)結(jié)構(gòu)為：哈希表。</p><p>　　程序中建立了兩個(gè)結(jié)構(gòu)體，要

22、求輸入電話號(hào)碼、用戶名、QQ、地址、四個(gè)信息，給struct Name結(jié)構(gòu)體變量，在創(chuàng)建哈希表時(shí)哈希函數(shù)用除留余數(shù)法構(gòu)照，并把struct Name結(jié)構(gòu)體中的數(shù)據(jù)賦值給哈希表結(jié)構(gòu)體。</p><p>　　在鏈地址法中，每個(gè)結(jié)點(diǎn)對(duì)應(yīng)一個(gè)鏈表結(jié)點(diǎn)，它由六個(gè)域組成，鏈地址法結(jié)點(diǎn)結(jié)構(gòu)如表：</p><p><b>　　表 3.1</b></p><p>

23、;　　其中哈希表是以用戶名為關(guān)鍵字 next指針是用來指向下一個(gè)結(jié)點(diǎn)的地址。</p><p>　　具體的存儲(chǔ)結(jié)構(gòu)如下圖所示:</p><p>　　圖3.1數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)圖</p><p>　　3.2主要算法流程圖</p><p>　　3.2.1 以姓名為關(guān)鍵字的CreateHashList()函數(shù)流程圖</p><p>

24、<b>　　圖 3.2</b></p><p>　　3.2.2 哈希表查找算法流程圖</p><p><b>　　圖 3.3</b></p><p>　　3.2.3主程序流程圖</p><p><b>　　圖 3.4</b></p><p>　　第4章

25、 詳細(xì)設(shè)計(jì)和編碼</p><p><b>　　4.1節(jié)點(diǎn)的建立</b></p><p>　　定義結(jié)構(gòu)體如下所示:</p><p>　　typedef struct Name</p><p><b>　　{</b></p><p>　　char strName[20];//姓名

26、</p><p>　　char strClass[20];//班級(jí)</p><p>　　char strPhone[11];//手機(jī)號(hào)碼</p><p>　　char strAddress[30];//地址</p><p>　　char Nqq[10];//QQ</p><p>　　int num;//關(guān)鍵字</

27、p><p>　　struct Name *next;</p><p><b>　　}pName;</b></p><p>　　pName NameList[HASH_LEN];</p><p><b>　　pName k;</b></p><p>　　struct Hlist&l

28、t;/p><p><b>　　{</b></p><p>　　pName *next;</p><p>　　}HashList[HASH_LEN];</p><p>　　4.2 對(duì)哈希函數(shù)的定義</p><p>　　本程序設(shè)計(jì)一個(gè)hash()函數(shù)，本設(shè)計(jì)中按照題意要求知對(duì)散列函數(shù)選擇的是除留余數(shù)法，

29、即對(duì)關(guān)鍵字進(jìn)行模運(yùn)算，將計(jì)算結(jié)果所得的余數(shù)作為關(guān)鍵字（或結(jié)點(diǎn)）的存儲(chǔ)地址，即H(key)=key mod p,在程序中p取的值為范圍內(nèi)的最大的素?cái)?shù)，以用戶名為關(guān)鍵字建立哈希函數(shù)CreateHash()，利用強(qiáng)制類型轉(zhuǎn)換將用戶名的每一個(gè)字母的ASCLL碼值相加并且除以范圍內(nèi)最大的素?cái)?shù)，將計(jì)算出來的數(shù)作為該結(jié)點(diǎn)的地址賦給adr。然后通過以下幾種方式就可以完成哈希表程序的設(shè)計(jì)了。</p><p>　　4.3 創(chuàng)建哈希表

30、算法、代碼如下所示:</p><p><b>　　4.3.1 算法</b></p><p>　　建立結(jié)點(diǎn)，并添加結(jié)點(diǎn)，利用鏈地址法解決沖突。建立結(jié)點(diǎn)應(yīng)包括動(dòng)態(tài)申請內(nèi)存空間。向結(jié)點(diǎn)中輸入信息。同時(shí)將結(jié)點(diǎn)中的next指針等于null。添加結(jié)點(diǎn)，首先需要利用哈希函數(shù)計(jì)算出地址即關(guān)鍵字，其次將該結(jié)點(diǎn)插入以關(guān)鍵字為地址的鏈表后。</p><p><

31、b>　　4.3.2代碼</b></p><p>　　void CreateHashList()</p><p><b>　　{</b></p><p><b>　　int i;</b></p><p>　　for(i=0; i<HASH_LEN; i++)</p>

32、<p><b>　　{</b></p><p>　　HashList[i].next=NULL;</p><p><b>　　}</b></p><p>　　for(i=0; i<2; i++)</p><p><b>　　{</b></p>

33、<p>　　struct Hlist *q;</p><p>　　pName *p,*m;</p><p>　　int adr=(NameList[i].num)%M;//哈希函數(shù)</p><p>　　if(HashList[adr].next==NULL)//表明不沖突</p><p><b>　　{</b>

34、</p><p>　　HashList[adr].next=&NameList[i];</p><p><b>　　}</b></p><p>　　else//表明沖突</p><p><b>　　{</b></p><p>　　q=&HashList[adr

35、];</p><p>　　m=q->next;</p><p>　　while(m->next!=NULL)</p><p><b>　　{ </b></p><p>　　m=m->next;</p><p><b>　　}</b></p>

36、<p>　　p=(pName *)malloc(sizeof(pName));</p><p>　　strcpy(p->strName,NameList[i].strName);</p><p>　　strcpy(p->strPhone, NameList[i].strPhone);</p><p>　　strcpy(p->strAdd

37、ress,NameList[i].strAddress);</p><p>　　strcpy(p->Nqq, NameList[i].Nqq);</p><p>　　p->num=NameList[i].num;</p><p>　　m->next=p;//單鏈表向后指</p><p><b>　　}</b&

38、gt;</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　4.4哈希查找</b></p><p>　　想要實(shí)現(xiàn)查找功能，需要一個(gè)查找函數(shù)，以用戶名為關(guān)鍵字來實(shí)現(xiàn)查找，首先，需要利用hash函數(shù)來計(jì)算出地址。再通過比對(duì)，如

39、果該地址中的用戶名拼音字符相加的num與查找的相同則輸出該結(jié)點(diǎn)的所有信息，否則輸出“無此記錄”。</p><p>　　具體實(shí)現(xiàn)代碼如下所示:</p><p>　　void SearchList()</p><p><b>　　{</b></p><p>　　system("cls");</p&g

40、t;<p><b>　　char *f;</b></p><p>　　printf("\n\n請輸入你要查找姓名（拼音）");//輸入姓名</p><p>　　char name[20];</p><p>　　scanf("%s",name);</p><p><

41、;b>　　f=name;</b></p><p>　　int s=0, r;</p><p>　　for(r=0; *(f+r)!='\0'; r++)//求出姓名的拼音所對(duì)應(yīng)的整數(shù)也就是關(guān)鍵字</p><p><b>　　{</b></p><p>　　s+=(int)*(f+r);/

42、/利用字符與整數(shù)的自動(dòng)轉(zhuǎn)換相加字符的ASCII碼</p><p><b>　　}</b></p><p>　　int adr=s%M;//使用哈希函數(shù)</p><p>　　if(HashList[adr].next==NULL)//通過指針的指向判斷一個(gè)單鏈表中是否存在要查找的數(shù)</p><p><b>　　{

43、</b></p><p>　　printf("無該記錄");</p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　if((Has

44、hList[adr].next)->next==NULL)</p><p><b>　　{</b></p><p>　　if((HashList[adr].next)->num==s)</p><p><b>　　{</b></p><p><b>　　int i=1;<

45、/b></p><p>　　printf(“\n姓名:%s”, (HashList[adr].next)->strName);</p><p>　　printf(“班級(jí):%s”, (HashList[adr].next)->strClass);</p><p>　　printf(“電話:%s”, (HashList[adr].next)->s

46、trPhone);</p><p>　　printf(“QQ:%s”, HashList[adr].next)->Nqq);</p><p>　　printf(“地址: %s\n”, (HashList[adr].next)->strAddress);</p><p>　　printf(“關(guān)鍵字:%d”, (HashList[adr].next)->

47、;num);</p><p>　　printf(“查找長度:%d”, i);</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</

48、b></p><p><b>　　pName *m;</b></p><p><b>　　int i=1;</b></p><p>　　m=HashList[adr].next;</p><p>　　while(m->next!=NULL)//循環(huán)該單鏈表查找出你所要查找的數(shù)據(jù)并把他們輸

49、出</p><p><b>　　{</b></p><p>　　if(m->num==s)</p><p><b>　　{</b></p><p>　　Printf(“\n姓名:%s”, m->strName);</p><p>　　Printf(“班級(jí):%s”,

50、 m->strClass);</p><p>　　Printf(“電話:%s”, m->strPhone);</p><p>　　Printf(“QQ：%s”, m->Nqq);</p><p>　　Printf(“地址: %s”, m->strAddress);</p><p>　　Printf(“關(guān)鍵字:%d”,

51、m->num);</p><p>　　printf("查找長度:%d", i);</p><p><b>　　break;</b></p><p><b>　　}</b></p><p>　　m=m->next;</p><p><b&g

52、t;　　i++;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>

53、　　4.5顯示哈希表</b></p><p>　　通過姓名關(guān)鍵字，循環(huán)查找有值的下標(biāo)并輸出來,具體設(shè)計(jì)代碼如下：</p><p>　　void Display()</p><p><b>　　{</b></p><p>　　system("cls");</p><p&g

54、t;　　int i, s, j, adr, n=0;</p><p><b>　　char *f;</b></p><p>　　struct Hlist *m;</p><p>　　struct Name *k;</p><p>　　char name[20];</p><p>　　printf(

55、"\n\n下標(biāo)地址\t關(guān)鍵字\tH(key)\t拼音 班級(jí) QQ 地址 電話 \n"); //顯示的格式</p><p>　　for(i=0; i<2; i++)</p><p><b>　　{</b></p><p><b>　　s=0;</b></p><p&

56、gt;　　strcpy(name,NameList[i].strName);</p><p><b>　　f=name;</b></p><p>　　for(j=0; *(f+j)!='\0'; j++)</p><p><b>　　{</b></p><p>　　s+=(int)*

57、(f+j);</p><p><b>　　}</b></p><p><b>　　adr=s%M;</b></p><p>　　m=&HashList[adr];</p><p>　　if(m->next!=NULL)</p><p><b>　　{&

58、lt;/b></p><p>　　k=m->next;</p><p><b>　　n+=1;</b></p><p>　　while(k->next!=NULL)</p><p><b>　　{</b></p><p>　　printf("下標(biāo)地

59、址:%d",i);</p><p>　　printf("\t%d ",k->num); </p><p>　　printf("\t%d ",(k->num)%M); </p><p>　　printf("\t %s ",k->strName); </p><p

60、>　　printf(" %s",k->strClass);</p><p>　　printf(" %s",k->Nqq);</p><p>　　printf(" %s",k->strAddress);</p><p>　　printf(" %s",k-

61、>strPhone);</p><p>　　printf("\n"); </p><p>　　k=k->next;</p><p><b>　　}</b></p><p>　　printf("下標(biāo)地址:%d",i);</p><p>　　prin

62、tf("\t%d ",k->num); </p><p>　　printf("\t%d ",(k->num)%M); </p><p>　　printf("\t %s ",k->strName); </p><p>　　printf(" %s",k->strCl

63、ass);</p><p>　　printf(" %s",k->Nqq);</p><p>　　printf(" %s",k->strAddress);</p><p>　　printf(" %s",k->strPhone);</p><p>　　prin

64、tf("\n"); </p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　4.6主菜單設(shè)計(jì)</b></p><p>

65、　　根據(jù)題目中的要求我們只要寫出哈希表的初始化 查找 顯示三個(gè)功能，代碼如下所示:</p><p>　　void Menu()</p><p><b>　　{</b></p><p>　　printf("\n------------------------哈希表的建立和查找操作----------------------")

66、; </p><p>　　printf("\n\n"); </p><p>　　printf(" 1. 哈希表初始化\n");</p><p>　　printf(" 2. 顯示哈希表\n"); </p><p>　　printf(" 3. 查找\n"); &l

67、t;/p><p>　　printf(" 4. 退出\n");</p><p><b>　　}</b></p><p><b>　　4.7 主函數(shù)設(shè)計(jì)</b></p><p>　　主函數(shù)是一個(gè)軟件運(yùn)行的入口，其通過調(diào)用自定義函數(shù)來完成相應(yīng)的功能,其實(shí)現(xiàn)代碼如下所示:</p>

68、<p>　　int main(int argc, char *argv[])</p><p><b>　　{</b></p><p>　　int i,f=0;</p><p><b>　　while(1)</b></p><p><b>　　{</b></p

69、><p><b>　　Menu();</b></p><p>　　scanf("%d",&i);</p><p><b>　　switch(i)</b></p><p><b>　　{</b></p><p>　　case 1:

70、InitNameList(); </p><p>　　CreateHashList(); </p><p><b>　　f=1;</b></p><p><b>　　break;</b></p><p>　　case 2: if(f==1)</p><p><b>

71、;　　{</b></p><p>　　Display();</p><p><b>　　break;</b></p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{<

72、;/b></p><p>　　printf("哈希表未初始化請先初始化再操作");</p><p><b>　　}</b></p><p><b>　　break;</b></p><p>　　case 3: if(f==1)</p><p><

73、;b>　　{</b></p><p>　　SearchList();</p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　printf(&qu

74、ot;哈希表未初始化請先初始化再操作");</p><p><b>　　}</b></p><p><b>　　break;</b></p><p>　　case 4:return 0;</p><p>　　default:printf("請輸入正確的選項(xiàng)");<

75、/p><p><b>　　break;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　第5章 程序運(yùn)行測試</p>&l

76、t;p><b>　　5.1程序主界面</b></p><p>　　圖5.1 程序主界面</p><p><b>　　5.2哈希表初始化</b></p><p>　　測試數(shù)據(jù)(正確): </p><p>　　姓名:kaluo班級(jí):305電話:123456789 地址:長沙涉外 QQ:282265

77、478</p><p>　　姓名:tianxia  班級(jí):306 電話:987654321 地址:長沙理工 QQ:974562228</p><p>　　姓名:xiantu  班級(jí):3076 電話:987654322 地址:長沙學(xué)院 QQ:974562222</p><p><b>　　測試數(shù)據(jù)(錯(cuò)誤):</b></p

78、><p>　　姓名:張三(否拼音)  班級(jí):3077 電話:987654322 地址:長沙學(xué)院 QQ:974562222</p><p>　　姓名:李四(否拼音)  班級(jí):3078電話:987654322 地址:長沙學(xué)院 QQ:974562222</p><p>　　圖5.2 哈希表正確初始化</p><p>　　圖5.3 哈

79、希表的錯(cuò)誤初始化</p><p>　　圖5.4 哈希表初始化</p><p>　　5.3按姓名查找記錄</p><p>　　圖5.5 輸入查找條件</p><p>　　圖5.6 查找結(jié)果 </p><p>　　5.4顯示哈希表全部記錄</p><p>　　圖5.7 顯示表中全部記錄</p&

80、gt;<p><b>　　總結(jié)</b></p><p>　　1、語法錯(cuò)誤及修改：程序是分塊寫的,調(diào)試時(shí)可以使用分步調(diào)試的方式進(jìn)行,以便能查找看程序是在哪出錯(cuò)了。程序中使用了鏈表結(jié)構(gòu)和鏈地址法解決沖突的問題，以姓名為關(guān)鍵字的哈希表中要注意涉及ASCLL碼的類型轉(zhuǎn)換。</p><p>　　2、邏輯問題修改和調(diào)整：鏈表結(jié)構(gòu)方法雖然方便了運(yùn)行，但是增加了對(duì)算法過

81、程的認(rèn)識(shí)難度。在本程序中每一個(gè)函數(shù)中都需要涉及到指針的操作。所以需要仔細(xì)分析函數(shù)中的指針指向。</p><p>　　3、時(shí)間，空間性能分析：散列法本質(zhì)上是一種通過關(guān)鍵字直接計(jì)算存儲(chǔ)地址的方法。在理想情況下，散列函數(shù)可以把結(jié)點(diǎn)均勻地分布到散列表中，不發(fā)生沖突，則查找過程無需比較，其時(shí)間復(fù)雜度O（n）=1。但在實(shí)際使用過程中，為了將范圍廣泛的關(guān)鍵字映射到一組連續(xù)的存儲(chǔ)空間，往往會(huì)發(fā)生同義詞沖突，這時(shí)在查找過程中就需要

82、進(jìn)行關(guān)鍵字比較。因此散列法的查找性能取決于3個(gè)因素：散列函數(shù)、沖突處理方法和填充因子。采用鏈地址法，可以從根本上杜絕“二次聚集”的發(fā)生，從而提高散列表的均勻度，提高查找性能，不過也會(huì)“浪費(fèi)”一部分散列表的空間。當(dāng)散列函數(shù)和沖突處理辦法固定時(shí)，散列法的查找性能就取決于散列表的填充因子。填充因子a=表中已有的結(jié)點(diǎn)數(shù)/表的長度。填充因子a標(biāo)志表的添滿程度。很顯然，a越小則發(fā)生沖突的機(jī)會(huì)就越小；反之，a越大沖突的機(jī)會(huì)就越大，查找的性能也就越低。

83、哈希表鏈地址法查找成功的平均查找長度SNc=1+a/2。鏈地址法查找不成功的平均查找長度Un滿足：Unc=a+e-a.由以上可以看出，散列表的平均查找長度是填充因子的函數(shù)，和散列表的長度沒有關(guān)系，因此在實(shí)際應(yīng)用中，我們應(yīng)該選擇一個(gè)適當(dāng)?shù)奶畛湟蜃樱员惆哑骄檎?lt;/p><p><b>　　參考文獻(xiàn)</b></p><p>　　[1]（美）佛羅贊(Forouzan).計(jì)

84、算機(jī)科學(xué)導(dǎo)論[M].北京：機(jī)械工業(yè)出版社,2004.217~219</p><p>　　[2] 嚴(yán)蔚敏 吳偉民.數(shù)據(jù)結(jié)構(gòu)[M].北京：清華大學(xué)出版社,1997.251~259</p><p>　　[3] 王昆侖 李紅.數(shù)據(jù)結(jié)構(gòu)與算法[M].北京：中國鐵道出版社,2007.6</p><p>　　[4] 李春葆.數(shù)據(jù)結(jié)構(gòu)題集[M].北京：清華大學(xué)出版社，1992.2&