數(shù)據(jù)結(jié)構(gòu)課程設(shè)計----哈希表設(shè)計

1、<p><b>　　學(xué) 號 </b></p><p><b>　　數(shù)據(jù)結(jié)構(gòu)課程設(shè)計</b></p><p><b>　　設(shè)計說明書</b></p><p>　　起止日期： 2011年 12月 12 日 至 2011 年 12月16日</p><p><

2、;b>　　電子與信息工程系</b></p><p>　　2011年 12月16日</p><p><b>　　課程設(shè)計任務(wù)書</b></p><p>　　2011—2012學(xué)年第1學(xué)期</p><p>　　電子與信息工程 系 軟件工程 專業(yè) 班級</p><p>

3、;　　課程設(shè)計名稱： 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 </p><p>　　設(shè)計題目： 哈希表設(shè)計 </p><p>　　完成期限：自 2011 年 12 月 12 日至 2011 年 12 月 16 日共 1 周</p><p>　　設(shè)計依據(jù)、要求及主要內(nèi)

4、容（可另加附頁）：</p><p><b>　　一、設(shè)計目的</b></p><p>　　熟悉各種數(shù)據(jù)結(jié)構(gòu)和運(yùn)算，會使用數(shù)據(jù)結(jié)構(gòu)的基本操作解決一些實(shí)際問題。</p><p><b>　　二、設(shè)計要求 </b></p><p>　　（1）重視課程設(shè)計環(huán)節(jié)，用嚴(yán)謹(jǐn)、科學(xué)和踏實(shí)的工作態(tài)度對待課程設(shè)計的

5、每一項(xiàng)任務(wù)；</p><p>　　（2）按照課程設(shè)計的題目要求，獨(dú)立地完成各項(xiàng)任務(wù)，嚴(yán)禁抄襲；凡發(fā)現(xiàn)抄襲，抄襲者與被抄襲者皆以零分計入本課程設(shè)計成績。凡發(fā)現(xiàn)實(shí)驗(yàn)報告或源程序雷同，涉及的全部人員皆以零分計入本課程設(shè)計成績；</p><p>　?。?）學(xué)生在接受設(shè)計任務(wù)后，首先要按設(shè)計任務(wù)書的要求編寫設(shè)計進(jìn)程表；</p><p>　　（4）認(rèn)真編寫課程設(shè)計報告。<

6、/p><p><b>　　三、設(shè)計內(nèi)容</b></p><p><b>　　1)問題描述</b></p><p>　　針對某個集體中人名設(shè)計一個哈希表，使得平均查找長度不超過R，并完成相應(yīng)的建表和查表程序。</p><p><b>　　2)基本要求</b></p>&

7、lt;p>　　假設(shè)人名為中國人姓名的漢語拼音形式。待填入哈希表的人名共有30個，取平均查找長度的上限為2。哈希函數(shù)用除留余數(shù)法構(gòu)造，用線性探測再散列法或鏈地址法處理沖突。</p><p><b>　　3)測試數(shù)據(jù)</b></p><p>　　取讀者周圍較熟悉的30個人名。</p><p><b>　　四、參考文獻(xiàn)</b&g

8、t;</p><p>　　1．王紅梅．?dāng)?shù)據(jù)結(jié)構(gòu)．清華大學(xué)出版社</p><p>　　2．王紅梅．?dāng)?shù)據(jù)結(jié)構(gòu)學(xué)習(xí)輔導(dǎo)與實(shí)驗(yàn)指導(dǎo)．清華大學(xué)出版社</p><p>　　3．嚴(yán)蔚敏，吳偉民．?dāng)?shù)據(jù)結(jié)構(gòu)（C語言版）．清華大學(xué)出版社</p><p><b>　　一、需求分析</b></p><p>　　要建立一個

9、哈希表，并完成查詢的功能，首先要定義兩個結(jié)構(gòu)體，一個Name、一個Hash。輸入的時候一定要輸入姓名的拼音，否則將無法實(shí)現(xiàn)。</p><p><b>　　二、問題求解</b></p><p>　　對哈希表的查詢，首先輸入要查詢?nèi)说男彰匆?，然后程序會根?jù)拼音從第一個字母開始查找并輸出其相應(yīng)的ASCII值，依次向后查找，直到字符串結(jié)束，最后輸出總的ASCII碼值，所得A

