哈希表課程設(shè)計(jì)--哈希表的實(shí)現(xiàn)與應(yīng)用

上傳人：奔*** IP屬地：河北更新時(shí)間：2024-04-01 格式：doc 頁(yè)數(shù)：42 大?。?44.50KB 人氣指數(shù)：12 舉報(bào) 版權(quán)申訴

哈希表課程設(shè)計(jì)--哈希表的實(shí)現(xiàn)與應(yīng)用_第1頁(yè)

已閱讀1頁(yè)，還剩41頁(yè)未讀，繼續(xù)免費(fèi)閱讀

版權(quán)說(shuō)明：本文檔由用戶(hù)提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

1、　　數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)　　設(shè)計(jì)說(shuō)明書(shū)　　2012 年 3 月 3 日數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)評(píng)閱書(shū)　　摘要　　隨著計(jì)算機(jī)的普及，社會(huì)的信息化不斷普及提

2、高，在此課程設(shè)計(jì)中。設(shè)計(jì)了一個(gè)人員信息查找系統(tǒng)，本查找系統(tǒng)采用VC++作為軟件開(kāi)發(fā)環(huán)境，采用本系統(tǒng)可以簡(jiǎn)單地實(shí)現(xiàn)人員信息的查詢(xún)，顯示所有人員的信息。在編制人員的信息中，具有人員的姓名、聯(lián)系電話(huà)、以及人員的地址。在插入人員信息中，采用以姓名為關(guān)鍵字插入，實(shí)現(xiàn)了哈希值的插入運(yùn)算。在查詢(xún)具體人員的信息是可以采用以姓名為關(guān)鍵查人員信息，也可以采用以號(hào)碼作為關(guān)鍵字查找人員信息。在用姓名作為關(guān)鍵字查詢(xún)信息時(shí)采用二次散列法處進(jìn)行沖突處理，在以電話(huà)號(hào)碼

3、進(jìn)行人員的信息查找時(shí)采用線(xiàn)性探測(cè)法處理沖突。在界面設(shè)設(shè)計(jì)方面界面清晰，明了。操作簡(jiǎn)單，易于用戶(hù)所接受。 　　關(guān)鍵詞：哈希表;信息查找系統(tǒng);函數(shù)　　目錄　　1 課題描述……………………………………………… 1&

4、lt;p>　　2 需求分析………………………………………………………………………… 2　　3 設(shè)計(jì)概要…………………………………………………………………………… 2　　3.1 系統(tǒng)菜單……………………………………………………………………… 2

5、;　　3.2 各個(gè)模塊之間調(diào)用關(guān)系……………………………………………… 3 　　3.3 數(shù)據(jù)結(jié)構(gòu)描述與定義…………………………………………………… 4 　　3.4 各個(gè)模塊主要算法描述及流程圖…………………………… 5 　　4詳細(xì)設(shè)計(jì)……………………

6、………………… 11 　　4.1程序描述……………………………………………………………………… 11　　4.2具體步驟………………………………………………………………… 11　　5 程序編碼…………………………………………………………… 14&

7、lt;p>　　6 程序調(diào)試與測(cè)試…………………………………………………… 25　　7 結(jié)果分析…………………………………………………………… 32 　　8 總結(jié)………………………………………………………………… 33　　參考文獻(xiàn)………………………………………………………………

8、……………………… 34　　1 課題描述　　散列表(也叫哈希表),是根據(jù)關(guān)鍵碼值直接進(jìn)行訪問(wèn)的數(shù)據(jù)結(jié)構(gòu),也就是說(shuō),它通過(guò)把關(guān)鍵碼值映射到表中一個(gè)位置來(lái)訪問(wèn)記錄,以加快查找的速度。這個(gè)映射函數(shù)叫做散列函數(shù),存放記錄的數(shù)組叫做散列表。　　本課程設(shè)計(jì)只要完成以下任務(wù)：

9、　　1）完成哈希表的初始化、哈希函數(shù)值的運(yùn)算、插入元素、查找元素。　　2）求出每次哈希表查找的平均查找長(zhǎng)度ASL。　　3)利用線(xiàn)形探測(cè)和二次探測(cè)再散列處理沖突的功能。　　2 需求分析　　哈希

