哈希表課程設(shè)計(jì)

1、<p><b>　　課 程 設(shè) 計(jì)</b></p><p><b>　　目 錄</b></p><p><b>　　課程設(shè)計(jì)任務(wù)書(shū)2</b></p><p><b>　　1．問(wèn)題描述3</b></p><p><b>　　1.

2、1問(wèn)題描述3</b></p><p><b>　　1.2基本要求3</b></p><p><b>　　1.3測(cè)試數(shù)據(jù)3</b></p><p><b>　　2.實(shí)現(xiàn)分析3</b></p><p><b>　　3．程序設(shè)計(jì)4</b>&

3、lt;/p><p>　　3.1存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)4</p><p>　　3.2主要算法設(shè)計(jì)4</p><p>　　3.2.1程序主要函數(shù)原型及功能4</p><p>　　3.2.2各函數(shù)的實(shí)現(xiàn)5</p><p>　　3.2.3函數(shù)模塊9</p><p>　　3.2.4程序流程圖9</p&

4、gt;<p><b>　　4.調(diào)試報(bào)告11</b></p><p>　　4.1調(diào)試中的問(wèn)題11</p><p>　　4.2對(duì)設(shè)計(jì)和編碼的討論和分析11</p><p>　　5. 程序運(yùn)行結(jié)果11</p><p>　　6.經(jīng)驗(yàn)和體會(huì)13</p><p>　　6.1感受和體會(huì)

5、13</p><p>　　6.2對(duì)算法改進(jìn)的想法15</p><p>　　7.哈希表和源程序15</p><p><b>　　7.1哈希表15</b></p><p><b>　　7.2源程序16</b></p><p>　　本科生課程設(shè)計(jì)成績(jī)?cè)u(píng)定表21</p

6、><p><b>　　課程設(shè)計(jì)任務(wù)書(shū)</b></p><p>　　學(xué)生姓名： 專業(yè)班級(jí)： 班 </p><p>　　指導(dǎo)教師： 工作單位： 計(jì)算機(jī)科學(xué)系 </p><p>　　題 目: 哈希表設(shè)計(jì)

7、 </p><p><b>　　初始條件：</b></p><p>　　針對(duì)某個(gè)集體（比如你所在的班級(jí)）中的“人名”設(shè)計(jì)一個(gè)哈希表，使得平均查找長(zhǎng)度不超過(guò)R，完成相應(yīng)的建表和查表程序。</p><p>　　假設(shè)人名為中國(guó)人姓名的漢語(yǔ)拼音形式。待填入哈希表的人名共有30個(gè)，取平均查找長(zhǎng)度的上限為2。哈希函數(shù)用除留余

8、數(shù)法構(gòu)造，用偽隨機(jī)探測(cè)再散列發(fā)處理沖突。</p><p>　　測(cè)試用例見(jiàn)題集p166。</p><p>　　要求完成的主要任務(wù): （包括課程設(shè)計(jì)工作量及其技術(shù)要求，以及說(shuō)明書(shū)撰寫(xiě)等具體要求）</p><p>　　課程設(shè)計(jì)報(bào)告按學(xué)校規(guī)定格式用A4紙打?。〞?shū)寫(xiě)），并應(yīng)包含如下內(nèi)容： </p><p><b>　　1、 問(wèn)題描述</

9、b></p><p>　　簡(jiǎn)述題目要解決的問(wèn)題是什么。</p><p><b>　　2、 設(shè)計(jì)</b></p><p>　　存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)、主要算法設(shè)計(jì)（用類(lèi)C語(yǔ)言或用框圖描述）、測(cè)試用例設(shè)計(jì)；</p><p><b>　　3、 調(diào)試報(bào)告</b></p><p>　　調(diào)試

