數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)校園導(dǎo)游系統(tǒng)

1、1. 設(shè)計(jì)目的 設(shè)計(jì)一個(gè)學(xué)校的導(dǎo)游系統(tǒng)，方便游客游覽我們學(xué)校。二. 設(shè)計(jì)內(nèi)容為來訪的客人提供各種信息查詢服務(wù)。主要包括：查看學(xué)校的全景圖各個(gè)景點(diǎn)的簡介學(xué)校主要景點(diǎn)的分布查看某一景點(diǎn)到其它所有景點(diǎn)的最短路徑查詢?nèi)我鈨蓚€(gè)景點(diǎn)之間的最短路徑。三概要設(shè)計(jì)1功能模塊圖；maininigraphbrowsershortestpath_dijserchmapprimprintmenucmd2功能模塊詳細(xì)介紹；(1)main: 主函數(shù)(2) browser：(3) inigraph：初始化學(xué)校地圖，給出景點(diǎn)的詳細(xì)信息，以及景點(diǎn)之間的距離。(4) shortestpath_dij：迪杰斯特拉算法，用于求兩個(gè)景點(diǎn)

2、之間的最短路徑。(5) serch：供游客查詢單個(gè)景點(diǎn)的詳細(xì)信息(6) prim：普利姆算法，用于得出最佳布網(wǎng)方案。(7) map：無參函數(shù)，打印學(xué)校的全景圖。(8) menu：游客的輸入界面。(9) print：打印相應(yīng)的游覽路線。(10) cmd：輸入相應(yīng)的選擇進(jìn)行不同的游覽方式。四詳細(xì)設(shè)計(jì)search1功能函數(shù)的調(diào)用關(guān)系圖primshortestpath_dijcmdmainprintbrowserinigraphmenumap2各功能函數(shù)的數(shù)據(jù)流程圖無參函數(shù)，打印平面圖map圖存在且非空打印路線，文件存儲(chǔ)輸入起止點(diǎn)標(biāo)號(hào)，非法則提示再次輸入prim輸入起點(diǎn)編號(hào)，非法提示，再次輸入圖存在且

3、非空dij依次輸入，到各個(gè)景點(diǎn)最短距離，文件存儲(chǔ)無參函數(shù)，菜單欄menu無向網(wǎng)初始化，得到景點(diǎn)距離，以及信息initgraph打印景點(diǎn)信息圖存在且非空browserfor循環(huán)控制結(jié)點(diǎn)數(shù)目，并打印。圖存在且非空print3重點(diǎn)設(shè)計(jì)及編碼創(chuàng)建結(jié)構(gòu)體，表示景點(diǎn)，成員為編號(hào)，名稱，簡介typedef struct /圖中頂點(diǎn)表示主要景點(diǎn)，存放景點(diǎn)的編號(hào)、名稱、簡介等信息，char name30;int num;char introduction100;/簡介infotype;prim算法：void prim(mgraph *g)file *fp;fp=fopen(d:sight.txt,at+);if

4、(fp=null)printf(fail to open!n);elseint v,u,i,w,k,j,flag=1,p101010,d1010; for(v=0;vvexnum;v+) for(w=0;wvexnum;w+) dvw=g-arcsvw.adj; for(u=0;uvexnum;u+) pvwu=0; if(dvwinfinity) pvwv=1;pvww=1; for(u=0;uvexnum;u+) for(v=0;vvexnum;v+) for(w=0;wvexnum;w+) if(dvu+duwdvw) dvw=dvu+duw; for(i=0;ivexnum;i+) p

