課程設計試驗報告-哈希表的設計與實現

1、數據結構課程設計題目哈希表的設計與實現作者院系信息工程學院專業(yè)信息管理與信息系統(tǒng)學號1514210117扌旨導老師張慧答辯時間 2016 年12月18日目錄數據結構課程設計01系統(tǒng)需求分析21.1用戶需求分析31.2功能需求分析 31.3數據需求分析 31.4小結42系統(tǒng)設計42.1設計內容及要求42.2總體設計思路42.3程序詳細設計流程圖52.31以姓名為關鍵字的Hash()函數流程圖 52.32添加結點信息流程圖: 72.33按姓名查找流程圖: 82.34按號碼查找流程圖92.35 主程序流程圖 92.4詳細設計編碼 112.41建立節(jié)點112.42對哈希函數的定義112.43哈希查找1

2、22.44主函數123系統(tǒng)測試133.1上機調試133.2調試結果與分析1418184總結 5附錄1系統(tǒng)需求分析在信息化時代的今天，計算機技術已經是發(fā)展到一個很可觀的地步了，特別是 面向窗口的操作系統(tǒng)的出現，使得程序設計更加的容易了。在過去計算機內存容量 小，CPU計算速度慢，關于程序設計中的數據結構也因此提出來很多的關于解決這 方面的問題。哈希表就是其中之一，哈希表是一個由關鍵字與值組成的特殊的一種 數據結構。它的出現主要是為了解決在結構中查找記錄時需要進行一系列和關鍵字 的比較,這一類查找方法是建立在“比較”的基礎上的，在順序等的查找中，查找的 效率是依賴于查找過程中所比較的次數。理想的情

3、況是希望不經過任何的比較一次存取便能得到所查記錄，那就必須在 記錄的存儲位置和它的關鍵字之間建立一個確定的對應關系，使得每個關鍵字和結 構中一個唯一的存儲位置相對應。因而在查找時只要根據這個對應關系找到給定的 值的像。若結構中存在關鍵字和該值相等的記錄，則所要查找的數就必定就是這個 所查找到的記錄。哈希函數是建立哈希表的一個重要的成員，它的構造方法分為以下幾種：直接定址法、數字分析法、平方取中法、折疊法、除留余數法、隨機數法。本程序中主要用的是除余取留法，除留取余法主要是取關鍵字被某個不大于哈 希表表長m的數p出后所得余數為哈希地址即：H(key)=key MOtp, p<=m這是一種

4、最簡單，也是一種最常用的構造函數的方法，它不僅可以對關鍵字直接取模，也可 在折疊、平方中等運算之后取模。在哈希表的建立中，很容易出現同義詞，這些同義詞的出現也導致了建立哈希 表時沖突的出現，如果不解決這些沖突那么建立好的哈希表與預料的哈希表不同。 關于處理沖突的方法主要有：開放定址法、再哈希法、鏈地址法。本程序中主要用 的就是鏈地址法萊解決沖突的。1.1用戶需求分析設計一個程序能夠使用哈希表實現電話號碼查詢系統(tǒng)。該系統(tǒng)能夠從鍵盤輸入 各記錄，分別以電話號碼和用戶名為關鍵字建立哈希表，能夠從輸入記錄中查找并 顯示給定用戶的記錄，最后并且能夠進行清除記錄和退出功能。1.2功能需求分析(1) 設計一

5、個結點使該結點包括電話號碼、用戶名、地址。(2) 利用用戶名和電話號碼為關鍵字建立哈希表，哈希函數用除留余數法構照(3) 禾I用鏈表法處理沖突問題。(4) 查找并顯示給定用戶名，地址，電話號碼的記錄。(5) 顯示哈希表中的給定用戶的記錄。(6) 當完成操作后，可以退出系統(tǒng)。1.3數據需求分析由問題分析知，本設計主要要求分別以電話號碼和用戶名為關鍵字建立哈希表， 并實現查找功能。所以本設計的核心問題是如何解決散列的問題，亦即設計一個良 好的哈希表。由于結點的個數無法確認，并且如果采用線性探測法散列算法，刪除 結點會引起“信息丟失”的問題。所以采用鏈地址法散列算法。采用鏈地址法，當 出現同義詞沖突

