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

2、校園景點平面圖，圖中頂點表示主要景點，存放景點的編號、名稱、簡介等信息，圖中的邊表示景點間的道路，存放路徑長度等信息。要求能夠回答有關(guān)景點介紹、游覽路徑等問題?；疽蟛樵兏骶包c的相關(guān)信息；查詢圖中任意兩個景點間的最短路徑。查詢圖中任意兩個景點間的所有路徑。（ 4 ）增加、刪除、更新有關(guān)景點和道路的信息三、課程設(shè)計過程1 需求分析1 ） 設(shè)計學校的校園平面圖， 選取出若干的具有代表性的景點構(gòu)成一個抽象的無向帶權(quán)圖，頂點為景點，邊的權(quán)值代表了景點間路徑的長度。2 ）將景點的序號，名稱，介紹存放起來準備查詢。3 ）提供任意景點的信息；4 ）提供任意經(jīng)典的路徑查詢及其最優(yōu)路線的查詢5 ）平面圖景點的

3、增加及刪除，以及邊和權(quán)值（長度）的改變概要設(shè)計：第一點是主界面的設(shè)計，首先，為了該系統(tǒng)各個功能的管理，設(shè)計出含有多個菜單項的主菜單界面，可以更方便的使用該系統(tǒng)。:第二點是存儲結(jié)構(gòu)的設(shè)計，采取了圖結(jié)構(gòu)類型（mgraph）存儲校園圖的信息，景點信息用結(jié)構(gòu)數(shù)組vexs 存儲，而且利用全局變量： visited 數(shù)組用于存儲頂點是否被訪問標志； d 數(shù)組用于存放權(quán)值和查找路徑頂點的編號； campus 是一個圖結(jié)構(gòu)的全局變量。:第三點是設(shè)計各個功能的實現(xiàn)，學校景點的介紹通過函數(shù)browsecompus（）來實現(xiàn)；查詢景點間的最段路徑通過Floyd（ 弗洛伊德 ）算法實現(xiàn)；查詢景點間的所有路徑通過 al

4、lpath 函數(shù)和 path 函數(shù)來實現(xiàn)；更改圖的信息可以由主函數(shù)changegraph 以及其他函數(shù)可以實現(xiàn)。詳細設(shè)計1 ）主要的操作界面的顯示以及無向網(wǎng)操作void initgraph(graph *ga) int i,j;ga-n=9;ga-e=11;for( i=0;in;i+)ga-vexsi.num=i;strcpy(, 西門 ); TOC o 1-5 h z strcpy(roduce, 學校的正大門，設(shè)有公交站);strcpy(, 風雨籃球場);strcpy(roduce,);s

5、trcpy(, 田徑場 );strcpy(roduce, 舉辦運動會，平時體育跑步鍛煉等);strcpy(, 京元食堂 );strcpy(roduce, 新食堂 );strcpy（, 蒼霞湖畔 ）; TOC o 1-5 h z strcpy（roduce, 戲稱“分手湖” ，景色宜人）;strcpy（, 思源樓 ）;strcpy（roduce, 學校王牌土木的教學區(qū) ）;strcpy（ga-vex

6、,圖書館）;strcpy（roduce, 是大學城最高的標志性建筑）;strcpy（,北教區(qū)）;strcpy（roduce, 北校區(qū)集中的教學樓）;strcpy（, 禾堂餐廳 ）;strcpy（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=

