哈希表的設(shè)計與實現(xiàn)畢業(yè)論文

1、 . 哈希表的設(shè)計與實現(xiàn)摘要哈希表的設(shè)計與實現(xiàn)是用Visual C+ 6.0編寫的能夠?qū)崿F(xiàn)數(shù)據(jù)的存儲，更新與查找的程序。它可以方便的進行基本數(shù)據(jù)信息的輸入（如:、地址等），查詢（按查詢.按號查詢），刪除（運用刪除），添加新的數(shù)據(jù)等。易于管理員進行管理。本設(shè)計使用Visual C+ 6.0開發(fā)工具利用其提供的各種面向?qū)ο蟮拈_發(fā)工具將數(shù)據(jù)信息定義在結(jié)構(gòu)體中，運用類實現(xiàn)了對數(shù)據(jù)不同信息的操作功能。關(guān)鍵字：哈希表; Visual C+ 6.0; 地址1 / 25目 錄1、題目分析32、設(shè)計思路32.1問題描述32.2基本要求32.3數(shù)據(jù)結(jié)構(gòu)33、設(shè)計思路44、測試的實驗結(jié)果和測試過程114.1詳細設(shè)計

2、114.2屏幕截圖114.3問題分析：135、課程設(shè)計體會與問題分析136、參考文獻147、源程序清單141、 題目分析在21世紀信息時代里，各個機構(gòu)企業(yè)都需要處理一些龐大的重要的數(shù)據(jù)，而這些數(shù)據(jù)既需要隨時查找還需要隨時紀錄新的數(shù)據(jù)。這工作量無疑是巨大，如果用人力去完成，不僅效率底，易出錯，而且其他各個方面都受到一定的限制，如時間資源等。針對這種情況，應(yīng)用哈希表來規(guī)化管理這些數(shù)據(jù)是一個既明知又科學(xué)選折。它不但能有效的準確的存儲大量數(shù)據(jù)，還可以根據(jù)需要不斷的更新與插入新的數(shù)據(jù)。2、設(shè)計思路2.1問題描述實現(xiàn)本程序需要解決以下幾個問題：（1） 如何設(shè)計一個結(jié)構(gòu)體數(shù)組使該數(shù)組中每個元素包含、用戶名、

3、地址。（2） 如何分別以和用戶名為關(guān)鍵字建立哈希表。（3） 如何利用線性探測再散列法解決沖突。（4） 如何實現(xiàn)用哈希法查找并顯示給定的記錄。（5） 如何查找并顯示給定用戶的記錄。2.2基本要求（哈希表的設(shè)計與實現(xiàn)的問題）設(shè)計哈希表實現(xiàn)查詢系統(tǒng)。設(shè)計程序完成以下要求：（1）、設(shè)每個記錄有下列數(shù)據(jù)項：、用戶名、地址；（2）、從鍵盤輸入各記錄，分別以和用戶名為關(guān)鍵字建立哈希表；（3）、采用再哈希法解決沖突（4）、查找并顯示給定的記錄；（5）、查找并顯示給定用戶的記錄。要完成以上要求，設(shè)計哈希表實現(xiàn)查詢系統(tǒng)。2.3數(shù)據(jù)結(jié)構(gòu)本設(shè)計涉與到的數(shù)據(jù)結(jié)構(gòu)為：哈希表。要求輸入、用戶名、地址三個信息，并要求分別以和

4、用戶名為關(guān)鍵字進行查找，所以本問題要用到兩個哈希函數(shù)，進行哈希查找。typedef struct char name20;/名字char num20;/char add30;/地址Record;Record InfM;/輔助數(shù)組Record HM;/哈希表3、設(shè)計思路主要算法的流程圖如下：1、創(chuàng)建輔助數(shù)組流程圖： 開始初始化哈希表往輔助數(shù)組輸入元素N結(jié)束Y結(jié)束并返回數(shù)組元素總數(shù)選擇Y/N2、以為關(guān)鍵字的哈希函數(shù)流程圖：開始取整形數(shù)據(jù)0賦給ai從0開始取numi!=0a=a+(int)(namei)a=a%29結(jié)束i+3、以為關(guān)鍵字創(chuàng)建哈希表流程圖：開始j從0開始elsekey+計算以XX為關(guān)鍵