6、時，使用鏈表結構把同義詞鏈接在一起，即同義詞的存儲地址不是 散列表中其他的空地址。首先，解決的是定義鏈表結點，在鏈地址法中，每個結點對應一個鏈表結點， 它由三個域組成，而由于該程序需要分別用電話號碼和用戶名為關鍵字建立哈希表， 所以該鏈表結點它是由四個域組成.name8 、num11和address20都是char浮 點型，輸入輸出都只能是浮點型的。采用鏈地址法，其中的所有同義詞構成一個單鏈表，再由一個表頭結點指向這 個單鏈表的第一個結點。這些表頭結點組成一個一維數組，即哈希表。數組元素的 下標對應由散列函數求出的散列地址。1.4小結通過以上需求分析，知道了設計一個哈希表的目的和能夠 “實現什

7、么功能”，為 接下來的操作明確方向，羅列了需要運用到的知識，自己應該在接下來的程序設計 和實現應該怎么做。2系統(tǒng)設計2.1設計內容及要求本設計主要要求分別以電話號碼和用戶名為關鍵字建立哈希表，并實現查找功 能。本程序的要求是設計散列函數，亦即設計一個良好的哈希表。本程序需要設計 兩個散列函數才能解決問題，程序需要分別為以電話號碼和用戶名為關鍵字建立哈 希表。所以要分別以用戶名、號碼為關鍵字建立兩個散列函數，要添加用戶信息， 即要有實現添加結點的功能的函數，所以要設計一個必須包括一個輸入結點信息、 添加結點的函數；要實現查找函數，則必須包括一個查找結點的函數；另外還有一個必不可少的就是運行之后要

8、有一個主菜單，即要設計一個主函數 (main()。2.2總體設計思路本設計涉及到的數據結構為：哈希表。要求輸入電話號碼、用戶名、地址三個 信息，并要求分別以電話號碼和用戶名為關鍵字進行查找，所以本問題要用到兩個 哈希函數，進行哈希查找。在鏈地址法中，每個結點對應一個鏈表結點，它由三個域組成，而由于該程序需 要分別用電話號碼和用戶名為關鍵字建立哈希表，所以該鏈表結點它是由四個域組 成，鏈地址法結點結構如圖：n ame8nu m11address20n ext其中name8和num11是分別為以電話號碼和用戶名為關鍵字域, (key); address20(data) 為結點的數據域，用來存儲用戶

9、的地址。用來指向下一個結點的地址。存放關鍵字Next指針是2.3程序詳細設計流程圖2.31以姓名為關鍵字的Hash()函數流程圖結束1-1姓名為關鍵字的 Hash()函數流程圖2.32添加結點信息流程圖1-2添加結點信息流程圖2.33按姓名查找流程圖2.34按號碼查找流程圖2.35主程序流程圖初始化散列鏈表(2)并為其動態(tài)分配內存空間Menu ()主 菜單1輸入選擇選6選擇1選7選擇2進行姓名散列Iist2()選擇* 添加記錄 apend()0.進行號碼散列l(wèi)ist()選擇3> 清空 creat();creat2()選擇4查找號碼fin d()輸出 結果查找用戶find2()號碼散列 結

10、果輸岀結姓名散列結果.列表已清, 空選擇5. 退出系統(tǒng)return 02.4詳細設計編碼2.41建立節(jié)點struct node / 建節(jié)點char name8,address20;節(jié)點中要包含用戶名，用戶地址，電話號碼以及指向下一個結點的指針char nu m11;node * n ext;；typedef node* pnode; /typedef可以為一個已有的數據類型聲明多個別名，這里為該類型聲明了兩個指針typedef no de* min gzi;node *ph one;node *n am;node *a;2.42對哈希函數的定義void hash(char num11) /以電

11、話號碼為關鍵字建立哈希函數key=(i nt) nu m2;while( nu mi!=NULL)key+=(i nt) nu mi;i+;key=key%20;b)void hash2(char n ame8)以用戶名為關鍵字建立哈希函數int i = 1;key2=(i nt) name0;while( namei!=NULL)key2+=(i nt)n amei;i+;key2=key2%20;2.43哈希查找void find(char num11) /在以電話號碼為關鍵字的哈希表中查找用戶信息hash( nu m);node *q=pho nekey->n ext;while(

12、q!= NULL)if(strcmp( nu m,q->num)=0)break;q=q->n ext;if(q)prin tf("%s_%s_%sn",q->n ame,q->address,q->nu m);else printf("無此記錄 n");b)、void find2(char name8) /在以用戶名為關鍵字的哈希表中查找用戶信息hash2( name);node *q=n amkey2->n ext;while(q!= NULL)if(strcmp( name,q->n ame)=0)brea