10、表是用散列表建立關(guān)鍵碼字與其存儲(chǔ)位置的對(duì)應(yīng)關(guān)系，或者說(shuō)，由關(guān)鍵碼的函數(shù)值決定數(shù)據(jù)的存儲(chǔ)地址，是根據(jù)關(guān)鍵碼值直接進(jìn)行訪問(wèn)的數(shù)據(jù)結(jié)構(gòu),查找速度極快（O(1)）,查找效率與元素個(gè)數(shù)n無(wú)關(guān)！在設(shè)計(jì)中需要實(shí)現(xiàn)哈希表的初始化、插入運(yùn)算，以及每次查找的哈希表的平均長(zhǎng)度ASL,同時(shí)在設(shè)計(jì)中要實(shí)現(xiàn)用線(xiàn)性探測(cè)和二次散列兩種方法處理沖突等功能。在建立哈希表中建立的不同哈希表會(huì)有不同的平均長(zhǎng)度，同不同的處理沖突方法會(huì)有不同的平均查找長(zhǎng)度。

11、　　3 設(shè)計(jì)概要　　進(jìn)入主函數(shù),用戶(hù)輸入需要功能代號(hào)進(jìn)入選擇選1:建立用戶(hù)信息,選。2.顯示所有用戶(hù)信息。3.以姓名關(guān)鍵字插入用戶(hù)信息。4。以姓名產(chǎn)生哈希表。5，以號(hào)碼產(chǎn)生哈希表。6，以姓名查找關(guān)鍵字。7以號(hào)碼查找用戶(hù)信息。0，退出系統(tǒng)。分別以上述確定的方法分別以用戶(hù)名為檢索以及以以電話(huà)號(hào)碼將用戶(hù)信息添加到哈希表。在查找用戶(hù)信息時(shí)必須

12、先建立哈希表（先進(jìn)行4、5步驟）。只需輸入用戶(hù)的姓名或號(hào)碼就可以查找到用戶(hù)信息。程序用結(jié)構(gòu)體存儲(chǔ)用戶(hù)信息，建立的哈希表方便快速的查找到用戶(hù)信息。程序用鏈表的方式存儲(chǔ)信息以及構(gòu)造哈希表　　具體流程圖如下所示:　　3.1功能模塊　　圖3.2 菜單系統(tǒng)&

13、lt;p>　　3.2程序主流程圖　　是　　是　　否　　否

14、;　　否　　圖3.2 各個(gè)模塊之間調(diào)用關(guān)系　　3．3數(shù)據(jù)結(jié)構(gòu)描述與定義　　用結(jié)構(gòu)體數(shù)據(jù)定義哈希表　　typedef struct //哈希表</p&g

15、t;　　{　　Record *elem[HASHSIZE]; //數(shù)據(jù)元素存儲(chǔ)基址　　int count; //當(dāng)前數(shù)據(jù)元素個(gè)數(shù)　　int size;

16、 //當(dāng)前容量　　}HashTable;　　用結(jié)構(gòu)體定義建立用戶(hù)記錄　　typedef struct //記錄　　{　　char

17、 name[20];　　char tel[20];　　char add[20];　　}Record;　　初始化哈希表地址，初始化哈希表　　#define LEN sizeof(HashTabl

18、e)　　#define HASHSIZE 54 //定義哈希表長(zhǎng) 　　HashTable *H;　　H=(HashTable*)malloc(LEN); //申請(qǐng)哈希表空間地址　　for(i=0;i<HASHSIZE;

19、i++) //初始化哈希表　　H->elem[i]=NULL;　　H->size=HASHSIZE; //哈希表大小 　　H->count=0; //記錄哈希表內(nèi)個(gè)數(shù)大小

20、　　Record a[MAXSIZE];　　3.4主要模塊算法描述及流程圖　　1）增加信息　　yes 　　圖3.4.1 用來(lái)輸入用戶(hù)信息，輸入用戶(hù)信息最大不能超

21、過(guò)結(jié)構(gòu)體所定義大小　　2）顯示存儲(chǔ)信息　　圖3.4.2 顯示用戶(hù)信息,現(xiàn)實(shí)包括添加的用戶(hù)在內(nèi)的所有用戶(hù)信息　　3)添加用戶(hù)信息　　NO

22、　　圖3.4.3 按照關(guān)鍵字以用戶(hù)姓名添加用戶(hù)信息　　4）沖突處理函數(shù)　　YES　　NO　　圖3.4.4 建立以姓名為關(guān)鍵字的沖突處

23、理函數(shù)　　5）建立哈希表（姓名） 　　NO　　YES　　圖3.4.5 以姓名作為關(guān)鍵字建立哈希表　　6）查找（姓名）&l

