數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告校園導(dǎo)航

1、-. z一、課程設(shè)計(jì)目的本課程設(shè)計(jì)的目標(biāo)就是要到達(dá)理論與實(shí)際應(yīng)用相結(jié)合，提高學(xué)生組織數(shù)據(jù)及編寫(xiě)大型程序的能力，并培養(yǎng)根本的、良好的程序設(shè)計(jì)技能以及合作能力。設(shè)計(jì)中要求綜合運(yùn)用所學(xué)知識(shí)，上機(jī)解決一些與實(shí)際應(yīng)用結(jié)合嚴(yán)密的、規(guī)模較大的問(wèn)題，通過(guò)分析、設(shè)計(jì)、編碼、調(diào)試等各環(huán)節(jié)的訓(xùn)練，使學(xué)生深刻理解、結(jié)實(shí)掌握數(shù)據(jù)構(gòu)造和算法設(shè)計(jì)技術(shù)，掌握分析、解決實(shí)際問(wèn)題的能力。通過(guò)這次設(shè)計(jì)，要求在數(shù)據(jù)構(gòu)造的邏輯特性和物理表示、數(shù)據(jù)構(gòu)造的選擇和應(yīng)用、算法的設(shè)計(jì)及其實(shí)現(xiàn)等方面，加深對(duì)課程根本容的理解。同時(shí)，在程序設(shè)計(jì)方法以及上機(jī)操作等根本技能和科學(xué)作風(fēng)方面受到比擬系統(tǒng)和嚴(yán)格的訓(xùn)練。課程設(shè)計(jì)容1)問(wèn)題描述用無(wú)向網(wǎng)表示你所在學(xué)

2、校的校園景點(diǎn)平面圖，圖中頂點(diǎn)表示主要景點(diǎn)，存放景點(diǎn)的編號(hào)、名稱(chēng)、簡(jiǎn)介等信息，圖中的邊表示景點(diǎn)間的道路，存放路徑長(zhǎng)度等信息。要求能夠答復(fù)有關(guān)景點(diǎn)介紹、游覽路徑等問(wèn)題。2)根本要求1查詢(xún)各景點(diǎn)的相關(guān)信息；2查詢(xún)圖中任意兩個(gè)景點(diǎn)間的最短路徑。3查詢(xún)圖中任意兩個(gè)景點(diǎn)間的所有路徑。增加、刪除、更新有關(guān)景點(diǎn)和道路的信息三、課程設(shè)計(jì)過(guò)程1需求分析1設(shè)計(jì)學(xué)校的校園平面圖，選取出假設(shè)干的具有代表性的景點(diǎn)構(gòu)成一個(gè)抽象的無(wú)向帶權(quán)圖，頂點(diǎn)為景點(diǎn)，邊的權(quán)值代表了景點(diǎn)間路徑的長(zhǎng)度。2將景點(diǎn)的序號(hào)，名稱(chēng)，介紹存放起來(lái)準(zhǔn)備查詢(xún)。3提供任意景點(diǎn)的信息；4提供任意經(jīng)典的路徑查詢(xún)及其最優(yōu)路線的查詢(xún)5平面圖景點(diǎn)的增加及刪除，以及邊和

3、權(quán)值長(zhǎng)度的改變2概要設(shè)計(jì)1：第一點(diǎn)是主界面的設(shè)計(jì)，首先，為了該系統(tǒng)各個(gè)功能的管理，設(shè)計(jì)出含有多個(gè)菜單項(xiàng)的主菜單界面，可以更方便的使用該系統(tǒng)。 2：第二點(diǎn)是存儲(chǔ)構(gòu)造的設(shè)計(jì)，采取了圖構(gòu)造類(lèi)型mgraph存儲(chǔ)校園圖的信息，景點(diǎn)信息用構(gòu)造數(shù)組ve*s存儲(chǔ)，而且利用全局變量：visited數(shù)組用于存儲(chǔ)頂點(diǎn)是否被標(biāo)志；d數(shù)組用于存放權(quán)值和查找路徑頂點(diǎn)的編號(hào)；campus是一個(gè)圖構(gòu)造的全局變量。 3：第三點(diǎn)是設(shè)計(jì)各個(gè)功能的實(shí)現(xiàn)，學(xué)校景點(diǎn)的介紹通過(guò)函數(shù)browsepus()來(lái)實(shí)現(xiàn)；查詢(xún)景點(diǎn)間的最段路徑通過(guò)Floyd(弗洛伊德)算法實(shí)現(xiàn)；查詢(xún)景點(diǎn)間的所有路徑通過(guò)allpath函數(shù)和path函數(shù)來(lái)實(shí)現(xiàn)；更改圖的信

