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

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

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

3、典的路徑查詢及其最優(yōu)路線的查詢（ 5平面圖景點的增加及刪除，以及邊和權(quán)值長度的改變專業(yè)資料整理WORD格式2概要設(shè)計專業(yè)資料整理WORD格式1：第一點是主界面的設(shè)計，首先，為了該系統(tǒng)各個功能的管理，設(shè)計出含有多個菜單項的主菜單界面，可以更方便的使用該系統(tǒng)。專業(yè)資料整理WORD格式2 ：第二點是存儲構(gòu)造的設(shè)計，采取了圖構(gòu)造類型mgraph存儲校園圖的信息，景專業(yè)資料整理WORD格式點信息用構(gòu)造數(shù)組vexs 存儲，而且利用全局變量：標志； d 數(shù)組用于存放權(quán)值和查找路徑頂點的編號；visited數(shù)組用于存儲頂點是否被訪問campus 是一個圖構(gòu)造的全局變量。專業(yè)資料整理WORD格式3 ：第三點是設(shè)

4、計各個功能的實現(xiàn)，學(xué)校景點的介紹通過函數(shù)browsecompus()來實現(xiàn)；專業(yè)資料整理WORD格式查詢景點間的最段路徑通過Floyd( 弗洛伊德) 算法實現(xiàn)；查詢景點間的所有路徑通過allpath函數(shù)和 path 函數(shù)來實現(xiàn)；更改圖的信息可以由主函數(shù)changegraph 以及其他函數(shù)可以實現(xiàn)。專業(yè)資料整理WORD格式3詳細設(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->v

5、," 西門 "); strcpy(ga->roduce," 學(xué)校的正大門，設(shè)有公交站 "); strcpy(ga->," 風(fēng)雨籃球場 "); strcpy(ga->roduce,""); strcpy(ga->," 田徑場 ");strcpy(ga->roduce," 舉辦運動會，平時體育跑步鍛煉等 "); strcpy(ga->

6、," 京元食堂 "); strcpy(ga->roduce," 新食堂 "); strcpy(ga->," 蒼霞湖畔 "); strcpy(ga->roduce," 戲稱“分手湖 ，風(fēng)光宜人 "); strcpy(ga->," 思源樓 "); strcpy(ga->roduce," 學(xué)校王牌土木的教學(xué)區(qū) "); strcpy(ga-&

7、gt;," 圖書館 "); strcpy(ga->roduce," 是大學(xué)城最高的標志性建筑 "); strcpy(ga->," 北教區(qū) "); strcpy(ga->roduce," 北校區(qū)集中的教學(xué)樓 "); strcpy(ga->," 禾堂餐廳 ");專業(yè)資料整理WORD格式strcpy(ga->roduce," 舊食堂 ");

8、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->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-&g