24、t;/b>　　NO　　YES　　圖3.4.6 以姓名作為關(guān)鍵字進(jìn)行查找　　以號(hào)碼建立哈希表，把號(hào)碼作為關(guān)鍵字進(jìn)行查找與以姓名作為關(guān)鍵字見(jiàn)建立哈希表把號(hào)碼作為關(guān)鍵字進(jìn)行查找相同，具體可參

25、考以上對(duì)應(yīng)個(gè)圖。　　4詳細(xì)設(shè)計(jì)　　4.1程序描述: 　　本程序以要求使用哈希表為工具快速快速查詢(xún)學(xué)生信息，學(xué)生信息包括電話(huà)號(hào)碼、用戶(hù)名、地址；用結(jié)構(gòu)體存儲(chǔ)，并顯示所有用戶(hù)信息　　typedef s

26、truct //記錄用戶(hù)信息　　{　　char name[20];　　char tel[20];　　char add[20];

27、　　}Record;　　4.2具體步驟　　主要函數(shù)　　int getin(Record* a,int n) 　　該函數(shù)用于建立用戶(hù)信息，用結(jié)構(gòu)體Record a.類(lèi)型來(lái)建

28、立用戶(hù)信息。n用來(lái)記錄建立的人員個(gè)數(shù)。　　其核心語(yǔ)句是：　　for(i=0;i<NUM_BER;i++)　　{　　printf("\t聯(lián)系人%d\n",i+1);<

29、/p>　　printf("\t\t用戶(hù)名:");　　scanf("%s",a[i+n].name);　　printf("\t\t號(hào)碼: ");　　scanf("%s",a[i+n].tel);</p

30、>　　printf("\t\t地址: ");　　scanf("%s",a[i+n].add);//gets(str2);　　int Hash1(char str[]) //以姓名產(chǎn)生哈希值　　該函數(shù)用于以人名建立哈希表時(shí)產(chǎn)生哈希值，用st

31、r[]來(lái)傳遞人名。其核心語(yǔ)句是 m=n%HASHSIZE; 　　Status collision1(int p,int &c) //沖突處理函數(shù)，采用二次探測(cè)再散列沖突　　該函數(shù)用于以人名建立哈希表時(shí)產(chǎn)生沖突時(shí)的沖突處理函數(shù)，該函數(shù)采用二次探測(cè)再散列沖突法處理沖突，p表示沖突的哈希地址，c用來(lái)記錄沖沖突次數(shù)。其核心語(yǔ)句是c++；&

32、lt;/p>　　q=(p+i*i)%HASHSIZE; q=(p-i*i)%HASHSIZE;　　int CreateHash1(HashTable* H,Record* a,int n) 　　該函數(shù)用于以人名建立哈希表，便于以人民作為關(guān)鍵字查找信息。用哈希表H->elem[pp]來(lái)接受產(chǎn)生的哈希值，record

33、 a[i],用來(lái)傳遞需要建立哈希地址的人員記錄信息，n用來(lái)表示需要建立哈希地址的人員記錄個(gè)數(shù)。其關(guān)鍵語(yǔ)句是 H->elem[pp]=&(a[i]); H->count++;　　for(i=0;i<n;i++)　　{ 　　c=0

34、;　　p=Hash1(a[i].name);　　pp=p;　　while(H->elem[pp]!=NULL) 　　{<b

35、>　　m++;　　pp=collision(p,c);　　if(pp<0||pp>HASHSIZE)　　{　　printf("\t\t第%d記錄無(wú)法解決沖突",i+1) <

36、;/p>　　}　　break;　　}　　H->elem[pp]=&(a[i]); //求得哈希地址，將信

37、息存入　　H->count++;　　IntSearchHash1(HashTable *H,int &c,char str[],int n) 　　該函數(shù)用于以姓名作為關(guān)鍵字進(jìn)行查找信息。HashTable *H表示需要在哈希表中查找，c表示查找時(shí)的沖突次數(shù)，str[]表示需要查找的人員姓名。其

38、關(guān)鍵語(yǔ)句是　　while((H->elem[pp]!=NULL)&&(eq(str,H->elem[pp]->name)==-1))　　pp=collision(p,c);　　if(H->elem[pp]!=NULL&&eq(str,H->elem[p

39、p]->name)==1)　　Status collision2(int p,int &c)　　在以號(hào)碼建立哈希表遇到?jīng)_突時(shí)用該函數(shù)線(xiàn)性探測(cè)法解決沖突處理，p表示以號(hào)碼建立哈希表時(shí)的哈希地址，c代表沖突次數(shù)。其核心語(yǔ)句是 p=(p+1)%HASHSIZE;　　int Hash2(char str[

40、]) 　　該函數(shù)表示以號(hào)碼作為關(guān)鍵字產(chǎn)生哈希值的哈希函數(shù)，str[]表示要產(chǎn)生哈希值的號(hào)碼。其核心語(yǔ)句是m=n%HASHSIZE; 用除留余數(shù)法構(gòu)造哈希函數(shù)　　int CreateHash2(HashTable* H,Record* a,int n) 　　該函數(shù)表示建表以電話(huà)號(hào)碼為關(guān)鍵字

41、建立相應(yīng)的散列表，HashTable* H表示哈希表地址，Record* a表示要建立哈希地址的人員記錄，n表示要建立的記錄個(gè)數(shù)。其核心語(yǔ)句是 while(H->elem[pp]!=NULL)　　{　　m++;　　pp

42、=collision1(p,c);　　if(pp>HASHSIZE)　　{　　printf("\t\t第%d記錄無(wú)法解決沖突",i+1); / break;<p

43、>　　} //無(wú)法解決沖突，跳入下一循環(huán)　　break;　　} //求得哈希地址，將信息存入　　H->elem[pp]=&(a[i]); 　　H->

44、count++;　　SearchHash2(HashTable* H,int &c,char tele[],int n ) 　　該函數(shù)表示以電話(huà)號(hào)碼關(guān)鍵字進(jìn)行查找，HashTable* H 表示需要查找的哈希表，tele[]表示需要查找的號(hào)碼，其核心語(yǔ)句是

45、 　　p=Hash2(tele);　　pp=p;　　while((H->elem[pp]!=NULL)&&(eq(tele,H->elem[pp]->tel)==-1))　　pp=collision

46、(p,c);　　if(H->elem[pp]!=NULL&&eq(tele,H->elem[pp]->tel)==1)　　{　　printf("\n\t\t查找成功！\n\t\t查找過(guò)程沖突次數(shù)為%d\n",c);<

47、/p>　　printf("\t\t以下是您需要要查找的信息:\n");　　printf("\t\t姓名：%s\n\t\t電話(huà)號(hào)碼：%s\n\t\t聯(lián)系地址：%s\n",H->elem[pp]->name,H->elem[pp]->tel,H->elem[pp]->add);</p&g

48、t;　　5 程序編碼　　#include<stdio.h>　　#include<stdlib.h>　　#include<string>　　#define MAXSIZE 2

49、0 //電話(huà)薄記錄數(shù)量 　　#define MAX_SIZE 20 //人名的最大長(zhǎng)度　　#define HASHSIZE 54 //定義表長(zhǎng) 　　#define SUCCESS 1&l

50、t;p>　　#define UNSUCCESS -1　　#define LEN sizeof(HashTable)　　typedef int Status;　　Status NUM_BER; //記錄的個(gè)數(shù)　　typed

51、ef struct //記錄　　{　　char name[20];　　char tel[20];　　char add[20];

52、　　}Record;　　typedef struct //哈希表　　{　　Record *elem[HASHSIZE]; //數(shù)據(jù)元素存儲(chǔ)基址<p

53、>　　int count; //當(dāng)前數(shù)據(jù)元素個(gè)數(shù)　　int size; //當(dāng)前容量　　}HashTable;　　Status eq(char x[],char y[]) //關(guān)鍵

54、字比較，相等返回SUCCESS；否則返回UNSUCCESS　　{　　if(strcmp(x,y)==0)　　return SUCCESS;　　else

55、return UNSUCCESS;　　}　　int getin(Record* a,int n) //鍵盤(pán)輸入各人的信息　　{　　printf("\t\

56、t要添加的個(gè)數(shù)：");　　scanf("%d",&NUM_BER);　　int i; 　　if(NUM_BER<MAXSIZE)　　{ </p&g

57、t;　　for(i=0;i<NUM_BER;i++)　　{　　printf("\t聯(lián)系人%d\n",i+1);　　printf("\t\t用戶(hù)名:");　　scanf

58、("%s",a[i+n].name);　　printf("\t\t號(hào)碼: ");　　scanf("%s",a[i+n].tel);　　printf("\t\t地址: ");　　scanf(

59、"%s",a[i+n].add);//gets(str2); 　　}　　return n+NUM_BER;　　}　　else&l

60、t;/p>　　{　　printf("\t\t輸入的個(gè)數(shù)過(guò)大，請(qǐng)重新選擇：\n");　　return UNSUCCESS;　　}

61、;　　}　　void ShowInformation(Record* a,int n) //顯示輸入的用戶(hù)信息　　{　　int i;　　for( i=0;i&

62、lt;n;i++) 　　printf("\n\t第%d個(gè)用戶(hù)信息:\n\t\t姓名：%s\n \t\t電話(huà)號(hào)碼：%s\n \t\t聯(lián)系地址：%s\n",i+1,a[i].name,a[i].tel,a[i].add); 　　} </p&g