10、CSII值之和作為關(guān)鍵碼，然后輸出相應(yīng)的查找長度。例如 輸入：xuyanqing 輸出： 關(guān)鍵碼：996 查找長度：1</p><p><b>　　三、總體設(shè)計</b></p><p><b>　　框圖及流程圖：</b></p><p><b>　　四、詳細(xì)設(shè)計</b></p>&

11、lt;p><b>　　結(jié)構(gòu)體：</b></p><p>　　struct Name</p><p><b>　　{</b></p><p>　　char *py; //姓名拼音</p><p>　　int k; //拼音所對應(yīng)的ASCII碼</p><p>&

12、lt;b>　　};</b></p><p>　　struct Hash</p><p><b>　　{</b></p><p><b>　　char *py;</b></p><p><b>　　int k;</b></p><p>　

13、　int si; //查找長度</p><p><b>　　};</b></p><p>　　void main() 主函數(shù)</p><p>　　void ListName() //人名列表</p><p>　　void CreateHashList() //建立Hash表</p><p&g

14、t;　　void HashSearch() //查找</p><p>　　void Display() 顯示</p><p>　　五、關(guān)鍵源程序清單和執(zhí)行結(jié)果</p><p><b>　　源程序：</b></p><p>　　#include<iostream></p><p>

15、;　　#include<string></p><p>　　using namespace std;</p><p>　　#define L 50 //哈希表長度</p><p>　　#define P 47 //隨機(jī)數(shù)</p><p>　　#define N 30 //人名個數(shù)</p><p>　　

16、struct Name</p><p><b>　　{</b></p><p>　　char *py; //姓名拼音</p><p>　　int k; //拼音所對應(yīng)的ASCII碼</p><p><b>　　};</b></p><p>　　Name NameLi

17、st[L];</p><p>　　struct Hash</p><p><b>　　{</b></p><p><b>　　char *py;</b></p><p><b>　　int k;</b></p><p>　　int si; //查找長

18、度</p><p><b>　　};</b></p><p>　　Hash HashList[L];</p><p>　　void ListName() //人名列表</p><p><b>　　{</b></p><p>　　NameList[0].py="zh

19、uangdong";</p><p>　　NameList[1].py="chenmengsheng";</p><p>　　NameList[2].py="chenya";</p><p>　　NameList[3].py="litao";</p><p>　　NameL

20、ist[4].py="xiaqian";</p><p>　　NameList[5].py="aijing";</p><p>　　NameList[6].py="zengguoyan";</p><p>　　NameList[7].py="hantingkai";</p>

21、<p>　　NameList[8].py="yuzhikai";</p><p>　　NameList[9].py="zhangyanyu";</p><p>　　NameList[10].py="ouzining";</p><p>　　NameList[11].py="yuegua

22、ngbo";</p><p>　　NameList[12].py="yinyongchao";</p><p>　　NameList[13].py="wangxiao";</p><p>　　NameList[14].py="heguoqing";</p><p>　　Na

23、meList[15].py="xuyanqing";</p><p>　　NameList[16].py="zhujiongming";</p><p>　　NameList[17].py="zhuanghao";</p><p>　　NameList[18].py="zhangzongang&q

24、uot;;</p><p>　　NameList[19].py="luoqing";</p><p>　　NameList[20].py="zhoukangning";</p><p>　　NameList[21].py="liyuan";</p><p>　　NameList[22

25、].py="xutingting";</p><p>　　NameList[23].py="zhoumeirong";</p><p>　　NameList[24].py="wangshuxia";</p><p>　　NameList[25].py="zhanghuijiuan";&l

26、t;/p><p>　　NameList[26].py="wangpengkun";</p><p>　　NameList[27].py="shenxiaoli";</p><p>　　NameList[28].py="ganyuqin";</p><p>　　NameList[29].p

27、y="sunliwen";</p><p><b>　　char *f;</b></p><p>　　for(int i=0;i<N;i++)// 求出各個姓名的拼音所對應(yīng)的整數(shù)</p><p><b>　　{</b></p><p><b>　　int s=0;

28、</b></p><p>　　f=NameList[i].py;</p><p>　　for(int r=0;*(f+r)!='\0';r++)//將各個字符所對應(yīng)的ASCII碼相加，所得整數(shù)為關(guān)鍵字</p><p>　　s+=*(f+r);</p><p>　　NameList[i].k=s;</p>

29、<p><b>　　}</b></p><p><b>　　}</b></p><p>　　void CreateHashList() //建立Hash表</p><p><b>　　{</b></p><p>　　for(int i=0;i<L;i++)&

