哈希表的設(shè)計與實現(xiàn)

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

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è)計

4、涉及到的數(shù)據(jù)結(jié)構(gòu)為：哈希表。要求輸入電話號碼、用戶名、地址三個信息，并要求分別以電話號碼和用戶名為關(guān)鍵字進行查找，所以本問題要用到兩個哈希函數(shù)，進行哈希查找。typedefstructcharname20;/名字charnum20;/電話號碼charadd30;/地址Record;RecordInfM;/輔助數(shù)組RecordHM;/哈希表3、設(shè)計思路主要算法的流程圖如下:1、創(chuàng)建輔助數(shù)組流程圖:N結(jié)束4、以電話號碼為關(guān)鍵字的哈希函數(shù)流程圖:3、5、7、以姓名為關(guān)鍵字的哈希表按姓名查找函數(shù)流程圖:7、以電話號碼為關(guān)鍵字的哈希表按號碼查找函數(shù)流程圖:9、以姓名為關(guān)鍵字的哈希表按姓名插入函數(shù)流程圖:

5、9、以號碼為關(guān)鍵字的哈希表按號碼插入函數(shù)流程圖:10、以姓名為關(guān)鍵字的哈希表按姓名刪除函數(shù)流程圖:key+11、主函數(shù)調(diào)用函數(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ù)域（data）,用來存儲用戶的地址信4.2 屏幕截圖主界面如圖圖11、給出一組測試數(shù)據(jù)及運

6、行結(jié)果如下:輸入數(shù)據(jù)后按姓名散列結(jié)果如下：圖2每個元素的哈希地址正是用名字中每個字母的ASCII碼值相加再對小于哈希表長的最大素數(shù)求余得到的，根據(jù)輸入數(shù)據(jù)計算和書上ASCII值計算出結(jié)果相比對，數(shù)據(jù)正確，剛開始老師檢查時，覺得我的程序缺少輸出哈希地址的步驟，回來后我又加以改進，把哈希地址正常輸出。1"OWC+6,0COMMONMSDEV98BINDebvg3.eKF"I口I'入 玲硼找人除叫輸入數(shù)據(jù)后按號碼散列結(jié)果如下：每個元素的哈希地址正是用號碼中每個字符的ASCII碼值相加再對小于哈希表長的最大素數(shù)求余得到的，根據(jù)輸入數(shù)據(jù)計算和書上ASCII值計算出結(jié)果相比對，

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

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

9、是十分困難的。本程序就有許多的不足，以及編譯時出現(xiàn)的困難。列如：（ 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è)計,我

10、發(fā)現(xiàn)了自身的很多不足,在以后的學(xué)習(xí)中,我會不斷完善自我.不斷進取,使自己在編程這方面的能力得到更進一步的提高.6、參考文獻1 譚浩強.C程序設(shè)計（第三版）.北京：清華大學(xué)出版社.20052 劉斌.王忠.面向?qū)ο蟪绦蛟O(shè)計VisualC+.北京：清華大學(xué)出版社.20033嚴蔚敏.吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語言版）.北京：清華大學(xué)出版社.20074譚浩強編著.C+程序設(shè)計.北京：清華大學(xué)出版社，2004.5美S巴斯計算機算法：設(shè)計和分析引論.朱洪等譯.上海：復(fù)旦大學(xué)出版社.1985.6 HuddardJR.ProhrammingwithC+（英文版，第二版）.北京：機械工業(yè)出版社.2002.87陳華生.C

11、V+S序設(shè)計基礎(chǔ).江蘇：蘇州大學(xué)出版社.20027、源程序清單*程序源代碼*#include<stdio.h>#include<string.h>#include<stdlib.h>#defineM30#defineNULLKEY"0"typedefstructcharname20;charnum20;charadd30;Record;RecordInfM;/定義輔助數(shù)組為全局變量RecordHM;/定義哈希表為全局變量intmenu_select()/*菜單函數(shù)*/intc;dosystem("cls");/*運行前

