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

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

3、lt;/p><p>　　3.1存儲結(jié)構(gòu)設(shè)計4</p><p>　　3.2主要算法設(shè)計4</p><p>　　3.2.1程序主要函數(shù)原型及功能4</p><p>　　3.2.2各函數(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)試報告11</b></p><p>　　4.1調(diào)試中的問題11</p><p>　　4.2對設(shè)計和編碼的討論和分析11</p><p>　　5. 程序運行結(jié)果11</p><p>　　6.經(jīng)驗和體會13</p><p>　　6.1感受和體會

5、13</p><p>　　6.2對算法改進的想法15</p><p>　　7.哈希表和源程序15</p><p><b>　　7.1哈希表15</b></p><p><b>　　7.2源程序16</b></p><p>　　本科生課程設(shè)計成績評定表21</p

6、><p><b>　　課程設(shè)計任務書</b></p><p>　　學生姓名： 專業(yè)班級： 班 </p><p>　　指導教師： 工作單位： 計算機科學系 </p><p>　　題 目: 哈希表設(shè)計

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

25、的函數(shù)void Display()的：</p><p><b>　　主函數(shù)設(shè)計</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></p><p><b>　　4.1調(diào)試中的問題</b></p><p>　　經(jīng)過對哈希表的研究后，即進行程序的設(shè)計和編碼；將原程序編好后，經(jīng)過編譯，有如下幾個問題：</p><p>　

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

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

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

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

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

32、><b>　　選擇S后結(jié)果為：</b></p><p>　　結(jié)果顯示，平均查找長度為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)驗和體會</b></p><p><b>　　6.1感受和體會</b></p><p>　　《數(shù)據(jù)結(jié)構(gòu)》這門課程是計算機專業(yè)一門基礎(chǔ)性學科，重要性可見一斑，學好這門課程對以后人生的發(fā)展具有深遠的影響。而數(shù)據(jù)結(jié)構(gòu)的課程設(shè)計便是對學習效果的檢驗。數(shù)據(jù)結(jié)構(gòu)課程設(shè)計不僅可以鍛煉我們獨立思考問題、解決

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

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

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

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

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

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

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

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

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

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