10、過(guò)程中遇到的問(wèn)題是如何解決的；對(duì)設(shè)計(jì)和編碼的討論和分析。</p><p>　　4、 經(jīng)驗(yàn)和體會(huì)（包括對(duì)算法改進(jìn)的設(shè)想）</p><p>　　5、 附源程序清單和運(yùn)行結(jié)果。源程序要加注釋。如果題目規(guī)定了測(cè)試數(shù)據(jù)，則運(yùn)行結(jié)果要包含這些測(cè)試數(shù)據(jù)和運(yùn)行輸出，</p><p>　　6、 設(shè)計(jì)報(bào)告、程序不得相互抄襲和拷貝；若有雷同，則所有雷同者成績(jī)均為0分。</p>

11、<p><b>　　時(shí)間安排：</b></p><p><b>　　1、第19周完成。</b></p><p>　　2、7月1 日14：00到計(jì)算中心檢查程序、交課程設(shè)計(jì)報(bào)告、源程序（CD盤(pán)）。</p><p>　　指導(dǎo)教師簽名： 年 月 日</p>

12、<p>　　系主任（或責(zé)任教師）簽名： 年 月 日</p><p><b>　　課程設(shè)計(jì)報(bào)告書(shū)</b></p><p><b>　　1．問(wèn)題描述</b></p><p><b>　　1.1問(wèn)題描述</b></p><p>　　針對(duì)某個(gè)集體（比如你

13、所在的班級(jí)）中的“人名”設(shè)計(jì)一個(gè)哈希表，使得平均查找長(zhǎng)度不超過(guò)R，完成相應(yīng)的建表和查表程序。</p><p><b>　　1.2基本要求</b></p><p>　　假設(shè)人名為中國(guó)人姓名的漢語(yǔ)拼音形式。待填入哈希表的人名共有30個(gè)，取平均查找長(zhǎng)度的上限為2。哈希函數(shù)用除留余數(shù)法構(gòu)造，用偽隨機(jī)探測(cè)再散列發(fā)處理沖突。</p><p><b&g

14、t;　　1.3測(cè)試數(shù)據(jù)</b></p><p>　　取自己班級(jí)成員的名字作為測(cè)試數(shù)據(jù)，建立一個(gè)相關(guān)哈希表，并計(jì)算平均查找長(zhǎng)度，完成查詢。</p><p><b>　　2.實(shí)現(xiàn)分析</b></p><p>　?。?） 針對(duì)某個(gè)集體中的人名設(shè)計(jì)一個(gè)哈希表，使得平均查找長(zhǎng)度不超過(guò)R，完成相應(yīng)的建立和查表程序。</p><

15、;p>　?。?） 人名為漢語(yǔ)拼音形式，最長(zhǎng)不超過(guò)19個(gè)字符(如：莊雙雙 zhuangshuangshuang)。</p><p>　?。?） 假設(shè)待填入哈希表的人名有30個(gè)，平均查找長(zhǎng)度的上限為2。哈希表用除留余數(shù)法構(gòu)造，用偽隨機(jī)探測(cè)在散列法處理沖突。</p><p>　?。?） 如果隨機(jī)函數(shù)自行構(gòu)造，則應(yīng)首先調(diào)整好隨機(jī)函數(shù)，使其分布均勻。字符的取碼方法可直接利用C語(yǔ)言中的toas

16、cii函數(shù)，并可對(duì)過(guò)長(zhǎng)人名先進(jìn)行折疊處理。</p><p>　　（5） 查找成功時(shí)，顯示姓名及關(guān)鍵字，并計(jì)算和輸出查找成功的平均查找長(zhǎng)度。</p><p><b>　　3．程序設(shè)計(jì)</b></p><p><b>　　3.1存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)</b></p><p>　　根據(jù)哈希函數(shù)可唯一確定一個(gè)記錄的地

17、址，在理想情況下，記錄就可以按照這個(gè)存儲(chǔ)地址進(jìn)行存儲(chǔ)。因此哈希表的存儲(chǔ)結(jié)構(gòu)可以是鏈表和線性表，但一般情況下選擇線性表進(jìn)行存儲(chǔ)。本次課程設(shè)計(jì)用到的存儲(chǔ)結(jié)構(gòu)如下：</p><p><b>　　3.2主要算法設(shè)計(jì)</b></p><p>　　3.2.1程序主要函數(shù)原型及功能</p><p>　　首先定義兩個(gè)結(jié)構(gòu)體數(shù)組：</p><