12、清屏*/printf("*哈希表printf("*創(chuàng)建哈希表按姓名散列按號碼散列0. 結(jié) 束 程 序printf("*1.*n");printf("*2.*n");printf("*3.*n");printf("*n");printf("*n");printf("請選擇您要運行的選項按(0-3):");scanf("%d",&c);/*讀入選擇*/getchar();while(c<0|c>3);return(c);

13、/*返回選擇*/intCreate(RecordHM)/創(chuàng)建輔助數(shù)組inti;for(i=0;i<30;i+)/初始化哈希表strcpy(Hi.add,"0");strcpy(Hi.num,"0");strcpy(H,"0");i=0;charsign;while(sign!='n'&&sign!='N')printf("請輸入名字n");scanf("%s",I);printf("請輸入號碼n"

14、;);scanf("%s",Infi.num);printf("請輸入地址n");scanf("%s",Infi.add);printf("ttt還需要繼續(xù)輸入嗎?(Y/N)");scanf("ttt%c",&sign);/*輸入判斷*/i+;returni;intHash_name(charname20)/以姓名為關(guān)鍵字的哈希函數(shù)inti=0;inta=0;while(namei!='0')/計算姓名中每個字符的ASCII碼值相加a=a+namei;i+;a=a%29;

15、對小于哈希表的最大素數(shù)求余，此處哈希表長為30,對29求余return(a);voidinput_name(RecordInfM,intm,RecordHM)/以姓名為關(guān)鍵字創(chuàng)建哈希表intj,key=0;for(j=0;j<m;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)

16、;break;elsekey+;/如果為空，采用線性探測法，將元素后移intHash_num(charnum20)/以姓名為關(guān)鍵字的哈希函數(shù)inti=0;intb=0;while(numi!='0')/計算電話號碼中每個字符的ASCII碼值相加b=b+numi;i+;b=b%29;對小于哈希表的最大素數(shù)求余，此處哈希表長為30,對29求余return(b);voidinput_num(RecordInfM,intm,RecordHM)/以電話號碼為關(guān)鍵字創(chuàng)建哈希表intj,key=0;for(j=0;j<m;j+)key=Hash_num(Infj.num);/計算哈希地

17、址while(1)if(strcmp(Hkey.num,NULLKEY)=0)/判斷該位置是否為空，不為空就把輔助數(shù)組中的元素存到該位置strcpy(H,I);strcpy(Hkey.num,Infj.num);strcpy(Hkey.add,Infj.add);break;elsekey+;/如果為空，采用線性探測法，將元素后移intSearch_name(RecordH,charname20)/以姓名為關(guān)鍵字的哈希表的查找函數(shù)intkey=0;key=Hash_name(name);/計算哈希地址while(strcmp(H,name)!=0

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

19、LKEY)=0)/遇到空格表示該元素不存在printf("查找號碼不存在n");return(-1);break;return(key);/返回查找到的哈希地址voidInsert_name(RecordHM,charname20,charnum20,charadd30)/以姓名為關(guān)鍵字哈希表的插入函數(shù)intkey;key=Hash_name(name);/計算哈希地址while(1)if(strcmp(H,NULLKEY)=0)/如果該位置為空，把元素存到該位置strcpy(H,name);strcpy(Hkey.num,num);strc

20、py(Hkey.add,add);break;elsekey+;/如果該位置不為空，向后移插入元素voidInsert_num(RecordHM,charname20,charnum20,charadd30)/以電話號碼為關(guān)鍵字的哈希表插入函數(shù)intkey;key=Hash_num(num);/計算哈希地址while(1)if(strcmp(Hkey.num,NULLKEY)=0)/如果該位置為空，把元素存到該位置strcpy(H,name);strcpy(Hkey.num,num);strcpy(Hkey.add,add);break;elsekey+;/如果該位置不為空，向

