課程設計試驗報告哈希表的設計與實現(xiàn)[共25頁]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

14、0];//節(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]) //以電話號碼為關鍵字建立哈希函數(shù) { key=(int)num[2]

15、; while(num[i]!=NULL) { key+=(int)num[i]; i++; } key=key%20; } b) void hash2(char name[8]) //以用戶名為關鍵字建立哈希函數(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]) //在以電話號碼為關鍵字的哈希表中查找用戶信息 { 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]) // 在以用戶名為關鍵字的哈希表中查找用戶信息 { 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ù)中，包括所有功能對應的數(shù)值，使之和主菜單相對應。 ***********************

18、****主函數(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上機調試 1首先鍵入0,添加結點信息,然后按1進行查找,分別進行號碼和姓名查找,最后可在主菜單中，選擇號碼散列和姓名散列,由此查看程序運行結果。 2語法錯誤及修改：程序是分塊寫的,調試時可以使用分步調試的方式進行,以便能查找看程序是在哪出錯了。本算法使用了鏈表結構和鏈地址法解決沖突的問題，在以姓名為關鍵字的哈希表中要注意涉及ASCLL碼的類型轉換，要注意輸出不能是“%d”，

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

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

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

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

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

26、define NULL 0 unsigned int key; //定義兩個關鍵字 unsigned int key2; int *p; struct node //建節(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ù) ，以電話號碼為關鍵字建立哈希函數(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ù) 以用戶名為關鍵字建立哈希函數(shù) //利用強

28、制類型轉換，將用戶名的每一個字母的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é)點信息 ，建立結點，并將結點的next指針指空 { node *temp; temp = new node; //new的功能是動態(tà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ù)計算出對應關鍵字的存儲地址 hash2(newname->name); newphone->next = phone[key]->next; //利用電話號碼為關鍵字插入 phone[key]->next=newphone; //是采用鏈地址法，拉鏈法處理沖突的散列表結構 newname->next = nam[key2]->next; //利用用戶名為關鍵字插入 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]) //在以電話號碼為關鍵字的哈希表中查找用戶信息 { 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]) // 在以用戶名為關鍵字的哈希表中查找用戶信息 { 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("姓名散列結果:\n"); list2();} if(sel==0) {printf("請輸入要添加的內容:\n"); apend();} if(sel==3) {printf("號碼散列結果:\n"); list(); } if(sel==4) {printf("列表已清空:\n"); create();create2();} if(sel==6) return 0; } return 0; }