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

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

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

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

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

5、9、以號(hào)碼為關(guān)鍵字的哈希表按號(hào)碼插入函數(shù)流程圖:10、以姓名為關(guān)鍵字的哈希表按姓名刪除函數(shù)流程圖:key+11、主函數(shù)調(diào)用函數(shù)流程圖:4、測(cè)試的實(shí)驗(yàn)結(jié)果和測(cè)試過程4.1 詳細(xì)設(shè)計(jì)首先定義結(jié)構(gòu)體類型，在線性探測(cè)法中，每個(gè)結(jié)構(gòu)體元素對(duì)應(yīng)一個(gè)數(shù)組位置，它由三個(gè)域組成，而由于該程序需要分別用電話號(hào)碼和用戶名為關(guān)鍵字建立哈希表，所以該數(shù)組的元素它由三個(gè)域組成：name20num20address30其中name20和num20是分別為以電話號(hào)碼和用戶名為關(guān)鍵字域（key）,存放關(guān)鍵字；address30為元素的數(shù)據(jù)域（data）,用來存儲(chǔ)用戶的地址信4.2 屏幕截圖主界面如圖圖11、給出一組測(cè)試數(shù)據(jù)及運(yùn)

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

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

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

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

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

11、V+S序設(shè)計(jì)基礎(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");/*運(yùn)行前

12、清屏*/printf("*哈希表printf("*創(chuàng)建哈希表按姓名散列按號(hào)碼散列0. 結(jié) 束 程 序printf("*1.*n");printf("*2.*n");printf("*3.*n");printf("*n");printf("*n");printf("請(qǐng)選擇您要運(yùn)行的選項(xiàng)按(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("請(qǐng)輸入名字n");scanf("%s",I);printf("請(qǐng)輸入號(hào)碼n"

14、;);scanf("%s",Infi.num);printf("請(qǐng)輸入地址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')/計(jì)算姓名中每個(gè)字符的ASCII碼值相加a=a+namei;i+;a=a%29;

15、對(duì)小于哈希表的最大素?cái)?shù)求余，此處哈希表長(zhǎng)為30,對(duì)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);/計(jì)算哈希地址while(1)if(strcmp(H,NULLKEY)=0)/判斷該位置是否為空，不為空就把輔助數(shù)組中的元素存到該位置strcpy(H,I);strcpy(Hkey.num,Infj.num);strcpy(Hkey.add,Infj.add)

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

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+;/如果為空，采用線性探測(cè)法，將元素后移intSearch_name(RecordH,charname20)/以姓名為關(guān)鍵字的哈希表的查找函數(shù)intkey=0;key=Hash_name(name);/計(jì)算哈希地址while(strcmp(H,name)!=0

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

19、LKEY)=0)/遇到空格表示該元素不存在printf("查找號(hào)碼不存在n");return(-1);break;return(key);/返回查找到的哈希地址voidInsert_name(RecordHM,charname20,charnum20,charadd30)/以姓名為關(guān)鍵字哈希表的插入函數(shù)intkey;key=Hash_name(name);/計(jì)算哈希地址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)/以電話號(hào)碼為關(guān)鍵字的哈希表插入函數(shù)intkey;key=Hash_num(num);/計(jì)算哈希地址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號(hào)碼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)/以電話號(hào)碼為關(guān)鍵字的哈希表的輸出函數(shù)inti;printf("t哈希地址t姓名tt號(hào)碼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為標(biāo)志位，如果該元素被刪除了，把t置為1inti,k;key=Hash_name(name);/計(jì)算哈希地址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)/以電話號(hào)碼為關(guān)鍵字的哈希表的刪除函數(shù)intkey=0,t=0;/設(shè)置t為標(biāo)志位，如果該元素被刪除了，把t置為1key=Hash_num(num);/計(jì)算哈希地址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("該號(hào)碼不存在!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請(qǐng)輸入要查找的名字：n");scanf("%s&q

28、uot;,name);k=Search_name(H,name);printf("查找該人的信息是：n");printf("該人的姓名是:%sn",H);printf("該人的電話號(hào)碼是:%sn",Hk.num);printf("該人的地址是:%sn",Hk.add);break;case 2:printf("n請(qǐng)輸入要插入的信息：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("請(qǐng)輸入要?jiǎng)h除的名字: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);/以電話號(hào)碼為關(guān)鍵字創(chuàng)建哈希表Print_num(H);while(1)flag=0;printf("n");printf("1:查找n");printf(&q