30、lt;/p><p><b>　　{</b></p><p>　　HashList[i].py="";</p><p>　　HashList[i].k=0;</p><p>　　HashList[i].si=0;</p><p><b>　　}</b></

31、p><p>　　for(i=0;i<P;i++)</p><p><b>　　{</b></p><p>　　int sum=0;</p><p>　　int adr=(NameList[i].k)%P;</p><p>　　int d=adr;</p><p>　　if

32、(HashList[adr].si==0) //不沖突</p><p><b>　　{</b></p><p>　　HashList[adr].k=NameList[i].k;</p><p>　　HashList[adr].py=NameList[i].py;</p><p>　　HashList[adr].si=1

33、;</p><p><b>　　}</b></p><p>　　while(HashList[d].k!=0&&d!=adr){</p><p><b>　　{</b></p><p>　　d=(d+NameList[i].k%10+1)%P;</p><p>

34、;　　sum=sum+1;</p><p><b>　　}</b></p><p>　　HashList[d].k=NameList[i].k;</p><p>　　HashList[d].py=NameList[i].py;</p><p>　　HashList[d].si=sum+1;}</p><

35、;p><b>　　}</b></p><p><b>　　}</b></p><p>　　void HashSearch() //查找 </p><p><b>　　{</b></p><p>　　string name;</p><p>　　

36、int s=0,r,sum=1;</p><p>　　cout<<"請輸入姓名拼音：";</p><p>　　cin>>name;</p><p>　　for(r=0;r<20;r++) //輸入姓名所對應(yīng)的關(guān)鍵字</p><p>　　s+=name[r];</p><p

37、>　　int adr=s%P;</p><p>　　//int d=adr;</p><p>　　if(HashList[adr].k==s)</p><p>　　{cout<<"姓名："<<HashList[adr].py<<endl;</p><p>　　cout<&

38、lt;"關(guān)鍵字："<<s<<endl;</p><p>　　cout<<"查找長度："<<sum<<endl;</p><p><b>　　}</b></p><p>　　int d=(adr+1)%L;</p><p>

39、　　while(HashList[d].k!=0&&adr!=d)</p><p><b>　　{</b></p><p>　　if(HashList[d].k==s)</p><p><b>　　{</b></p><p>　　cout<<"姓名："

40、<<HashList[d].py<<endl;</p><p>　　cout<<"關(guān)鍵字："<<s<<endl;</p><p>　　cout<<"查找長度："<<sum<<endl;</p><p><b>　　}<

41、;/b></p><p>　　d=(d+1)%L;</p><p><b>　　}</b></p><p>　　if(adr==d) throw "溢出";</p><p>　　else HashList[d].k=s;</p><p><b>　　}</

42、b></p><p>　　void Display()</p><p><b>　　{</b></p><p><b>　　int i;</b></p><p>　　for(i=0;i<30;i++)</p><p>　　cout<<i<<

43、" "<<NameList[i].py<<" "<<NameList[i].k<<endl;</p><p><b>　　}</b></p><p>　　void main()</p><p><b>　　{</b><

44、/p><p><b>　　int x;</b></p><p>　　ListName();</p><p>　　CreateHashList();</p><p>　　cout<<"1. 顯示哈希表 "<<endl;</p><p>　　cout<&l

45、t;"2. 查找 "<<endl;</p><p>　　cout<<"3. 退出 "<<endl;</p><p>　　cout<<"請輸入相應(yīng)的序號：";</p><p><b>　　cin>>x;</b></p>

46、;<p><b>　　if(x==1)</b></p><p>　　Display();</p><p>　　else if(x==2)</p><p>　　HashSearch();</p><p>　　else if(x==3)</p><p><b>　　return

47、;</b></p><p><b>　　else</b></p><p>　　cout<<"輸入錯誤！"<<endl;</p><p><b>　　}</b></p><p><b>　　運(yùn)行結(jié)果：</b></p&g