18、p>　　NAME NameList[HASH_LENGTH]; //全局變量NAME，存儲(chǔ)原始姓名</p><p>　　HASH HashList[HASH_LENGTH]; //全局變量HASH，存儲(chǔ)哈希表中的姓名</p><p>　　主要函數(shù)原型及功能：</p><p>　　void InitNameList()</p>&l

19、t;p>　　功能：主要完成初始化姓名列表，并且將字符串的各個(gè)字符所對(duì)應(yīng)的ASCII碼相加，所得的整數(shù)作為哈希表的關(guān)鍵字。以便利用關(guān)鍵字和除留余數(shù)法得到每個(gè)姓名的哈希地址。</p><p>　　void CreateHashList() </p><p>　　功能：構(gòu)建一個(gè)哈希表并進(jìn)行初始化；利用各個(gè)姓名的關(guān)鍵字得到哈希地址，將各個(gè)姓名按哈希地址進(jìn)行存儲(chǔ)，如果發(fā)生沖突，則利用偽隨機(jī)探

20、測(cè)再序列解決沖突，最終將姓名全部存放在哈希表中。</p><p>　　void FindList() </p><p>　　功能：對(duì)用戶輸入的姓名進(jìn)行查找；查找結(jié)果分兩種情況：（1）查找成功，則輸出姓名、關(guān)鍵字和查找長(zhǎng)度；（2）查找失敗，則返回相應(yīng)的失敗信息。查找時(shí)關(guān)鍵字的求法和處理沖突的方法與函數(shù)InitNameList()、CreateHashList()中的相關(guān)算法一致。</

21、p><p>　　void ShowHash() </p><p>　　功能：完成度已經(jīng)建立好的哈希表進(jìn)行輸出顯示，并輸出平均查找長(zhǎng)度。</p><p>　　void main()</p><p>　　功能：完成對(duì)個(gè)函數(shù)的調(diào)用和與用戶的交互。</p><p>　　3.2.2各函數(shù)的實(shí)現(xiàn)</p><

22、p><b>　　初始化姓名列表：</b></p><p>　　哈希地址方法：將字符串的各個(gè)字符所對(duì)應(yīng)的ASCII碼相加，所得的整數(shù)做為哈希表的關(guān)鍵字key。</p><p>　　函數(shù)void InitNameList()的實(shí)現(xiàn)（以班級(jí)30人的人名作為初始值）：</p><p><b>　　建立哈希表 </b><

23、;/p><p>　　用除留余數(shù)法構(gòu)建哈希函數(shù)</p><p>　　用偽隨機(jī)探測(cè)再散列法處理沖突</p><p>　　構(gòu)建哈希函數(shù)void CreateHashList()的實(shí)現(xiàn)：</p><p><b>　　查找哈希表</b></p><p>　　若查找成功，則輸出姓名、關(guān)鍵字和查找長(zhǎng)度；查找失敗，則

24、返回相應(yīng)的失敗信息。</p><p>　　查找函數(shù)void FindList()的實(shí)現(xiàn)：</p><p><b>　　顯示哈希表</b></p><p>　　顯示哈希表的的格式：</p><p>　　\n地址\t關(guān)鍵字\t\t搜索長(zhǎng)度\tH(key)\t 姓名\n</p><p>　　顯示哈希表

25、的函數(shù)void Display()的：</p><p><b>　　主函數(shù)設(shè)計(jì)</b></p><p><b>　　3.2.3函數(shù)模塊</b></p><p><b>　　模塊調(diào)用關(guān)系</b></p><p>　　3.2.4 程序流程圖</p><p&g

26、t;<b>　　本次程序流程圖如下</b></p><p><b>　　4.調(diào)試報(bào)告</b></p><p><b>　　4.1調(diào)試中的問(wèn)題</b></p><p>　　經(jīng)過(guò)對(duì)哈希表的研究后，即進(jìn)行程序的設(shè)計(jì)和編碼；將原程序編好后，經(jīng)過(guò)編譯，有如下幾個(gè)問(wèn)題：</p><p>　

