計(jì)算機(jī)課程設(shè)計(jì)---基于哈希表的學(xué)生信息查詢系統(tǒng)的實(shí)現(xiàn)

1、<p><b>　　課程設(shè)計(jì)報(bào)告書</b></p><p>　　課程名稱： 計(jì)算機(jī)技術(shù)課程設(shè)計(jì) </p><p>　　題 目： 基于哈希表的學(xué)生信息查詢系統(tǒng)的實(shí)現(xiàn) </p><p>　　系 （院）： </p><p>

2、;　　學(xué) 期： 2011—2012學(xué)年第2學(xué)期 </p><p>　　專業(yè)班級(jí)： 電子信息工程 D電子091 </p><p>　　姓 名： </p><p>　　學(xué) 號(hào)： </p>

3、<p>　　一、題目：基于哈希表的學(xué)生信息查詢系統(tǒng)的實(shí)現(xiàn)</p><p><b>　　二、設(shè)計(jì)任務(wù)</b></p><p>　　1、針對(duì)D電子091班級(jí)的學(xué)生名設(shè)計(jì)一個(gè)哈希表，使得平均查找長度不超過R，完成相應(yīng)的建立和查表程序。</p><p>　　2、姓名為漢語拼音形式，最長不超過18個(gè)字符。</p><p>

4、;　　3、待填入哈希表的學(xué)生名有45人，平均查找長度為2。哈希表用除留余數(shù)法構(gòu)造，用隨機(jī)探測再散列法處理沖突。</p><p>　　4、在輸入人名過程中能自動(dòng)識(shí)別非法輸入，并給與非法輸入的反饋信息要求重新輸入。</p><p><b>　　5、測試數(shù)據(jù)：</b></p><p><b>　　輸入數(shù)據(jù)：</b></p&

5、gt;<p>　　在輸入是可以輸入非法數(shù)據(jù)來檢驗(yàn)如：12345，$%&^&等等</p><p>　　2）查找輸入：chenjimei 輸出：查找成功</p><p>　　輸入：chenjinmen 輸出：查找失敗</p><p>　　輸入：chenyang 輸出：查找成功</p>&

6、lt;p>　　輸入：yangchen 輸出：查找失敗 （在輸入時(shí)也輸入非法數(shù)據(jù)來檢驗(yàn)）</p><p><b>　　三、設(shè)計(jì)原理</b></p><p><b>　　除留余數(shù)法：</b></p><p>　　取關(guān)鍵字被某個(gè)不大于哈希表長m的數(shù)P除后所得余數(shù)為哈希地址。 </p>

7、<p>　　H(key)=key MOD P (P<=m)</p><p><b>　　隨機(jī)探測再散列法：</b></p><p>　　選擇一個(gè)隨機(jī)函數(shù)，取關(guān)鍵字的隨機(jī)函數(shù)值為它的哈希地址，即</p><p>　　Hi=random(key) MOD P (P<=m)</p><p>　　其中

8、random 為隨機(jī)函數(shù)。通常用于關(guān)鍵字長度不等時(shí)采用此法。</p><p><b>　　四、設(shè)計(jì)方案</b></p><p>　　1、采用的設(shè)計(jì)方法：</p><p>　?。?）對(duì)于以學(xué)號(hào)為關(guān)鍵字的散列函數(shù)，是將十一個(gè)數(shù)字全部相加，然后對(duì)20求余。得到的數(shù)作為地址。對(duì)于以姓名為關(guān)鍵字的散列函數(shù)，是將所有字母的ASCLL碼值相加，然后對(duì)20求余

9、。.0</p><p>　?。?）要添加用戶信息，即要有實(shí)現(xiàn)添加結(jié)點(diǎn)的功能的函數(shù)，所以要設(shè)計(jì)一個(gè)必須包括一個(gè)輸入結(jié)點(diǎn)信息、添加結(jié)點(diǎn)的函數(shù)；</p><p>　?。?）要實(shí)現(xiàn)查找函數(shù)，則必須包括一個(gè)查找結(jié)點(diǎn)的函數(shù)；</p><p>　　另外還有一個(gè)必不可少的就是運(yùn)行之后要有一個(gè)主菜單，即要設(shè)計(jì)一個(gè)主函數(shù)（main()）。</p><p>　　本

10、設(shè)計(jì)涉及到的數(shù)據(jù)結(jié)構(gòu)為：哈希表。要求輸入學(xué)號(hào)、姓名、地址三個(gè)信息，并要求分別以學(xué)號(hào)和姓名為關(guān)鍵字進(jìn)行查找，所以本問題要用到兩個(gè)哈希函數(shù)，進(jìn)行哈希查找。</p><p>　　在鏈地址法中，每個(gè)結(jié)點(diǎn)對(duì)應(yīng)一個(gè)鏈表結(jié)點(diǎn)，它由三個(gè)域組成，而由于該程序需要分別用學(xué)號(hào)和姓名為關(guān)鍵字建立哈希表，所以該鏈表結(jié)點(diǎn)它是由四個(gè)域組成，鏈接地址法結(jié)點(diǎn)結(jié)構(gòu)如圖：</p><p>　　name[8]num[11]a