5、字的哈希地址keyif(strcmp(H,NULLKEY)=0)將輔助數(shù)組中的元素存入哈希表結(jié)束4、以為關(guān)鍵字的哈希函數(shù)流程圖：開始取整形數(shù)據(jù)0賦給bi從0開始取numi!=0i+b=b+(int)(namei)b=b%29結(jié)束5、以為關(guān)鍵字創(chuàng)建哈希表流程圖：開始j從0開始計算以 號碼為關(guān)鍵字的哈希地址keyif(strcmp(Hkey.num,NULLKEY)=0)將輔助數(shù)組中的元素存入哈希表elsekey+結(jié)束6、以為關(guān)鍵字的哈希表按查找函數(shù)流程圖：查找名字不存在return(key);結(jié)束開始調(diào)用Hash_namewhile(strcmp(H,name)!

6、=0)key+if(strcmp(H,NULLKEY)=0)7、以為關(guān)鍵字的哈希表按查找函數(shù)流程圖：查找號碼不存在return(key);結(jié)束開始調(diào)用Hash_numwhile(strcmp(Hkey.num,num)!=0)key+if(strcmp(Hkey.num,NULLKEY)=0)8、以為關(guān)鍵字的哈希表按插入函數(shù)流程圖：開始調(diào)用Hash_nameif(strcmp(H,NULLKEY)=0)else key+while(1)將數(shù)據(jù)以XX為關(guān)鍵字插入哈希表結(jié)束9、以為關(guān)鍵字的哈希表按插入函數(shù)流程圖：開始調(diào)用Hash_numif(strcmp(Hkey.

7、num,NULLKEY)=0)else key+while(1)將數(shù)據(jù)以號碼為關(guān)鍵字插入哈希表結(jié)束10、以為關(guān)鍵字的哈希表按刪除函數(shù)流程圖：開始調(diào)用Hash_name,計算下標key，記錄key為iif(strcmp(H,name)=0)while(1)key+在以XX為關(guān)鍵字的哈希表中刪除數(shù)據(jù)，標志位賦1結(jié)束while(key30)key+將存放在后面的下標為i的元素依次向前移動11、主函數(shù)調(diào)用函數(shù)流程圖：開始選擇1調(diào)用Create創(chuàng)建輔助數(shù)組選擇2以XX為關(guān)鍵字創(chuàng)建哈希表input_name選擇3以號碼為關(guān)鍵字創(chuàng)建哈希表input_num 選擇0退出選擇0退出選擇0退出選擇

8、1查找，調(diào)用Search_name函數(shù)選擇2插入，調(diào)用Insert_name函數(shù)選擇3刪除，調(diào)用Del_name函數(shù)選擇1查找，調(diào)用Search_num函數(shù)選擇2插入，調(diào)用Insert_num函數(shù)選擇3刪除，調(diào)用Del_num函數(shù)4、測試的實驗結(jié)果和測試過程4.1詳細設(shè)計 首先定義結(jié)構(gòu)體類型，在線性探測法中，每個結(jié)構(gòu)體元素對應(yīng)一個數(shù)組位置，它由三個域組成，而由于該程序需要分別用和用戶名為關(guān)鍵字建立哈希表，所以該數(shù)組的元素它由三個域組成：name20num20address30其中name20和num20是分別為以和用戶名為關(guān)鍵字域（key），存放關(guān)鍵字；address30為元素的數(shù)據(jù)域(dat

9、a)，用來存儲用戶的地址信息。4.2屏幕截圖主界面如圖圖11、給出一組測試數(shù)據(jù)與運行結(jié)果如下：輸入數(shù)據(jù)后按散列結(jié)果如下：圖2每個元素的哈希地址正是用名字中每個字母的ASCII碼值相加再對小于哈希表長的最大素數(shù)求余得到的，根據(jù)輸入數(shù)據(jù)計算和書上ASCII值計算出結(jié)果相比對，數(shù)據(jù)正確，剛開始老師檢查時，覺得我的程序缺少輸出哈希地址的步驟，回來后我又加以改進，把哈希地址正常輸出。圖3輸入數(shù)據(jù)后按散列結(jié)果如下：每個元素的哈希地址正是用中每個字符的ASCII碼值相加再對小于哈希表長的最大素數(shù)求余得到的，根據(jù)輸入數(shù)據(jù)計算和書上ASCII值計算出結(jié)果相比對，數(shù)據(jù)正確。4.3問題分析：剛開始調(diào)試時運行刪除功能

