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

1、精選文檔一、課程設(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é)合緊密的、規(guī)模較大的問(wèn)題，通過(guò)分析、設(shè)計(jì)、編碼、調(diào)試等各環(huán)節(jié)的訓(xùn)練，使學(xué)生深刻理解、牢固掌握數(shù)據(jù)結(jié)構(gòu)和算法設(shè)計(jì)技術(shù)，掌握分析、解決實(shí)際問(wèn)題的能力。通過(guò)這次設(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)練。2、 課程設(shè)計(jì)內(nèi)容1)問(wèn)題描述用無(wú)向網(wǎng)表

2、示你所在學(xué)校的校園景點(diǎn)平面圖，圖中頂點(diǎn)表示主要景點(diǎn)，存放景點(diǎn)的編號(hào)、名稱(chēng)、簡(jiǎn)介等信息，圖中的邊表示景點(diǎn)間的道路，存放路徑長(zhǎng)度等信息。要求能夠回答有關(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)間的所有路徑。（4） 增加、刪除、更新有關(guān)景點(diǎn)和道路的信息 三、課程設(shè)計(jì)過(guò)程1需求分析（1）設(shè)計(jì)學(xué)校的校園平面圖，選取出若干的具有代表性的景點(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)

3、及其最優(yōu)路線的查詢(xún)（5）平面圖景點(diǎn)的增加及刪除，以及邊和權(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ǔ)結(jié)構(gòu)的設(shè)計(jì)，采取了圖結(jié)構(gòu)類(lèi)型（mgraph）存儲(chǔ)校園圖的信息，景點(diǎn)信息用結(jié)構(gòu)數(shù)組vexs存儲(chǔ)，而且利用全局變量：visited數(shù)組用于存儲(chǔ)頂點(diǎn)是否被訪問(wèn)標(biāo)志；d數(shù)組用于存放權(quán)值和查找路徑頂點(diǎn)的編號(hào)；campus是一個(gè)圖結(jié)構(gòu)的全局變量。 3： 第三點(diǎn)是設(shè)計(jì)各個(gè)功能的實(shí)現(xiàn)，學(xué)校景點(diǎn)的介紹通過(guò)函數(shù)browsecompus()來(lái)實(shí)現(xiàn)；查詢(xún)景點(diǎn)間的最段路徑通過(guò)Floyd(弗洛伊德)算法

4、實(shí)現(xiàn)；查詢(xún)景點(diǎn)間的所有路徑通過(guò)allpath函數(shù)和path函數(shù)來(lái)實(shí)現(xiàn)；更改圖的信息可以由主函數(shù)changegraph以及其他函數(shù)可以實(shí)現(xiàn)。 3 詳細(xì)設(shè)計(jì)（1）主要的操作界面的顯示以及無(wú)向網(wǎng)操作void initgraph(graph *ga) int i,j;ga->n=9;ga->e=11; for( i=0;i<ga->n;i+) ga->vexsi.num=i; strcpy(ga->,"西門(mén)");strcpy(ga->roduce,"學(xué)校的正大門(mén)，設(shè)有公交站");st