11、ddress[20]next</p><p>　　其中name[8]和num[11]是分別為以學(xué)號(hào)和姓名為關(guān)鍵字域，存放關(guān)鍵字（key）；address[20](data)為結(jié)點(diǎn)的數(shù)據(jù)域，用來存儲(chǔ)用戶的地址。Next指針是用來指向下一個(gè)結(jié)點(diǎn)的地址。</p><p><b>　　2、流程圖</b></p><p>　?。?）Hash函數(shù)流程圖&

12、lt;/p><p><b>　　*</b></p><p>　　4.1 Hash函數(shù)流程圖</p><p>　?。?）以姓名為關(guān)鍵字的hash函數(shù)流程圖</p><p>　　4.2以姓名為關(guān)鍵字的hash函數(shù)流程圖</p><p>　?。?）添加信息節(jié)點(diǎn)流程圖</p><p>

13、　　4.3添加信息節(jié)點(diǎn)流程圖</p><p>　?。?）姓名查找流程圖</p><p>　　4.4姓名查找流程圖</p><p>　　（5）學(xué)號(hào)查詢流程圖</p><p>　　4.5學(xué)號(hào)查詢流程圖</p><p><b>　　五、設(shè)計(jì)結(jié)果</b></p><p><b

14、>　　1、運(yùn)行實(shí)例界面</b></p><p>　?。?）以下是主界面：</p><p><b>　　5.1主界面</b></p><p>　　（2）以下是添加功能： </p><p><b>　　5.2添加功能</b></p><p>　?。?）以下是查找

15、功能：</p><p><b>　　5.3查找功能</b></p><p>　?。?）以下是顯示所有的功能：</p><p>　　5.4顯示所有的功能</p><p>　?。?）以下是刪除的功能：</p><p><b>　　5.5刪除的功能</b></p>&

16、lt;p><b>　?。?）以下是退出：</b></p><p><b>　　5.6退出</b></p><p><b>　　2.運(yùn)行結(jié)果分析</b></p><p>　　通過對(duì)各功能模塊進(jìn)行詳細(xì)設(shè)計(jì)，并進(jìn)行充分的測試，發(fā)現(xiàn)基本能夠達(dá)到預(yù)期的結(jié)果，功能也比較完善。但在功能上仍存在一定的不足，經(jīng)常

17、出現(xiàn)好幾種問題</p><p>　　問題1：運(yùn)行結(jié)果出現(xiàn)人名出現(xiàn)<null>,并且擁有查找長度，使得最終的平均查找長度不正確。</p><p>　　分析： 通過重新修改程序，避免了此事件的發(fā)生。</p><p>　　問題2：運(yùn)行結(jié)果出現(xiàn)錯(cuò)誤，提示內(nèi)存不足。</p><p>　　分析：哈希表的長度設(shè)置太短，實(shí)用偽隨機(jī)探測再散列法處理

18、沖突并不難把數(shù)據(jù)完全填入表中。通過修改哈希表長度即可</p><p>　　問題3：調(diào)式過程經(jīng)常遇到標(biāo)點(diǎn)符號(hào)遺失，或者運(yùn)用錯(cuò)誤，造成了許多了麻煩。</p><p>　　分析：通過出錯(cuò)信息，不斷尋找錯(cuò)誤點(diǎn)，并修正。</p><p>　　3，設(shè)計(jì)心得以及總結(jié)</p><p>　　這次課程設(shè)計(jì)鞏固和加深了對(duì)數(shù)據(jù)結(jié)構(gòu)的理解，提高綜合運(yùn)用本課程所學(xué)知識(shí)的

19、能力。培養(yǎng)獨(dú)立思考，深入研究，分析問題、解決問題的能力。通過實(shí)際編譯系統(tǒng)的分析設(shè)計(jì)、編程調(diào)試，掌握應(yīng)用軟件的分析方法和工程設(shè)計(jì)方法。在本次課程設(shè)計(jì)中，不得不提的還有合作。雖說課題不是太難，但有時(shí)自己想不明白，通過大家的討論可以更快和更有效率的解決問題，而且映象還很深刻。所以以后要多多和同學(xué)討論，畢竟自己的不可能想得很全。</p><p>　　通過這次課程設(shè)計(jì)，讓我學(xué)到了很多，讓我知道了認(rèn)真上好專業(yè)實(shí)驗(yàn)課的重要性，

20、以后多在實(shí)踐中鍛煉自己，畢竟說和做還是有很大差距的，而且寫程序的過程中要考慮周到，嚴(yán)密。在做設(shè)計(jì)的時(shí)候要有信心，有耐心，切勿浮躁。認(rèn)真的學(xué)習(xí)課本知識(shí)，掌握課本中的知識(shí)點(diǎn)，并在此基礎(chǔ)上學(xué)會(huì)靈活運(yùn)用。在課余時(shí)間里多寫程序，熟練掌握在調(diào)試程序的過程中所遇到的常見錯(cuò)誤。</p><p><b>　　六、源程序清單</b></p><p><b>　　建立節(jié)點(diǎn)<