10、時，發(fā)現(xiàn)刪除元素后，哈希地址也在該位置而卻往后移動的元素不能回到該位置，然后我又分析算法，進行改進，現(xiàn)在算法可以在刪除元素后將哈希地址在該位置的而又移到后面的元素依次向前移動。5、課程設(shè)計體會與問題分析課程設(shè)計的過程是艱辛的,但是收獲確實另人欣喜的,這次課程設(shè)計我主要是應(yīng)用我們以前學(xué)習(xí)的C語言與C+中的知識來完成的,雖然這個程序功能還很不完善,但自己從中卻學(xué)到了很多東西.首先，綜合課程設(shè)計讓我把以前學(xué)習(xí)到的知識得到鞏固和進一步的提高認識，對已有知識有了更進一步的理解和認識，再次，我在課程設(shè)計中碰到了很多的問題，我通過查閱相關(guān)書籍，資料，通過自己鉆研，特別是得到了老師的諄諄教導(dǎo)，老師給予了我很大

11、的幫助，不僅給了我思路上的開闊，還讓我認識到了自己對以前所學(xué)知識的不足方面。首先,綜合課程設(shè)計讓我把以前學(xué)習(xí)的知識得到了加深與鞏固,對自己學(xué)習(xí)的知識有了一次全面的認識,也給自己指明了以后復(fù)習(xí)的重點與方向,再次,在程序設(shè)計中遇到的一些問題,我通過查閱資料,請教老師與同學(xué),提高了自己解決問題的能力。但由于還有很多問題無法解決，導(dǎo)致很多功能不能實現(xiàn)，未能達到預(yù)期的目的。 隨著社會的不斷發(fā)展,計算機在各領(lǐng)域也得到廣泛的應(yīng)用，同時對軟件的要求也越來越高，只有不斷的利用新的知識來更新程序，才能滿足社會的需求。但是，對于一個初學(xué)者來說，要想編譯一個完美的程序是十分困難的。本程序就有許多的不足，以與編譯時出現(xiàn)

12、的困難。列如：（1）在準備資料時，選取與設(shè)計適合的哈希函數(shù)，成首要難題，也是整個程序關(guān)鍵。因為在設(shè)計哈希函數(shù)時，要做到最大的減少沖突，確定在記錄的儲存位置和他個關(guān)鍵字之間建立一個取得對應(yīng)關(guān)系，使沒關(guān)鍵字和結(jié)構(gòu)中的一個惟一的儲存位置相對應(yīng)，這是以個比較復(fù)雜的過程。（2）沖突是使用哈希表不可避免的問題。對不同的關(guān)鍵字卻可能得到同一哈希地址，并且在一般情況下，沖突只能盡可能避免而不能完全避免。因此，在建造哈希表時不僅要設(shè)定以個好的哈希函數(shù)，而且要設(shè)定一種處理沖突的方法。在泵系統(tǒng)的開發(fā)過程中，主要采用了開放地址法中的二次探測法。通過這次課程設(shè)計,我發(fā)現(xiàn)了自身的很多不足,在以后的學(xué)習(xí)中,我會不斷完善自我

13、.不斷進取,使自己在編程這方面的能力得到更進一步的提高.6、參考文獻1 譚浩強.C程序設(shè)計（第三版）.：清華大學(xué).20052 斌.王忠.面向?qū)ο蟪绦蛟O(shè)計 Visual C+.：清華大學(xué).20033 嚴蔚敏.吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語言版）.：清華大學(xué).20074 譚浩強編著.C+程序設(shè)計.：清華大學(xué)，2004.5 美S巴斯計算機算法：設(shè)計和分析引論.朱洪等譯.：復(fù)旦大學(xué).1985.6 Huddard J R.Prohramming with C+(英文版，第二版).：機械工業(yè).2002.87 華生.CV+程序設(shè)計基礎(chǔ).：大學(xué).20027、源程序清單*程序源代碼*#include#include#i

