計算機課程設計---基于哈希表的學生信息查詢系統(tǒng)的實現(xiàn)

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

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

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

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

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

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

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

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

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

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

11、ddress[20]next</p><p>　　其中name[8]和num[11]是分別為以學號和姓名為關(guān)鍵字域，存放關(guān)鍵字（key）；address[20](data)為結(jié)點的數(shù)據(jù)域，用來存儲用戶的地址。Next指針是用來指向下一個結(jié)點的地址。</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é)點流程圖</p><p>

13、　　4.3添加信息節(jié)點流程圖</p><p>　?。?）姓名查找流程圖</p><p>　　4.4姓名查找流程圖</p><p>　?。?）學號查詢流程圖</p><p>　　4.5學號查詢流程圖</p><p><b>　　五、設計結(jié)果</b></p><p><b

14、>　　1、運行實例界面</b></p><p>　?。?）以下是主界面：</p><p><b>　　5.1主界面</b></p><p>　?。?）以下是添加功能： </p><p><b>　　5.2添加功能</b></p><p>　　（3）以下是查找

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>　　（6）以下是退出：</b></p><p><b>　　5.6退出</b></p><p><b>　　2.運行結(jié)果分析</b></p><p>　　通過對各功能模塊進行詳細設計，并進行充分的測試，發(fā)現(xiàn)基本能夠達到預期的結(jié)果，功能也比較完善。但在功能上仍存在一定的不足，經(jīng)常

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

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

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

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

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; //可以為一個已有的數(shù)據(jù)類型聲明多個別名，這里為該類型聲明了兩個指針</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>　　本程序要設計兩個hash（）函數(shù)，分別對應學號和姓名。對關(guān)鍵字進行模運算，將運算結(jié)果所得的余數(shù)作為關(guān)鍵字（或結(jié)點）的存儲地址，方法如下：以學號為關(guān)鍵字建立哈希函數(shù)hash(char

24、num[11])。以姓名為關(guān)鍵字建立哈希函數(shù)hash2(char name[8])。利用強制類型轉(zhuǎn)換，將姓名的每一個字母的ASCLL碼值相加并且除以20后的余數(shù)。將計算出來的數(shù)作為該結(jié)點的地址賦給key2。</p><p>　　void hash(char num[11]); //以學號為關(guān)鍵字建立哈希函數(shù)</p><p>　　//哈希函數(shù)的主旨是將學號的十一位數(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; } //利用強制類型轉(zhuǎn)換，將姓名的每一個字母的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>　　想要實現(xiàn)查找功能，同樣需要兩個查找函數(shù)，無論以姓名還是以學號為關(guān)鍵字，首先，都需要利用hash函數(shù)來計算出地址。再通過比對，如果是以學號為關(guān)鍵字，比較其學號是否相同，如果相同則輸出該結(jié)點的所有信息，如果以姓名為關(guān)鍵字，則比較姓名是否相同，如果相同

30、則輸出該結(jié)點的所有信息。如果找不到與之對應相同的，則輸出“無此記錄”。</p><p>　　void find(char num[11]) ; //在以學號為關(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>　　七、參考文獻</b></p><p>　　1）《C程序設計（第三版）》 譚浩強 清華大學出版社 2005