13、k;q=q->n ext;if(q)prin tf("%s_%s_%sn",q->n ame,q->address,q->nu m);else printf("無此記錄 n");2.44主函數主函數本程序需要創(chuàng)建一個主菜單和一個主函數，主菜單便于用戶的使用，主函數中，包 括所有功能對應的數值，使之和主菜單相對應。*主函數界面設計如下*0添加記錄1查找記錄2姓名散列3號碼散列4清空記錄5退出系統(tǒng)void menu（） /菜單 system（"color 2d"）;printf（"*n"）pri

14、ntf（"ttt*歡迎使用 *tttn"）； prin tf（"n"）;printf（"tttt 0.添加記錄 ttttn"）;printf（"tttt 1.查找記錄 ttttn"）;printf（"tttt 2.姓名散列 ttttn"）; printf（"tttt 3.號碼散列 ttttn"）; printf（"tttt 4.清空記錄 ttttn"）; printf（"tttt 5.退出系統(tǒng) ttttn"）;3系統(tǒng)測試3.1上機調試1

15、首先鍵入0,添加結點信息，然后按1進行查找，分別進行號碼和姓名查找，最后可在主 菜單中，選擇號碼散列和姓名散列，由此查看程序運行結果。2語法錯誤及修改：程序是分塊寫的，調試時可以使用分步調試的方式進行，以便能查 找看程序是在哪出錯了。本算法使用了鏈表結構和鏈地址法解決沖突的問題，在以 姓名為關鍵字的哈希表中要注意涉及ASCLL碼的類型轉換，要注意輸出不能是“d”，否則不能輸出結果。編寫程序時要多注意程序中各種指針的使用，還有各 類變量的定義，函數的使用。這些問題均可以根據編譯器的警告提示，對應的將其 解決。3邏輯問題修改和調整：鏈表結構方法雖然方便了運行，但是增加了對算法過程的 認識難度。在本

16、程序中每一個函數中都需要涉及到指針的操作。所以需要仔細分析 函數中的指針指向。在插入結點，查找結點時尤為突出。對于主菜單和主函數的對 應，一定要一致，這樣才能保證運行時不會出錯。4時間，空間性能分析：散列法本質上是一種通過關鍵字直接計算存儲地址的方 法。在理想情況下，散列函數可以把結點均勻地分布到散列表中，不發(fā)生沖突，貝U 查找過程無需比較，其時間復雜度 O (n) =1。但在實際使用過程中，為了將范圍 廣泛的關鍵字映射到一組連續(xù)的存儲空間，往往會發(fā)生同義詞沖突，這時在查找過 程中就需要進行關鍵字比較。因此散列法的查找性能取決于3個因素：散列函數、沖突處理方法和填充因子。采用鏈地址法，可以從根

17、本上杜絕“二次聚集”的發(fā)生, 從而提高散列表的均勻度，提高查找性能，不過也會“浪費” 一部分散列表的空間。 當散列函數和沖突處理辦法固定時，散列法的查找性能就取決于散列表的填充因子。 填充因子a=表中已有的結點數/表的長度。填充因子a標志表的添滿程度。很顯然， a越小則發(fā)生沖突的機會就越??； 反之，a越大沖突的機會就越大，查找的性能也就 越低。哈希表鏈地址法查找成功的平均查找長度 SNc=1+a/2。鏈地址法查找不成功的 平均查找長度Un滿足：Unc=a+e-a.由以上可以看出，散列表的平均查找長度是填充 因子的函數，和散列表的長度沒有關系，因此在實際應用中，我們應該選擇一個適 當的填充因子，

18、以便把平均查找長度控制在一個盡量小的范圍內。3.2調試結果與分析程序主菜單3UsersAdm in istt atai LieXop Uebu goo.Mce1'KM KWM-MMH M M KM KMMMM KM M M M M M KM M M K M H KM KMMMMM M M M M K-M K H K KM KMB -添扣記錄1 .香我記糸氏妊名嵌列証號碼欝列乂退岀系貌添加記錄:0冃 WMM-MMWXWMKM9 " G Users'llAdmin istrator lAesMop Uebuq ooqxW0詳輪人慕誼擁的向容：謹輸入姓窯；小明竄入±