27、　在聲明了結(jié)構(gòu)體NAME后，最開(kāi)始結(jié)構(gòu)體內(nèi)的char name[20]用來(lái)存放姓名拼音，最長(zhǎng)為20位；經(jīng)分析，name表示所存姓名拼音的首地址，無(wú)需再申明具體的數(shù)組長(zhǎng)度來(lái)存放姓名拼音，這樣增加了系統(tǒng)的開(kāi)銷(xiāo)，最后改成char*name，對(duì)存放姓名拼音時(shí)直接對(duì)name賦值，系統(tǒng)直接按照字符數(shù)組來(lái)存放姓名拼音，而存放長(zhǎng)度沒(méi)有固定。</p><p>　　建立哈希表的函數(shù)：void CreateHashList()中，如果

28、遇到?jīng)_突后，在do{}while()；語(yǔ)句中，利用偽隨機(jī)探測(cè)再散列法處理沖突，沒(méi)執(zhí)行一次就要將記錄查找長(zhǎng)度的sum增加一次，在這個(gè)循環(huán)執(zhí)行完后，即找到一個(gè)不沖突的地址來(lái)存放姓名拼音，經(jīng)過(guò)自習(xí)分析，此時(shí)的查找長(zhǎng)度需要加1，即將原來(lái)的語(yǔ)句HashList[d].si=sum; 改成HashList[d].si=sum+1;此時(shí)的HashList[d].si才是正確的查找長(zhǎng)度。</p><p>　　main函數(shù)中的do

29、{}while()語(yǔ)句中，最開(kāi)始while()語(yǔ)句是：while(a!='N'||a!='n') 經(jīng)過(guò)分析，在用戶需要退出時(shí)，不論輸入a=N還是a=n，都將繼續(xù)循環(huán)；經(jīng)過(guò)自習(xí)思考，最終將while()語(yǔ)句改成：while(a=='Y'||a=='y')，這樣就實(shí)現(xiàn)了用戶的選擇。</p><p>　　4.2對(duì)設(shè)計(jì)和編碼的討論和分析</p>

30、<p>　　算法采用結(jié)構(gòu)體和數(shù)組來(lái)存儲(chǔ)數(shù)據(jù)，利用除留余數(shù)法得到哈希地址，利用為隨機(jī)序列法來(lái)處理沖突，姓名拼音的關(guān)鍵字為字符串的各個(gè)字符所對(duì)應(yīng)的ASCII碼相加，所得的整數(shù)。求哈希地址時(shí)模為51，哈希表的總長(zhǎng)度為50，而實(shí)際名字只有30個(gè)，因此有20個(gè)地址空間被空閑著，這浪費(fèi)了一定的內(nèi)存。</p><p>　　算法的時(shí)間復(fù)雜度為：O(n)。</p><p>　　平均查找長(zhǎng)度為：1

31、.566667</p><p>　　裝填因子為：30/50=0.6</p><p><b>　　5. 程序運(yùn)行結(jié)果</b></p><p>　　經(jīng)過(guò)對(duì)程序錯(cuò)誤的修改后，程序執(zhí)行，經(jīng)過(guò)分析，程序運(yùn)行結(jié)果正確，滿足題目要求！運(yùn)行結(jié)果主要截圖如下：</p><p>　　程序開(kāi)始后，初始界面為：</p><p

32、><b>　　選擇S后結(jié)果為：</b></p><p>　　結(jié)果顯示，平均查找長(zhǎng)度為1.566667，符合題設(shè)要求！</p><p>　　選擇Y繼續(xù)后選擇F查找</p><p><b>　　查找成功結(jié)果為：</b></p><p><b>　　查找失敗結(jié)果為：</b>&l

33、t;/p><p><b>　　6.經(jīng)驗(yàn)和體會(huì)</b></p><p><b>　　6.1感受和體會(huì)</b></p><p>　　《數(shù)據(jù)結(jié)構(gòu)》這門(mén)課程是計(jì)算機(jī)專業(yè)一門(mén)基礎(chǔ)性學(xué)科，重要性可見(jiàn)一斑，學(xué)好這門(mén)課程對(duì)以后人生的發(fā)展具有深遠(yuǎn)的影響。而數(shù)據(jù)結(jié)構(gòu)的課程設(shè)計(jì)便是對(duì)學(xué)習(xí)效果的檢驗(yàn)。數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)不僅可以鍛煉我們獨(dú)立思考問(wèn)題、解決

