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

1、本課程設(shè)計(jì)的目標(biāo)就是要達(dá)到理論與實(shí)際應(yīng)用相結(jié)合，提高學(xué)生組織數(shù)據(jù)及編 寫大型程序的能力，并培養(yǎng)基本的、良好的程序設(shè)計(jì)技能以及合作能力。設(shè)計(jì)中要求綜合運(yùn)用所學(xué)知識，上機(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)等方面，加深對課程基本內(nèi)容的理解。同時(shí)，在程序設(shè)計(jì) 方法以及上機(jī)操作等基本技能和科學(xué)作風(fēng)方面受到比較系統(tǒng)和嚴(yán)格的訓(xùn)練。二、課程設(shè)計(jì)內(nèi)容1）問題描述用無向網(wǎng)表示你所在學(xué)校的校園

2、景點(diǎn)平面圖，圖中頂點(diǎn)表示主要景點(diǎn)，存放景 點(diǎn)的編號、名稱、簡介等信息，圖中的邊表示景點(diǎn)間的道路，存放路徑長度等信息。 要求能夠回答有關(guān)景點(diǎn)介紹、游覽路徑等問題。2）基本要求（1）查詢各景點(diǎn)的相關(guān)信息；（2）查詢圖中任意兩個(gè)景點(diǎn)間的最短路徑。（3）查詢圖中任意兩個(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)的序號，名稱，介紹存放起來準(zhǔn)備查詢。（3）提供任意景點(diǎn)的信息；（4）提供任意經(jīng)典的路徑查詢及其最優(yōu)路線的查詢（5）

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

4、實(shí)現(xiàn)；查詢景點(diǎn)間的所有 路徑通過 allpath 函數(shù)和 path 函數(shù)來實(shí)現(xiàn)；更改圖的信息可以由主函數(shù) changegraph 以及其他函數(shù)可以實(shí)現(xiàn)。3詳細(xì)設(shè)計(jì)（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è)有公交站 "

5、）; strcpy（ga->," 風(fēng)雨籃球場 "）; strcpy（ga->roduce,""）;strcpy（ga->," 田徑場 "）;strcpy（ga->roduce," 舉辦運(yùn)動會，平時(shí)體育跑步鍛煉等 "）; strcpy（ga->," 京元食堂 "）;strcpy（ga->roduce," 新食堂 "）;strcpy

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

7、strcpy（ga->," 北教區(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;g

8、a->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->n;j+)ga->edgesji=ga->edgesij;(2) 確定頂點(diǎn)是否存在已經(jīng)頂點(diǎn)是否已經(jīng)被訪問過來確定路徑void Create_graph(graph *ga)int i,j,k,w

9、;printf(" 請輸入頂點(diǎn)數(shù)和邊數(shù) :n");scanf("%d %d",&(ga->n),&(ga->e);printf(" 請輸入景點(diǎn)編號，景點(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

10、<=ga->n;j+) ga->edgesij=1000;for(k=0;k<ga->e;k+)printf("請輸入£條邊的景點(diǎn)序號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<i+) for(j=0;j<j+)printf("%d",ij);if(j+1= printf

11、("n"); void visit(graph ga)int a;printf(" 請輸入景點(diǎn)編號： "); scanf("%d",&a);int i;for( i=0;i<i+)if(a=i.num)printf(" 景點(diǎn)編號為 %d n",i.num); printf(" 景點(diǎn)名稱為 "););printf(" 景點(diǎn)介紹為 "); roduce);break;無此點(diǎn) n"); if(i=printf("