19、;n址：rajr輸人氐沿1879152O18BXMX耳X耳XxhxKXXHXHX X”卅耳討耳托X興X第KXMXkhMX就XHxHHKXXK耳貳制耳KxXkXX料XXHXKXKH科対示錄列列錄紙 記記談散in系 和U魚碼守H-. 0 12 35小紅入:肌址;分別按電話號碼和姓名查找B h U WsersI；Adminjsttator L>e£ctop LBebuqoo-eKe'1MM MM M M M MM M K K M M KM KMM;M M;M M M M MMKM M M M M M K M H M M M M KM HMM AM KM M M M M M M

20、 M K M K M MM.K KK M H M KM MX錄錄爲錄絨 ip,記堂散記系 相檢窯碼空出 価信息馬曲腿 0 12 351&號再香詢.T妗卑百詢詣輸入電話號碼：13S92S303MG軸岀音炭的信息：小紆湖南.1399263G8H®XlrfXMKHHWHMXWHHXHX XX KXXXWWWMMWWJfVXNXXWMX KHXyWHMWMKMKWXWXWMWWXWXXVXMXHX »<X XHXXX：WF材齋建葺抵普%欠i里彳尹WKkfM tf H tf KF V bf W氛移加記錄1 .畫找注8姓名散列氛號碼載列叭滑宇記錄3+很出系誌岳號碼査詢，了

21、姓名査詢?請輸入姓名：/卜明竄出胥找鬧信見；小明四_1«7152918«MKM KM MH M M H MM HMM KM KMMKM » M ME-HE M-He H KM MMMMM MM MMM KM M H M M N KMtMM M K M M H MKM M M KMMMMKMKMXHxhmXMKMV I®f? RhxKXMmmXhKX錄最列列錄統(tǒng) IP,記核貳話乘 如U.?;匡空出 訴青爐號請遲 -R44I- 0 12 35分別輸出按姓名和號碼散列的結果B " C:訶 sersl Adm initiator besfctop Ue

22、buqoo!Ke"瑋尹 瑋*處*芹里 f 總冃 MMHMKHKMHKM氛添加記錄 記錄 孔対名鍛列 氛號碼鰹列 耳猜空記錄5 退岀系統(tǒng)2莊名能列椿卑：汁紅-細甬3926305 H8小SL酊 _iar«i52ei88MMHMM KHMM HMMMMlri KM KMMMMMEHMM HMXKMMMM HMMMMMMKM MMHH NKMMMMMM MMMK 9N MMKMHMHMH錄錄列列錄統(tǒng) ip.記核懺記親 如找憶碼空出 質芒芒P用遲 0 12 35.rz 二二； Cl *峠尹齊*x *熬i里使冃瑋託* * 尹0.押加記錄 1査找記錄2 姓宓毓冽 趺號碼骸列 叭清寧記錄5

23、.退圧索統(tǒng)倉碼昶列潔果：廠紅 _.139326308*»® 小 9I_Qjn_1t 791529188 小明 _QJfLl«152018SKM KM HM M H H M34 MM HMM KM KMMMM MFM MEM H-He HHM W>ti MMM KM M M M N KMMM M M H M K% MKM H M KMM-MMMHKMXHxhmXMKMV I®f? RhxKXMmmXhKX錄最列列錄統(tǒng) IP,記核貳話乘 如U.?;匡空出 訴青爐號請遲 -R44I- 0 12 35清空記錄:9 " C: Users Adm i

24、n strator beslctop lllebuqooQe"KM KM M M K K M M M M KMMM H H M M M K M H H H M M KM H MM * MM M M M K M K * K K K KM H M M MMKXXrtKAMKXXXy'|£f HXMXMMKMhKX9.沛卅亍朋1 脊棧記錄 g沽散列 g,號碼散列 U誦空記錄 5”遲出殺踏H楓表已清空:MMH KM MHMM HMM KM KKMMM MEH M M H MMMMM MM MMM WM M H H H N KM KMMMM MM M 94 M M MM M

25、KMkOfMMH耳討耳HxhxX孰KX孜j也彳已冃HXX高XhmHhX”錄錄列列錄統(tǒng) 忻記核散記親 如U.?;碼空出 0 12 35半：4總結經過為期兩周的課程設計，此次課程設計時間雖然比較短暫，但是我通過這次實踐 學到了很多知識，也了解了自己的很多的不足之處。我是一名信息工程學院的學生， 數據結構對于我來說就顯得尤為重要，這也是我必須認真學懂的一門課程。在課程 設計之前，我們已經學習C語言這門課程已經一個學期，對其有了一定的了解，但 是更多的還是停留在學習了解的范圍，對里面的好多東西還是很陌生，并不是很熟 練，有著許多欠缺，更多的在運用起來的時候還是感到很不好動手。C語言課堂上許多關于C語言

