《課程設(shè)計試驗報告哈希表的設(shè)計與實現(xiàn)[共25頁]》由會員分享，可在線閱讀，更多相關(guān)《課程設(shè)計試驗報告哈希表的設(shè)計與實現(xiàn)[共25頁]（25頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 題 目 哈希表的設(shè)計與實現(xiàn) 作 者 院 系 信息工程學(xué)院 專 業(yè) 信息管理與信息系統(tǒng) 學(xué) 號 1514210117 指導(dǎo)老師 張 慧 答辯時間 2016年12月18日 目錄 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 0 1系統(tǒng)需求分析 2 1.1用戶需求分析 3 1.2功能需求

2、分析 3 1.3數(shù)據(jù)需求分析 3 1.4 小結(jié) 4 2系統(tǒng)設(shè)計 4 2.1設(shè)計內(nèi)容及要求 4 2.2總體設(shè)計思路 4 2.3程序詳細設(shè)計流程圖 5 2.31以姓名為關(guān)鍵字的Hash()函數(shù)流程圖 5 2.32添加結(jié)點信息流程圖: 7 2.33按姓名查找流程圖: 7 2.34按號碼查找流程圖 8 2.35主程序流程圖 9 2.4詳細設(shè)計編碼 11 2.41建立節(jié)點 11 2.42對哈希函數(shù)的定義 11 2.43哈希查找 12 2.44主函數(shù) 12 3系統(tǒng)測試 13 3.1上機調(diào)試 13 3.2調(diào)試結(jié)果與分析 14 4總結(jié) 18 5附錄 18 1

3、系統(tǒng)需求分析 在信息化時代的今天，計算機技術(shù)已經(jīng)是發(fā)展到一個很可觀的地步了，特別是面向窗口的操作系統(tǒng)的出現(xiàn)，使得程序設(shè)計更加的容易了。在過去計算機內(nèi)存容量小，CPU計算速度慢，關(guān)于程序設(shè)計中的數(shù)據(jù)結(jié)構(gòu)也因此提出來很多的關(guān)于解決這方面的問題。哈希表就是其中之一，哈希表是一個由關(guān)鍵字與值組成的特殊的一種數(shù)據(jù)結(jié)構(gòu)。它的出現(xiàn)主要是為了解決在結(jié)構(gòu)中查找記錄時需要進行一系列和關(guān)鍵字的比較,這一類查找方法是建立在“比較”的基礎(chǔ)上的，在順序等的查找中，查找的效率是依賴于查找過程中所比較的次數(shù)。 理想的情況是希望不經(jīng)過任何的比較一次存取便能得到所查記錄，那就必須在記錄的存儲位置和它的關(guān)鍵字之間建立一個確定的

4、對應(yīng)關(guān)系，使得每個關(guān)鍵字和結(jié)構(gòu)中一個唯一的存儲位置相對應(yīng)。因而在查找時只要根據(jù)這個對應(yīng)關(guān)系找到給定的值的像。若結(jié)構(gòu)中存在關(guān)鍵字和該值相等的記錄，則所要查找的數(shù)就必定就是這個所查找到的記錄。 哈希函數(shù)是建立哈希表的一個重要的成員，它的構(gòu)造方法分為以下幾種： 直接定址法、數(shù)字分析法、平方取中法、折疊法、除留余數(shù)法、隨機數(shù)法。 本程序中主要用的是除余取留法,除留取余法主要是取關(guān)鍵字被某個不大于哈希表表長m的數(shù)p出后所得余數(shù)為哈希地址即:H(key)=key MOD p, p<=m，這是一種最簡單，也是一種最常用的構(gòu)造函數(shù)的方法，它不僅可以對關(guān)鍵字直接取模，也可在折疊、平方中等運算之后取模。

5、 在哈希表的建立中，很容易出現(xiàn)同義詞，這些同義詞的出現(xiàn)也導(dǎo)致了建立哈希表時沖突的出現(xiàn)，如果不解決這些沖突那么建立好的哈希表與預(yù)料的哈希表不同。關(guān)于處理沖突的方法主要有：開放定址法、再哈希法、鏈地址法。本程序中主要用的就是鏈地址法萊解決沖突的。 1.1用戶需求分析 設(shè)計一個程序能夠使用哈希表實現(xiàn)電話號碼查詢系統(tǒng)。該系統(tǒng)能夠從鍵盤輸入各記錄，分別以電話號碼和用戶名為關(guān)鍵字建立哈希表，能夠從輸入記錄中查找并顯示給定用戶的記錄，最后并且能夠進行清除記錄和退出功能。 1.2功能需求分析 （1）設(shè)計一個結(jié)點使該結(jié)點包括電話號碼、用戶名、地址。 （2）利用用戶名和電話號碼為

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

