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

1、精選文檔一、課程設(shè)計目的本課程設(shè)計的目標(biāo)就是要達(dá)到理論與實際應(yīng)用相結(jié)合，提高學(xué)生組織數(shù)據(jù)及編寫大型程序的能力，并培養(yǎng)基本的、良好的程序設(shè)計技能以及合作能力。設(shè)計中要求綜合運用所學(xué)知識，上機解決一些與實際應(yīng)用結(jié)合緊密的、規(guī)模較大的問題，通過分析、設(shè)計、編碼、調(diào)試等各環(huán)節(jié)的訓(xùn)練，使學(xué)生深刻理解、牢固掌握數(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è)計方法以及上機操作等基本技能和科學(xué)作風(fēng)方面受到比較系統(tǒng)和嚴(yán)格的訓(xùn)練。2、 課程設(shè)計內(nèi)容1)問題描述用無向網(wǎng)表

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

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

4、實現(xiàn)；查詢景點間的所有路徑通過allpath函數(shù)和path函數(shù)來實現(xiàn)；更改圖的信息可以由主函數(shù)changegraph以及其他函數(shù)可以實現(xiàn)。 3 詳細(xì)設(shè)計（1）主要的操作界面的顯示以及無向網(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->,"西門");strcpy(ga->roduce,"學(xué)校的正大門，設(shè)有公交站");st

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

6、e,"蒼霞湖畔");strcpy(ga->roduce,"戲稱“分手湖”，景色宜人"); strcpy(ga->,"思源樓");strcpy(ga->roduce,"學(xué)校王牌土木的教學(xué)區(qū)");strcpy(ga->,"圖書館");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）確定頂點是否存在已經(jīng)頂點是否已經(jīng)被訪問過來確定路徑void Create_graph(graph *ga)int i,j,k,w;printf("請輸入頂點數(shù)和邊數(shù):n");scanf

9、("%d %d",&(ga->n),&(ga->e);printf("請輸入景點編號，景點名字，景點介紹，建立信息表: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("請輸入%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;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("請輸入景點編號：");scanf("%d",&a); int i;for( i=0;i<ga.n;i+) if(a=ga.vexsi.num) printf("景點編號為%d n",ga.vexsi.num); printf("景點名稱為"); puts(); printf("景點介紹為"); puts(roduce); break; if(i=ga.n)printf("無

12、此點n");（3）得出景點間的最短路徑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請輸入出發(fā)點和目的地編號：");scanf("%d %d",&k,&j);printf("nn");while(k<0|k>ga.n|j<0|j>ga.n) printf("n輸入的編號不存在"); printf("n請重新輸入編號：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總長度為%d千米nnn",dkj);（4）得到景點之間的所有路徑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請輸入您要查詢的兩個景點的編號: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)無頂邊

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

18、 enarc(graph &ga)int m,n,distance;printf("請輸入邊的起點和終點編號，權(quán)值：");scanf("%d %d %d",&m,&n,&distance);while(m<0|m>ga.n|n<0|n>ga.n)printf("輸入錯誤，請重新輸入：");scanf("%d %d",&m,&n);if(locatevex(ga,m)<0)printf("此節(jié)點%d已經(jīng)刪除",m);re

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

20、（2） 學(xué)校景點的介紹（3） 學(xué)校景點從西門的禾堂餐廳的所有路徑所有路徑（4）學(xué)校景點從西門的禾堂餐廳的所有路徑最短路徑（5） 圖的更改的界面（6）邊的刪除界面展示7 附錄#define MAX 100 /數(shù)據(jù)類型的定義#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ǎng)操作 int i,j;ga->n=9;ga->e=11; for( i=0;i<ga->n;i+) ga->vexsi.num=i; strcpy(ga->,"西門");strcpy(ga->roduce,"學(xué)校的正大門，設(shè)有公交站");strcpy(ga->,"風(fēng)雨籃球場"

22、);strcpy(ga->roduce,"");strcpy(ga->,"田徑場");strcpy(ga->roduce,"舉辦運動會，平時體育跑步鍛煉等");strcpy(ga->,"京元食堂");strcpy(ga->roduce,"新食堂");strcpy(ga->,"蒼霞湖畔");strcpy(ga->vexs4.

23、introduce,"戲稱“分手湖”，景色宜人"); strcpy(ga->,"思源樓");strcpy(ga->roduce,"學(xué)校王牌土木的教學(xué)區(qū)");strcpy(ga->,"圖書館");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) / /查找景點在圖中的序號 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("請輸入頂點數(shù)和邊數(shù):n");scanf("%d %d",&(ga->n),&(ga->e);printf("請輸入景點編號，景點名字，景點介紹，建立信息表: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("請輸入%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;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("請輸入景點編號：");scanf("%d",&a); int i;for( i=0;i<ga.n;i+) if(a=ga.vexsi.num) printf("景點編號為%d n",ga.vexsi.num); printf("景點名稱為"); puts(); printf("景點介紹為"); puts(ga.vexsi

29、.introduce); 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;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請輸入出發(fā)點和目的地編號：");scanf("%d %d",&k,&j);printf("nn");while(k<0|k>ga.n|j<0|j>ga.n) printf("n輸入的編號不存在"); printf("n請重新輸入編號：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總長度為%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請輸入您要查詢的兩個景點的編號: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請輸入要修改景點的個數(shù)：n");scanf("%d",&changenum);while(changenum<0|changenum>ga.n)printf("n輸入錯誤！請重新輸入");scanf("%d",&changenum);for(i=0;i<changenum;i+)printf("n請輸入景點的編號：");scanf("%d,&m");t=locatevex(ga,m);printf(&qu

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

36、num);printf("n請輸入更新邊的信息： n");for(i=1;i<=changenum;i+)printf("n修改的第%d條邊的起點終點長度為：",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、刪除頂點int i=0,j;int m,v;if(ga.n<=0)printf("圖中已經(jīng)無頂點");return 1;printf("n請輸入要刪除的景點編號：");scanf("%d",&v);while(v<0|v>ga.n) printf("n輸入錯誤，請重新輸入"); scanf("%d",&v);m=locatevex(ga,v);if(m<0)printf("此頂點%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)無頂邊，無法刪除");return 1;printf("n請輸入要刪除的邊的起點和終點的編號：");scanf("%d %d",&v0,&v1); m=locatevex(ga,v0);if(m<0)printf("此頂點%d已刪除",v0);return 1; n=locatevex(ga,v1); if(n<0)printf("此頂點%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("請輸入邊的起點和終點編號，權(quán)值：");scanf("%d %d %d",&m,&n,&distance);while(m<0|m>ga.n|n<0|n>ga.n)printf("輸入錯誤，請重新輸入：");scanf("%d %d",&m,&n);if(locatevex(ga,m)<0)printf

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

42、名稱：");scanf("%s",);printf("簡介：");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請選擇nn (1)刪除結(jié)點 (2)刪除邊n");printf("n

43、(3)增加結(jié)點 (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("請重新輸入：");scanf("%d",&yourchoice);while(1)switch(yourchoice) case 1: delvex(ga); break; case 2: delarc(ga); break; case