第一篇：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)之姓名哈希表的建立及查找
武漢理工大學(xué)《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)說明書
課程設(shè)計(jì)任務(wù)書
學(xué)生姓名： 劉穎 專業(yè)班級(jí)： 計(jì)科1003班 指導(dǎo)教師： 譚新明 工作單位： 計(jì)算機(jī)科學(xué)系 題 目: 哈希表的設(shè)計(jì)與實(shí)現(xiàn) 初始條件：
針對(duì)某個(gè)集體（比如你所在的班級(jí)）中的“人名”設(shè)計(jì)并實(shí)現(xiàn)一個(gè)哈希表，使得平均查找長度不超過R，完成相應(yīng)的建表和查表程序。
（1）假設(shè)人名為中國人姓名的漢語拼音形式。待填入哈希表的人名共有30個(gè)，取平均查找長度的上限為2。
（2）哈希函數(shù)用除留余數(shù)法構(gòu)造
（3）用偽隨機(jī)探測再散列法處理沖突。
（4）測試用例見嚴(yán)蔚敏《數(shù)據(jù)結(jié)構(gòu)習(xí)題集(C語言版)》p166。
要求完成的主要任務(wù):（包括課程設(shè)計(jì)工作量及其技術(shù)要求，以及說明書撰寫等具體要求）
課程設(shè)計(jì)報(bào)告按學(xué)校規(guī)定格式用A4紙打?。〞鴮懀?，并應(yīng)包含如下內(nèi)容：
1.問題描述
簡述題目要解決的問題是什么。2.設(shè)計(jì)
存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)、主要算法設(shè)計(jì)（用類C/C++語言或用框圖描述）、測試用例設(shè)計(jì)； 3.調(diào)試報(bào)告
調(diào)試過程中遇到的問題是如何解決的；對(duì)設(shè)計(jì)和編碼的討論和分析。4.經(jīng)驗(yàn)和體會(huì)（包括對(duì)算法改進(jìn)的設(shè)想）
5.附源程序清單和運(yùn)行結(jié)果。源程序要加注釋。如果題目規(guī)定了測試數(shù)據(jù)，則運(yùn)行結(jié)果要包含這些測試數(shù)據(jù)和運(yùn)行輸出。
說明：
1.設(shè)計(jì)報(bào)告、程序不得相互抄襲和拷貝；若有雷同，則所有雷同者成績均為0分。2.凡拷貝往年任務(wù)書或課程設(shè)計(jì)充數(shù)者，成績一律無效，以0分記。
時(shí)間安排： 1、6月15日～6月21日完成。2、6月22日上午和下午在實(shí)驗(yàn)中心檢查程序、交課程設(shè)計(jì)報(bào)告、源程序（U盤）。
指導(dǎo)教師簽名： 2012年6月14日 系主任（或責(zé)任教師）簽名： 年 月 日
武漢理工大學(xué)《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)說明書
目錄
1問題分析和任務(wù)定義...............................................3 1.1問題描述.......................................................3 1.2問題分析.......................................................3 2開發(fā)平臺(tái).........................................................3 3數(shù)據(jù)類型和系統(tǒng)設(shè)計(jì)...............................................3 3.1存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)...................................................3 3.2主要算法設(shè)計(jì)...................................................4 3.2.1姓名結(jié)構(gòu)體數(shù)組初始化.........................................4 3.2.2獲取關(guān)鍵碼...................................................5 3.2.3哈希表結(jié)構(gòu)體數(shù)組初始化.......................................5 3.2.4構(gòu)造哈希表...................................................5 3.2.5打印哈希表...................................................6 3.2.6在哈希表中查找姓名...........................................6 4調(diào)試結(jié)果與運(yùn)行情況分析...........................................8 4.1程序運(yùn)行結(jié)果...................................................8 4.2運(yùn)行情況分析...................................................9 4.3算法的時(shí)間復(fù)雜度...............................................9 5自我評(píng)價(jià)與總結(jié)...................................................9 6參考文獻(xiàn)........................................................10 7附：源代碼......................................................11
武漢理工大學(xué)《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)說明書
哈希表的設(shè)計(jì)與實(shí)現(xiàn)
1問題分析和任務(wù)定義
1.1問題描述
設(shè)計(jì)哈希表，要求用除留余數(shù)法構(gòu)造哈希函數(shù)，用偽隨機(jī)探測再散列法處理沖突，使平均查找長度的上限為2。待填入哈希表的人名共有30個(gè)，且為中國人姓名的漢語拼音形式。
1.2問題分析
（1）待填入哈希表的人名有30個(gè)，平均查找長度的上限為2。用除留余數(shù)法構(gòu)造哈希表，用偽隨機(jī)探測再散列法處理沖突，完成相應(yīng)的建立和查表程序。
（2）人名為漢語拼音形式，最長不超過20個(gè)字符。
（3）查找成功時(shí)，顯示姓名、關(guān)鍵字、初散列值、再散列值、哈希表中的位置及查找長度；查找失敗時(shí)，顯示無此記錄。
（4）可多次查找，繼續(xù)查找輸入1，退退出輸入0。
2開發(fā)平臺(tái)
系統(tǒng)：Windows 7 開發(fā)工具：Visual studio 2008 語言：C++ 3數(shù)據(jù)類型和系統(tǒng)設(shè)計(jì)
3.1 存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)
typedef struct {
int key;
char *p;}NAME;
武漢理工大學(xué)《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)說明書
typedef struct {
int key;//關(guān)鍵字
int hash;//初始地址
int reha;//再散列值
char *p;//名字
int l;//查找長度 }HASH;3.2主要算法設(shè)計(jì)
3.2.1 NAME（結(jié)構(gòu)體數(shù)組）初始化
NAME a[30];a[0].p=“wangjunzhe”;a[1].p=“mahaiping”;a[2].p=“l(fā)uozijian”;a[3].p=“l(fā)uoxiangzhou”;a[4].p=“zhangkai”;a[5].p=“fengyuyang”;a[6].p=“wuzhenzhen”;a[7].p=“haokaiqi”;a[8].p=“caopu”;a[9].p=“l(fā)iuying”;a[10].p=“cuijuan”;a[11].p=“hanqianqiqn”;a[12].p=“l(fā)ixiaoyu”;a[13].p=“caoyingnan”;a[14].p=“jinbaoyu”;a[15].p=“zhaduo”;a[16].p=“wenbo”;a[17].p=“cuichangwei”;a[18].p=“zhangqiu”;a[19].p=“l(fā)uopeng”;a[20].p=“hudie”;a[21].p=“xieshanshan”;a[22].p=“l(fā)iming”;a[23].p=“zhangshuai”;a[24].p=“qiuyajun”;a[25].p=“yanruibin”;a[26].p=“jiangwei”;a[27].p=“fangzhaohua”;a[28].p=“yujia”;
武漢理工大學(xué)《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)說明書
a[29].p=“l(fā)iuzhenzhen”;3.2.2獲取關(guān)鍵碼
字符串的各個(gè)字符所對(duì)應(yīng)的ASCII碼相加，所得的整數(shù)做為關(guān)鍵字。
int i,s,r;for(i=0;i<30;i++){
s=0;for(r=0;*(a[i].p+r)!='