7、是散列表中其他的空地址。 首先，解決的是定義鏈表結(jié)點，在鏈地址法中，每個結(jié)點對應(yīng)一個鏈表結(jié)點，它由三個域組成，而由于該程序需要分別用電話號碼和用戶名為關(guān)鍵字建立哈希表，所以該鏈表結(jié)點它是由四個域組成.name[8] 、num[11]和address[20]都是char浮點型，輸入輸出都只能是浮點型的。 采用鏈地址法，其中的所有同義詞構(gòu)成一個單鏈表，再由一個表頭結(jié)點指向這個單鏈表的第一個結(jié)點。這些表頭結(jié)點組成一個一維數(shù)組，即哈希表。數(shù)組元素的下標對應(yīng)由散列函數(shù)求出的散列地址。 1.4 小結(jié) 通過以上需求分析，知道了設(shè)計一個哈希表的目的和能夠“實現(xiàn)什么功能”，為接下來的操作明確方向，羅列了

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

9、主函數(shù)（main()）。 2.2總體設(shè)計思路 本設(shè)計涉及到的數(shù)據(jù)結(jié)構(gòu)為：哈希表。要求輸入電話號碼、用戶名、地址三個信息，并要求分別以電話號碼和用戶名為關(guān)鍵字進行查找，所以本問題要用到兩個哈希函數(shù)，進行哈希查找。 在鏈地址法中，每個結(jié)點對應(yīng)一個鏈表結(jié)點，它由三個域組成，而由于該程序需要分別用電話號碼和用戶名為關(guān)鍵字建立哈希表，所以該鏈表結(jié)點它是由四個域組成，鏈地址法結(jié)點結(jié)構(gòu)如圖： name[8] num[11] address[20] next 其中name[8]和num[11]是分別為以電話號碼和用戶名為關(guān)鍵字域，存放關(guān)鍵字（key）；address[20](data

10、)為結(jié)點的數(shù)據(jù)域，用來存儲用戶的地址。Next指針是用來指向下一個結(jié)點的地址。 2.3程序詳細設(shè)計流程圖 2.31以姓名為關(guān)鍵字的Hash()函數(shù)流程圖 結(jié)束 Key2=key%20 name[i]不為空 開始 i從0開始取 取整型name[0]賦給key2 Key2+=name[i] i++ 1-1 姓名為關(guān)鍵字的Hash()函數(shù)流程圖 2.32添加結(jié)點信息流程圖: 利用用戶名為關(guān)鍵字插入 拉鏈法處理沖突 調(diào)用hash()函數(shù) 調(diào)用hash()函數(shù) Newname指向

11、newphone Newphone=input() 結(jié)束 申請新的結(jié)點newphone,newname即新的號碼和名字 開始 1-2添加結(jié)點信息流程圖: 2.33按姓名查找流程圖: q不為空 結(jié)束 輸出無記錄 輸出相應(yīng)記錄 q=q->next q 不為空 調(diào)用hash()函數(shù)中新結(jié)點q指向phone[key

12、]->next 開始 2.34按號碼查找流程圖 開始 調(diào)用hash2()函數(shù)中新結(jié)點q指向phone[key]->next q 不為空 q=q->next q不為空 輸出無記錄 輸出相應(yīng)記錄 結(jié)束 2.35主程序流程圖 開 始 Main () 初始化散列鏈表（1）并為其動態(tài)分配內(nèi)存空間 初始化散列鏈

13、表（2）并為其動態(tài)分配內(nèi)存空間 Menu（）主菜單 輸入選擇 選擇1 選６ 選7 查找號碼find() 查找用戶 find2() 輸出結(jié)果 輸出結(jié)果 選擇2 選擇0 選擇3 選擇4 選擇5 進行姓名散列l(wèi)ist2() 姓名散列結(jié)果 添加記錄 apend() 退出系統(tǒng)return 0 進行號碼散列 list() 清空creat();creat2() 列表已清空 號碼散列結(jié)果 結(jié) 束 2.4詳細設(shè)計編碼 2.41建立節(jié)點 struct node //建節(jié)點 { char name[8],address[2

