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

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

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

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

4、lpath 函數(shù)和 path 函數(shù)來實(shí)現(xiàn)；更改圖的信息可以由主函數(shù)changegraph 以及其他函數(shù)可以實(shí)現(xiàn)。詳細(xì)設(shè)計(jì)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, 學(xué)校的正大門，設(shè)有公交站);strcpy(, 風(fēng)雨籃球場);strcpy(roduce,);s

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

6、,圖書館）;strcpy（roduce, 是大學(xué)城最高的標(biāo)志性建筑）;strcpy（,北教區(qū)）;strcpy（roduce, 北校區(qū)集中的教學(xué)樓）;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 )確定頂點(diǎn)是否存在已經(jīng)頂點(diǎn)是否已經(jīng)被訪問過來確定路徑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);:n);printf( 請(qǐng)輸入景點(diǎn)編號(hào)，景點(diǎn)名字，景點(diǎn)介紹，建立信息表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( 請(qǐng)輸入 %d 條邊的景點(diǎn)序號(hào)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( 請(qǐng)輸入景點(diǎn)編號(hào)： );scanf(%d,&a);int i;for( i=0;iga.n;i+)if(a=ga.vexsi.num)printf( 景點(diǎn)編號(hào)為%d n,ga.vexsi.num);printf( 景點(diǎn)名稱為);puts();printf( 景點(diǎn)介紹為 );puts(roduce);break;if(i=ga.n)printf( 無此點(diǎn) n);( 3 )得出景點(diǎn)間的最短路徑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 請(qǐng)輸入出發(fā)點(diǎn)和目的地編號(hào)： );scanf(%d %

11、d,&k,&j);printf(nn);while(kga.n|jga.n) printf(n 輸入的編號(hào)不存在 );printf(n 請(qǐng)重新輸入編號(hào)： nn);scanf(%d %d,&k,&j);printf(nn);printf(%s,);for(u=0;u%s,);printf(-%s,);printf(nnn 總長度為 %d 千米 nnn,dkj);( 4 )得到景點(diǎn)之間的所有路徑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 請(qǐng)輸入您要查詢的兩個(gè)景點(diǎn)的編號(hào)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 請(qǐng)輸入要?jiǎng)h除的邊的起點(diǎn)和終點(diǎn)的編號(hào)：scanf(%d %d,&v0,&v1);m=locatevex(ga,v0);if(m0) printf( 此頂點(diǎn) %d 已刪除 ,v0);return 1;n=locatevex(ga,v1);if(n0)printf( 此頂點(diǎn) %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( 請(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(locatevex(ga,m)0)printf( 此節(jié)點(diǎn) %d 已經(jīng)刪除 ,m);return 1;if(locatevex(ga,n)0)printf（ 此節(jié)點(diǎn) %d 已經(jīng)刪除 ,n）;return

15、1;ga.edgesmn=distance;ga.edgesnm=ga.edgesmn;return 1;調(diào)試分析內(nèi)容包括：a 調(diào)試過程中遇到的問題是如何解決的以及對(duì)設(shè)計(jì)與實(shí)現(xiàn)的回顧討論和分析；b 算法的時(shí)空分析（包括基本操作和其他算法的時(shí)間復(fù)雜度和空間復(fù)雜度的分析 ）和改進(jìn)設(shè)想；c 經(jīng)驗(yàn)和體會(huì)等。用戶使用說明通過主菜單提示，選擇出你所想要知道的信息，然后通過輸入節(jié)點(diǎn)來代替景點(diǎn)，從而得到景點(diǎn)間的所有路徑，最短路徑等其他信息。測(cè)試結(jié)果（ 1 ）操作的主界面2 ）學(xué)校景點(diǎn)的介紹3 ）學(xué)校景點(diǎn)從西門的禾堂餐廳的所有路徑所有路徑4 ）學(xué)校景點(diǎn)從西門的禾堂餐廳的所有路徑最短路徑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, 學(xué)校的正大門，設(shè)有公交站);strcpy(, 風(fēng)雨籃球場);strcpy（roduce,）;strcpy（, 田徑場 ）; TOC o 1-5 h z strcpy（roduce, 舉辦運(yùn)動(dòng)會(huì)，平時(shí)體育跑步鍛煉等）;strcpy（,京元食堂）;strcpy（roduce, 新食堂 ）;str

18、cpy（,蒼霞湖畔）;strcpy（roduce, 戲稱“分手湖” ，景色宜人）;strcpy（, 思源樓 ）;strcpy（roduce, 學(xué)校王牌土木的教學(xué)區(qū) ）;strcpy（,圖書館）;strcpy（roduce, 是大學(xué)城最高的標(biāo)志性建筑）;strcpy（,北教區(qū)）;strcpy（roduce, 北校區(qū)集中的教學(xué)樓）;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、景點(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-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(請(qǐng)輸入d條邊的景點(diǎn)序號(hào)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( 請(qǐng)輸入景點(diǎn)編號(hào)： );scanf(%d,&a);int i;for( i=0;iga.n;i+)if(a=ga.vexsi.num)printf( 景點(diǎn)編號(hào)為 %d n,ga.vexsi.num);printf（ 景點(diǎn)名稱為 ）;puts();printf( 景點(diǎn)介紹

22、為 );puts(roduce);break;if(i=ga.n)printf( 無此點(diǎn) 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 請(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 %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 請(qǐng)輸入您要查詢的兩個(gè)景點(diǎn)的

25、編號(hào):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 請(qǐng)輸入要修改景點(diǎn)的個(gè)數(shù)： n);scanf(%d,&changenum);while(changenumga.n)printf(n 輸入錯(cuò)誤！請(qǐng)重新輸入 );scanf(%d,&changenu

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

27、or(i=1;i=0&n=0)ga.edgesmn=distance;ga.edgesnm=ga.edgesmn;int delvex(graph &ga) / 刪除頂點(diǎn)int i=0,j;int m,v;if(ga.n=0)printf( 圖中已經(jīng)無頂點(diǎn) );return 1;printf（n 請(qǐng)輸入要?jiǎng)h除的景點(diǎn)編號(hào)： ）;scanf(%d,&v);while(vga.n)printf(n 輸入錯(cuò)誤，請(qǐng)重新輸入);scanf(%d,&v);m=locatevex(ga,v);if(m0)printf( 此頂點(diǎn) %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 請(qǐng)輸入要?jiǎng)h除的邊的起點(diǎn)和終點(diǎn)的編號(hào)：scanf(%d %d,&v0,&v1);m=locatevex(ga,v0);if(m0)printf( 此頂點(diǎn) %d 已刪除 ,v0);return 1;n=locatevex(ga,v1);if(n0)printf( 此頂點(diǎn) %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( 請(qǐng)輸入邊的起點(diǎn)和終點(diǎn)編號(hào)

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

31、intf(n 編號(hào)： );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 請(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);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)delvex(ga); bre