9、t;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("%d %d",&(ga->n),&(ga->e);printf(" 請輸入景點編號，景點名字，景點介紹，建立信息表 :n"); for(i=0;i<ga->n;i+)scanf("%d",&(ga->

10、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;k<ga->e;k+)printf(" 請輸入 %d 條邊的景點序號i， j 和長度： ",k+1);scanf("%d %d %d",&i,&j,&w);ga->edgesij=w;ga->edgesji=w;專業(yè)資料整理W

11、ORD格式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(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&q

12、uot;,ga.vexsi.num);printf(" 景點名稱為 ");puts();printf(" 景點介紹為 ");puts(roduce);break;if(i=ga.n)printf(" 無此點 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+)專業(yè)資料整理WORD

13、格式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(dvu+duw<dvw)dvw=dvu+duw;for(i=0;i<ga.n;i+)pvwi=pvui|puwi;printf("n請輸入出發(fā)點和目的地編號：");scanf("%d %d",&k,&j);pr

14、intf("nn");while(k<0|k>ga.n|j<0|j>ga.n)printf("n輸入的編號不存在");printf("n請重新輸入編號：nn");scanf("%d %d",&k,&j);printf("nn");printf("%s",);for(u=0;u<ga.n;u+)if(pkju && k!=u &&j!=u)printf("->

15、%s",);printf("->%s",);printf("nnn總長度為 %d 千米 nnn",dkj);專業(yè)資料整理WORD格式4得到景點之間的所有路徑專業(yè)資料整理WORD格式void path(graph c,int m,int n,int k)int s,x=0;int t;t=k+1;if(dk=n && k<8)專業(yè)資料整理WORD格式for(s=0;s<k;s+)printf("%s->",);

16、printf("%snn",);elses=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)int k,i,j,m,n;printf("nn請輸入您要查詢的兩個景點的編號:nn");scanf("%d %d",&i,&j);printf("nn");m=locateve

17、x(c,i);n=locatevex(c,j);d0=m;for(k=0;k<c.n;k+)visitedk=0;專業(yè)資料整理WORD格式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(

18、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 enarc(graph &ga)int m,n,distance;printf(" 請輸入邊的起點和終點編號，權(quán)值：");scanf("%d %d %d",&m,&n,&di

19、stance);while(m<0|m>ga.n|n<0|n>ga.n)printf(" 輸入錯誤，請重新輸入：");scanf("%d %d",&m,&n);專業(yè)資料整理WORD格式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 1;ga.edgesmn=distance;ga.edgesnm

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

21、資料整理WORD格式7附錄#define MAX 100/ 數(shù)據(jù)類型的定義#include<string>#include<iostream>using 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)/主要的操作界面的顯示以及無向

22、網(wǎng)操作int i,j;ga->n=9;ga->e=11;專業(yè)資料整理WORD格式for( i=0;i<ga->n;i+)ga->vexsi.num=i;strcpy(ga->," 西門 "); strcpy(ga->roduce," 學(xué)校的正大門，設(shè)有公交站 "); strcpy(ga->," 風(fēng)雨籃球場 "); strcpy(ga->roduce,""); strcpy(ga->

23、," 田徑場 ");strcpy(ga->roduce," 舉辦運動會，平時體育跑步鍛煉等 "); strcpy(ga->," 京元食堂 "); strcpy(ga->roduce," 新食堂 "); strcpy(ga->," 蒼霞湖畔 "); strcpy(ga->roduce," 戲稱“分手湖 ，風(fēng)光宜人 "); strcpy(

24、ga->," 思源樓 "); strcpy(ga->roduce," 學(xué)校王牌土木的教學(xué)區(qū) "); strcpy(ga->," 圖書館 "); strcpy(ga->roduce," 是大學(xué)城最高的標志性建筑 "); strcpy(ga->," 北教區(qū) "); strcpy(ga->roduce," 北校區(qū)集中的教學(xué)樓 ");

25、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->edges48=1;ga->edges56=

26、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;專業(yè)資料整理WORD格式for(i=0;i<ga.n;i+)if(v=ga.vexsi.num)return i;return -1;void Create_graph(graph *ga)int i,j,k,w;printf(

27、" 請輸入頂點數(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<=ga->

28、n;j+)ga->edgesij=1000;for(k=0;k<ga->e;k+)專業(yè)資料整理WORD格式printf(" 請輸入 %d 條邊的景點序號i， j 和長度：",k+1);專業(yè)資料整理WORD格式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

29、.edgesij);if(j+1=ga.n)printf("n");void visit(graph ga)專業(yè)資料整理WORD格式int a;printf(" 請輸入景點編號：scanf("%d",&a);int i;");專業(yè)資料整理WORD格式for( i=0;i<ga.n;i+)if(a=ga.vexsi.num)printf(" 景點編號為 %d n",ga.vexsi.num);printf(" 景點名稱為 ");puts();printf(&

30、quot; 景點介紹為 ");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;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

31、(u=0;u<ga.n;u+)for(v=0;v<ga.n;v+)for(w=0;w<ga.n;w+)if(dvu+duw<dvw)dvw=dvu+duw;專業(yè)資料整理WORD格式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輸入的編號不存在&qu

32、ot;);printf("n請重新輸入編號：nn");scanf("%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總長度為

33、 %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 && k<8)for(s=0;s<k;s+)printf("%s->",);printf("%snn",);elses=0;while(s<c.n)if(c.edgesdks<1000)&&(visiteds=0)專業(yè)資料整理WORD格式visiteds=1;dk+1=

34、s;path(c,m,n,t);visiteds=0;s+;void allpath(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 chang

35、enum;int i,m,n,t,distance,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=

36、locatevex(ga,m);printf("n請輸入景點的名稱：");scanf("%s",);printf("n請輸入景點簡介：");scanf("%s",roduce);專業(yè)資料整理WORD格式printf("n請輸入您要更新的邊數(shù)");scanf("%d",&changenum);while(changenum<0|changenum>ga.n)printf(" 輸入錯誤，請重新輸入：&

37、quot;);scanf("%d",&changenum);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.edgesn

38、m=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(v<0|v>ga.n)printf("n輸入錯誤，請重新輸入");scanf("%d",&v);m=locatevex(ga,v);if(m<0)printf(&quo

39、t; 此頂點 %d 已刪除 ",v);return 1;專業(yè)資料整理WORD格式for(i=m;i<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-;retu

40、rn 1;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(m<0)printf(" 此頂點 %d 已刪除 ",v0);return 1;n=locatevex(ga,v1);if(n<0)printf(&qu

41、ot; 此頂點 %d 已刪除 ",v1);return 1;ga.edgesmn=1000;ga.edgesnm=1000;ga.e-;return 1;int enarc(graph &ga)專業(yè)資料整理WORD格式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(" 輸入錯誤，請重新輸入："

42、);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 1;ga.edgesmn=distance;ga.edgesnm=ga.edgesmn;return 1;int envex(graph &ga)/ 增加節(jié)點int i;printf(" 請輸入增加節(jié)點的信息：");p

43、rintf("n編號： ");scanf("%d",&ga.vexsga.n.num);printf(" 名稱： ");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;專業(yè)資料整理WORD格式intchan

44、gegraph(graph &ga)專業(yè)資料整理WORD格式專業(yè)資料整理WORD格式int yourchoice;printf("n請選擇 nnprintf("n(3)增加結(jié)點printf("n(5)更新信息(1)刪除結(jié)點(2)刪除邊(4) 增加邊 n");(6) 返回 nn" );n");專業(yè)資料整理WORD格式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;