5、rcpy(ga->,"風(fēng)雨籃球場(chǎng)");strcpy(ga->roduce,"");strcpy(ga->,"田徑場(chǎng)");strcpy(ga->roduce,"舉辦運(yùn)動(dòng)會(huì)，平時(shí)體育跑步鍛煉等");strcpy(ga->,"京元食堂");strcpy(ga->roduce,"新食堂");strcpy(ga->vexs4.nam

6、e,"蒼霞湖畔");strcpy(ga->roduce,"戲稱(chēng)“分手湖”，景色宜人"); strcpy(ga->,"思源樓");strcpy(ga->roduce,"學(xué)校王牌土木的教學(xué)區(qū)");strcpy(ga->,"圖書(shū)館");strcpy(ga->roduce,"是大學(xué)城最高的標(biāo)志性建筑");strcpy(ga->,&quo

7、t;北教區(qū)");strcpy(ga->roduce,"北校區(qū)集中的教學(xué)樓");strcpy(ga->,"禾堂餐廳");strcpy(ga->roduce,"舊食堂"); for(i=0;i<ga->n;i+)for(j=0;j<ga->n;j+)ga->edgesij=1000;ga->edges01=1;ga->edges12=2;ga->edges13=5;ga->edges24=4;ga-&g

8、t;edges34=9;ga->edges45=1;ga->edges48=1;ga->edges56=5;ga->edges57=7;ga->edges78=1;ga->edges67=9; for(i=0;i<ga->n;i+)for(j=0;j<ga->n;j+)ga->edgesji=ga->edgesij;（2）確定頂點(diǎn)是否存在已經(jīng)頂點(diǎn)是否已經(jīng)被訪問(wèn)過(guò)來(lái)確定路徑void Create_graph(graph *ga)int i,j,k,w;printf("請(qǐng)輸入頂點(diǎn)數(shù)和邊數(shù):n");scanf

9、("%d %d",&(ga->n),&(ga->e);printf("請(qǐng)輸入景點(diǎn)編號(hào)，景點(diǎn)名字，景點(diǎn)介紹，建立信息表:n");for(i=0;i<ga->n;i+)scanf("%d",&(ga->vexsi.num); gets(ga->);gets(ga->roduce);for(i=0;i<ga->n;i+)for(j=0;j<=ga->n;j+)ga->edgesij=1000;for(k=0;

10、k<ga->e;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;i<ga.n;i+) for(j=0;j<ga.n;j+) printf("%d",ga.edgesij); if(j+1=ga.n) printf("n"); void visit

11、(graph ga) int a;printf("請(qǐng)輸入景點(diǎn)編號(hào)：");scanf("%d",&a); int i;for( i=0;i<ga.n;i+) if(a=ga.vexsi.num) printf("景點(diǎn)編號(hào)為%d n",ga.vexsi.num); printf("景點(diǎn)名稱(chēng)為"); puts(); printf("景點(diǎn)介紹為"); puts(roduce); break; if(i=ga.n)printf("無(wú)

12、此點(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;v<ga.n;v+)for(w=0;w<ga.n;w+)dvw=ga.edgesvw;for(u=0;u<ga.n;u+)pvwu=0;if(dvw<1000)pvwv=1;pvww=1; for(u=0;u<ga.n;u+)for(v=0;v<ga.n;v+)for(w=0;w<ga.n;w+)if

13、(dvu+duw<dvw)dvw=dvu+duw;for(i=0;i<ga.n;i+)pvwi=pvui|puwi;printf("n請(qǐng)輸入出發(fā)點(diǎn)和目的地編號(hào)：");scanf("%d %d",&k,&j);printf("nn");while(k<0|k>ga.n|j<0|j>ga.n) printf("n輸入的編號(hào)不存在"); printf("n請(qǐng)重新輸入編號(hào)：nn"); scanf("%d %d",&k,&am

14、p;j); printf("nn");printf("%s",);for(u=0;u<ga.n;u+)if(pkju && k!=u &&j!=u)printf("->%s",);printf("->%s",);printf("nnn總長(zhǎng)度為%d千米nnn",dkj);（4）得到景點(diǎn)之間的所有路徑void path(graph c,int m,int n,int k)

15、int s,x=0; int t; t=k+1; if(dk=n && k<8) for(s=0;s<k;s+) printf("%s->",); printf("%snn",); else s=0; while(s<c.n) if(c.edgesdks<1000)&&(visiteds=0) visiteds=1; dk+1=s; path(c,m,n,t); visiteds=0; s+; void allpath(graph c) in

16、t 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=locatevex(c,i); n=locatevex(c,j); d0=m; for(k=0;k<c.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)無(wú)頂邊

17、，無(wú)法刪除");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(m<0)printf("此頂點(diǎn)%d已刪除",v0);return 1; n=locatevex(ga,v1); if(n<0)printf("此頂點(diǎn)%d已刪除",v1);return 1; ga.edgesmn=1000; ga.edgesnm=1000; ga.e-; return 1;int

18、 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(m<0|m>ga.n|n<0|n>ga.n)printf("輸入錯(cuò)誤，請(qǐng)重新輸入：");scanf("%d %d",&m,&n);if(locatevex(ga,m)<0)printf("此節(jié)點(diǎn)%d已經(jīng)刪除",m);re

19、turn 1;if(locatevex(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)試分析內(nèi)容包括：a調(diào)試過(guò)程中遇到的問(wèn)題是如何解決的以及對(duì)設(shè)計(jì)與實(shí)現(xiàn)的回顧討論和分析；b算法的時(shí)空分析(包括基本操作和其他算法的時(shí)間復(fù)雜度和空間復(fù)雜度的分析)和改進(jìn)設(shè)想；c經(jīng)驗(yàn)和體會(huì)等。5 用戶(hù)使用說(shuō)明 通過(guò)主菜單提示，選擇出你所想要知道的信息，然后通過(guò)輸入節(jié)點(diǎn)來(lái)代替景點(diǎn)，從而得到景點(diǎn)間的所有路徑，最短路徑等其他信息。6 測(cè)試結(jié)果 （1）操作的主界面

20、（2） 學(xué)校景點(diǎn)的介紹（3） 學(xué)校景點(diǎn)從西門(mén)的禾堂餐廳的所有路徑所有路徑（4）學(xué)校景點(diǎn)從西門(mén)的禾堂餐廳的所有路徑最短路徑（5） 圖的更改的界面（6）邊的刪除界面展示7 附錄#define MAX 100 /數(shù)據(jù)類(lèi)型的定義#include<string>#include<iostream>using namespace std;int visited35;int d35;struct views int num; char name10; char introduce100;typedef views datatype;typedef struct datatype ve

21、xsMAX; int edgesMAXMAX; int n,e;graph;void initgraph(graph *ga)/主要的操作界面的顯示以及無(wú)向網(wǎng)操作 int i,j;ga->n=9;ga->e=11; for( i=0;i<ga->n;i+) ga->vexsi.num=i; strcpy(ga->,"西門(mén)");strcpy(ga->roduce,"學(xué)校的正大門(mén)，設(shè)有公交站");strcpy(ga->,"風(fēng)雨籃球場(chǎng)"

22、);strcpy(ga->roduce,"");strcpy(ga->,"田徑場(chǎng)");strcpy(ga->roduce,"舉辦運(yùn)動(dòng)會(huì)，平時(shí)體育跑步鍛煉等");strcpy(ga->,"京元食堂");strcpy(ga->roduce,"新食堂");strcpy(ga->,"蒼霞湖畔");strcpy(ga->vexs4.

23、introduce,"戲稱(chēng)“分手湖”，景色宜人"); strcpy(ga->,"思源樓");strcpy(ga->roduce,"學(xué)校王牌土木的教學(xué)區(qū)");strcpy(ga->,"圖書(shū)館");strcpy(ga->roduce,"是大學(xué)城最高的標(biāo)志性建筑");strcpy(ga->,"北教區(qū)");strcpy(ga->rodu

24、ce,"北校區(qū)集中的教學(xué)樓");strcpy(ga->,"禾堂餐廳");strcpy(ga->roduce,"舊食堂"); for(i=0;i<ga->n;i+)for(j=0;j<ga->n;j+)ga->edgesij=1000;ga->edges01=1;ga->edges12=2;ga->edges13=5;ga->edges24=4;ga->edges34=9;ga->edges45=1;ga->edge

25、s48=1;ga->edges56=5;ga->edges57=7;ga->edges78=1;ga->edges67=9; for(i=0;i<ga->n;i+)for(j=0;j<ga->n;j+)ga->edgesji=ga->edgesij;int locatevex(graph ga,int v) / /查找景點(diǎn)在圖中的序號(hào) int i; for(i=0;i<ga.n;i+) if(v=ga.vexsi.num)return i; return -1; void Create_graph(graph *ga)int i

26、,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;i<ga->n;i+)scanf("%d",&(ga->vexsi.num); gets(ga->);gets(ga->roduce);for(i=0;i<ga->n;i+)for(j=0;j&

27、lt;=ga->n;j+)ga->edgesij=1000;for(k=0;k<ga->e;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;i<ga.n;i+) for(j=0;j<ga.n;j+) printf("%d",ga.edgesij); if

28、(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;i<ga.n;i+) if(a=ga.vexsi.num) printf("景點(diǎn)編號(hào)為%d n",ga.vexsi.num); printf("景點(diǎn)名稱(chēng)為"); puts(); printf("景點(diǎn)介紹為"); puts(ga.vexsi

29、.introduce); 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,p353535;for(v=0;v<ga.n;v+)for(w=0;w<ga.n;w+)dvw=ga.edgesvw;for(u=0;u<ga.n;u+)pvwu=0;if(dvw<1000)pvwv=1;pvww=1; for(u=0;u<ga.n;u+)for(v=0;v<

30、ga.n;v+)for(w=0;w<ga.n;w+)if(dvu+duw<dvw)dvw=dvu+duw;for(i=0;i<ga.n;i+)pvwi=pvui|puwi;printf("n請(qǐng)輸入出發(fā)點(diǎn)和目的地編號(hào)：");scanf("%d %d",&k,&j);printf("nn");while(k<0|k>ga.n|j<0|j>ga.n) printf("n輸入的編號(hào)不存在"); printf("n請(qǐng)重新輸入編號(hào)：nn"); sca

31、nf("%d %d",&k,&j); printf("nn");printf("%s",);for(u=0;u<ga.n;u+)if(pkju && k!=u &&j!=u)printf("->%s",);printf("->%s",);printf("nnn總長(zhǎng)度為%d千米nnn",dkj);void path(graph c,in

32、t m,int n,int k) int s,x=0; int t; t=k+1; if(dk=n && k<8) for(s=0;s<k;s+) printf("%s->",); printf("%snn",); else s=0; while(s<c.n) if(c.edgesdks<1000)&&(visiteds=0) visiteds=1; dk+1=s; path(c,m,n,t); visiteds=0; s+; void al

33、lpath(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=locatevex(c,i); n=locatevex(c,j); d0=m; for(k=0;k<c.n;k+) visitedk=0; visitedm=1; path(c,m,n,0);void newgraph(graph &ga)int changenum;int i,m,n,t,distance,

34、v0,v1;printf("n請(qǐng)輸入要修改景點(diǎn)的個(gè)數(shù)：n");scanf("%d",&changenum);while(changenum<0|changenum>ga.n)printf("n輸入錯(cuò)誤！請(qǐng)重新輸入");scanf("%d",&changenum);for(i=0;i<changenum;i+)printf("n請(qǐng)輸入景點(diǎn)的編號(hào)：");scanf("%d,&m");t=locatevex(ga,m);printf(&qu

35、ot;n請(qǐng)輸入景點(diǎn)的名稱(chēng)：");scanf("%s",);printf("n請(qǐng)輸入景點(diǎn)簡(jiǎn)介：");scanf("%s",roduce);printf("n請(qǐng)輸入您要更新的邊數(shù)");scanf("%d",&changenum);while(changenum<0|changenum>ga.n)printf("輸入錯(cuò)誤，請(qǐng)重新輸入：");scanf("%d",&change

36、num);printf("n請(qǐng)輸入更新邊的信息： n");for(i=1;i<=changenum;i+)printf("n修改的第%d條邊的起點(diǎn)終點(diǎn)長(zhǎng)度為：",i);scanf("%d %d %d",&v0,&v1,&distance);m=locatevex(ga,v0);n=locatevex(ga,v1);if(m>=0&&n>=0)ga.edgesmn=distance;ga.edgesnm=ga.edgesmn;int delvex(graph &ga) /

37、刪除頂點(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除的景點(diǎn)編號(hào)：");scanf("%d",&v);while(v<0|v>ga.n) printf("n輸入錯(cuò)誤，請(qǐng)重新輸入"); scanf("%d",&v);m=locatevex(ga,v);if(m<0)printf("此頂點(diǎn)%d已刪除",v);return 1;for(i=m;i&

38、lt;ga.n-1;i+)strcpy(,ga.vexsi+1.name);strcpy(roduce,ga.vexsi+1.introduce);for(i=m;i<ga.n-1;i+)for(j=0;j<ga.n;j+)ga.edgesij=ga.edgesi+1j;for(i=m;i<ga.n-1;i+)for(j=0;j<ga.n;j+)ga.edgesji=ga.edgesji+1;ga.n-;return 1;int delarc(graph &ga) /刪除邊int m,n,v0,v1;if(ga.

39、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=locatevex(ga,v0);if(m<0)printf("此頂點(diǎn)%d已刪除",v0);return 1; n=locatevex(ga,v1); if(n<0)printf("此頂點(diǎn)%d已刪除",v1);return 1; ga.edgesmn=1000; ga.edges

40、nm=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(m<0|m>ga.n|n<0|n>ga.n)printf("輸入錯(cuò)誤，請(qǐng)重新輸入：");scanf("%d %d",&m,&n);if(locatevex(ga,m)<0)printf

41、("此節(jié)點(diǎn)%d已經(jīng)刪除",m);return 1;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)的信息：");printf("n編號(hào)：");scanf("%d",&ga.vexsga.n.num);printf("

42、名稱(chēng)：");scanf("%s",);printf("簡(jiǎn)介：");scanf("%s",roduce);ga.n+;for(i=0;i<ga.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

43、(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: delvex(ga); break; case 2: delarc(ga); break; case