14、0];//節(jié)點中要包含用戶名，用戶地址，電話號碼以及指向下一個結(jié)點的指針 char num[11]; node * next; }; typedef node* pnode; //typedef可以為一個已有的數(shù)據(jù)類型聲明多個別名，這里為該類型聲明了兩個指針 typedef node* mingzi; node **phone; node **nam; node *a; 2.42對哈希函數(shù)的定義 void hash(char num[11]) //以電話號碼為關(guān)鍵字建立哈希函數(shù) { key=(int)num[2]

15、; while(num[i]!=NULL) { key+=(int)num[i]; i++; } key=key%20; } b) void hash2(char name[8]) //以用戶名為關(guān)鍵字建立哈希函數(shù) { int i = 1; key2=(int)name[0]; while(name[i]!=NULL) { key2+=(int)name[i]; i++; } key2=key2%20; } 2.43哈希查找 void find(char num

16、[11]) //在以電話號碼為關(guān)鍵字的哈希表中查找用戶信息 { hash(num); node *q=phone[key]->next; while(q!= NULL) { if(strcmp(num,q->num)==0) break; q=q->next; } if(q) printf("%s_%s_%s\n",q->name,q->address,q->num); else printf("無此記錄\n"); } b)、void find2(char name[8]) // 在以用戶名為關(guān)鍵字的哈希表中查找用戶信息 { ha

17、sh2(name); node *q=nam[key2]->next; while(q!= NULL) { if(strcmp(name,q->name)==0) break; q=q->next; } if(q) printf("%s_%s_%s\n",q->name,q->address,q->num); else printf("無此記錄\n"); } 2.44主函數(shù) 主函數(shù) 本程序需要創(chuàng)建一個主菜單和一個主函數(shù)，主菜單便于用戶的使用，主函數(shù)中，包括所有功能對應(yīng)的數(shù)值，使之和主菜單相對應(yīng)。 ***********************

18、****主函數(shù)界面設(shè)計如下************************ 0添加記錄 1查找記錄 2姓名散列 3號碼散列 4清空記錄 5退出系統(tǒng) void menu() //菜單 { system("color 2d"); printf("*

19、*******************************************************************************\n"); printf("\t\t\t***********歡迎使用***********\t\t\t\n"); printf("\n"); printf("\t\t\t\t 0.添加記錄\t\t\t\t\n"); printf("\t\t\t\t 1.查找記錄\t\t\t\t\n"); printf("\t\t\t\t 2.姓名散列\(zhòng)t\t\t\t\n"); printf("\t\t\t\t 3.號碼散列\(zhòng)t\t\t

20、\t\n"); printf("\t\t\t\t 4.清空記錄\t\t\t\t\n"); printf("\t\t\t\t 5.退出系統(tǒng)\t\t\t\t\n"); } 3系統(tǒng)測試 3.1上機調(diào)試 1首先鍵入0,添加結(jié)點信息,然后按1進行查找,分別進行號碼和姓名查找,最后可在主菜單中，選擇號碼散列和姓名散列,由此查看程序運行結(jié)果。 2語法錯誤及修改：程序是分塊寫的,調(diào)試時可以使用分步調(diào)試的方式進行,以便能查找看程序是在哪出錯了。本算法使用了鏈表結(jié)構(gòu)和鏈地址法解決沖突的問題，在以姓名為關(guān)鍵字的哈希表中要注意涉及ASCLL碼的類型轉(zhuǎn)換，要注意輸出不能是“%d”，

21、否則不能輸出結(jié)果。編寫程序時要多注意程序中各種指針的使用，還有各類變量的定義，函數(shù)的使用。這些問題均可以根據(jù)編譯器的警告提示，對應(yīng)的將其解決。 3邏輯問題修改和調(diào)整：鏈表結(jié)構(gòu)方法雖然方便了運行，但是增加了對算法過程的認識難度。在本程序中每一個函數(shù)中都需要涉及到指針的操作。所以需要仔細分析函數(shù)中的指針指向。在插入結(jié)點，查找結(jié)點時尤為突出。對于主菜單和主函數(shù)的對應(yīng)，一定要一致，這樣才能保證運行時不會出錯。 4時間，空間性能分析：散列法本質(zhì)上是一種通過關(guān)鍵字直接計算存儲地址的方法。在理想情況下，散列函數(shù)可以把結(jié)點均勻地分布到散列表中，不發(fā)生沖突，則查找過程無需比較，其時間復(fù)雜度O（n）=1。但