63、t;　　long fold(char s[20]) //人名的折疊處理　　{ 　　char *p;　　long sum=0;　　char ss[20];&l

64、t;/p>　　strcpy(ss,s); //復(fù)制字符串，不改變?cè)址拇笮?xiě)　　strupr(ss); //將字符串ss轉(zhuǎn)換為大寫(xiě)形式　　p=ss;　　while(*p!='\0')&

65、lt;/p>　　sum+=*p++;　　printf("\n\t\tsum=%d",sum); 　　return sum;　　}　　int Hash1(char str[]) //哈

66、希函數(shù)　　{ 　　long n;　　int m;　　n=fold(str); //先將用戶(hù)名進(jìn)行折疊處理<p

67、>　　m=n%HASHSIZE; //折疊處理后的數(shù)，用除留余數(shù)法構(gòu)造哈希函數(shù)　　return m; //并返回模值　　}　　Status collision1(int p,int &c) //沖突處理函數(shù)，采用二次探測(cè)再散列

68、法解決沖突。　　{ // p為由Hash1產(chǎn)生的哈希值，c為沖突次數(shù)。q,記錄處理沖突的值　　int i,q;　　i=c/2+1;　　while(i

69、<HASHSIZE)　　{　　if(c%2==0)　　{　　c++;　　q=(p+i*i)%HASHSIZE;

70、　　if(q>=0)　　return q;　　else i=c/2+1;　　}　　else&

71、lt;/b>　　{　　q=(p-i*i)%HASHSIZE;　　c++;　　if(q>=0)<b&

72、gt;　　return q;　　else i=c/2+1;　　}　　}　　return UNSUCCESS;　　}&