5、vwi=pvui|puwi; while(flag) printf(請(qǐng)輸入出發(fā)點(diǎn)和目的地的編號(hào):); scanf(%d%d,&k,&j); if(kg-vexnum|jg-vexnum) printf(景點(diǎn)編號(hào)不存在!請(qǐng)重新輸入出發(fā)點(diǎn)和目的地的編號(hào):); scanf(%d%d,&k,&j); if(k=0&kvexnum&j=0&jvexnum) flag=0; fprintf(fp,%s,g-); for(u=0;uvexnum;u+) if(pkju&k!=u&j!=u) fprintf(fp,-%s,g-); fprintf(fp,-%s,g-ve

6、); fprintf(fp, 總路線長%dmn,dkj);fclose(fp);迪杰斯特拉算法：void shortestpath_dij(mgraph * g)file *fp;fp=fopen(d:approach.txt,at+);if(fp=null)printf(fail to open!n);elseint v,w,i,min,t=0,x,flag=1,v0; int final20, d20, p2020;while(flag)printf(請(qǐng)輸入一個(gè)起始景點(diǎn)編號(hào):);scanf(%d,&v0);if(v0g-vexnum)printf(景點(diǎn)編號(hào)不存在!請(qǐng)重新輸入

7、景點(diǎn)編號(hào):);scanf(%d,&v0);if(v0=0&v0vexnum)flag=0;/endwhilefor(v=0;vvexnum;v+)finalv=0;dv=g-arcsv0v.adj;for(w=0;wvexnum;w+)pvw=0;if(dvinfinity)pvv0=1;pvv=1;dv0=0;finalv0=1;for(i=1;ivexnum;i+)min=infinity;for(w=0;wvexnum;w+)if(!finalw)if(dwmin)v=w;min=dw;finalv=1;for(w=0;wvexnum;w+)if(!finalw&(min+g-arcsv

8、w.adjarcsvw.adj;for(x=0;xvexnum;x+) pwx=pvx;pww=1;for(v=0;vvexnum;v+)if(v0!=v)fprintf(fp,%s,g-);for(w=0;wvexnum;w+)if(pvw&w!=v0) fprintf(fp,-%s,g-); t+; if(tg-vexnum-1&v0!=v) fprintf(fp, 總路線長%dmnn,dv); /endfor/endif/shortestpath_dij end五測(cè)試數(shù)據(jù)及運(yùn)行結(jié)果1 正常測(cè)試數(shù)據(jù)和運(yùn)行結(jié)果2異常測(cè)試數(shù)據(jù)及運(yùn)行結(jié)果六調(diào)試情況，設(shè)計(jì)

9、技巧及體會(huì)1改進(jìn)方案對(duì)于我的設(shè)計(jì)，合理之處是對(duì)每一次查詢都以文件的形式進(jìn)行了存儲(chǔ)，其次，校園的平面圖比較好的展現(xiàn)了我們學(xué)校的風(fēng)貌。不足之處是使用prim算法的時(shí)候，若終點(diǎn)輸入不合法，程序會(huì)陷入，死循環(huán)。這是致命的錯(cuò)誤，我的改進(jìn)方法是若輸入字符不合法，則跳出循環(huán)，再次輸入，直到合法為止。利用迪杰斯特拉算法在計(jì)算到剩下的頂點(diǎn)的最短距離時(shí)第一個(gè)for循環(huán)時(shí)時(shí)間復(fù)雜度是o（n），每進(jìn)行一次第二個(gè)for循環(huán)的時(shí)間復(fù)雜度都是o（n），第三個(gè)for循環(huán)也就是存儲(chǔ)途經(jīng)頂點(diǎn)時(shí)用的循環(huán)而不是書中算法所用的只是個(gè)地址的賦值，所以時(shí)間復(fù)雜度也是o（n），這樣總的時(shí)間復(fù)雜度就是o(n3)。改進(jìn)設(shè)想主要就是給用戶一個(gè)瀏覽

10、路線的推薦本來在程序設(shè)計(jì)初期是計(jì)劃要實(shí)現(xiàn)這個(gè)功能的，但是由于時(shí)間和能力問題沒有去實(shí)現(xiàn)，因?yàn)樗婕暗綕h密爾頓路的實(shí)現(xiàn)，目前感覺還比較復(fù)雜所以暫時(shí)放棄了，日后如果有機(jī)會(huì)一定將這個(gè)功能完善。2體會(huì)調(diào)試過程中難免會(huì)遇見這樣或者那樣的問題，一個(gè)很低級(jí)的錯(cuò)誤就是在字符串的賦值上居然還會(huì)出錯(cuò)，本來是不可以像int型數(shù)據(jù)那樣直接用等于號(hào)賦值的，可是剛開始由于失誤卻犯了這樣低級(jí)的錯(cuò)誤結(jié)果導(dǎo)致出現(xiàn)102個(gè)錯(cuò)誤，當(dāng)時(shí)確實(shí)有點(diǎn)慌了，等冷靜下來一想才把問題想明白，字符串的賦值必須用strcpy函數(shù)。看來基本功還是相當(dāng)?shù)闹匾?。此外，迪杰斯特拉算法其?shí)放在這里多少有些不合適，因?yàn)椴还茉谇笕我鈨蓚€(gè)景點(diǎn)之間的最短路徑還是求某