7、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;( 2 )確定頂點是否存在已經(jīng)頂點是否已經(jīng)被訪問過來確定路徑void Create_graph(graph *ga)int i,j,k,w;printf( 請輸入頂點數(shù)和邊數(shù):n);scanf(%d %d,&(ga-n),&(ga-e);:n);printf( 請輸入景點編號，景點名字，景點介紹，建立信息表for(i=0;in;i+)scanf(%d,&(ga-v

8、exsi.num);gets();gets(roduce);for(i=0;in;i+)for(j=0;jn;j+)ga-edgesij=1000;for(k=0;ke;k+)printf( 請輸入 %d 條邊的景點序號i ， j 和長度： ,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)p

9、rintf(n);void visit(graph ga)int a;printf( 請輸入景點編號： );scanf(%d,&a);int i;for( i=0;iga.n;i+)if(a=ga.vexsi.num)printf( 景點編號為%d n,ga.vexsi.num);printf( 景點名稱為);puts();printf( 景點介紹為 );puts(roduce);break;if(i=ga.n)printf( 無此點 n);( 3 )得出景點間的最短路徑void shortestpath_djst(graph ga)void

10、shortestpath_floyd(graph ga)int i,j,k,v,u,w,d3535,p353535;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 請輸入出發(fā)點和目的地編號： );scanf(%d %

11、d,&k,&j);printf(nn);while(kga.n|jga.n) printf(n 輸入的編號不存在 );printf(n 請重新輸入編號： nn);scanf(%d %d,&k,&j);printf(nn);printf(%s,);for(u=0;u%s,);printf(-%s,);printf(nnn 總長度為 %d 千米 nnn,dkj);( 4 )得到景點之間的所有路徑void path(graph c,int m,int n,int k)int s,x=0;int t;t=k+1;if(dk=

12、n & k8)for(s=0;s,);printf(%snn,);elses=0;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;:nn);printf(nn 請輸入您要查詢的兩個景點的編號scanf(%d %d,&i,&j);printf(nn);m=locatevex(c,i);n=locatevex(c,j);d0=m;for(k=0;kc.

13、n;k+)visitedk=0;visitedm=1;path(c,m,n,0);( 5 )刪除邊int delarc(graph &ga) int m,n,v0,v1;if(ga.e=0)printf( 圖中已經(jīng)無頂邊，無法刪除);return 1;);printf(n 請輸入要刪除的邊的起點和終點的編號：scanf(%d %d,&v0,&v1);m=locatevex(ga,v0);if(m0) printf( 此頂點 %d 已刪除 ,v0);return 1;n=locatevex(ga,v1);if(n0)printf( 此頂點 %d 已刪除 ,v1);return 1;ga.edge

14、smn=1000;ga.edgesnm=1000;ga.e-;return 1; int enarc(graph &ga)int m,n,distance;printf( 請輸入邊的起點和終點編號，權(quán)值： );scanf(%d %d %d,&m,&n,&distance);while(mga.n|nga.n)printf( 輸入錯誤，請重新輸入： );scanf(%d %d,&m,&n);if(locatevex(ga,m)0)printf( 此節(jié)點 %d 已經(jīng)刪除 ,m);return 1;if(locatevex(ga,n)0)printf（ 此節(jié)點 %d 已經(jīng)刪除 ,n）;return

15、1;ga.edgesmn=distance;ga.edgesnm=ga.edgesmn;return 1;調(diào)試分析內(nèi)容包括：a 調(diào)試過程中遇到的問題是如何解決的以及對設(shè)計與實現(xiàn)的回顧討論和分析；b 算法的時空分析（包括基本操作和其他算法的時間復(fù)雜度和空間復(fù)雜度的分析 ）和改進設(shè)想；c 經(jīng)驗和體會等。用戶使用說明通過主菜單提示，選擇出你所想要知道的信息，然后通過輸入節(jié)點來代替景點，從而得到景點間的所有路徑，最短路徑等其他信息。測試結(jié)果（ 1 ）操作的主界面2 ）學校景點的介紹3 ）學校景點從西門的禾堂餐廳的所有路徑所有路徑4 ）學校景點從西門的禾堂餐廳的所有路徑最短路徑5 ）圖的更改的界面6 ）

16、邊的刪除界面展示7附錄#define MAX 100/ 數(shù)據(jù)類型的定義#include#includeusing namespace std;int visited35;int d35;struct viewsint num;char name10;char introduce100;typedef views datatype;typedef struct datatype vexsMAX;int edgesMAXMAX;int n,e;graph;void initgraph(graph *ga)/ 主要的操作界面的顯示以及無向網(wǎng)操作int i,j;ga-n=9;ga-e=11;for(

17、i=0;in;i+)ga-vexsi.num=i;strcpy(, 西門 );strcpy(roduce, 學校的正大門，設(shè)有公交站);strcpy(, 風雨籃球場);strcpy（roduce,）;strcpy（, 田徑場 ）; TOC o 1-5 h z strcpy（roduce, 舉辦運動會，平時體育跑步鍛煉等）;strcpy（,京元食堂）;strcpy（roduce, 新食堂 ）;str

18、cpy（,蒼霞湖畔）;strcpy（roduce, 戲稱“分手湖” ，景色宜人）;strcpy（, 思源樓 ）;strcpy（roduce, 學校王牌土木的教學區(qū) ）;strcpy（,圖書館）;strcpy（roduce, 是大學城最高的標志性建筑）;strcpy（,北教區(qū)）;strcpy（roduce, 北校區(qū)集中的教學樓）;strcpy（, 禾堂餐廳 ）;strcpy

19、（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+)for(j=0;jn;j+)ga-edgesji=ga-edgesij;int locatevex(graph ga,int v) / / 查找