34、問(wèn)題的能力，而且可以培養(yǎng)我們的整體性思維的能力；通過(guò)課程設(shè)計(jì)，使我了解了很多數(shù)據(jù)結(jié)構(gòu)的經(jīng)典問(wèn)題和經(jīng)典算法，加深了對(duì)數(shù)據(jù)結(jié)構(gòu)的再認(rèn)識(shí)，鞏固了數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)性知識(shí)，比如：存儲(chǔ)結(jié)構(gòu)、數(shù)據(jù)查找、哈希表的設(shè)計(jì)和查找、算法分析等。</p><p>　　哈希表是根據(jù)關(guān)鍵碼值而直接進(jìn)行訪問(wèn)的數(shù)據(jù)結(jié)構(gòu)，它把關(guān)鍵碼值通過(guò)哈希函數(shù)映射到表中一個(gè)地址來(lái)存儲(chǔ)記錄，以加快查找的速度。哈希函數(shù)的構(gòu)造方法有：直接尋址法、數(shù)字分析法、平方取中法、

35、折疊法、隨機(jī)數(shù)法、除留余數(shù)法等；對(duì)于地址沖突要進(jìn)行解決，主要解決沖突的的方法有：開(kāi)放尋址法（線性探測(cè)再散列、二次探測(cè)再散列、偽隨機(jī)探測(cè)再散列）、再散列法、鏈地址法、建立一個(gè)公共溢出區(qū)等。查找過(guò)程中，關(guān)鍵碼的比較次數(shù)，取決于產(chǎn)生沖突的多少，產(chǎn)生的沖突少，查找效率就高，產(chǎn)生的沖突多，查找效率就低。因此，影響產(chǎn)生沖突多少的因素，也就是影響查找效率的因素。影響產(chǎn)生沖突多少有以下三個(gè)因素：散列函數(shù)是否均勻、處理沖突的方法、散列表的裝填因子。通過(guò)查

36、找相關(guān)資料還了解了著名的hash算法：MD4、MD5、SHA-1 及其他。哈希表的主要用途為：文件校驗(yàn)、數(shù)字簽名、鑒權(quán)協(xié)議等。這也是對(duì)于以后繼續(xù)研究數(shù)據(jù)結(jié)構(gòu)所必須了解的知識(shí)。</p><p>　　這次課程設(shè)計(jì)，我明白了對(duì)于編寫(xiě)程序，解題的思路尤為重要。在編寫(xiě)程序之前，如果沒(méi)有比較清晰的思路，根本不可能編出好的程序。就算馬馬虎虎的編出來(lái)，程序的邏輯性、健壯性、完善性、合理性也不會(huì)很強(qiáng)。在編程之前，我們應(yīng)反復(fù)研究題目

37、要求，對(duì)題目涉及的情況進(jìn)行比較充分的分析，以便編寫(xiě)出更加符合題意的程序；其次要充分考慮各種臨界情況，對(duì)一些錯(cuò)誤的輸入進(jìn)行處理。因此在我們編程序之前一定要做好充分的準(zhǔn)備，首先要理清自己的思路，然后再將思路分劃成幾個(gè)模塊，逐塊的寫(xiě)好算法，最后再將所有的模塊有機(jī)的聯(lián)系起來(lái)，組成一個(gè)完整的程序。在成功通過(guò)編譯的情況下，對(duì)程序運(yùn)行的結(jié)果進(jìn)行系統(tǒng)的分析，檢驗(yàn)其正確性，如果有錯(cuò)誤，應(yīng)立即去分析源程序的邏輯錯(cuò)誤，直到得到正確的結(jié)果。</p>