26、的語法規(guī)則，聽起來十分枯燥無味，也不容易記住，死記硬背是不 可取的。然而要使用C語言這個工具解決實際問題，又必須掌握它。通過多次上機 練習，對于語法知識有了感性的認識，加深對它的理解，在理解的基礎上就會自然 而然地掌握C語言的語法規(guī)定。對于一些內容自己認為在課堂上聽懂了，但上機實 踐中會發(fā)現原來理解的偏差，更加鞏固了學過的知識，而且在設計的時候學要系統(tǒng) 的知識，也是一個較大的挑戰(zhàn)，某一方面知識的欠缺都將影響到整個程序的設計。 我從原來的對這門課程的不懂，到目前的能夠獨立完成一個小型程序。這次課程設計，重溫了和學習了許多有關 c語言的知識，還掌握了一些現實中編程 的一些小技巧，實際的編程能力也得

27、到了歷練，本次課程設計對我?guī)椭芏唷?附錄*#i nclude<stdio.h> #i nclude<stri ng.h>程序源代碼*#defi ne NULL 0un sig ned int key; /定義兩個關鍵字un sig ned int key2;int *p;struct node / 建節(jié)點每個結點包括用戶姓名、地址、電話號碼、以及指向下 個結點的指針char n ame8,address20;char nu m11;node * n ext;；typedef node* pnode; /typedef 可以為一個已有的數據類型聲明多個別名，這里 為該類

28、型聲明了兩個指針typedef no de* min gzi;node *ph one;node *n am;node *a;void hash(char num11) /哈希函數，以電話號碼為關鍵字建立哈希函數/哈希函數的主旨是將電話號碼的十一位數字全部加起來int i = 3;key=(i nt) nu m2;while( nu mi!=NULL)key+=(i nt) nu mi;i+;key=key%20;void hash2(char name8) /哈希函數 以用戶名為關鍵字建立哈希函數/利用強制類型轉換，將用戶名的每一個字母的ASCLL碼值相加并且除以20后的余數int i =

29、1;key2=(i nt) name0;while( namei!=NULL)key2+=(i nt)n amei;i+;key2=key2%20;node* input() /輸入節(jié)點信息，建立結點，并將結點的 next指針指空node *temp;temp = new node; /new的功能是動態(tài)分配內存，語法形式：new類型名T (初值列表temp->n ext=NULL;printf("請輸入姓名：n");sea nf("%s",temp->n ame);prin tf("輸入地址：n");sea nf(&qu

30、ot;%s",temp->address);prin tf(" 輸入電話：n");sea nf("%s",temp->nu m);return temp; /對于指針類型返回的是地址int ape nd() /添加節(jié)點node *n ewpho ne;node *newn ame;n ewph one=in put();newn ame=n ewph one;n ewph one->n ext=NULL;newn ame->n ext=NULL;hash( newpho ne-> num); /利用哈希函數計算出對

31、應關鍵字的存儲地址hash2( newn ame->n ame);n ewph one->n ext = phon ekey->n ext; /利用電話號碼為關鍵字插入pho nekey-> next=newpho ne; /是采用鏈地址法，拉鏈法處理沖突的散列表結構newn ame-> next = namkey2-> next; /利用用戶名為關鍵字插入n amkey2->n ext=newn ame;return 0;void ereate() /新建節(jié)點int i;pho ne=new pn ode20;/ 動態(tài)創(chuàng)建對象數組for(i=0;i&

32、lt;20;i+)phon ei=new no de;pho nei-> next=NULL;void create2() / 新建節(jié)點int i;nam=new min gzi20;for(i=0;i<20;i+)n ami=new no de;nami-> next=NULL;void list() /顯示列表int i;node *p;for(i=0;i<20;i+)p=ph on ei->n ext;while(p)prin tf("%s_%s_%sn",p->n ame,p->address,p->nu m);p=p

33、->n ext;void list2() /顯示列表int i;node *p;for(i=0;i<20;i+)p=n ami->n ext;while(p)prin tf("%s_%s_%sn",p->n ame,p->address,p->nu m);p=p->n ext;void fin d(char num11) /在以電話號碼為關鍵字的哈希表中查找用戶信息hash( nu m);node *q=pho nekey->n ext;while(q!= NULL)if(strcmp( nu m,q->num)=0)break;q=q->n ext;if(q)prin tf("%s_%s_%sn",q->n ame,q->address,q->nu