22、在實際使用過程中，為了將范圍廣泛的關(guān)鍵字映射到一組連續(xù)的存儲空間，往往會發(fā)生同義詞沖突，這時在查找過程中就需要進行關(guān)鍵字比較。因此散列法的查找性能取決于3個因素：散列函數(shù)、沖突處理方法和填充因子。采用鏈地址法，可以從根本上杜絕“二次聚集”的發(fā)生，從而提高散列表的均勻度，提高查找性能，不過也會“浪費”一部分散列表的空間。當散列函數(shù)和沖突處理辦法固定時，散列法的查找性能就取決于散列表的填充因子。填充因子a=表中已有的結(jié)點數(shù)/表的長度。填充因子a標志表的添滿程度。很顯然，a越小則發(fā)生沖突的機會就越??；反之，a越大沖突的機會就越大，查找的性能也就越低。哈希表鏈地址法查找成功的平均查找長度SNc=1+a

23、/2。鏈地址法查找不成功的平均查找長度Un滿足：Unc=a+e-a.由以上可以看出，散列表的平均查找長度是填充因子的函數(shù)，和散列表的長度沒有關(guān)系，因此在實際應(yīng)用中，我們應(yīng)該選擇一個適當?shù)奶畛湟蜃?，以便把平均查找長度控制在一個盡量小的范圍內(nèi)。 3.2調(diào)試結(jié)果與分析 程序主菜單 添加記錄: 分別按電話號碼和姓名查找: 分別輸出按姓名和號碼散列的結(jié)果: 清空記錄: 4總結(jié) 經(jīng)過為期兩周的課程設(shè)計，此次課程設(shè)計時間雖然比較短暫，但是我通過這次實踐學(xué)到了很多知識，也了解了自己的

24、很多的不足之處。我是一名信息工程學(xué)院的學(xué)生，數(shù)據(jù)結(jié)構(gòu)對于我來說就顯得尤為重要，這也是我必須認真學(xué)懂的一門課程。在課程設(shè)計之前，我們已經(jīng)學(xué)習(xí)C語言這門課程已經(jīng)一個學(xué)期，對其有了一定的了解，但是更多的還是停留在學(xué)習(xí)了解的范圍，對里面的好多東西還是很陌生，并不是很熟練，有著許多欠缺，更多的在運用起來的時候還是感到很不好動手。C語言課堂上許多關(guān)于C語言的語法規(guī)則，聽起來十分枯燥無味，也不容易記住，死記硬背是不可取的。然而要使用C語言這個工具解決實際問題，又必須掌握它。通過多次上機練習(xí)，對于語法知識有了感性的認識，加深對它的理解，在理解的基礎(chǔ)上就會自然而然地掌握C語言的語法規(guī)定。對于一些內(nèi)容自己認為在課

25、堂上聽懂了，但上機實踐中會發(fā)現(xiàn)原來理解的偏差，更加鞏固了學(xué)過的知識，而且在設(shè)計的時候?qū)W要系統(tǒng)的知識，也是一個較大的挑戰(zhàn)，某一方面知識的欠缺都將影響到整個程序的設(shè)計。我從原來的對這門課程的不懂，到目前的能夠獨立完成一個小型程序。 這次課程設(shè)計，重溫了和學(xué)習(xí)了許多有關(guān)c語言的知識，還掌握了一些現(xiàn)實中編程的一些小技巧，實際的編程能力也得到了歷練，本次課程設(shè)計對我?guī)椭芏唷? 5附錄 ************************程序源代碼************************** #include #include #

26、define NULL 0 unsigned int key; //定義兩個關(guān)鍵字 unsigned int key2; int *p; struct node //建節(jié)點 每個結(jié)點包括用戶姓名、地址、電話號碼、以及指向下一個結(jié)點的指針 { char name[8],address[20]; char num[11]; node * next; }; typedef node* pnode; //typedef可以為一個已有的數(shù)據(jù)類型聲明多個別名，這里為該類型聲明了兩個指針 typedef node* mingzi; node **phone;