12、;(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<v+)for(w=0;w<w+)dvw=vw; for(u=0;u<u+) pvwu=0; if(dvw<1000) pvwv=1;pvww=1; for(u=0;u<u+)for(v=0;v<v+)for(w=0;w<w+)if(dvu+duw<dvw)dvw=dvu+duw;for(i=0;i<i

13、+)pvwi=pvui|puwi;printf("n 請輸入出發(fā)點(diǎn)和目的地編號： "); scanf("%d %d",&k,&j);printf("nn");while(k<0|k>|j<0|j>printf("n 輸入的編號不存在 "); printf("n 請重新輸入編號： nn"); scanf("%d %d",&k,&j);printf("nn");printf("%s",

14、);for(u=0;u<u+)if(pkju && k!=u &&j!=u)printf("->%s",);printf("->%s",);printf("nnn總長度為 c千米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=n && k<8)for(s=0;s<k;s+)printf(&q

15、uot;%s->",);printf("%snn",);elses=0;while(s<if(dks<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 請輸入您要查詢的兩個(gè)景點(diǎn)的編號 :nn");scanf("%d %d",&i,&j);printf("nn"

16、;);m=locatevex(c,i);n=locatevex(c,j);d0=m;for(k=0;k<k+)visitedk=0;visitedm=1;path(c,m,n,0);(5) 刪除邊int delarc(graph &ga) int m,n,v0,v1;if<=0)printf(" 圖中已經(jīng)無頂邊，無法刪除 ");return 1;printf("n 請輸入要刪除的邊的起點(diǎn)和終點(diǎn)的編號： ");scanf("%d %d",&v0,&v1);m=locatevex(ga,v0);if(m

17、<0)printf(" 此頂點(diǎn)d已刪除",vO);return 1;n=locatevex(ga,v1);if(n<O)printf(" 此頂點(diǎn)d已刪除",v1);return 1;mn=1OOO;nm=1OOO;return 1; int enarc(graph &ga)int m,n,distance;printf(" 請輸入邊的起點(diǎn)和終點(diǎn)編號，權(quán)值： "); scanf("%d %d %d",&m,&n,&distance); while(m<0|m>|

18、n<0|n>printf(" 輸入錯(cuò)誤，請重新輸入： "); scanf("%d %d",&m,&n); if(locatevex(ga,m)<0)printf(" 此節(jié)點(diǎn)cE經(jīng)刪除",m);return 1; if(locatevex(ga,n)<0)printf(" 此節(jié)點(diǎn)d已經(jīng)刪除",n); return 1;mn=distance;nm=mn;return 1;4調(diào)試分析 內(nèi)容包括：a調(diào)試過程中遇到的問題是如何解決的以及對設(shè)計(jì)與實(shí)現(xiàn)的回顧討論和分 析；b算法的時(shí)空分析

19、(包括基本操作和其他算法的時(shí)間復(fù)雜度和空間復(fù)雜度的分 析) 和改進(jìn)設(shè)想；C 經(jīng)驗(yàn)和體會等。5用戶使用說明 通過主菜單提示，選擇出你所想要知道的信息，然后通過輸入節(jié)點(diǎn)來代替景 點(diǎn)，從而得到景點(diǎn)間的所有路徑，最短路徑等其他信息。6測試結(jié)果（2）（3）（4）（5）（6）7附錄#define MAX 100 um=i;strcpy（ga->,"西門 "）;strcpy（ga->roduce," 學(xué)校的正大門，設(shè)有公交站 "）; strcpy（ga->," 風(fēng)雨籃球場 "

20、;）; strcpy（ga->roduce,""）;strcpy（ga->," 田徑場 "）;strcpy（ga->roduce," 舉辦運(yùn)動會，平時(shí)體育跑步鍛煉等 "）;strcpy（ga->," 京元食堂 "）;strcpy（ga->roduce," 新食堂 "）;strcpy（ga->," 蒼霞湖畔 "）;( 1)操作的主

21、界面 學(xué)校景點(diǎn)的介紹 學(xué)校景點(diǎn)從西門的禾堂餐廳的所有路徑所有路徑 學(xué)校景點(diǎn)從西門的禾堂餐廳的所有路徑最短路徑 圖的更改的界面 邊的刪除界面展示strcpy(ga->roduce," 戲稱“分手湖”，景色宜人 "); strcpy(ga->," 思源樓 ");strcpy(ga->roduce," 學(xué)校王牌土木的教學(xué)區(qū) ");strcpy(ga->," 圖書館 ");strcpy(ga->rod

22、uce," 是大學(xué)城最高的標(biāo)志性建筑 ");strcpy(ga->," 北教區(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-&g

23、t;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->n;j+)ga->edgesji=ga->edgesij;查找景點(diǎn)在圖中的序號int locatevex(graph ga,int v

24、) / /int i;for(i=0;i<i+) if(v=i.num)return i; return -1;void Create_graph(graph *ga)int i,j,k,w;printf(" 請輸入頂點(diǎn)數(shù)和邊數(shù) :n");scanf("%d %d",&(ga->n),&(ga->e);printf(" 請輸入景點(diǎn)編號，景點(diǎn)名字，景點(diǎn)介紹，建立信息表 :n"); for(i=0;i<ga->n;i+) scanf("%d",&(ga->ve

25、xsi.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("請輸入£條邊的景點(diǎn)序號i , j和長度：",k+1); scanf("%d %d %d",&i,&j,&w);ga->edgesij=w;ga->edgesji=w;void

26、 print(graph ga)int i,j;for(i=0;i<i+) for(j=0;j<j+)printf("%d",ij);if(j+1= printf("n");void visit(graph ga)int a;printf(" 請輸入景點(diǎn)編號： "); scanf("%d",&a);int i;for( i=0;i<i+)if(a=i.num)printf(" 景點(diǎn)編號為 %d n",i.num); printf(" 景點(diǎn)名稱為 ")

27、;);printf(" 景點(diǎn)介紹為 "); roduce);break;無此點(diǎn) n"); if(i=printf("void shortestpath_djst(graph ga)void shortestpath_floyd(graph ga)int i,j,k,v,u,w,d3535,p353535;for(v=0;v<v+)for(w=0;w<w+)dvw=vw; for(u=0;u<u+) pvwu=0; if(dvw<1000) pvwv=1;pvww=1; for(u=0;u<

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

29、anf("%d %d",&k,&j); printf("nn"); printf("%s",); for(u=0;u<u+)if(pkju && k!=u &&j!=u)printf("- ->%s",);printf("->%s",);printf("nnn總長度為 c千米nnn",dkj);void path(graph c,int m,int n,int k)int s

30、,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<if(dks<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 請輸入您要查詢的兩個(gè)景點(diǎn)

31、的編號 :nn"); scanf("%d %d",&i,&j);printf("nn");m=locatevex(c,i);n=locatevex(c,j);d0=m;for(k=0;k<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 請輸入要修改景點(diǎn)的個(gè)數(shù)： n"); scanf("%d",&am

32、p;changenum);while(changenum<0|changenum>printf("n 輸入錯(cuò)誤！請重新輸入 "); scanf("%d",&changenum); for(i=0;i<changenum;i+)printf("n 請輸入景點(diǎn)的編號： "); scanf("%d,&m");t=locatevex(ga,m);printf("n 請輸入景點(diǎn)的名稱： "); scanf("%s",);printf(&qu

33、ot;n 請輸入景點(diǎn)簡介： "); scanf("%s",roduce);printf("n 請輸入您要更新的邊數(shù) ");scanf("%d",&changenum);while(changenum<0|changenum>printf(" 輸入錯(cuò)誤，請重新輸入： "); scanf("%d",&changenum);printf("n 請輸入更新邊的信息： n");for(i=1;i<=changenum;i+)prin

34、tf("n修改的第d條邊的起點(diǎn)終點(diǎn)長度為：",i);scanf("%d %d %d",&v0,&v1,&distance); m=locatevex(ga,v0);n=locatevex(ga,v1);if(m>=0&&n>=0)mn=distance;nm=mn;int delvex(graph &ga) ame,i+1.name); roduce,i+1.introduce);for(i=m;i<i+)for(j=0;j<j+)i j=i+1j;for(i=

35、m;i<i+)for(j=0;j<j+)ji=ji+1;return 1;int delarc(graph &ga) um); printf(" 名稱： "); scanf("%s",.name); printf(" 簡介： "); scanf("%s",.introduce); +;for(i=0;i<i+)i=1000;i=1000;return 1; intchangegraph(graph &ga)int yourchoice;printf("nprintf(&q

36、uot;nprintf("nscanf("%d",&yourchoice);printf("nn");while(!(yourchoice=1|yourchoice=2|yourchoice=3|yourchoice=4|y ourchoice=5|yourchoice=6)printf(" 請重新輸入： ");scanf("%d",&yourchoice);while(1)switch(yourchoice)case 1:case 2:case 3:case 4:case 5:請選擇 nn(3)(5)(1)增加結(jié)點(diǎn) (4) 增加邊 n"); 更新信息 (6) 返回 nn" );刪除結(jié)點(diǎn) (2) 刪除邊 n");case 6: return 1;printf("nprintf("nprintf("ndelvex(ga); break; delarc(ga); break; envex(ga); break; enarc(ga); break; newgraph(ga); break;請選擇 nn(3)(5)(1)增加結(jié)點(diǎn)更新信息刪除結(jié)點(diǎn) (2) 刪除邊 n");(4