11、一景點(diǎn)到其它景點(diǎn)的最短路徑時(shí)都要完全的執(zhí)行一遍算法時(shí)間復(fù)雜度是很高的，當(dāng)時(shí)在實(shí)現(xiàn)時(shí)也確實(shí)考慮到了這個(gè)問題只是后來感覺要是實(shí)現(xiàn)時(shí)間復(fù)雜度的降低不是很簡單也就暫時(shí)放棄了，也就選擇了將這個(gè)算法直接搬了過來，這里是一點(diǎn)敗筆，尚需要改進(jìn)。七參考文獻(xiàn)數(shù)據(jù)結(jié)構(gòu) 嚴(yán)蔚敏 吳為民c語言程序設(shè)計(jì)（第三版） 譚浩強(qiáng) 八附錄：源代碼（電子版）#define infinity 10000 /*無窮大*/#define max_vertex_num 40#define max 40#include#include#include#includetypedef struct arcellint adj; /路徑長度arce

12、ll,adjmatrixmax_vertex_nummax_vertex_num;typedef struct /圖中頂點(diǎn)表示主要景點(diǎn)，存放景點(diǎn)的編號(hào)、名稱、簡介等信息，char name30;int num;char introduction100;/簡介infotype;typedef structinfotype vexsmax_vertex_num;adjmatrix arcs;int vexnum,arcnum;mgraph;mgraph b;void cmd(void);mgraph initgraph(void);void menu(void);void browser(mgra

13、ph *g);void shortestpath_dij(mgraph * g);void prim(mgraph *g);void search(mgraph *g);int locatevex(mgraph *g,char* v);mgraph * creatudn(mgraph *g);void print(mgraph *g);void map();/*/void main(void) system(mode con: cols=100 lines=30); cmd();/*/void cmd(void) int i; b=initgraph(); menu(); scanf(%d,&

14、i); while(i!=6) switch(i) case 1:browser(&b);menu();break; case 2:map();menu();break; case 3:shortestpath_dij(&b);menu();break; case 4:floyd(&b);menu();break; case 5:search(&b);menu();break; case 6:exit(1);break; default:break; scanf(%d,&i); mgraph initgraph(void) mgraph g; int i,j; g.vexnum=10; g.a