4、息可以由主函數(shù)changegraph以及其他函數(shù)可以實(shí)現(xiàn)。詳細(xì)設(shè)計(jì)1主要的操作界面的顯示以及無(wú)向網(wǎng)操作void initgraph(graph *ga) int i,j;ga-n=9;ga-e=11; for( i=0;in;i+) ga-ve*si.num=i; strcpy(ga-ve*,西門(mén));strcpy(ga-ve*roduce,學(xué)校的正大門(mén)，設(shè)有公交站);strcpy(ga-ve*,風(fēng)雨籃球場(chǎng));strcpy(ga-ve*roduce,);strcpy(ga-ve*,田徑場(chǎng));strcpy(ga-ve*r

5、oduce,舉辦運(yùn)動(dòng)會(huì)，平時(shí)體育跑步鍛煉等);strcpy(ga-ve*,京元食堂);strcpy(ga-ve*roduce,新食堂);strcpy(ga-ve*,蒼霞湖畔);strcpy(ga-ve*roduce,戲稱(chēng)分手湖，風(fēng)光宜人); strcpy(ga-ve*,思源樓);strcpy(ga-ve*roduce,學(xué)校王牌土木的教學(xué)區(qū));strcpy(ga-ve*,圖書(shū)館);strcpy(ga-ve*roduce,是大學(xué)城最高的標(biāo)志性建筑);strcpy(ga-ve*,北教

6、區(qū));strcpy(ga-ve*roduce,北校區(qū)集中的教學(xué)樓);strcpy(ga-ve*,禾堂餐廳);strcpy(ga-ve*roduce,舊食堂); for(i=0;in;i+)for(j=0;jn;j+)ga-edgesij=1000;ga-edges01=1;ga-edges12=2;ga-edges13=5;ga-edges24=4;ga-edges34=9;ga-edges45=1;ga-edges48=1;ga-edges56=5;ga-edges57=7;ga-edges78=1;ga-edges67=9; for(i=0;in;i+

7、)for(j=0;jn;j+)ga-edgesji=ga-edgesij;2確定頂點(diǎn)是否存在已經(jīng)頂點(diǎn)是否已經(jīng)被過(guò)來(lái)確定路徑void Create_graph(graph *ga)int i,j,k,w;printf(請(qǐng)輸入頂點(diǎn)數(shù)和邊數(shù):n);scanf(%d %d,&(ga-n),&(ga-e);printf(請(qǐng)輸入景點(diǎn)編號(hào)，景點(diǎn)名字，景點(diǎn)介紹，建立信息表:n);for(i=0;in;i+)scanf(%d,&(ga-ve*si.num); gets(ga-ve*);gets(ga-ve*roduce);for(i=0;in;i+)for(j=0;jn;j+)ga-e

8、dgesij=1000;for(k=0;ke;k+)printf(請(qǐng)輸入%d條邊的景點(diǎn)序號(hào)i，j和長(zhǎng)度：,k+1);scanf(%d %d %d,&i,&j,&w); ga-edgesij=w;ga-edgesji=w;void print(graph ga) int i,j; for(i=0;iga.n;i+) for(j=0;jga.n;j+) printf(%d,ga.edgesij); if(j+1=ga.n) printf(n); void visit(graph ga) int a;printf(請(qǐng)輸入景點(diǎn)編號(hào)：);scanf(%d,&a); int i;for( i=0;iga.

9、n;i+) if(a=ga.ve*si.num) printf(景點(diǎn)編號(hào)為%d n,ga.ve*si.num); printf(景點(diǎn)名稱(chēng)為); puts(ga.ve*); printf(景點(diǎn)介紹為); puts(ga.ve*roduce); break; if(i=ga.n)printf(無(wú)此點(diǎn)n);3得出景點(diǎn)間的最短路徑void shortestpath_djst(graph ga)void shortestpath_floyd(graph ga) int i,j,k,v,u,w,d3535,p353535;for(v=0;vga.n;v+)for(w=0;wga.

10、n;w+)dvw=ga.edgesvw;for(u=0;uga.n;u+)pvwu=0;if(dvw1000)pvwv=1;pvww=1; for(u=0;uga.n;u+)for(v=0;vga.n;v+)for(w=0;wga.n;w+)if(dvu+duwdvw)dvw=dvu+duw;for(i=0;iga.n;i+)pvwi=pvui|puwi;printf(n請(qǐng)輸入出發(fā)點(diǎn)和目的地編號(hào)：);scanf(%d %d,&k,&j);printf(nn);while(kga.n|jga.n) printf(n輸入的編號(hào)不存在); printf(n請(qǐng)重新輸入編號(hào)：nn); scanf(%d

11、%d,&k,&j); printf(nn);printf(%s,ga.ve*);for(u=0;u%s,ga.ve*);printf(-%s,ga.ve*);printf(nnn總長(zhǎng)度為%d千米nnn,dkj);4得到景點(diǎn)之間的所有路徑void path(graph c,int m,int n,int k) int s,*=0; int t; t=k+1; if(dk=n & k8) for(s=0;s,c.ve*); printf(%snn,c.ve*); else s=0; while(sc.n) if(c.edge

12、sdks1000)&(visiteds=0) visiteds=1; dk+1=s; path(c,m,n,t); visiteds=0; s+; void allpath(graph c) int k,i,j,m,n; printf(nn請(qǐng)輸入您要查詢(xún)的兩個(gè)景點(diǎn)的編號(hào):nn); scanf(%d %d,&i,&j); printf(nn); m=locateve*(c,i); n=locateve*(c,j); d0=m; for(k=0;kc.n;k+) visitedk=0; visitedm=1; path(c,m,n,0);5刪除邊int delarc(graph &ga) int

13、m,n,v0,v1;if(ga.e=0)printf(圖中已經(jīng)無(wú)頂邊，無(wú)法刪除);return 1;printf(n請(qǐng)輸入要?jiǎng)h除的邊的起點(diǎn)和終點(diǎn)的編號(hào)：);scanf(%d %d,&v0,&v1); m=locateve*(ga,v0);if(m0)printf(此頂點(diǎn)%d已刪除,v0);return 1; n=locateve*(ga,v1); if(n0)printf(此頂點(diǎn)%d已刪除,v1);return 1; ga.edgesmn=1000; ga.edgesnm=1000; ga.e-; return 1;int enarc(graph &ga)int m,n,distance;pr

14、intf(請(qǐng)輸入邊的起點(diǎn)和終點(diǎn)編號(hào)，權(quán)值：);scanf(%d %d %d,&m,&n,&distance);while(mga.n|nga.n)printf(輸入錯(cuò)誤，請(qǐng)重新輸入：);scanf(%d %d,&m,&n);if(locateve*(ga,m)0)printf(此節(jié)點(diǎn)%d已經(jīng)刪除,m);return 1;if(locateve*(ga,n)0)printf(此節(jié)點(diǎn)%d已經(jīng)刪除,n);return 1;ga.edgesmn=distance;ga.edgesnm=ga.edgesmn;return 1;4調(diào)試分析容包括：a調(diào)試過(guò)程中遇到的問(wèn)題是如何解決的以及對(duì)設(shè)計(jì)與實(shí)現(xiàn)的回憶討論

15、和分析；b算法的時(shí)空分析(包括根本操作和其他算法的時(shí)間復(fù)雜度和空間復(fù)雜度的分析)和改良設(shè)想；c經(jīng)歷和體會(huì)等。用戶(hù)使用說(shuō)明通過(guò)主菜單提示，選擇出你所想要知道的信息，然后通過(guò)輸入節(jié)點(diǎn)來(lái)代替景點(diǎn)，從而得到景點(diǎn)間的所有路徑，最短路徑等其他信息。測(cè)試結(jié)果1操作的主界面學(xué)校景點(diǎn)的介紹學(xué)校景點(diǎn)從西門(mén)的禾堂餐廳的所有路徑所有路徑4學(xué)校景點(diǎn)從西門(mén)的禾堂餐廳的所有路徑最短路徑圖的更改的界面6邊的刪除界面展示附錄#define MA* 100 /數(shù)據(jù)類(lèi)型的定義#include#includeusing namespace std;int visited35;int d35;struct views int num;

16、 char name10; char introduce100;typedef views datatype;typedef struct datatype ve*sMA*; int edgesMA*MA*; int n,e;graph;void initgraph(graph *ga)/主要的操作界面的顯示以及無(wú)向網(wǎng)操作int i,j;ga-n=9;ga-e=11; for( i=0;in;i+) ga-ve*si.num=i; strcpy(ga-ve*,西門(mén));strcpy(ga-ve*roduce,學(xué)校的正大門(mén)，設(shè)有公交站);strcpy(ga-ve*s1.n

17、ame,風(fēng)雨籃球場(chǎng));strcpy(ga-ve*roduce,);strcpy(ga-ve*,田徑場(chǎng));strcpy(ga-ve*roduce,舉辦運(yùn)動(dòng)會(huì)，平時(shí)體育跑步鍛煉等);strcpy(ga-ve*,京元食堂);strcpy(ga-ve*roduce,新食堂);strcpy(ga-ve*,蒼霞湖畔);strcpy(ga-ve*roduce,戲稱(chēng)分手湖，風(fēng)光宜人); strcpy(ga-ve*,思源樓);strcpy(ga-ve*roduce,學(xué)校王牌土木的教學(xué)區(qū));strc

18、py(ga-ve*,圖書(shū)館);strcpy(ga-ve*roduce,是大學(xué)城最高的標(biāo)志性建筑);strcpy(ga-ve*,北教區(qū));strcpy(ga-ve*roduce,北校區(qū)集中的教學(xué)樓);strcpy(ga-ve*,禾堂餐廳);strcpy(ga-ve*roduce,舊食堂); for(i=0;in;i+)for(j=0;jn;j+)ga-edgesij=1000;ga-edges01=1;ga-edges12=2;ga-edges13=5;ga-edges24=4;ga-edges34=9;ga-edge

19、s45=1;ga-edges48=1;ga-edges56=5;ga-edges57=7;ga-edges78=1;ga-edges67=9; for(i=0;in;i+)for(j=0;jn;j+)ga-edgesji=ga-edgesij;int locateve*(graph ga,int v) / /查找景點(diǎn)在圖中的序號(hào) int i; for(i=0;in),&(ga-e);printf(請(qǐng)輸入景點(diǎn)編號(hào)，景點(diǎn)名字，景點(diǎn)介紹，建立信息表:n);for(i=0;in;i+)scanf(%d,&(ga-ve*si.num); gets(ga-ve*);gets(ga-ve*si

20、.introduce);for(i=0;in;i+)for(j=0;jn;j+)ga-edgesij=1000;for(k=0;ke;k+)printf(請(qǐng)輸入%d條邊的景點(diǎn)序號(hào)i，j和長(zhǎng)度：,k+1);scanf(%d %d %d,&i,&j,&w); ga-edgesij=w;ga-edgesji=w;void print(graph ga) int i,j; for(i=0;iga.n;i+) for(j=0;jga.n;j+) printf(%d,ga.edgesij); if(j+1=ga.n) printf(n); void visit(graph ga) int a;printf

21、(請(qǐng)輸入景點(diǎn)編號(hào)：);scanf(%d,&a); int i;for( i=0;iga.n;i+) if(a=ga.ve*si.num) printf(景點(diǎn)編號(hào)為%d n,ga.ve*si.num); printf(景點(diǎn)名稱(chēng)為); puts(ga.ve*); printf(景點(diǎn)介紹為); puts(ga.ve*roduce); break; if(i=ga.n)printf(無(wú)此點(diǎn)n);void shortestpath_djst(graph ga)void shortestpath_floyd(graph ga) int i,j,k,v,u,w,d3535,p353

22、535;for(v=0;vga.n;v+)for(w=0;wga.n;w+)dvw=ga.edgesvw;for(u=0;uga.n;u+)pvwu=0;if(dvw1000)pvwv=1;pvww=1; for(u=0;uga.n;u+)for(v=0;vga.n;v+)for(w=0;wga.n;w+)if(dvu+duwdvw)dvw=dvu+duw;for(i=0;iga.n;i+)pvwi=pvui|puwi;printf(n請(qǐng)輸入出發(fā)點(diǎn)和目的地編號(hào)：);scanf(%d %d,&k,&j);printf(nn);while(kga.n|jga.n) printf(n輸入的編號(hào)不存在

23、); printf(n請(qǐng)重新輸入編號(hào)：nn); scanf(%d %d,&k,&j); printf(nn);printf(%s,ga.ve*);for(u=0;u%s,ga.ve*);printf(-%s,ga.ve*);printf(nnn總長(zhǎng)度為%d千米nnn,dkj);void path(graph c,int m,int n,int k) int s,*=0; int t; t=k+1; if(dk=n & k8) for(s=0;s,c.ve*); printf(%snn,c.ve*); else s=0;

24、while(sc.n) if(c.edgesdks1000)&(visiteds=0) visiteds=1; dk+1=s; path(c,m,n,t); visiteds=0; s+; void allpath(graph c) int k,i,j,m,n; printf(nn請(qǐng)輸入您要查詢(xún)的兩個(gè)景點(diǎn)的編號(hào):nn); scanf(%d %d,&i,&j); printf(nn); m=locateve*(c,i); n=locateve*(c,j); d0=m; for(k=0;kc.n;k+) visitedk=0; visitedm=1; path(c,m,n,0);void newg

25、raph(graph &ga)int changenum;int i,m,n,t,distance,v0,v1;printf(n請(qǐng)輸入要修改景點(diǎn)的個(gè)數(shù)：n);scanf(%d,&changenum);while(changenumga.n)printf(n輸入錯(cuò)誤！請(qǐng)重新輸入);scanf(%d,&changenum);for(i=0;ichangenum;i+)printf(n請(qǐng)輸入景點(diǎn)的編號(hào)：);scanf(%d,&m);t=locateve*(ga,m);printf(n請(qǐng)輸入景點(diǎn)的名稱(chēng)：);scanf(%s,ga.ve*);printf(n請(qǐng)輸入景點(diǎn)簡(jiǎn)介：);scanf(

26、%s,ga.ve*roduce);printf(n請(qǐng)輸入您要更新的邊數(shù));scanf(%d,&changenum);while(changenumga.n)printf(輸入錯(cuò)誤，請(qǐng)重新輸入：);scanf(%d,&changenum);printf(n請(qǐng)輸入更新邊的信息： n);for(i=1;i=0&n=0)ga.edgesmn=distance;ga.edgesnm=ga.edgesmn;int delve*(graph &ga) /刪除頂點(diǎn)int i=0,j;int m,v;if(ga.n=0)printf(圖中已經(jīng)無(wú)頂點(diǎn));return 1;printf(n請(qǐng)輸入要?jiǎng)h除的

27、景點(diǎn)編號(hào)：);scanf(%d,&v);while(vga.n) printf(n輸入錯(cuò)誤，請(qǐng)重新輸入); scanf(%d,&v);m=locateve*(ga,v);if(m0)printf(此頂點(diǎn)%d已刪除,v);return 1;for(i=m;iga.n-1;i+)strcpy(ga.ve*,ga.ve*si+1.name);strcpy(ga.ve*roduce,ga.ve*si+1.introduce);for(i=m;iga.n-1;i+)for(j=0;jga.n;j+)ga.edgesij=ga.edgesi+1j;for(i=m;iga.n-1;

28、i+)for(j=0;jga.n;j+)ga.edgesji=ga.edgesji+1;ga.n-;return 1;int delarc(graph &ga) /刪除邊int m,n,v0,v1;if(ga.e=0)printf(圖中已經(jīng)無(wú)頂邊，無(wú)法刪除);return 1;printf(n請(qǐng)輸入要?jiǎng)h除的邊的起點(diǎn)和終點(diǎn)的編號(hào)：);scanf(%d %d,&v0,&v1); m=locateve*(ga,v0);if(m0)printf(此頂點(diǎn)%d已刪除,v0);return 1; n=locateve*(ga,v1); if(n0)printf(此頂點(diǎn)%d已刪除,v1);return 1;

