1、華 北 科 技 學 院課程設計說明書學號： 班級: 網絡B15-1 姓名: 設計題目: 散列表的設計與實現 設計地點:_設計時間: 2017-2-27 至 2017-3-10 成績評定：1、工作量： A（ ），B（ ），C（ ），D（ ）,F( )2、難易度： A（ ），B（ ），C（ ），D（ ）,F( )3、答辯情況： A（ ），B（ ），C（ ），D（ ）,F( )4、報告規范度：A（ ），B（ ），C（ ），D（ ）,F( )5、學習態度： A（ ），B（ ），C（ ），D（ ）,F( )總評成績:_指導教師: 朱冬梅一、問題描述與需求分析1、問題描述設計散列表實現電話號碼查找系統。2

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

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

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

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

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

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

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

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

10、華大學出版社。程序源碼：#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;/沖突次數newnode2,*anode2;typedef struct node3anode2 q;/信息錄入數組int i;/判斷存儲空間int j;/表長newnode3,*anode3;void hashlistinit(newnode *p)/初始化散列表鏈地址法int i;for(i=0;i<n;i+) pi=NULL;printf("親，散列表已初始化完畢n");void hashinputname(newnode *p)/添加記錄（以用戶名為關鍵字）鏈地址法int i,v;printf("請輸入數據n");printf(&quo

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

13、 printf("請輸入電話號碼，輸入-1結束n"); scanf("%d",&v);void hashshow2name(newnode *p)/查詢記錄（以用戶名為關鍵字）鏈地址法char asize;anode t;int i;printf("請輸入要查詢用戶名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)/添加記錄（以號碼為關鍵字）鏈地址法int t,v;printf("請輸入數據n");printf("請輸入電話號碼，輸入-1結束n&quo

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

16、quot;); scanf("%d",&v);void hashshow(newnode *p)/查詢記錄（以號碼為關鍵字）鏈地址法int d,h;anode t;printf("請輸入所要查詢的電話號碼n");scanf("%d",&d);h=d%n;t=ph;while(t&&t->number!=d) t=t->next;if(t=NULL) printf("您所要查詢的號碼不存在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)/計算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)/添加記錄（以號碼為關鍵字）開放定址法int d,t,k;k=1;printf("親請輸入所要錄入的信息n");printf("電話號碼(輸入-1結束)：");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");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("電話號碼(輸入-1結束)：");scanf("%d",&d);t=d%w->j;void ha

22、shshow2(anode3 w)/查詢記錄（以號碼為關鍵字）開放定址法int d,k,t;k=1;printf("請輸入要查詢的電話號碼：");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("您所要查詢的號碼不存在n"); void hashinputname2(anode3 w)/添加記錄（以用戶名為關鍵字）開放定址法char asize;int e,k,d;k=1;printf("請輸入要錄入的信息n");printf("電話號碼(輸入-1結束)：");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");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("電話號碼(輸入-1結束)：");scanf("%d",&d);void hashshow2name2(anode3 w)/查詢記錄（以用戶名為關鍵字）開放定址法char asize;int e,k;k=1;printf("請輸入要查詢的用戶名（英文）:");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)/計算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("親，您要用選用哪個方法？n");printf("1.鏈地址法n");printf("2.開放定址法n");printf("-n");printf(&q

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