21、/b></p><p>　　struct node </p><p><b>　　{ </b></p><p>　　char name[8],address[20]; </p><p>　　char num[11]; </p><p>　　node * next; </p>&

22、lt;p><b>　　}; </b></p><p>　　typedef node* pnode; //可以為一個(gè)已有的數(shù)據(jù)類型聲明多個(gè)別名，這里為該類型聲明了兩個(gè)指針</p><p>　　typedef node* mingzi; </p><p>　　node **phone; </p><p>　　node

23、**nam; </p><p><b>　　node *a;</b></p><p><b>　　哈希函數(shù)的定義</b></p><p>　　本程序要設(shè)計(jì)兩個(gè)hash（）函數(shù)，分別對(duì)應(yīng)學(xué)號(hào)和姓名。對(duì)關(guān)鍵字進(jìn)行模運(yùn)算，將運(yùn)算結(jié)果所得的余數(shù)作為關(guān)鍵字（或結(jié)點(diǎn)）的存儲(chǔ)地址，方法如下：以學(xué)號(hào)為關(guān)鍵字建立哈希函數(shù)hash(char

24、num[11])。以姓名為關(guān)鍵字建立哈希函數(shù)hash2(char name[8])。利用強(qiáng)制類型轉(zhuǎn)換，將姓名的每一個(gè)字母的ASCLL碼值相加并且除以20后的余數(shù)。將計(jì)算出來的數(shù)作為該結(jié)點(diǎn)的地址賦給key2。</p><p>　　void hash(char num[11]); //以學(xué)號(hào)為關(guān)鍵字建立哈希函數(shù)</p><p>　　//哈希函數(shù)的主旨是將學(xué)號(hào)的十一位數(shù)字全部加起來 </p

25、><p><b>　　{ </b></p><p>　　int i = 3; </p><p>　　key=(int)num[2]; </p><p>　　while(num[i]!=NULL) </p><p><b>　　{ </b></p><p>

26、　　key+=(int)num[i]; </p><p><b>　　i++; </b></p><p><b>　　} </b></p><p>　　key=key%20; } //利用強(qiáng)制類型轉(zhuǎn)換，將姓名的每一個(gè)字母的ASCLL碼值相加并且除以20后的余數(shù) </p><p>　　

27、void hash2(char name[8]); //哈希函數(shù) 以姓名為關(guān)鍵字建立哈希函數(shù)</p><p><b>　　{ </b></p><p>　　int i = 1; </p><p>　　key2=(int)name[0]; </p><p>　　while(name[i]!=NULL) </p>

28、<p><b>　　{ </b></p><p>　　key2+=(int)name[i]; </p><p><b>　　i++; </b></p><p><b>　　} </b></p><p>　　key2=key2%20; </p><

29、;p><b>　　}</b></p><p><b>　　哈希查找</b></p><p>　　想要實(shí)現(xiàn)查找功能，同樣需要兩個(gè)查找函數(shù)，無論以姓名還是以學(xué)號(hào)為關(guān)鍵字，首先，都需要利用hash函數(shù)來計(jì)算出地址。再通過比對(duì)，如果是以學(xué)號(hào)為關(guān)鍵字，比較其學(xué)號(hào)是否相同，如果相同則輸出該結(jié)點(diǎn)的所有信息，如果以姓名為關(guān)鍵字，則比較姓名是否相同，如果相同

30、則輸出該結(jié)點(diǎn)的所有信息。如果找不到與之對(duì)應(yīng)相同的，則輸出“無此記錄”。</p><p>　　void find(char num[11]) ; //在以學(xué)號(hào)為關(guān)鍵字的哈希表中查找用戶信息</p><p><b>　　{ </b></p><p>　　hash(num); </p><p>　　node *q=phone[

31、key]->next; </p><p>　　while(q!= NULL) </p><p><b>　　{ </b></p><p>　　if(strcmp(num,q->num)==0) </p><p><b>　　break; </b></p><p>

32、　　q=q->next; </p><p><b>　　} </b></p><p><b>　　if(q) </b></p><p>　　printf("%s_%s_%s\n",q->name,q->address,q->num);</p><p>　　

33、else printf("無此記錄\n"); </p><p><b>　　} </b></p><p>　　void find2(char name[8]) ;// 在以姓名為關(guān)鍵字的哈希表中查找用戶信息</p><p><b>　　{ </b></p><p>　　hash2

34、(name); </p><p>　　node *q=nam[key2]->next; </p><p>　　while(q!= NULL) </p><p><b>　　{ </b></p><p>　　if(strcmp(name,q->name)==0) </p><p><

35、;b>　　break; </b></p><p>　　q=q->next; </p><p><b>　　}</b></p><p><b>　　七、參考文獻(xiàn)</b></p><p>　　1）《C程序設(shè)計(jì)（第三版）》 譚浩強(qiáng) 清華大學(xué)出版社 2005