21、后移插入元素voidPrint_name(RecordHM)/以姓名為關(guān)鍵字的哈希表的輸出函數(shù)inti;printf("t哈希地址t姓名tt號碼tt地址n");for(i=0;i<30;i+)if(strcmp(H,"0")!=0)printf("t%dtt%stt%stt%sn",i,H,Hi.num,Hi.add);voidPrint_num(RecordHM)/以電話號碼為關(guān)鍵字的哈希表的輸出函數(shù)inti;printf("t哈希地址t姓名tt號碼tt地址n");for(i=0;i

22、<30;i+)if(strcmp(Hi.num,"0")!=0)printf("t%dtt%stt%stt%sn",i,H,Hi.num,Hi.add);voidDel_name(RecordHM,charname20)/以姓名為關(guān)鍵字的哈希表的刪除函數(shù)int key,t=0;/設(shè)置t為標志位，如果該元素被刪除了，把t置為1inti,k;key=Hash_name(name);/計算哈希地址i=key;while(1)if(strcmp(H,name)=0)/如果元素存在該位置，將該位置置空t=1;strcpy(Hkey

23、.name,"0");strcpy(Hkey.num,"0");strcpy(Hkey.add,"0");k=key;while(key<30)key+;if(Hash_name(H)=i)/然后將哈希地址在該位置的存在后面的元素依次前移strcpy(H,H);strcpy(Hk.num,Hkey.num);strcpy(Hk.add,Hkey.add);k=key;strcpy(H,"0");strcpy(Hkey.num,"0"

24、;);strcpy(Hkey.add,"0");break;key+;/如果元素不在該位置，向后移查找該元素再刪除if(t=0)/t為0表示沒有執(zhí)行刪除操作printf("該姓名不存在!");voidDel_num(RecordHM,charnum20)/以電話號碼為關(guān)鍵字的哈希表的刪除函數(shù)intkey=0,t=0;/設(shè)置t為標志位，如果該元素被刪除了，把t置為1key=Hash_num(num);/計算哈希地址inti,k;i=key;while(1)if(strcmp(Hkey.num,num)=0)/如果元素存在該位置，將該位置置空t=1;strc

25、py(H,"0");strcpy(Hkey.num,"0");strcpy(Hkey.add,"0");k=key;while(key<30)key+;if(Hash_num(Hkey.num)=i)/然后將哈希地址在該位置的存在后面的元素依次前移strcpy(H,H);strcpy(Hk.num,Hkey.num);strcpy(Hk.add,Hkey.add);k=key;strcpy(H,"0");strcpy(Hkey.num,"0

26、");strcpy(Hkey.add,"0");break;elsekey+;/如果元素不在該位置，向后移查找該元素再刪除if(t=0)/t為0表示沒有執(zhí)行刪除操作printf("該號碼不存在!n");voidmain()/主函數(shù)charname20,num20;chara020,b020,c030;chara120,b120,c120;intm,i,g;intw,k;intflag=0;while(1)switch(menu_select()case 1:m=Create(H);/創(chuàng)建輔助數(shù)組break;case 2:input_name(I

27、nf,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&q

28、uot;,name);k=Search_name(H,name);printf("查找該人的信息是：n");printf("該人的姓名是:%sn",H);printf("該人的電話號碼是:%sn",Hk.num);printf("該人的地址是:%sn",Hk.add);break;case 2:printf("n請輸入要插入的信息：n");printf("插入的姓名是:");scanf("%s",a0);printf("插入的電話是:

29、");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(H,name);printf("刪除后的信息:n");Print_name(H);break;case0:flag=1;break;if(flag=1)break;將哈希表清空Hi.add,"0");Hi.num,"0");H,"0");for(i=0;i<30;i+)/strcpy(strcpy(strcpy(break;printf("n");case3:input_num(Inf,m,H);/以電話號碼為關(guān)鍵字創(chuàng)建哈希表Print_num(H);while(1)flag=0;printf("n");printf("1:查找n");printf(&q