14、nclude#define M 30#define NULLKEY 0typedef struct char name20;char num20;char add30;Record;Record InfM;/定義輔助數(shù)組為全局變量Record HM;/定義哈希表為全局變量int menu_select() /*菜單函數(shù)*/ int c; do system(cls); /*運行前清屏*/printf( *n); printf( * 哈希表 *n); printf( * 1. 創(chuàng)建哈希表 *n); printf( * 2. 按散列 *n); printf( * 3. 按散列 *n); print

15、f( * 0. 結(jié)束程序 *n); printf( *n); printf(請選擇您要運行的選項按(0-3):); scanf(%d,&c); /*讀入選擇*/getchar(); while(c3); return(c); /*返回選擇*/int Create(Record HM)/創(chuàng)建輔助數(shù)組int i;for(i=0;i30;i+)/初始化哈希表strcpy(Hi.add,0);strcpy(Hi.num,0);strcpy(H,0);i=0; char sign; while(sign!=n&sign!=N) printf(請輸入名字n); scanf(%s,Infi.na

16、me); printf(請輸入n); scanf(%s,Infi.num); printf(請輸入地址n); scanf(%s,Infi.add); printf(ttt還需要繼續(xù)輸入嗎?(Y/N); scanf(ttt%c,&sign); /*輸入判斷*/ i+; return i;int Hash_name(char name20)/以為關(guān)鍵字的哈希函數(shù)int i=0;int a=0;while(namei!=0)/計算中每個字符的ASCII碼值相加a=a+namei;i+;a=a%29;/對小于哈希表的最大素數(shù)求余，此處哈希表長為30，對29求余return(a);void input_

17、name(Record InfM,int m,Record HM)/以為關(guān)鍵字創(chuàng)建哈希表int j,key=0; for(j=0;jm;j+) key=Hash_name(I);/計算哈希地址 while(1) if(strcmp(H,NULLKEY)=0)/判斷該位置是否為空，不為空就把輔助數(shù)組中的元素存到該位置 strcpy(H,I); strcpy(Hkey.num,Infj.num); strcpy(Hkey.add,Infj.add); break; else key+;/如果為空，采用線性探測法，將元素后移 int H

18、ash_num(char num20)/以為關(guān)鍵字的哈希函數(shù)int i=0;int b=0;while(numi!=0)/計算中每個字符的ASCII碼值相加b=b+numi;i+;b=b%29;/對小于哈希表的最大素數(shù)求余，此處哈希表長為30，對29求余return(b);void input_num(Record InfM,int m,Record HM)/以為關(guān)鍵字創(chuàng)建哈希表int j,key=0;for(j=0;jm;j+) key=Hash_num(Infj.num);/計算哈希地址 while(1) if(strcmp(Hkey.num,NULLKEY)=0)/判斷該位置是否為空，不

19、為空就把輔助數(shù)組中的元素存到該位置 strcpy(H,I); strcpy(Hkey.num,Infj.num); strcpy(Hkey.add,Infj.add); break; else key+;/如果為空，采用線性探測法，將元素后移 int Search_name(Record H,char name20)/以為關(guān)鍵字的哈希表的查找函數(shù)int key=0; key=Hash_name(name);/計算哈希地址 while(strcmp(H,name)!=0)/如果元素不在該位置，將元素后移再判斷 key+; if(strcmp(Hke

20、,NULLKEY)=0)/遇到空格表示該元素不存在 printf(查找名字不存在!n);return(-1);break; return(key);/返回查找到的哈希地址int Search_num(Record H,char num20)/以為關(guān)鍵字的哈希表的查找函數(shù)int key=0;key=Hash_num(num);/計算哈希地址 while(strcmp(num,Hkey.num)!=0)/如果元素不在該位置，將元素后移再判斷 key+; if(strcmp(Hkey.num,NULLKEY)=0)/遇到空格表示該元素不存在 printf(查找不存在n);return(-

21、1);break; return(key);/返回查找到的哈希地址void Insert_name(Record HM,char name20,char num20,char add30)/以為關(guān)鍵字哈希表的插入函數(shù)int key;key=Hash_name(name);/計算哈希地址while(1) if(strcmp(H,NULLKEY)=0)/如果該位置為空，把元素存到該位置 strcpy(H,name); strcpy(Hkey.num,num); strcpy(Hkey.add,add); break; else key+;/如果該位置不為空，向后移插

22、入元素 void Insert_num(Record HM,char name20,char num20,char add30)/以為關(guān)鍵字的哈希表插入函數(shù)int key;key=Hash_num(num);/計算哈希地址while(1) if(strcmp(Hkey.num,NULLKEY)=0)/如果該位置為空，把元素存到該位置 strcpy(H,name); strcpy(Hkey.num,num); strcpy(Hkey.add,add); break; else key+;/如果該位置不為空，向后移插入元素 void Print_name(Record HM)/以為

23、關(guān)鍵字的哈希表的輸出函數(shù)int i;printf(t哈希地址ttttt地址n);for(i=0;i30;i+)if(strcmp(H,0)!=0)printf(t%dtt%stt%stt%sn,i,H,Hi.num,Hi.add);void Print_num(Record HM)/以為關(guān)鍵字的哈希表的輸出函數(shù)int i;printf(t哈希地址ttttt地址n);for(i=0;i30;i+)if(strcmp(Hi.num,0)!=0) printf(t%dtt%stt%stt%sn,i,H,Hi.num,Hi.add);void Del_name(Re

24、cord HM,char name20)/以為關(guān)鍵字的哈希表的刪除函數(shù) int key,t=0;/設(shè)置t為標志位，如果該元素被刪除了，把t置為1int i,k; key=Hash_name(name);/計算哈希地址 i=key;while(1) if(strcmp(H,name)=0)/如果元素存在該位置，將該位置置空 t=1; strcpy(H,0); strcpy(Hkey.num,0); strcpy(Hkey.add,0); k=key; while(key30) key+; if(Hash_name(H)=i)/然后將哈希地址在該位置

25、的存在后面的元素依次前移 strcpy(H,H); strcpy(Hk.num,Hkey.num); strcpy(Hk.add,Hkey.add); k=key; strcpy(H,0); strcpy(Hkey.num,0); strcpy(Hkey.add,0); break; key+; /如果元素不在該位置，向后移查找該元素再刪除 if(t=0)/t為0表示沒有執(zhí)行刪除操作 printf(該不存在!); void Del_num(Record HM,char num20)/以為關(guān)鍵字的哈希表的刪除函數(shù)int key=0,t=0;/設(shè)置t為標

26、志位，如果該元素被刪除了，把t置為1 key=Hash_num(num);/計算哈希地址 int i,k; i=key;while(1) if(strcmp(Hkey.num,num)=0)/如果元素存在該位置，將該位置置空 t=1; strcpy(H,0); strcpy(Hkey.num,0); strcpy(Hkey.add,0); k=key; while(key30) key+; if(Hash_num(Hkey.num)=i)/然后將哈希地址在該位置的存在后面的元素依次前移 strcpy(H,H); strcpy(Hk.num,Hkey.

27、num); strcpy(Hk.add,Hkey.add); k=key; strcpy(H,0); strcpy(Hkey.num,0); strcpy(Hkey.add,0); break; else key+; /如果元素不在該位置，向后移查找該元素再刪除 if(t=0)/t為0表示沒有執(zhí)行刪除操作 printf(該不存在!n); void main()/主函數(shù)char name20,num20;char a020,b020,c030;char a120,b120,c120;int m,i,g;int w,k;int flag=0; while(1)switch(menu

28、_select() )case 1:m=Create(H);/創(chuàng)建輔助數(shù)組break;case 2: input_name(Inf,m,H);/以為關(guān)鍵字創(chuàng)建哈希表Print_name(H);while(1)flag=0; printf(n); printf(1:查找n); printf(2:插入n); printf(3:刪除n);printf(0:返回n); printf(輸入（0-3）:n); scanf(%d,&g); switch(g) case 1: printf(n請輸入要查找的名字：n); scanf(%s,name); k=Search_name(H,name); printf

29、(查找該人的信息是：n); printf(該人的是:%sn,H); printf(該人的是:%sn,Hk.num); printf(該人的地址是:%sn,Hk.add); break; case 2: printf(n請輸入要插入的信息：n); printf(插入的是:); scanf(%s,a0); printf(插入的是:); scanf(%s,b0); printf(插入的地址是:); scanf(%s,c0); Insert_name(H,a0,b0,c0); printf(插入后的結(jié)果:n); Print_name(H); break; case 3: printf(請輸入要刪除的名字:n); scanf(%s,name); Del_name(