73、lt;/b>　　int CreateHash1(HashTable* H,Record* a,int n) //建表，以人的姓名為關(guān)鍵字，建立相應(yīng)的散列表　　{ //若哈希地址沖突，進(jìn)行沖突處。n為記錄中的人員個(gè)數(shù)　　H->count

74、=0;　　int i,p=-1,c,pp,m=0;//p用來(lái)記錄哈希值,pp作為哈希表的元素變量，m用來(lái)記錄查找次數(shù)。 　　float ASL;　　for(i=0;i<n;i++)　　{ <p&

75、gt;　　c=0;　　p=Hash1(a[i].name);　　pp=p;　　while(H->elem[pp]!=NULL) 　　{

76、;　　m++;　　pp=collision1(p,c);　　if(pp<0||pp>HASHSIZE)　　{　　printf("\t\t第%d記錄無(wú)法解

77、決沖突",i+1); //需要顯示沖突次數(shù)時(shí)輸出 ,無(wú)法解決沖突，跳入下一循環(huán)　　}　　break;　　}　　H->elem[pp]=&

78、amp;(a[i]); //求得哈希地址，將信息存入　　H->count++;　　printf("\t\t第%d個(gè)記錄沖突次數(shù)為%d。\n",i+1,c); //需要顯示沖突次數(shù)時(shí)輸出　　}

79、;　　ASL=float((m+n-1)/(n-1));　　printf("\t\t平均查找長(zhǎng)度為ASL=%f\n",ASL);　　printf("\n\t\t建表完成!\n\t\t此哈希表容量為%d,當(dāng)前表內(nèi)存儲(chǔ)的記錄個(gè)數(shù)為%d.\n",HASHSIZE,H->co

80、unt);　　return SUCCESS ;　　}　　int SearchHash1(HashTable* H,int &c,char str[],int n) //在通訊錄里查找姓名關(guān)鍵字，若查找成功，顯示信息&l

81、t;p>　　{ //c用來(lái)記錄沖突次數(shù),查找成功時(shí)顯示沖突　　int p,pp; //p用來(lái)記錄哈希值,pp作為哈希表的元素變量　　p=Hash1(str);&

82、lt;b>　　pp=p;　　while((H->elem[pp]!=NULL)&&(eq(str,H->elem[pp]->name)==-1))　　pp=collision1(p,c);　　if(H->elem[pp]!=NULL&&am

83、p;eq(str,H->elem[pp]->name)==1)　　{　　printf("\n\t\t查找成功！\n\t\t查找過(guò)程沖突次數(shù)為%d \n ",c);　　printf("\t\t 以下是您需要要查找的信息：\n\n&quo

84、t;);　　printf("\t\t姓名：%s\n\t\t電話(huà)號(hào)碼：%s\n\t\t聯(lián)系地址：%s\n",H->elem[pp]->name,H->elem[pp]->tel,H->elem[pp]->add);　　return SUCCESS; &

85、lt;b>　　}　　else　　{　　printf("\t\t此人不存在，查找不成功!\n");　　return UNSUCCESS ;</p&

86、gt;　　} 　　}　　int Hash2(char str[]) //哈希函數(shù)　　{　　long

87、n;　　int m;　　n = atoi(str); //把字符串轉(zhuǎn)換成整型數(shù).　　m=n%HASHSIZE; //用除留余數(shù)法構(gòu)造哈希函數(shù)　　return m; //并返回模值

88、　　}　　Status collision2(int p,int &c) //沖突處理函數(shù)，采用線(xiàn)性探測(cè)法解決沖突。p為由Hash2產(chǎn)生的哈希值，c為沖突次數(shù)。　　{&

89、lt;p>　　p=(p+1)%HASHSIZE;　　c++;　　if(p>HASHSIZE)　　{　　printf("\t\t第%d記錄無(wú)法解決沖突");</

90、p>　　return UNSUCCESS;　　}　　else　　return p;　　}&l