29、ga.edgesmn=1000; ga.edgesnm=1000; ga.e-; return 1;int enarc(graph &ga)int m,n,distance;printf(請(qǐng)輸入邊的起點(diǎn)和終點(diǎn)編號(hào)，權(quán)值：);scanf(%d %d %d,&m,&n,&distance);while(mga.n|nga.n)printf(輸入錯(cuò)誤，請(qǐng)重新輸入：);scanf(%d %d,&m,&n);if(locateve*(ga,m)0)printf(此節(jié)點(diǎn)%d已經(jīng)刪除,m);return 1;if(locateve*(ga,n)0)printf(此節(jié)點(diǎn)%d已經(jīng)刪除,n);return 1;g

30、a.edgesmn=distance;ga.edgesnm=ga.edgesmn;return 1;int enve*(graph &ga) /增加節(jié)點(diǎn)int i;printf(請(qǐng)輸入增加節(jié)點(diǎn)的信息：);printf(n編號(hào)：);scanf(%d,&ga.ve*sga.n.num);printf(名稱(chēng)：);scanf(%s,ga.ve*);printf(簡(jiǎn)介：);scanf(%s,ga.ve*roduce);ga.n+;for(i=0;iga.n;i+)ga.edgesga.n-1i=1000;ga.edgesiga.n-1=1000; return 1;

31、int changegraph(graph &ga)int yourchoice;printf(n請(qǐng)選擇nn (1)刪除結(jié)點(diǎn) (2)刪除邊n);printf(n (3)增加結(jié)點(diǎn) (4)增加邊n);printf(n (5)更新信息 (6)返回nn );scanf(%d,&yourchoice);printf(nn);while(!(yourchoice=1|yourchoice=2|yourchoice=3|yourchoice=4|yourchoice=5|yourchoice=6)printf(請(qǐng)重新輸入：);scanf(%d,&yourchoice);while(1)switch(yourchoice) case 1: delve*(ga); break; case 2: delarc(ga); break; case 3: enve*(ga); break; case 4: enarc(ga); br