20、景點在圖中的序號int i;for(i=0;in),&(ga-e);printf( 請輸入景點編號，景點名字，景點介紹，建立信息表:n);for(i=0;in;i+)scanf(%d,&(ga-vexsi.num);gets();gets(roduce);for(j=0;jga.n;j+)for(j=0;jga.n;j+)for(i=0;in;i+)for(j=0;jn;j+)ga-edgesij=1000;for(k=0;ke;k+)printf(請輸入d條邊的景點序號i, j和長度：”,k+1);scanf(%d %d %d,&i,&j,&

21、w);ga-edgesij=w;ga-edgesji=w;)void print(graph ga)int i,j;for(i=0;iga.n;i+)printf(%d,ga.edgesij);if(j+1=ga.n)printf(n);void visit(graph ga)int a;printf( 請輸入景點編號： );scanf(%d,&a);int i;for( i=0;iga.n;i+)if(a=ga.vexsi.num)printf( 景點編號為 %d n,ga.vexsi.num);printf（ 景點名稱為 ）;puts();printf( 景點介紹

22、為 );puts(roduce);break;if(i=ga.n)printf( 無此點 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.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

23、;wga.n;w+)if(dvu+duwdvw)dvw=dvu+duw;for(i=0;iga.n;i+)pvwi=pvui|puwi;printf(n 請輸入出發(fā)點和目的地編號： );scanf(%d %d,&k,&j);printf(nn);while(kga.n|jga.n)printf(n 輸入的編號不存在 );printf(n 請重新輸入編號： nn);scanf(%d %d,&k,&j);printf(nn);printf(%s,);for(u=0;u%s,);printf(-%s,);printf(nn

24、n 總長度為 %d 千米 nnn,dkj);void path(graph c,int m,int n,int k)int s,x=0;int t;t=k+1;if(dk=n & k8)for(s=0;s,);printf(%snn,);elses=0;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 請輸入您要查詢的兩個景點的

25、編號:nn);scanf(%d %d,&i,&j);printf(nn);m=locatevex(c,i);n=locatevex(c,j);d0=m;for(k=0;kc.n;k+)visitedk=0;visitedm=1;path(c,m,n,0);void newgraph(graph &ga) int changenum;int i,m,n,t,distance,v0,v1;printf(n 請輸入要修改景點的個數(shù)： n);scanf(%d,&changenum);while(changenumga.n)printf(n 輸入錯誤！請重新輸入 );scanf(%d,&changenu

26、m);for(i=0;ichangenum;i+)printf(n 請輸入景點的編號： );scanf(%d,&m);t=locatevex(ga,m);printf(n 請輸入景點的名稱： );scanf(%s,);printf(n 請輸入景點簡介： );scanf(%s,roduce);printf(n 請輸入您要更新的邊數(shù));scanf(%d,&changenum);while(changenumga.n)printf( 輸入錯誤，請重新輸入： );scanf(%d,&changenum);printf(n 請輸入更新邊的信息： n);f

27、or(i=1;i=0&n=0)ga.edgesmn=distance;ga.edgesnm=ga.edgesmn;int delvex(graph &ga) / 刪除頂點int i=0,j;int m,v;if(ga.n=0)printf( 圖中已經(jīng)無頂點 );return 1;printf（n 請輸入要刪除的景點編號： ）;scanf(%d,&v);while(vga.n)printf(n 輸入錯誤，請重新輸入);scanf(%d,&v);m=locatevex(ga,v);if(m0)printf( 此頂點 %d 已刪除 ,v);return 1;for(i=m;iga.n-1;i+)st

28、rcpy(,ga.vexsi+1.name);strcpy(roduce,ga.vexsi+1.introduce);return 1;return 1;for(i=m;iga.n-1;i+)for(j=0;jga.n;j+)ga.edgesij=ga.edgesi+1j;for(i=m;iga.n-1;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)

29、無頂邊，無法刪除););printf(n 請輸入要刪除的邊的起點和終點的編號：scanf(%d %d,&v0,&v1);m=locatevex(ga,v0);if(m0)printf( 此頂點 %d 已刪除 ,v0);return 1;n=locatevex(ga,v1);if(n0)printf( 此頂點 %d 已刪除 ,v1);return 1;ga.edgesmn=1000;ga.edgesnm=1000;return 1;return 1;ga.e-;return 1;int enarc(graph &ga)int m,n,distance;);printf( 請輸入邊的起點和終點編號

30、，權(quán)值：scanf(%d %d %d,&m,&n,&distance);while(mga.n|nga.n)printf( 輸入錯誤，請重新輸入： );scanf(%d %d,&m,&n);if(locatevex(ga,m)0)printf( 此節(jié)點 %d 已經(jīng)刪除 ,m);if(locatevex(ga,n)0)printf( 此節(jié)點 %d 已經(jīng)刪除 ,n);return 1;ga.edgesmn=distance;ga.edgesnm=ga.edgesmn;return 1;int envex(graph &ga) / 增加節(jié)點int i;printf( 請輸入增加節(jié)點的信息： );pr

31、intf(n 編號： );scanf(%d,&ga.vexsga.n.num);printf( 名稱： );scanf(%s,);printf( 簡介： );scanf(%s,roduce);ga.n+;for(i=0;iga.n;i+)ga.edgesga.n-1i=1000;ga.edgesiga.n-1=1000;return 1;int changegraph(graph &ga)int yourchoice;printf(n 請選擇 nn(1)刪除結(jié)點(2)刪除邊 n);printf(n(3)增加結(jié)點(4)增加邊 n);printf(n(5)更新信息(6)返回nn );scanf(%d,&yourchoice);scanf(%d,&yourchoice);printf(nn);while(!(yourchoice=1|yourchoice=2|yourchoice=3|yourchoice=4|yourchoice=5|yourchoice=6)printf( 請重新輸入： );scanf(%d,&yourchoice);while(1)switch(yourchoice)delvex(ga); bre