設(shè)計(jì)散列表實(shí)現(xiàn)電話號(hào)碼查找系統(tǒng)

1、華 北 科 技 學(xué) 院課程設(shè)計(jì)說明書學(xué)號(hào)： 班級(jí): 網(wǎng)絡(luò)B15-1 姓名: 設(shè)計(jì)題目: 散列表的設(shè)計(jì)與實(shí)現(xiàn) 設(shè)計(jì)地點(diǎn):_設(shè)計(jì)時(shí)間: 2017-2-27 至 2017-3-10 成績?cè)u(píng)定：1、工作量： A（ ），B（ ），C（ ），D（ ）,F( )2、難易度： A（ ），B（ ），C（ ），D（ ）,F( )3、答辯情況： A（ ），B（ ），C（ ），D（ ）,F( )4、報(bào)告規(guī)范度：A（ ），B（ ），C（ ），D（ ）,F( )5、學(xué)習(xí)態(tài)度： A（ ），B（ ），C（ ），D（ ）,F( )總評(píng)成績:_指導(dǎo)教師: 朱冬梅一、問題描述與需求分析1、問題描述設(shè)計(jì)散列表實(shí)現(xiàn)電話號(hào)碼查找系統(tǒng)。2

2、、功能需求分析1)每個(gè)記錄有下列數(shù)據(jù)項(xiàng)：電話號(hào)碼、用戶名、地址；2)從鍵盤輸入各記錄，分別以電話號(hào)碼和用戶名為關(guān)鍵字建立散列表；3)采用一定的方法解決沖突；4)查找并顯示給定電話號(hào)碼的記錄；5)查找并顯示給定用戶名的記錄。6)在散列函數(shù)確定的前提下，嘗試各種不同類型處理沖突的方法，考察平均查找長度的變化。二、概要設(shè)計(jì)1、總體設(shè)計(jì)思路程序的總體實(shí)現(xiàn)思路、方法：本程序使用了鏈地址法和開放定址法處理沖突，可以實(shí)現(xiàn)從鍵盤輸入各記錄，分別以電話號(hào)碼和用戶名為關(guān)鍵字建立散列表；查找并顯示給定電話號(hào)碼的記錄；查找并顯示給定用戶名的記錄；計(jì)算使用不同方法處理沖突時(shí)的平均查找長度。當(dāng)使用鏈地址法處理沖突，電話號(hào)

3、碼為關(guān)鍵字建立散列表時(shí)，使用除留余數(shù)法(t=e->number%n)，確定哈希地址。當(dāng)使用鏈地址法處理沖突，用戶名為關(guān)鍵字建立散列表時(shí)，把儲(chǔ)存用戶名的字符數(shù)組（name）的0號(hào)位置的字符(name0)強(qiáng)制轉(zhuǎn)換為int類型(i)，即i=（int）name0,再使用除留余數(shù)法確定哈希地址(i=i%n，n=13)。當(dāng)使用開放定址法處理沖突，電話號(hào)碼為關(guān)鍵字建立散列表時(shí)，增量序列取用線性探測(cè)再散列法。當(dāng)使用開放定址法處理沖突，用戶名為關(guān)鍵字建立散列表時(shí)，把儲(chǔ)存用戶名的字符數(shù)組（name2）的0號(hào)位置的字符(name20)強(qiáng)制轉(zhuǎn)換為int類型(e)，即e=(int)name0,使用開放定址法取得哈

4、希地址，如果產(chǎn)生沖突增量取用線性探測(cè)再散列法。用戶名為關(guān)鍵字號(hào)碼為關(guān)鍵字添加查詢用戶名為關(guān)鍵字號(hào)碼為關(guān)鍵字用戶名為關(guān)鍵字號(hào)碼為關(guān)鍵字添加查詢用戶名為關(guān)鍵字號(hào)碼為關(guān)鍵字鏈地址法開放定址法電話號(hào)碼查找系統(tǒng)初始化散列表記算ASL程序總的功能結(jié)構(gòu)圖。2、 模塊簡介鏈地址法：void hashlistinit(newnode *p)/初始化散列表void hashinputname(newnode *p)/添加記錄（以用戶名為關(guān)鍵字）void hashshow2name(newnode *p)/查詢記錄（以用戶名為關(guān)鍵字）void hashinput(newnode *p)/添加記錄（以號(hào)碼為關(guān)鍵字）v

