設計散列表實現(xiàn)電話號碼查找系統(tǒng)

1、華 北 科 技 學 院 課程設計說明書學號：班級:網(wǎng)絡 b15-1姓名:設計題目:散列表的設計與實現(xiàn)設計地點:_設計時間: 2017-2-27 成績評定：至2017-3-101、 工作量：2、 難易度：3、 答辯情況：a（ ），b（ ），c（ ），d（ ）,f( ) a（ ），b（ ），c（ ），d（ ）,f( ) a（ ），b（ ），c（ ），d（ ）,f( )4、報告規(guī)范度：a（ ），b（ ），c（ ），d（ ）,f( )5、學習態(tài)度：a（ ），b（ ），c（ ），d（ ）,f( )總評成績:_指導教師:朱冬梅一、問題描述與需求分析 1、問題描述設計散列表實現(xiàn)電話號碼查找系統(tǒng)。2、功能需求

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

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

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

5、算 asl開放定址法void hashlistinit2(anode3 w)/初始化散列表void hashinput2(anode3 w)/添加記錄（以號碼為關(guān)鍵字） void hashshow2(anode3 w)/查詢記錄（以號碼為關(guān)鍵字）void hashinputname2(anode3 w/添加記錄（以用戶名為關(guān)鍵字）void hashshow2name2(anode3 w)/查詢記錄（以用戶名為關(guān)鍵字） void asl2(anode3 w)/計算 aslint scan()/菜單顯示函數(shù)int scan2()/菜單顯示函數(shù)三、詳細設計1、數(shù)據(jù)結(jié)構(gòu)設計鏈地址法：typedef s

6、truct node0int number;char addresssize;char namesize;struct node *next;newnode,*anode;電話號碼地址名字指向下一個結(jié) 點13開放定址法：typedef struct node2int number2;char address2size;char name2size; int v;/ 沖突次數(shù)newnode2,*anode2;typedef struct node3電話號碼地址名字記錄使用開放定址法時的沖突次數(shù)指向（newnod 型數(shù)組）儲 存錄入信息的數(shù)組anode2 q;/信息錄入數(shù)組判斷存儲空間是否已滿 記

7、錄表長yint i;/判斷存儲空間int j;/表長newnode3,*anode3;2、 算法分析與實現(xiàn)開放定址法添加記錄（以用戶名為關(guān)鍵字）使用開放定址法，以用戶名為關(guān)鍵字，添加記錄當輸入的電話號碼不為-1 時， 輸入姓名（英文），把姓名的第一個英文字母（char 型）強制轉(zhuǎn)換為整型 e, 再使用開放定址法獲取哈希地址，增量取用線性探測再散列法。開始輸入電話號碼 dyd= -1?n輸入姓名（char a100）e=(int)a0%表長該位置是否為空?yy y n哈希表是否已滿？n ynk=1e=（ (int)a0 +k）%表長輸入地址輸出內(nèi)存已滿在該位置插入數(shù)據(jù)結(jié)束四、運行結(jié)果和調(diào)試分析n

8、k=k+1該 位 置 是否為空?y輸入地址在該位置插入數(shù)據(jù)測試數(shù)據(jù)： 姓名fuyuandong住址云南河北山西電話號碼191423鏈地址法：用戶名為關(guān)鍵字建立散列表：asl=1以號碼為關(guān)鍵字建立散列表：asl=1開放定址法：用戶名為關(guān)鍵字建立散列表：asl=1以號碼為關(guān)鍵字建立散列表：asl=1運行結(jié)果圖。1.選用建表方法，初始化散列表。鏈地址法2. 添加記錄（以用戶名為關(guān)鍵字）鏈地址法3. 查詢記錄（以用戶名為關(guān)鍵字）鏈地址法4. 計算 asl鏈地址法5. 添加記錄（以號碼為關(guān)鍵字）鏈地址法6. 查詢記錄（以號碼為關(guān)鍵字）鏈地址法7.切換開放定址法8. 初始化散列表，添加記錄（以用戶名為關(guān)鍵

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

10、fine 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 v;/沖突次數(shù)newnode2,*anode2;typedef struct node3anode2 q;/信息錄入數(shù)組 int i;/判斷存儲空間int j;/表長newnode3,*anode3;void hashlis

11、tinit(newnode *p)/初始化散列表鏈地址法int i;for(i=0;inumber=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;printf(請輸入電話號碼，輸入-1 結(jié)束n);scanf(%d,&v);void hashshow2name(newnode *p)/查詢記錄（以用戶名為關(guān)鍵 字）鏈地址法char asize;anode t;int i;printf(請輸入要查詢用戶名n);scanf(%s

12、,a);i=(int)a0;i=i%n;t=pi;while(t&strcmp(t-name,a)!=0)t=t-next;if(t=null)printf(您所查詢的用戶不存在n);elseprintf(-n);printf(姓名:%sn,t-name);printf(電話:%dn,t-number);printf(地址:%sn,t-address);printf(-n);void hashinput(newnode *p)/添加記錄（以號碼為關(guān)鍵字）鏈地 址法int t,v;printf(請輸入數(shù)據(jù)n);printf(請輸入電話號碼，輸入-1 結(jié)束n);scanf(%d,&v);while

13、(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 結(jié)束n);scanf(%d,&v);void hashshow(newnode *p)/查詢記錄（以號碼為關(guān)鍵字）鏈地 址法int d,h;anode t;printf(請輸入所要查詢的電話號碼n);scanf(%d,&d);h=d%n;t=ph

14、;while(t&t-number!=d)t=t-next;if(t=null)printf( 您所要查詢的號碼不存在n);elseprintf(-n); printf(姓名:%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;lsize+1;l+)al=0;for(l=0;lnext;for(l=1;lq=e;w-i=n;w-j=n;for(int

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

16、);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&kj)t=(d+k)%w-j;k=k+1;w-qt.v+;w-qt.number2=d;printf(姓名：);scanf(%s,2);printf(地址：);scanf(%s,w-qt.address2);w-i=w-i-1;printf(電話號碼(輸入-1 結(jié)束)：); scanf(%

17、d,&d);t=d%w-j;void hashshow2(anode3 w)/查詢記錄（以號碼為關(guān)鍵字）開放定 址法int d,k,t;k=1;printf(請輸入要查詢的電話號碼：);scanf(%d,&d);t=d%w-j;if(w-qt.number2=d)printf(-n);printf(姓名:%sn,2);printf(電話:%dn,w-qt.number2);printf(地址:%sn,w-qt.address2);printf(-n);elset=(d+k)%w-j;k=k+1;while(w-qt.number2!=d&kj)t=(d+k)%w-j;k=k+

18、1;if(w-qt.number2=d)printf(-n);printf(姓名:%sn,2);printf(電話:%dn,w-qt.number2);printf(地址:%sn,w-qt.address2);printf(-n);elseprintf(您所要查詢的號碼不存在n);void hashinputname2(anode3 w)/添加記錄（以用戶名為關(guān)鍵字） 開放定址法char asize;int e,k,d;k=1;printf(請輸入要錄入的信息n);printf(電話號碼(輸入-1 結(jié)束)：);scanf(%d,&d);while(d!=-1)printf(姓

19、名（英文）：);scanf(%s,a);e=(int)a0;e=e%w-j;if(strcmp(2,無)=0&w-i!=0)strcpy(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(2,無)!=0) e=(e+k)%w-j;k=k+1;w-qe.v=2;while(strcmp(2,無)!=0&kj)e=(e+k)%w-j;k=k

20、+1;w-qe.v+;strcpy(2,a);w-qe.number2=d;printf( 地址：);scanf(%s,w-qe.address2);w-i=w-i-1;printf(電話號碼(輸入-1 結(jié)束)：);scanf(%d,&d);void hashshow2name2(anode3 w)/ 查詢記錄（以用戶名為關(guān)鍵 字）開放定址法char asize;int e,k;k=1;printf(請輸入要查詢的用戶名（英文）:);scanf(%s,a);e=(int)a0;e=e%w-j;if(strcmp(2,a)=0)printf(-n); prin

21、tf(姓名:%sn,2);printf(電話:%dn,w-qe.number2);printf(地址:%sn,w-qe.address2);printf(-n);elsee=(e+k)%w-j;k=k+1;while(strcmp(2,a)!=0&kj)e=(e+k)%w-j;k=k+1;if(k=w-j)printf(您所查詢的用戶不存在n);elseprintf(-n); printf(姓名:%sn,2);printf(電話:%dn,w-qe.number2);printf(地址:%sn,w-qe.address2);printf(-n

22、);void asl2(anode3 w)/計算 asl 開放定址法int asl,c,z;asl=0;z=0;for(c=0;cj;c+)asl=asl+w-qc.v;for(c=0;cj;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(親，請您輸入要選用的方法：); 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.添加記錄（以號碼為關(guān)鍵字）n);printf(5.查詢記錄（以號碼為關(guān)鍵字）n); printf(6.計算 asln);printf(7.選用另一個方