15、rcnum=14; for(i=0;ig.vexnum;i+) g.vexsi.num=i; strcpy(g.,旭日苑); strcpy(g.roduction,難吃,洗過的筷子上面都是菜葉子); strcpy(g.,校醫(yī)院); strcpy(g.roduction,校醫(yī)院，名副其實(shí)的校(shou)醫(yī)(yi)院(yuan); strcpy(g.,大學(xué)生活動(dòng)中心); strcpy(g.roduction,又名大活,舉辦一些沒什么卵用的晚會(huì)); strcpy(g.

16、,美食廣場(chǎng)); strcpy(g.roduction,吃貨的天堂,完爆旭日苑); strcpy(g.,圖書館); strcpy(g.roduction,warning!學(xué)霸出沒!); strcpy(g.,足球場(chǎng)); strcpy(g.roduction,國足的未來.23333333); strcpy(g.,水煮鴿子); strcpy(g.roduction,然而他并不能吃); strcpy(g.,東區(qū)教學(xué)樓); strcpy(g.vexs7.i

17、ntroduction,又名尼伯龍根,進(jìn)去就不要想出來); strcpy(g.,狗男女湖); strcpy(g.roduction,湖邊時(shí)?；厥幹鴨紊砉返陌Ш?; strcpy(g.,澡堂); strcpy(g.roduction,洗個(gè)澡,壓壓驚); for(i=0;ig.vexnum;i+) for(j=0;jg.vexnum;j+) g.arcsij.adj=infinity; g.arcs01.adj=100; g.arcs02.adj=200; g.arcs06.adj=400; g.arcs17.adj=30

18、0; g.arcs23.adj=120; g.arcs36.adj=220; g.arcs34.adj=100; g.arcs45.adj=300; g.arcs49.adj=250; g.arcs59.adj=350; g.arcs67.adj=60; g.arcs69.adj=200; g.arcs78.adj=50; g.arcs89.adj=20; for(i=0;ig.vexnum;i+) for(j=0;jg.vexnum;j+) g.arcsji.adj=g.arcsij.adj; return g;/initgraph endvoid menu() printf(n 西安郵(m

19、ei)電(dian)大學(xué)n); printf( n); printf( 1.校園景點(diǎn)介紹 n); printf( 2.校園平面圖 n); printf( 3.查看所有游覽路線(jiandan) n); printf( 4.選擇出發(fā)點(diǎn)和目的地(zuiduan) n); printf( 5.查看景點(diǎn)信息 n); printf( 6.退出系統(tǒng) n); printf( n); printf(option-:);void browser(mgraph *g) int v; printf(n); printf(編號(hào)景點(diǎn)名稱 簡介 n); for(v=0;vvexnum;v+) printf(%-4d%-1

20、6s%-56sn,g-vexsv.num,g-,g-roduction); printf(n);/ 迪杰斯特拉算法來計(jì)算出起點(diǎn)到各個(gè)頂點(diǎn)之間的最短路徑,v0為起點(diǎn)void shortestpath_dij(mgraph * g)file *fp;fp=fopen(d:approach.txt,at+);if(fp=null)printf(fail to open!n);elseint v,w,i,min,t=0,x,flag=1,v0; int final20, d20, p2020;while(flag)printf(請(qǐng)輸入一個(gè)起始景點(diǎn)編號(hào):);scan

21、f(%d,&v0);if(v0g-vexnum)printf(景點(diǎn)編號(hào)不存在!請(qǐng)重新輸入景點(diǎn)編號(hào):);scanf(%d,&v0);if(v0=0&v0vexnum)flag=0;/endwhilefor(v=0;vvexnum;v+)finalv=0;dv=g-arcsv0v.adj;for(w=0;wvexnum;w+)pvw=0;if(dvinfinity)pvv0=1;pvv=1;dv0=0;finalv0=1;for(i=1;ivexnum;i+)min=infinity;for(w=0;wvexnum;w+)if(!finalw)if(dwmin)v=w;min=dw;finalv=

22、1;for(w=0;wvexnum;w+)if(!finalw&(min+g-arcsvw.adjarcsvw.adj;for(x=0;xvexnum;x+) pwx=pvx;pww=1;for(v=0;vvexnum;v+)if(v0!=v)fprintf(fp,%s,g-);for(w=0;wvexnum;w+)if(pvw&w!=v0) fprintf(fp,-%s,g-); t+; if(tg-vexnum-1&v0!=v) fprintf(fp, 總路線長%dmnn,dv); /endfor/endifprintf(請(qǐng)稍候.n);printf

23、(文件已經(jīng)成功地保存至d:/approach.txt!n);/shortestpath_dij endvoid search(mgraph *g) int k,flag=1; while(flag) printf(請(qǐng)輸入要查詢的景點(diǎn)編號(hào):); scanf(%d,&k); if(kg-vexnum) printf(景點(diǎn)編號(hào)不存在!請(qǐng)重新輸入景點(diǎn)編號(hào):); scanf(%d,&k); if(k=0&kvexnum) flag=0; printf(n); printf(編號(hào)景點(diǎn)名稱 簡介 n); printf(%-4d%-16s%-56sn,g-vexsk.num,g-,g-ve

24、roduction); printf(n);/search endint locatevex(mgraph *g,char* v) int c=-1,i; for(i=0;ivexnum;i+) if(strcmp(v,g-)=0) c=i;break; return c;void print(mgraph *g)int v,w,t=0;for(v=0;vvexnum;v+) for(w=0;wvexnum;w+) if(g-arcsvw.adj=infinity) printf( ); else printf(%-7d,g-arcsvw.adj); t+;

25、if(t%g-vexnum=0) printf(n); void prim(mgraph *g)file *fp;fp=fopen(d:sight.txt,at+);if(fp=null)printf(fail to open!n);elseint v,u,i,w,k,j,flag=1,p101010,d1010; for(v=0;vvexnum;v+) for(w=0;wvexnum;w+) dvw=g-arcsvw.adj; for(u=0;uvexnum;u+) pvwu=0; if(dvwinfinity) pvwv=1;pvww=1; for(u=0;uvexnum;u+) for(v=0;vvexnum;v+) for(w=0;wvexnum;w+) if(dvu+duwdvw) dvw=dvu+duw; for(i=0;ivexnum;i+) pvwi=pvui|puwi; while(flag) printf(請(qǐng)輸入出發(fā)點(diǎn)和目的地的編號(hào):); sca