91、t;/p>　　int CreateHash2(HashTable* H,Record* a,int n) //建表，以電話(huà)號(hào)碼為關(guān)鍵字，建立相應(yīng)的散列表　　{ //若哈希地址沖突，進(jìn)行沖突處　　H->count=0

92、;　　int i,p,c,pp,m=0;　　float ASL;　　for(i=0;i<n;i++)　　{　　c=0;<

93、;p>　　p=Hash2(a[i].tel);　　pp=p;　　while(H->elem[pp]!=NULL)　　{　　m++;</p&g

94、t;　　pp=collision2(p,c);　　if(pp>HASHSIZE)　　{　　printf("\t\t第%d記錄無(wú)法解決沖突",i+1); //需要顯示沖突次數(shù)時(shí)輸出

95、　　break;　　} //無(wú)法解決沖突，跳入下一循環(huán)　　break;　　} <

96、p>　　H->elem[pp]=&(a[i]); //求得哈希地址，將信息存入 　　H->count++;　　printf("\t\t第%d個(gè)記錄沖突次數(shù)為%d.\n",i+1,c); //需要顯示沖突次數(shù)時(shí)

97、輸出　　}　　ASL=float((m+n-1)/(n-1));　　printf("\t\t平均查找長(zhǎng)度為ASL=%f\n",ASL);　　printf("\n\t\t建表完成!\n\t\t此哈希表容量為

98、%d,當(dāng)前表內(nèi)存儲(chǔ)的記錄個(gè)數(shù)為%d.\n",HASHSIZE,H->count);　　return SUCCESS ;　　}　　SearchHash2(HashTable*H,int &c,char tele[],int n )

99、 //在通訊錄里查找電話(huà)號(hào)碼關(guān)鍵字，若查找成功，顯示信息　　{ //c用來(lái)記錄沖突次數(shù),查找成功時(shí)顯示沖突次.n是記錄表中存儲(chǔ)的人員個(gè)數(shù)　　int m=0;　　int p,pp;

100、　　p=Hash2(tele);　　pp=p;　　while((H->elem[pp]!=NULL)&&(eq(tele,H->elem[pp]->tel)==-1))　　pp=collision2(p,c);</

101、p>　　if(H->elem[pp]!=NULL&&eq(tele,H->elem[pp]->tel)==1)　　{　　printf("\n\t\t查找成功！\n\t\t查找過(guò)程沖突次數(shù)為%d\n",c);<

102、;p>　　printf("\t\t以下是您需要要查找的信息:\n");　　printf("\t\t姓名：%s\n\t\t電話(huà)號(hào)碼：%s\n\t\t聯(lián)系地址：%s\n",H->elem[pp]->name,H->elem[pp]->tel,H->elem[pp]->add);<p&g

103、t;　　return SUCCESS ;　　}　　else 　　{　　printf("\n\t\t此人不存在，查找不成功!\n");&l

104、t;/p>　　return UNSUCCESS; 　　}　　}　　void InsertH(HashTable* H,Record* a,int c,int n) //以姓名作為關(guān)鍵字進(jìn)行函數(shù)值得插

105、入。c用來(lái)記錄沖突次數(shù)， 　　{ // n用來(lái)統(tǒng)計(jì)Record 類(lèi)型的結(jié)構(gòu)體中的記錄人員個(gè)數(shù)。　　int i, p=-1,pp;　　i=n;&l

106、t;/p>　　p=Hash1(a[i].name);　　pp=p;　　if(H->elem[pp]!=NULL) 　　{　　pp=collision1(p,c);

107、　　if(pp<0)　　{　　printf("\t\t第記錄無(wú)法解決沖突");　　}<

108、;b>　　}　　if(H->elem[pp]==NULL)　　{　　H->elem[pp]=&(a[NUM_BER]); 　　H->count++;<p

109、>　　}　　}　　int main()　　{　　int c=0,i,num,n=0;　　HashTable *

110、H;　　H=(HashTable*)malloc(LEN);　　for(i=0;i<HASHSIZE;i++)　　H->elem[i]=NULL;　　H->size=HASHSIZE;　　H->count=

111、0;　　Record a[MAXSIZE];　　do　　{　　system("cls");　　printf("\n

112、歡迎使用電話(huà)號(hào)碼查找系統(tǒng) "); 　　printf("\n ------------------------------------------------------------"); 　　printf("\n ┃

113、 -哈希表的設(shè)計(jì)與實(shí)現(xiàn) ┃");　　printf("\n ┃ 1. 建立用戶(hù)信息 ┃");　　printf("\n ┃ 2. 讀取所有用戶(hù)信息

114、 ┃");　　printf("\n ┃ 3. 添加用戶(hù)信息 ┃");　　printf("\n ┃ 4. 以姓名建立哈希表(二次散列法法解決沖突) ┃");<p&

115、gt;　　printf("\n ┃ 5. 以電話(huà)號(hào)碼建立哈希表(線(xiàn)性探測(cè)發(fā)法解決沖突) ┃");　　printf("\n ┃ 6. 查找并顯示給定用戶(hù)名的記錄 ┃");　　printf("\n ┃ 7. 查找并顯示

116、給定電話(huà)號(hào)碼的記錄 ┃");　　printf("\n ┃ 0. 退出程序 ┃"); 　　printf("\n ┃ 溫馨提示：

117、 ┃"); 　　printf("\n ┃ Ⅰ.進(jìn)行6操作前請(qǐng)先輸出4 ┃"); 　　printf("\n ┃ Ⅱ.進(jìn)行7操作前請(qǐng)先輸出5 ┃");

118、 　　printf("\n ┗〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓┛");　　printf("\n");　　printf("請(qǐng)輸入一個(gè)任務(wù)選項(xiàng):");　　scanf("%d&qu

119、ot;,&num);　　switch(num)　　{　　case 1:　　printf("\t1.建立用戶(hù)信息\n");　　n

120、=getin(a,n);　　system("pause");　　break;　　case 2:　　printf("\t2.讀取所有用戶(hù)信息\n"); <

121、;/p>　　ShowInformation(a,n);　　system("pause");　　break;　　case 3:　　printf(&qu

122、ot;\t3.添加用戶(hù)信息\n");　　printf("\t\t請(qǐng)輸入用戶(hù)名:");　　scanf("%s",a[n].name);　　printf("\t\t號(hào)碼: ");　　scanf("

123、;%s",a[n].tel);　　printf("\t\t地址: ");　　scanf("%s",a[n].add);　　InsertH(H,a,c,n);n++;　　system("pause");

124、　　break;　　case 4:　　printf("\t4.以姓名建立哈希表(二次散列法法解決沖突)\n");　　CreateHash1(H,a,n);

125、 /* 以姓名建立哈希表 */　　system("pause");　　break;　　case 5:　　printf("\t5.

126、以電話(huà)號(hào)碼建立哈希表(線(xiàn)性探測(cè)發(fā)法解決沖突)\n");　　CreateHash2(H,a,n); /* 以電話(huà)號(hào)碼建立哈希表 */　　system("pause");　　break ;

127、;　　case 6:　　char str[20];　　printf("\t 6.查找并顯示給定用戶(hù)名的記錄\n");　　printf("\t\t請(qǐng)輸入要查找記錄的姓名：");　　scanf(&q

128、uot;%s",str);　　SearchHash1(H,c,str,n);　　system("pause");　　break; 　　case 7:

129、;　　char tele[20];　　printf("\t7.查找并顯示給定電話(huà)號(hào)碼的記錄\n");　　printf("\n\t\t請(qǐng)輸入要查找記錄的電話(huà)號(hào)碼：");　　scanf("%s",tele);&l

130、t;p>　　SearchHash2(H,c,tele,n);　　system("pause");　　break; 　　case 0:　　printf("\t0.

131、退出程序\n"); 　　return 0;　　break;　　default:　　printf("\t\t你輸錯(cuò)了，請(qǐng)重新輸入!&quo

132、t;);　　printf("\n"); 　　}　　}while((0<=num)&&(num<=7));　　system("pause");&

133、lt;p>　　return 0;　　}　　6 程序調(diào)試與測(cè)試　　1）進(jìn)入程序后，顯示程序主菜單，并且提醒用戶(hù)輸入　　圖6.1 顯示程序主菜單</

134、p>　　2）選擇1后，提醒添加用戶(hù)個(gè)數(shù)，然后添加用戶(hù)信息　　圖6.2 建立用戶(hù)信息　　3）選擇序號(hào)2顯示所有用戶(hù)信息　　圖6.3顯示所有人員信息　　4.）選擇序號(hào)4 ，則顯示所有記錄的以姓名建立的哈希表。并顯示平均查找長(zhǎng)度ASL<

135、;/p>　　圖6.4以姓名作為關(guān)鍵字建立哈希表　　5）選擇序號(hào)6后提醒用戶(hù)輸入要查找的用戶(hù)姓名。輸入后顯示用戶(hù)信息和沖突次數(shù)　　圖6.5 以姓名作為關(guān)鍵字進(jìn)行查找　　6）選擇序號(hào)5 后，則顯示所有記錄的以號(hào)碼建立的哈希表。并顯示平均查找長(zhǎng)度ASL<p&g

136、t;　　圖6.6 以號(hào)碼作為關(guān)鍵字建立哈希表　　7）. 提醒用戶(hù)輸入要查找的用戶(hù)號(hào)碼，輸入后顯示用戶(hù)信息和沖突次數(shù)　　圖7.7 用號(hào)碼查找信息　　8）. 選擇序號(hào)2顯示所有用戶(hù)信息　　圖7.8顯示所有用戶(hù)信息　　9）．選擇序號(hào)

137、3后則提醒輸入用戶(hù)信息。（以人員姓名作為關(guān)鍵字進(jìn)行函數(shù)值得插入）　　圖9.9添加用戶(hù)信息　　10）輸入序號(hào)2后，則再顯示包括添加的用戶(hù)信息在內(nèi)的所有用戶(hù)信息　　圖9.10 讀取添加的結(jié)果，顯示所有用戶(hù)信息　　11.）添加后用姓名作為關(guān)鍵字從新建立哈希表

138、;　　圖9.11 以姓名建立哈希表　　12）用姓名查找添加的新用戶(hù)信息　　圖9.12 查找添加的用戶(hù)信息　　13.）用號(hào)碼作為關(guān)鍵字從新建立哈希表　　圖9.13 以號(hào)碼建立哈希表　　14

眾賞文庫(kù)> 全部分類(lèi)> 畢業(yè)設(shè)計(jì)

溫馨提示

1. 本站所有資源如無(wú)特殊說(shuō)明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶(hù)所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽，若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 眾賞文庫(kù)僅提供信息存儲(chǔ)空間，僅對(duì)用戶(hù)上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理，對(duì)用戶(hù)上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請(qǐng)與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶(hù)因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

哈希表課程設(shè)計(jì)--哈希表的實(shí)現(xiàn)與應(yīng)用

文檔簡(jiǎn)介

溫馨提示

最新文檔

評(píng)論

哈希表課程設(shè)計(jì)--哈希表的實(shí)現(xiàn)與應(yīng)用

文檔簡(jiǎn)介

溫馨提示

最新文檔

評(píng)論

免費(fèi)下載