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

數(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è)計01系統(tǒng)需求分析21.1用戶需求分析31.2功能需求分析31.3數(shù)據(jù)需求分析31.4 小結(jié)42系統(tǒng)設(shè)計42.1設(shè)計內(nèi)容及要求42.2總體設(shè)計思路42.3程序詳細設(shè)計流程圖52.31以姓名為關(guān)鍵字的Hash()函數(shù)流程圖52.32添加結(jié)點信息流程圖:72.33按姓名查找流程圖:72.34按號碼查找流程圖82.35主程序流程圖92.4詳細設(shè)計編碼112.41建立節(jié)點112.42對哈希函數(shù)的定義112.43哈希查找122.44主函數(shù)123系統(tǒng)測試133.1上機調(diào)試133.2調(diào)試結(jié)果與分析144總結(jié)185附錄181系統(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)鍵字之間建立一個確定的對應(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)鍵字直接取模，也可在折疊、平方中等運算之后取模。 在哈希表的建立中，很容易出現(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）利用用戶名和電話號碼為關(guān)鍵字建立哈希表，哈希函數(shù)用除留余數(shù)法構(gòu)照。（3）利用鏈表法處理沖突問題。（4）查找并顯示給定用戶名，地址，電話號碼的記錄。（5）顯示哈希表中的給定用戶的記錄。（6）當(dāng)完成操作后，可以退出系統(tǒng)。1.3數(shù)據(jù)需求分析由問題分析知，本設(shè)計主要要求分別以電話號碼和用戶名為關(guān)鍵字建立哈希表，并實現(xiàn)查找功能。所以本設(shè)計的核心問題是如何解決散列的問題，亦即設(shè)計一個良好的哈希表。由于結(jié)點的個數(shù)無法確認，并且如果采用線性探測法散列算法，刪除結(jié)點會引起“信息丟失”的問題。所以采用鏈地址法散列算法。采用鏈地址法，當(dāng)出現(xiàn)同義詞沖突時，使用鏈表結(jié)構(gòu)把同義詞鏈接在一起，即同義詞的存儲地址不是散列表中其他的空地址。首先，解決的是定義鏈表結(jié)點，在鏈地址法中，每個結(jié)點對應(yīng)一個鏈表結(jié)點，它由三個域組成，而由于該程序需要分別用電話號碼和用戶名為關(guān)鍵字建立哈希表，所以該鏈表結(jié)點它是由四個域組成.name8 、num11和address20都是char浮點型，輸入輸出都只能是浮點型的。采用鏈地址法，其中的所有同義詞構(gòu)成一個單鏈表，再由一個表頭結(jié)點指向這個單鏈表的第一個結(jié)點。這些表頭結(jié)點組成一個一維數(shù)組，即哈希表。數(shù)組元素的下標(biāo)對應(yīng)由散列函數(shù)求出的散列地址。1.4 小結(jié)通過以上需求分析，知道了設(shè)計一個哈希表的目的和能夠“實現(xiàn)什么功能”，為接下來的操作明確方向，羅列了需要運用到的知識，自己應(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è)計一個主函數(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)如圖：name8num11address20next其中name8和num11是分別為以電話號碼和用戶名為關(guān)鍵字域，存放關(guān)鍵字（key）；address20(data)為結(jié)點的數(shù)據(jù)域，用來存儲用戶的地址。Next指針是用來指向下一個結(jié)點的地址。2.3程序詳細設(shè)計流程圖2.31以姓名為關(guān)鍵字的Hash()函數(shù)流程圖結(jié)束Key2=key%20namei不為空開始i從0開始取取整型name0賦給key2Key2+=nameii+1-1 姓名為關(guān)鍵字的Hash()函數(shù)流程圖2.32添加結(jié)點信息流程圖:利用用戶名為關(guān)鍵字插入拉鏈法處理沖突調(diào)用hash()函數(shù)調(diào)用hash()函數(shù)Newname指向newphoneNewphone=input()結(jié)束申請新的結(jié)點newphone,newname即新的號碼和名字開始 1-2添加結(jié)點信息流程圖:2.33按姓名查找流程圖:q不為空結(jié)束輸出無記錄輸出相應(yīng)記錄q=q->nextq 不為空調(diào)用hash()函數(shù)中新結(jié)點q指向phonekey->next開始2.34按號碼查找流程圖開始調(diào)用hash2()函數(shù)中新結(jié)點q指向phonekey->nextq 不為空q=q->nextq不為空輸出無記錄輸出相應(yīng)記錄結(jié)束2.35主程序流程圖開 始Main ()初始化散列鏈表（1）并為其動態(tài)分配內(nèi)存空間初始化散列鏈表（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 name8,address20;/節(jié)點中要包含用戶名，用戶地址，電話號碼以及指向下一個結(jié)點的指針char num11; node * next; ; typedef node* pnode; /typedef可以為一個已有的數(shù)據(jù)類型聲明多個別名，這里為該類型聲明了兩個指針typedef node* mingzi; node *phone; node *nam; node *a;2.42對哈希函數(shù)的定義void hash(char num11) /以電話號碼為關(guān)鍵字建立哈希函數(shù) key=(int)num2; while(numi!=NULL) key+=(int)numi; i+; key=key%20; b) void hash2(char name8) /以用戶名為關(guān)鍵字建立哈希函數(shù) int i = 1; key2=(int)name0; while(namei!=NULL) key2+=(int)namei; i+; key2=key2%20; 2.43哈希查找void find(char num11) /在以電話號碼為關(guān)鍵字的哈希表中查找用戶信息 hash(num); node *q=phonekey->next; while(q!= NULL) if(strcmp(num,q->num)=0) break; q=q->next; if(q) printf("%s_%s_%sn",q->name,q->address,q->num);else printf("無此記錄n"); b)、void find2(char name8) / 在以用戶名為關(guān)鍵字的哈希表中查找用戶信息 hash2(name); node *q=namkey2->next; while(q!= NULL) if(strcmp(name,q->name)=0) break; q=q->next; if(q) printf("%s_%s_%sn",q->name,q->address,q->num);else printf("無此記錄n"); 2.44主函數(shù)主函數(shù)本程序需要創(chuàng)建一個主菜單和一個主函數(shù)，主菜單便于用戶的使用，主函數(shù)中，包括所有功能對應(yīng)的數(shù)值，使之和主菜單相對應(yīng)。*主函數(shù)界面設(shè)計如下* 0添加記錄 1查找記錄 2姓名散列 3號碼散列 4清空記錄 5退出系統(tǒng)void menu() /菜單 system("color 2d");printf("*n");printf("ttt*歡迎使用*tttn");printf("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上機調(diào)試1首先鍵入0,添加結(jié)點信息,然后按1進行查找,分別進行號碼和姓名查找,最后可在主菜單中，選擇號碼散列和姓名散列,由此查看程序運行結(jié)果。2語法錯誤及修改：程序是分塊寫的,調(diào)試時可以使用分步調(diào)試的方式進行,以便能查找看程序是在哪出錯了。本算法使用了鏈表結(jié)構(gòu)和鏈地址法解決沖突的問題，在以姓名為關(guān)鍵字的哈希表中要注意涉及ASCLL碼的類型轉(zhuǎn)換，要注意輸出不能是“%d”，否則不能輸出結(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。但在實際使用過程中，為了將范圍廣泛的關(guān)鍵字映射到一組連續(xù)的存儲空間，往往會發(fā)生同義詞沖突，這時在查找過程中就需要進行關(guān)鍵字比較。因此散列法的查找性能取決于3個因素：散列函數(shù)、沖突處理方法和填充因子。采用鏈地址法，可以從根本上杜絕“二次聚集”的發(fā)生，從而提高散列表的均勻度，提高查找性能，不過也會“浪費”一部分散列表的空間。當(dāng)散列函數(shù)和沖突處理辦法固定時，散列法的查找性能就取決于散列表的填充因子。填充因子a=表中已有的結(jié)點數(shù)/表的長度。填充因子a標(biāo)志表的添滿程度。很顯然，a越小則發(fā)生沖突的機會就越小；反之，a越大沖突的機會就越大，查找的性能也就越低。哈希表鏈地址法查找成功的平均查找長度SNc=1+a/2。鏈地址法查找不成功的平均查找長度Un滿足：Unc=a+e-a.由以上可以看出，散列表的平均查找長度是填充因子的函數(shù)，和散列表的長度沒有關(guān)系，因此在實際應(yīng)用中，我們應(yīng)該選擇一個適當(dāng)?shù)奶畛湟蜃?，以便把平均查找長度控制在一個盡量小的范圍內(nèi)。3.2調(diào)試結(jié)果與分析程序主菜單添加記錄:分別按電話號碼和姓名查找:分別輸出按姓名和號碼散列的結(jié)果:清空記錄:4總結(jié)經(jīng)過為期兩周的課程設(shè)計，此次課程設(shè)計時間雖然比較短暫，但是我通過這次實踐學(xué)到了很多知識，也了解了自己的很多的不足之處。我是一名信息工程學(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)容自己認為在課堂上聽懂了，但上機實踐中會發(fā)現(xiàn)原來理解的偏差，更加鞏固了學(xué)過的知識，而且在設(shè)計的時候?qū)W要系統(tǒng)的知識，也是一個較大的挑戰(zhàn)，某一方面知識的欠缺都將影響到整個程序的設(shè)計。我從原來的對這門課程的不懂，到目前的能夠獨立完成一個小型程序。這次課程設(shè)計，重溫了和學(xué)習(xí)了許多有關(guān)c語言的知識，還掌握了一些現(xiàn)實中編程的一些小技巧，實際的編程能力也得到了歷練，本次課程設(shè)計對我?guī)椭芏唷?附錄*程序源代碼*#include<stdio.h>#include<string.h> #define NULL 0 unsigned int key; /定義兩個關(guān)鍵字unsigned int key2; int *p; struct node /建節(jié)點 每個結(jié)點包括用戶姓名、地址、電話號碼、以及指向下一個結(jié)點的指針 char name8,address20; char num11; node * next; ; typedef node* pnode; /typedef可以為一個已有的數(shù)據(jù)類型聲明多個別名，這里為該類型聲明了兩個指針typedef node* mingzi; node *phone; node *nam; node *a; void hash(char num11) /哈希函數(shù) ，以電話號碼為關(guān)鍵字建立哈希函數(shù) /哈希函數(shù)的主旨是將電話號碼的十一位數(shù)字全部加起來 int i = 3; key=(int)num2; while(numi!=NULL) key+=(int)numi; i+; key=key%20; void hash2(char name8) /哈希函數(shù) 以用戶名為關(guān)鍵字建立哈希函數(shù)/利用強制類型轉(zhuǎn)換，將用戶名的每一個字母的ASCLL碼值相加并且除以20后的余數(shù) int i = 1; key2=(int)name0; while(namei!=NULL) key2+=(int)namei; 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; printf("請輸入姓名: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; newname->next=NULL; hash(newphone->num); /利用哈希函數(shù)計算出對應(yīng)關(guān)鍵字的存儲地址hash2(newname->name); newphone->next = phonekey->next; /利用電話號碼為關(guān)鍵字插入phonekey->next=newphone; /是采用鏈地址法，拉鏈法處理沖突的散列表結(jié)構(gòu)newname->next = namkey2->next; /利用用戶名為關(guān)鍵字插入namkey2->next=newname; return 0; void create() /新建節(jié)點 int i; phone=new pnode20;/動態(tài)創(chuàng)建對象數(shù)組 for(i=0;i<20;i+) phonei=new node; phonei->next=NULL; void create2() /新建節(jié)點 int i; nam=new mingzi20; for(i=0;i<20;i+) nami=new node; nami->next=NULL; void list() /顯示列表 int i; node *p; for(i=0;i<20;i+) p=phonei->next; while(p) printf("%s_%s_%sn",p->name,p->address,p->num);p=p->next; void list2() /顯示列表 int i; node *p; for(i=0;i<20;i+) p=nami->next; while(p) printf("%s_%s_%sn",p->name,p->address,p->num);p=p->next; void find(char num11) /在以電話號碼為關(guān)鍵字的哈希表中查找用戶信息 hash(num); node *q=phonekey->next; while(q!= NULL) if(strcmp(num,q->num)=0) break; q=q->next; if(q) printf("%s_%s_%sn",q->name,q->address,q->num);else printf("無此記錄n"); void find2(char name8) / 在以用戶名為關(guān)鍵字的哈希表中查找用戶信息 hash2(name); node *q=namkey2->next; while(q!= NULL) if(strcmp(name,q->name)=0) break; q=q->next; if(q) printf("%s_%s_%sn",q->name,q->address,q->num);else printf("無此記錄n"); void menu() /菜單 printf("0.添加記錄n"); printf("1.查找記錄n"); printf("2.姓名散列n"); printf("3.號碼散列n"); printf("4.清空記錄n"); printf("5.退出系統(tǒng)n"); int main() char num11; char name8; create(); create2() ; int sel; while(1) menu(); scanf("%d",&sel); if(sel=1) printf("6號碼查詢，7姓名查詢n"); int 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;