5、oid hashshow(newnode *p)/查詢記錄（以號(hào)碼為關(guān)鍵字）void ASL(newnode *p)/計(jì)算ASL開放定址法void hashlistinit2(anode3 w)/初始化散列表void hashinput2(anode3 w)/添加記錄（以號(hào)碼為關(guān)鍵字）void hashshow2(anode3 w)/查詢記錄（以號(hào)碼為關(guān)鍵字）void hashinputname2(anode3 w/添加記錄（以用戶名為關(guān)鍵字）void hashshow2name2(anode3 w)/查詢記錄（以用戶名為關(guān)鍵字）void ASL2(anode3 w)/計(jì)算ASLint sca

6、n()/菜單顯示函數(shù)int scan2()/菜單顯示函數(shù)三、詳細(xì)設(shè)計(jì)1、數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)鏈地址法：電話號(hào)碼地址名字指向下一個(gè)結(jié)點(diǎn)typedef struct node 0int number; char addresssize;char namesize;struct node *next;newnode,*anode; 13開放定址法： 電話號(hào)碼地址名字記錄使用開放定址法時(shí)的沖突次數(shù)typedef struct node2 int number2;char address2size;char name2size;int v;/沖突次數(shù)newnode2,*anode2;指向（newnod型數(shù)組）儲(chǔ)

7、存錄入信息的數(shù)組判斷存儲(chǔ)空間是否已滿記錄表長typedef struct node3anode2 q;/信息錄入數(shù)組int i;/判斷存儲(chǔ)空間int j;/表長newnode3,*anode3;2、 算法分析與實(shí)現(xiàn)開放定址法添加記錄（以用戶名為關(guān)鍵字）使用開放定址法，以用戶名為關(guān)鍵字，添加記錄當(dāng)輸入的電話號(hào)碼不為-1時(shí)，輸入姓名（英文），把姓名的第一個(gè)英文字母（char型）強(qiáng)制轉(zhuǎn)換為整型e,再使用開放定址法獲取哈希地址，增量取用線性探測(cè)再散列法。e=（ (int)a0 +k）%表長該位置是否為空?在該位置插入數(shù)據(jù)輸入地址K=k+1輸入地址 在該位置插入數(shù)據(jù)輸出內(nèi)存已滿結(jié)束e=(int)a0%表

8、長該位置是否為空?哈希表是否已滿？K=1輸入姓名（char a100）d= -1?開始輸入電話號(hào)碼d Y N N Y Y Y N N Y N Y Y 四、運(yùn)行結(jié)果和調(diào)試分析測(cè)試數(shù)據(jù)：姓名住址電話號(hào)碼Fu云南19Yuan河北14Dong山西23鏈地址法：用戶名為關(guān)鍵字建立散列表：ASL=1以號(hào)碼為關(guān)鍵字建立散列表：ASL=1開放定址法：用戶名為關(guān)鍵字建立散列表：ASL=1以號(hào)碼為關(guān)鍵字建立散列表：ASL=1運(yùn)行結(jié)果圖。1.選用建表方法，初始化散列表。鏈地址法2. 添加記錄（以用戶名為關(guān)鍵字）鏈地址法3. 查詢記錄（以用戶名為關(guān)鍵字）鏈地址法4. 計(jì)算ASL鏈地址法5. 添加記錄（以號(hào)碼為關(guān)鍵字）

9、鏈地址法6. 查詢記錄（以號(hào)碼為關(guān)鍵字）鏈地址法7.切換開放定址法8. 初始化散列表，添加記錄（以用戶名為關(guān)鍵字）開放定址法9. 查詢記錄（以用戶名為關(guān)鍵字）開放定址法10. 計(jì)算ASL開放定址法11. 添加記錄（以號(hào)碼為關(guān)鍵字）開放定址法12. 查詢記錄（以號(hào)碼為關(guān)鍵字）開放定址法13.退出系統(tǒng)五、總結(jié)體會(huì)課程設(shè)計(jì)使我對(duì)數(shù)據(jù)結(jié)構(gòu)課程的理解更深入，也能夠發(fā)現(xiàn)自己平時(shí)不太注意的語法錯(cuò)誤。當(dāng)遇到問題時(shí)就翻書，或者上網(wǎng)查資料。在程序調(diào)試的過程中也能夠完善系統(tǒng)。在課程設(shè)計(jì)過程中，使我的思路更為開拓。參考文獻(xiàn)1嚴(yán)蔚敏，吳偉民編著數(shù)據(jù)結(jié)構(gòu)（C語言版）清華大學(xué)出版社。2孫改平，王德志編著，C語言程序設(shè)計(jì)，清