27、 node **nam; node *a; void hash(char num[11]) //哈希函數(shù) ，以電話號碼為關(guān)鍵字建立哈希函數(shù) //哈希函數(shù)的主旨是將電話號碼的十一位數(shù)字全部加起來 { int i = 3; key=(int)num[2]; while(num[i]!=NULL) { key+=(int)num[i]; i++; } key=key%20; } void hash2(char name[8]) //哈希函數(shù) 以用戶名為關(guān)鍵字建立哈希函數(shù) //利用強

28、制類型轉(zhuǎn)換，將用戶名的每一個字母的ASCLL碼值相加并且除以20后的余數(shù) { int i = 1; key2=(int)name[0]; while(name[i]!=NULL) { key2+=(int)name[i]; i++; } key2=key2%20; } node* input() //輸入節(jié)點信息 ，建立結(jié)點，并將結(jié)點的next指針指空 { node *temp; temp = new node; //new的功能是動態(tài)分配內(nèi)存，語法形式：new 類型名T（初值列表 temp->next=NULL; print

29、f("請輸入姓名:\n"); scanf("%s",temp->name); printf("輸入地址： \n"); scanf("%s",temp->address); printf("輸入電話：\n"); scanf("%s",temp->num); return temp; //對于指針類型返回的是地址 } int apend() //添加節(jié)點 { node *newphone; node *newname; newphone=input(); newname=newphone; newphone->next=NULL; newna

30、me->next=NULL; hash(newphone->num); //利用哈希函數(shù)計算出對應(yīng)關(guān)鍵字的存儲地址 hash2(newname->name); newphone->next = phone[key]->next; //利用電話號碼為關(guān)鍵字插入 phone[key]->next=newphone; //是采用鏈地址法，拉鏈法處理沖突的散列表結(jié)構(gòu) newname->next = nam[key2]->next; //利用用戶名為關(guān)鍵字插入 nam[key2]->next=newname; return 0; } void create() //新建

31、節(jié)點 { int i; phone=new pnode[20];//動態(tài)創(chuàng)建對象數(shù)組 for(i=0;i<20;i++) { phone[i]=new node; phone[i]->next=NULL; } } void create2() //新建節(jié)點 { int i; nam=new mingzi[20]; for(i=0;i<20;i++) { nam[i]=new node; nam[i]->next=NULL; } } void list() //顯示列表 { int i;

32、node *p; for(i=0;i<20;i++) { p=phone[i]->next; while(p) { printf("%s_%s_%s\n",p->name,p->address,p->num); p=p->next; } } } void list2() //顯示列表 { int i; node *p; for(i=0;i<20;i++) { p=nam[i]->next; while(p) { printf("%s_%s_%s\n",p->name,p->address,p->num);

33、p=p->next; } } } void find(char num[11]) //在以電話號碼為關(guān)鍵字的哈希表中查找用戶信息 { hash(num); node *q=phone[key]->next; while(q!= NULL) { if(strcmp(num,q->num)==0) break; q=q->next; } if(q) printf("%s_%s_%s\n",q->name,q->address,q->num); else printf("無此記錄\n"); } void find2(char

34、 name[8]) // 在以用戶名為關(guān)鍵字的哈希表中查找用戶信息 { hash2(name); node *q=nam[key2]->next; while(q!= NULL) { if(strcmp(name,q->name)==0) break; q=q->next; } if(q) printf("%s_%s_%s\n",q->name,q->address,q->num); else printf("無此記錄\n"); } void menu() //菜單 { printf("0.添加記錄\n"); pri

35、ntf("1.查找記錄\n"); printf("2.姓名散列\(zhòng)n"); printf("3.號碼散列\(zhòng)n"); printf("4.清空記錄\n"); printf("5.退出系統(tǒng)\n"); } int main() { char num[11]; char name[8]; create(); create2() ; int sel; while(1) { menu(); scanf("%d",&sel); if(sel==1) { printf("6號碼查詢，7姓名查詢\n"); int

36、b; scanf("%d",&b); if(b==6) { printf("請輸入電話號碼:\n"); scanf("%s",num); printf("輸出查找的信息:\n"); find(num); } else { printf("請輸入姓名:\n"); scanf("%s",name); printf("輸出查找的信息:\n"); find2(name);}} if(sel==2) {printf("姓名散列結(jié)果:\n"); list2();} if(sel==0) {printf("請輸入要添加的內(nèi)容:\n"); apend();} if(sel==3) {printf("號碼散列結(jié)果:\n"); list(); } if(sel==4) {printf("列表已清空:\n"); create();create2();} if(sel==6) return 0; } return 0; }