38、<p>　　在這次課程設(shè)計(jì)的過(guò)程中，我也遇到了很多難題。在種種的困難中，我明白了在編寫(xiě)程序時(shí)要有耐心。如果你沒(méi)有耐心，即使再好的算法思路也不會(huì)得到很好的表達(dá)，特別是在調(diào)試的過(guò)程中，對(duì)于各種各樣的錯(cuò)誤，要特別的有耐心去自習(xí)分析原因，特別是一些基本的語(yǔ)法錯(cuò)誤，不能一看到錯(cuò)誤很多就亂了陣腳，更不能輕易的放棄，半途而廢。比如在調(diào)試中沒(méi)有定義某些變量的錯(cuò)誤、基本的輸入輸出錯(cuò)誤、數(shù)據(jù)選取不合理的錯(cuò)誤、變量名前后不一的錯(cuò)誤、函數(shù)返回值的

39、錯(cuò)誤等等。其實(shí)只要有耐心，你就會(huì)發(fā)現(xiàn)，在你修改了一個(gè)錯(cuò)誤之后，其它有的錯(cuò)誤也會(huì)跟著消失，所以在編譯的時(shí)候一定要有耐心。</p><p>　　數(shù)據(jù)結(jié)構(gòu)是一門(mén)比較難的課程，需要花很多的時(shí)間去不斷地練習(xí)和實(shí)踐。要想把這門(mén)課程學(xué)好學(xué)精并非一件容易的事，特別是一些經(jīng)典算法，是幾十年前人智慧的結(jié)晶，對(duì)于初學(xué)者的理解和應(yīng)用有一定的難度；但是事在人為，只要肯下功夫，便一定可以學(xué)好。總的來(lái)說(shuō)，這次程序設(shè)計(jì)讓我獲益匪淺，相信在以后的

40、學(xué)習(xí)生活中我也能從中獲得啟發(fā)。</p><p>　　6.2對(duì)算法改進(jìn)的想法</p><p>　　本次哈希表的設(shè)計(jì)采用的存儲(chǔ)結(jié)構(gòu)為順序存儲(chǔ)，這樣的存儲(chǔ)結(jié)構(gòu)簡(jiǎn)單易操作，但是必須實(shí)現(xiàn)給定存儲(chǔ)大小，這樣不利于動(dòng)態(tài)操作，在題目允許的情況下，可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，從而實(shí)現(xiàn)動(dòng)態(tài)存儲(chǔ)；對(duì)關(guān)鍵字的選取還可以按照各個(gè)姓名的字母表的順序等方式，哈希地址的除留余數(shù)法的模還可以是其他的接近表長(zhǎng)的素?cái)?shù)，解決沖突的偽隨

41、機(jī)序列取余的模長(zhǎng)也可以是其他的接近表長(zhǎng)的素?cái)?shù)；本次哈希表的總長(zhǎng)度為50，而實(shí)際只用到了30個(gè)，還余下20個(gè)空閑地址被白白浪費(fèi)了，可以在滿足題目要求的情況下適當(dāng)?shù)倪x取小一點(diǎn)的總表長(zhǎng)。</p><p><b>　　7.哈希表和源程序</b></p><p><b>　　7.1哈希表</b></p><p>　　經(jīng)過(guò)分析，最后得

42、到的哈希表如下：</p><p><b>　　7.2源程序</b></p><p>　　整個(gè)程序的源代碼為：</p><p><b>　　參考文獻(xiàn)：</b></p><p>　　《數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）》，嚴(yán)蔚敏 吳偉民 編著，清華大學(xué)出版社，出版時(shí)間：1997.4</p><p&

43、gt;　　《數(shù)據(jù)結(jié)構(gòu)題集（C語(yǔ)言版）》，嚴(yán)蔚敏 吳偉民 米寧 編著，清華大學(xué)出版社，出版時(shí)間：2000.11</p><p>　　本科生課程設(shè)計(jì)成績(jī)?cè)u(píng)定表</p><p>　　班級(jí)：計(jì)算機(jī)班 　 姓名：　　學(xué)號(hào)：</p><p>　　注：最終成績(jī)以五級(jí)分制記。優(yōu)（90-100分）、良（80-89分）、中（70-79分）、</p><p>