10、華大學(xué)出版社。程序源碼：#include <iostream>#include <stdio.h>#include<stdlib.h>#include<string.h>#define size 100#define n 13typedef struct nodeint number;char addresssize;char namesize;struct node *next;newnode,*anode;typedef struct node2int number2;char address2size;char name2size;int

11、v;/沖突次數(shù)newnode2,*anode2;typedef struct node3anode2 q;/信息錄入數(shù)組int i;/判斷存儲(chǔ)空間int j;/表長newnode3,*anode3;void hashlistinit(newnode *p)/初始化散列表鏈地址法int i;for(i=0;i<n;i+) pi=NULL;printf("親，散列表已初始化完畢n");void hashinputname(newnode *p)/添加記錄（以用戶名為關(guān)鍵字）鏈地址法int i,v;printf("請(qǐng)輸入數(shù)據(jù)n");printf(&quo

12、t;請(qǐng)輸入電話號(hào)碼，輸入-1結(jié)束n");scanf("%d",&v);while(v!=-1) anode e=(anode)malloc(sizeof(newnode); e->number=v; printf("請(qǐng)輸入地址n"); scanf("%s",e->address); printf("請(qǐng)輸入名字(英文)n"); scanf("%s",e->name); i=(int)e->name0; i=i%n; e->next=pi; pi=e;

13、 printf("請(qǐng)輸入電話號(hào)碼，輸入-1結(jié)束n"); scanf("%d",&v);void hashshow2name(newnode *p)/查詢記錄（以用戶名為關(guān)鍵字）鏈地址法char asize;anode t;int i;printf("請(qǐng)輸入要查詢用戶名n");scanf("%s",a);i=(int)a0;i=i%n;t=pi;while(t&&strcmp(t->name,a)!=0) t=t->next;if(t=NULL) printf("您所查詢

14、的用戶不存在n");else printf("-n"); printf("姓名:%sn",t->name); printf("電話:%dn",t->number); printf("地址:%sn",t->address); printf("-n");void hashinput(newnode *p)/添加記錄（以號(hào)碼為關(guān)鍵字）鏈地址法int t,v;printf("請(qǐng)輸入數(shù)據(jù)n");printf("請(qǐng)輸入電話號(hào)碼，輸入-1結(jié)束n&quo

15、t;);scanf("%d",&v);while(v!=-1) anode e=(anode)malloc(sizeof(newnode); e->number=v; printf("請(qǐng)輸入地址n"); scanf("%s",e->address); printf("請(qǐng)輸入名字(英文)n"); scanf("%s",e->name); t=e->number%n; e->next=pt; pt=e; printf("請(qǐng)輸入電話號(hào)碼，輸入-1結(jié)束n&

16、quot;); scanf("%d",&v);void hashshow(newnode *p)/查詢記錄（以號(hào)碼為關(guān)鍵字）鏈地址法int d,h;anode t;printf("請(qǐng)輸入所要查詢的電話號(hào)碼n");scanf("%d",&d);h=d%n;t=ph;while(t&&t->number!=d) t=t->next;if(t=NULL) printf("您所要查詢的號(hào)碼不存在n");else printf("-n"); printf(&qu

17、ot;姓名:%sn",t->name); printf("電話:%dn",t->number); printf("地址:%sn",t->address); printf("-n");void ASL(newnode *p)/計(jì)算ASL鏈地址法int asize,l,asl,z,b;asl=0;z=0;anode u;for(l=0;l<size+1;l+) al=0;for(l=0;l<n;l+) b=1; u=pl; while(u) ab+; b+; u=u->next; for(l=

18、1;l<n+1;l+) asl=asl+al*l; z=z+al;asl=asl/z;printf("用鏈地址法處理沖突：ASL=%dn",asl);void hashlistinit2(anode3 w)/初始化散列表開放定址法鏈地址法anode2 e;e=(anode2)malloc(n*sizeof(newnode2);if(!e) exit(0);w->q=e;w->i=n;w->j=n;for(int h=0;h<w->j;h+) w->qh.number2=0; w->qh.v=0; strcpy(w->qh

19、.address2,"無"); strcpy(w->2,"無");void hashinput2(anode3 w)/添加記錄（以號(hào)碼為關(guān)鍵字）開放定址法int d,t,k;k=1;printf("親請(qǐng)輸入所要錄入的信息n");printf("電話號(hào)碼(輸入-1結(jié)束)：");scanf("%d",&d);t=d%w->j;while(d!=-1)if(w->qt.number2=0&&w->i!=0)w->qt.number2=

20、d;printf("姓名：");scanf("%s",w->2);printf("地址：");scanf("%s",w->qt.address2);w->i=w->i-1;w->qt.v=1;else if(w->i=0) printf("內(nèi)存已滿n");else if(w->qt.number2!=0) t=(d+k)%w->j; k=k+1; w->qt.v=2; while(w->qt.number2!=0&

21、&k<w->j) t=(d+k)%w->j; k=k+1; w->qt.v+; w->qt.number2=d;printf("姓名：");scanf("%s",w->2);printf("地址：");scanf("%s",w->qt.address2);w->i=w->i-1;printf("電話號(hào)碼(輸入-1結(jié)束)：");scanf("%d",&d);t=d%w->j;void ha

22、shshow2(anode3 w)/查詢記錄（以號(hào)碼為關(guān)鍵字）開放定址法int d,k,t;k=1;printf("請(qǐng)輸入要查詢的電話號(hào)碼：");scanf("%d",&d);t=d%w->j;if(w->qt.number2=d) printf("-n"); printf("姓名:%sn",w->2); printf("電話:%dn",w->qt.number2); printf("地址:%sn",w->qt.addres

23、s2); printf("-n");else t=(d+k)%w->j; k=k+1; while(w->qt.number2!=d&&k<w->j) t=(d+k)%w->j; k=k+1; if(w->qt.number2=d) printf("-n"); printf("姓名:%sn",w->2); printf("電話:%dn",w->qt.number2); printf("地址:%sn",w->qt.

24、address2); printf("-n"); else printf("您所要查詢的號(hào)碼不存在n"); void hashinputname2(anode3 w)/添加記錄（以用戶名為關(guān)鍵字）開放定址法char asize;int e,k,d;k=1;printf("請(qǐng)輸入要錄入的信息n");printf("電話號(hào)碼(輸入-1結(jié)束)：");scanf("%d",&d);while(d!=-1) printf("姓名（英文）："); scanf("%s&q

25、uot;,a); e=(int)a0; e=e%w->j; if(strcmp(w->2,"無")=0&&w->i!=0) strcpy(w->2,a); w->qe.number2=d; printf("地址："); scanf("%s",w->qe.address2); w->i=w->i-1; w->qe.v=1;else if(w->i=0) printf("內(nèi)存已滿n");else if(strcmp(

26、w->2,"無")!=0) e=(e+k)%w->j; k=k+1; w->qe.v=2; while(strcmp(w->2,"無")!=0&&k<w->j) e=(e+k)%w->j; k=k+1; w->qe.v+; strcpy(w->2,a); w->qe.number2=d; printf("地址："); scanf("%s",w->qe.address2); w->i=w-

27、>i-1;printf("電話號(hào)碼(輸入-1結(jié)束)：");scanf("%d",&d);void hashshow2name2(anode3 w)/查詢記錄（以用戶名為關(guān)鍵字）開放定址法char asize;int e,k;k=1;printf("請(qǐng)輸入要查詢的用戶名（英文）:");scanf("%s",a);e=(int)a0;e=e%w->j;if(strcmp(w->2,a)=0) printf("-n"); printf("姓名:%sn&

28、quot;,w->2); printf("電話:%dn",w->qe.number2); printf("地址:%sn",w->qe.address2); printf("-n");else e=(e+k)%w->j; k=k+1; while(strcmp(w->2,a)!=0&&k<w->j) e=(e+k)%w->j; k=k+1; if(k>=w->j) printf("您所查詢的用戶不存在n"); el

29、se printf("-n"); printf("姓名:%sn",w->2); printf("電話:%dn",w->qe.number2); printf("地址:%sn",w->qe.address2); printf("-n"); void ASL2(anode3 w)/計(jì)算ASL開放定址法int asl,c,z;asl=0;z=0;for(c=0;c<w->j;c+) asl=asl+w->qc.v;for(c=0;c<w->

30、j;c+) if(w->qc.number2!=0) z+; asl=asl/z;printf("用開放定址法處理沖突：ASL=%dn",asl);int scan()int m;printf("*n");printf(" 菜單 1 n");printf("*n");printf("親，您要用選用哪個(gè)方法？n");printf("1.鏈地址法n");printf("2.開放定址法n");printf("-n");printf(&q

31、uot;親，請(qǐng)您輸入要選用的方法：");scanf("%d",&m);return m;int scan2()int j1;printf("*n");printf(" 菜單 2 n");printf("*n");printf("親啊，我有如下功能哦n");printf("1.初始化散列表n");printf("2.添加記錄（以用戶名為關(guān)鍵字）n");printf("3.查詢記錄（以用戶名為關(guān)鍵字）n");printf("4.添加記錄（以號(hào)碼為關(guān)鍵字）n")