校園導(dǎo)游程序

1、洛 陽 理 工 學(xué) 院課 程 設(shè) 計(jì) 報(bào) 告 課程名稱 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 題 目 校園導(dǎo)游程序 課 程 設(shè) 計(jì) 任 務(wù) 書1、設(shè)計(jì)題目： 校園導(dǎo)游程序 2、設(shè)計(jì)內(nèi)容與要求：問題描述用無向網(wǎng)表示你所在學(xué)校的校園景點(diǎn)平面圖，圖中頂點(diǎn)表示主要景點(diǎn)，存放景點(diǎn)的編號、名稱、簡介等信息，圖中的邊表示景點(diǎn)間的道路，存放路徑長度等信息。要求能夠回答有關(guān)景點(diǎn)介紹、游覽路徑等問題?；疽?（1） 查詢各景點(diǎn)的相關(guān)信息；（2） 查詢圖中任意兩個(gè)景點(diǎn)間的最短路徑。（3） 查詢圖中任意兩個(gè)景點(diǎn)間的所有路徑。（4） 增加、刪除、更新有關(guān)景點(diǎn)和道路的信息。課 程 設(shè) 計(jì) 評 語 成績： 指導(dǎo)教師：_ 年 月 日洛 陽 理

2、 工 學(xué) 院 課 程 設(shè) 計(jì) 報(bào) 告3、 流程圖校園導(dǎo)游圖刪除景點(diǎn)和路徑添加景點(diǎn)和路徑查詢所有路徑查詢最短路徑查詢景點(diǎn)信息修改景點(diǎn)和路徑結(jié) 束 4、模塊劃分（1）主函數(shù)：void main( )（2）void CreateUDN(int v,int a); /* 造圖函數(shù) */（3）void narrate(); /*說明函數(shù)*/（4）void ShortestPath(int num); /*最短路徑函數(shù)*/（5）void output(int sight1,int sight2); /*輸出函數(shù)*/（6）char Menu(); /* 主菜單 */（7）void search(); /*

3、查詢景點(diǎn)信息 */（8）char SearchMenu(); /* 查詢子菜單 */（9）void HaMiTonian(int); /*圖的遍歷 */（10）void Searchpath1(MGraph g);/*查詢兩個(gè)景點(diǎn)間的所有路徑*/（11）void disppath(MGraph g,int i,int j);（12）void path(MGraph g,int i,int j,int k);/*確定路徑上第k+1個(gè)頂點(diǎn)的序號*/（13）void NextValue(int); （14）void display(); /* 顯示遍歷結(jié)果 */（15）int Addnewsight

4、(int n); /*添加新的景點(diǎn)和路徑*/（16）int Deletesight(int n); /*刪除景點(diǎn)和路徑*/5、數(shù)據(jù)結(jié)構(gòu)類型定義typedef struct ArcCell int adj; /* 相鄰接的景點(diǎn)之間的路程 */ArcCell; /* 定義邊的類型 */ typedef struct VertexType int number; /* 景點(diǎn)編號 */ char sight100; /* 景點(diǎn)名稱 */ char description1000; /* 景點(diǎn)描述 */VertexType; /* 定義頂點(diǎn)的類型 */typedef struct VertexType

5、vex20; /* 圖中的頂點(diǎn)，即為景點(diǎn) */ ArcCell arcs2020; /* 圖中的邊，即為景點(diǎn)間的距離 */ int vexnum,arcnum; /* 頂點(diǎn)數(shù)，邊數(shù) */MGraph; /* 定義圖的類型 */6、測試結(jié)果1、查詢景點(diǎn)信息2、 查詢兩景點(diǎn)間最短路徑 3、查詢兩景點(diǎn)間所有路徑4、添加新的景點(diǎn)和路徑5、刪除已有的景點(diǎn)和路徑6、修改刪除已有的景點(diǎn)和路徑7、 實(shí)驗(yàn)心得經(jīng)過幾天的課程設(shè)計(jì)，總的來說收獲還是很大的！首先代碼能力明顯提高，有了想法基本都能順利表達(dá)出來；再者就是數(shù)據(jù)結(jié)構(gòu)的選擇使用能力也有了很大的提高！雖說平時(shí)的實(shí)驗(yàn)課我們也有用各種數(shù)據(jù)做題，但那些都是很明確的知道

6、該做什么操作，存什么，我們的發(fā)揮空間不大一般照做就行，然而這次實(shí)習(xí)我們卻在自主的選擇判斷，這本身就是一個(gè)很大的提高！還有就是算法方面的學(xué)習(xí)有了初步進(jìn)階，如最短路徑，這樣比較簡單的圖論算法能比較熟練的寫出來。但是還是有很多的只是不了解！收獲真的很多，但是最大的收獲可能就是對編程的興趣吧，在一次次的改錯(cuò)，一次次的完成想要的效果后，越寫越有感覺！當(dāng)然還收獲了無知，更確切的說是自知，原來我們現(xiàn)在什么也不算，還有很多有用的只是等著我們?nèi)W(xué)習(xí)！課程設(shè)計(jì)是把我們所學(xué)的理論知識進(jìn)行系統(tǒng)的總結(jié)并應(yīng)用于實(shí)踐的良好機(jī)會(huì)，有利于加強(qiáng)我們用知識理論來分析實(shí)際問題的能力，進(jìn)而加強(qiáng)了我們對知識認(rèn)識的實(shí)踐度，鞏固了我們的理論

7、知識，深化了對知識的認(rèn)識，并為走向社會(huì)打下一個(gè)良好的基礎(chǔ)。8、 源程序#include <string.h> #include <stdio.h> #include <stdio.h>#include <malloc.h>#include <stdlib.h>#define Max 20000typedef struct ArcCellint adj; /* 相鄰接的景點(diǎn)之間的路程 */ArcCell; /* 定義邊的類型 */typedef struct VertexTypeint number; /* 景點(diǎn)編號 */ char s

8、ight100; /* 景點(diǎn)名稱 */ char description1000; /* 景點(diǎn)描述 */VertexType; /* 定義頂點(diǎn)的類型 */typedef structVertexType vex20; /* 圖中的頂點(diǎn)，即為景點(diǎn) */ ArcCell arcs2020; /* 圖中的邊，即為景點(diǎn)間的距離 */ int vexnum,arcnum; /* 頂點(diǎn)數(shù)，邊數(shù) */MGraph; /* 定義圖的類型 */MGraph G; /* 把圖定義為全局變量 */char nameofschool100;int NUM=9;int P2020; /* */int p20;/*全局?jǐn)?shù)

9、組，用來存放路徑上的各頂點(diǎn)*/int visited20;/*全局?jǐn)?shù)組，用來記錄各頂點(diǎn)被訪問的情況*/int a=0;/*全局變量，用來記錄每對頂點(diǎn)之間的所有路徑的條數(shù)*/long int D20; /* 輔助變量存儲最短路徑長度 */int x20=0; void CreateUDN(int v,int a); /* 造圖函數(shù) */void narrate(); /*說明函數(shù)*/void ShortestPath(int num); /*最短路徑函數(shù)*/void output(int sight1,int sight2); /*輸出函數(shù)*/char Menu(); /* 主菜單 */void

10、 search(); /* 查詢景點(diǎn)信息 */char SearchMenu(); /* 查詢子菜單 */void HaMiTonian(int); /* 圖的遍歷 */void Searchpath1(MGraph g);/*查詢兩個(gè)景點(diǎn)間的所有路徑*/void disppath(MGraph g,int i,int j);void path(MGraph g,int i,int j,int k);/*確定路徑上第k+1個(gè)頂點(diǎn)的序號*/void NextValue(int); void display(); /* 顯示遍歷結(jié)果 */int Addnewsight(int n); /*添加新的

11、景點(diǎn)和路徑*/int Deletesight(int n); /*刪除景點(diǎn)和路徑*/void Changesight(); /*修改景點(diǎn)和路徑*/char Changemenu(); /*修改路徑或頂點(diǎn)的選擇菜單*/char Sightmenu(); /*選擇需該景點(diǎn)的菜單*/void main() /* 主函數(shù) */ int v0,v1; char ck; system("color 0"); CreateUDN(NUM,11); do ck=Menu(); switch(ck)case '1': search(); break; case '2&

12、#39;:system("cls");narrate(); printf("nnttt請選擇起點(diǎn)景點(diǎn)（0%d）：",NUM-1); scanf("%d",&v0); printf("ttt請選擇終點(diǎn)景點(diǎn)（0%d）：",NUM-1); scanf("%d",&v1); ShortestPath(v0); /* 計(jì)算兩個(gè)景點(diǎn)之間的最短路徑 */ output(v0,v1); /* 輸出結(jié)果 */ printf("nntttt請按任意鍵繼續(xù).n"); getchar

13、(); getchar();break; case '3':system("cls"); narrate(); x0=1; Searchpath1(G); printf("nntttt請按任意鍵繼續(xù).n"); getchar(); getchar(); break;case'4': system("cls"); narrate(); NUM=Addnewsight(NUM); system("cls"); narrate(); break;case'5': NUM=D

14、eletesight(NUM); break;case'6':Changesight(); break;while(ck!='e'); char Menu() /* 主菜單 */ char c; int flag; do flag=1; system("cls"); narrate(); printf("ntttn"); printf("ttt n"); printf("ttt 1、查詢景點(diǎn)信息 n"); printf("ttt 2、查詢兩景點(diǎn)間最短路徑 n");

15、 printf("ttt 3、查詢兩景點(diǎn)間所有路線 n"); printf("ttt 4、添加新的景點(diǎn)和路徑 n"); printf("ttt 5、刪除已有景點(diǎn)和路徑 n"); printf("ttt 6、修改已有景點(diǎn)和路徑 n"); printf("ttt e、退出 n"); printf("ttt n"); printf("tttn"); printf("tttt請輸入您的選擇："); scanf("%c",&a

16、mp;c); if(c='1'|c='2'|c='3'|c='4'|c='5'|c='6'|c='e') flag=0; while(flag); return c;char SearchMenu() /* 查詢子菜單 */ char c; int flag; do flag=1; system("cls"); narrate(); printf("ntttn"); printf("ttt n"); printf("

17、;ttt 1、按照景點(diǎn)編號查詢 n"); printf("ttt 2、按照景點(diǎn)名稱查詢 n"); printf("ttt e、返回 n"); printf("ttt n"); printf("tttn"); printf("tttt請輸入您的選擇："); scanf("%c",&c); if(c='1'|c='2'|c='e') flag=0; while(flag); return c;void search

18、() /* 查詢景點(diǎn)信息 */ int num; int i; char c; char name20; do system("cls"); c=SearchMenu(); switch (c) case '1': system("cls"); narrate(); printf("nntt請輸入您要查找的景點(diǎn)編號："); scanf("%d",&num); for(i=0;i<NUM;i+) if(num=G.vexi.number) printf("nnttt您要查找景點(diǎn)

19、信息如下:"); printf("nnttt%-25snn",G.vexi.description); printf("nttt按任意鍵返回."); getchar(); getchar(); break; if(i=NUM) printf("nnttt沒有找到！"); printf("nnttt按任意鍵返回."); getchar(); getchar(); break; case '2': system("cls"); narrate(); printf("

20、;nntt請輸入您要查找的景點(diǎn)名稱："); scanf("%s",name); for(i=0;i<NUM;i+) if(!strcmp(name,G.vexi.sight) printf("nnttt您要查找景點(diǎn)信息如下:"); printf("nnttt%-25snn",G.vexi.description); printf("nttt按任意鍵返回."); getchar(); getchar(); break; if(i=NUM) printf("nnttt沒有找到！");

21、 printf("nnttt按任意鍵返回."); getchar(); getchar(); break; while(c!='e');void CreateUDN(int v,int a) /* 造圖函數(shù) */ int i,j; strcpy(nameofschool,"洛陽理工學(xué)院"); G.vexnum=v; /* 初始化結(jié)構(gòu)中的景點(diǎn)數(shù)和邊數(shù) */ G.arcnum=a;for(i=0;i<20;+i) G.vexi.number=i; /* 初始化每一個(gè)景點(diǎn)的編號 */ /* 初始化每一個(gè)景點(diǎn)名及其景點(diǎn)描述 */ strcp

22、y(G.vex0.sight,"東門"); strcpy(G.vex0.description,"學(xué)校正門，圖書館。"); strcpy(G.vex1.sight,"圖書館"); strcpy( G.vex1.description,"藏書100萬冊，環(huán)境優(yōu)雅"); strcpy(G.vex2.sight,"教學(xué)樓"); strcpy(G.vex2.description,"學(xué)生上課的地方"); strcpy(G.vex3.sight,"子衿餐廳"); s

23、trcpy(G.vex3.description,"一餐廳，新裝修過的豪華餐廳"); strcpy(G.vex4.sight,"實(shí)驗(yàn)A樓"); strcpy(G.vex4.description,"辦公室"); strcpy(G.vex5.sight,"B樓"); strcpy(G.vex5.description,"機(jī)房"); strcpy(G.vex6.sight,"C樓"); strcpy(G.vex6.description,"電氣實(shí)驗(yàn)教室");

24、strcpy(G.vex7.sight,"璞院餐廳"); strcpy(G.vex7.description,"二餐廳"); strcpy(G.vex8.sight,"璞院"); strcpy(G.vex8.description,"男生的宿舍樓"); /* 這里把所有的邊假定為20000，含義是這兩個(gè)景點(diǎn)之間是不可到達(dá) */ for(i=0;i<20;+i) for(j=0;j<20;+j) G.arcsij.adj=Max; /* 下邊是可直接到達(dá)的景點(diǎn)間的距離，由于兩個(gè)景點(diǎn)間距離是互相的， 所以要

25、對圖中對稱的邊同時(shí)賦值。 */ G.arcs01.adj=G.arcs10.adj=50; G.arcs13.adj=G.arcs31.adj=70; G.arcs06.adj=G.arcs30.adj=250; G.arcs14.adj=G.arcs41.adj=80; G.arcs24.adj=G.arcs42.adj=100; G.arcs35.adj=G.arcs53.adj=90; G.arcs52.adj=G.arcs25.adj=100; G.arcs46.adj=G.arcs64.adj=75; G.arcs47.adj=G.arcs74.adj=300; G.arcs27.a

26、dj=G.arcs72.adj=400; G.arcs78.adj=G.arcs87.adj=40;void narrate() /* 說明函數(shù) */ int i,k=0; printf("nt*歡迎使用%s校園導(dǎo)游程序*n",nameofschool); printf("t_n"); printf("tt景點(diǎn)名稱tttt景點(diǎn)描述tttn"); printf("t_|_n"); for(i=0;i<NUM;i+) printf("t%c (%2d)%-10stt|t%-25s%cn",3,

27、i,G.vexi.sight,G.vexi.description,3); /* 輸出景點(diǎn)列表 */ k=k+1; printf("t_|_n");void ShortestPath(int num) /* 迪杰斯特拉算法最短路徑函數(shù) num為入口點(diǎn)的編號 */ int v,w,i,t; /* i、w和v為計(jì)數(shù)變量 */ int final20; /* */ int min; for(v=0;v<NUM;v+) finalv=0; /* 假設(shè)從頂點(diǎn)num到頂點(diǎn)v沒有最短路徑 */ Dv=G.arcsnumv.adj;/* 將與之相關(guān)的權(quán)值放入D中存放 */ for(w

28、=0;w<NUM;w+) /* 設(shè)置為空路徑 */ Pvw=0; if(Dv<20000) /* 存在路徑 */ Pvnum=1; /* 存在標(biāo)志置為一 */ Pvv=1; /* 自身到自身 */ Dnum=0; finalnum=1; /* 初始化num頂點(diǎn)屬于S集合 */ /* 開始主循環(huán)，每一次求得num到某個(gè)頂點(diǎn)的最短路徑，并將其加入到S集合 */ for(i=0;i<NUM;+i) /* 其余G.vexnum-1個(gè)頂點(diǎn) */ min=Max; /* 當(dāng)前所知離頂點(diǎn)num的最近距離 */ for(w=0;w<NUM;+w) if(!finalw) /* w頂點(diǎn)在

29、v-s中 */ if(Dw<min) /* w頂點(diǎn)離num頂點(diǎn)更近 */ v=w; min=Dw; finalv=1; /* 離num頂點(diǎn)更近的v加入到s集合 */ for(w=0;w<NUM;+w) /* 更新當(dāng)前最短路徑極其距離 */ if(!finalw&&(min+G.arcsvw.adj)<Dw)/* 不在s集合，并且比以前所找到的路徑都短就更新當(dāng)前路徑 */ Dw=min+G.arcsvw.adj; for(t=0;t<NUM;t+) Pwt=Pvt; Pww=1; void output(int sight1,int sight2) /*

30、輸出函數(shù) */int a,b,c,d,q=0; a=sight2; /* 將景點(diǎn)二賦值給a */ if(a!=sight1) /* 如果景點(diǎn)二不和景點(diǎn)一輸入重合，則進(jìn)行. */printf("nt從%s到%s的最短路徑是",G.vexsight1.sight,G.vexsight2.sight);/* 輸出提示信息 */ printf("t(最短距離為 %dm.)nnt",Da); /* 輸出sight1到sight2的最短路徑長度，存放在D數(shù)組中 */ printf("t%s",G.vexsight1.sight); /* 輸出景點(diǎn)

31、一的名稱 */ d=sight1; /* 將景點(diǎn)一的編號賦值給d */ for(c=0;c<NUM;+c) gate:; /* 標(biāo)號，可以作為goto語句跳轉(zhuǎn)的位置 */ Pasight1=0; for(b=0;b<NUM;b+) if(G.arcsdb.adj<20000&&Pab) /* 如果景點(diǎn)一和它的一個(gè)臨界點(diǎn)之間存在路徑且最短路徑 */ printf("->%s",G.vexb.sight); /* 輸出此節(jié)點(diǎn)的名稱 */ q=q+1; /* 計(jì)數(shù)變量加一，滿8控制輸出時(shí)的換行 */ Pab=0; d=b; /* 將b作為出

32、發(fā)點(diǎn)進(jìn)行下一次循環(huán)輸出，如此反復(fù) */ if(q%8=0) printf("n"); goto gate; void Searchpath1(MGraph g)/*查詢兩個(gè)景點(diǎn)間的所有路徑*/int l=0;int k=0;int i,j; printf("選擇出發(fā)景點(diǎn)："); scanf("%d",&i); printf("選擇目地景點(diǎn)："); scanf("%d",&j); for(;k<g.vexnum;k+)/*g.vexnumber表示網(wǎng)中的頂點(diǎn)個(gè)數(shù)*/ if(i

33、=g.vexk.number) i=k;/*在網(wǎng)中找到其編號與輸入的出發(fā)景點(diǎn)的編號相同的頂點(diǎn)*/ for(;l<g.vexnum;l+) if(j=g.vexl.number) j=l;/*在網(wǎng)中找到其編號與輸入的目地景點(diǎn)的編號相同的頂點(diǎn)*/ printf("n從%s到%s的所有游覽路徑有:nn",g.vexi.sight,g.vexj.sight);/*輸出出發(fā)景點(diǎn)和目地景點(diǎn)的名稱*/ disppath(g,i,j);/*調(diào)用disppath函數(shù),用來輸出兩個(gè)景點(diǎn)間的所有路徑*/void disppath(MGraph g,int i,int j)int k;p0=

34、i;for(k=0;k<g.vexnum;k+)visitedi=0;/*初始化各頂點(diǎn)的訪問標(biāo)志位，即都為未訪問過的*/a=0;/*初始化路徑的條數(shù)*/path(g,i,j,0);/*通過調(diào)用path函數(shù)，找到從vi到vj的所有路徑并輸出*/void path(MGraph g,int i,int j,int k)/*確定路徑上第k+1個(gè)頂點(diǎn)的序號*/int s;if(pk=j)/*找到一條路徑*/a+;/*路徑的條數(shù)值加1*/printf("第%d條:t",a);for(s=0;s<=k-1;s+)/*輸出一條路徑*/printf("%s"

35、,g.vexps.sight);printf("->");/cout<<g.vexps.sight;printf("%sn",g.vexps.sight); s=0;while(s<g.vexnum)if(s!=i)/*保證找到的是簡單路徑*/if(g.arcspks.adj!=Max&&visiteds=0)/*當(dāng)vk與vs之間有邊存在且vs未被訪問過*/visiteds=1;/*置訪問標(biāo)志位為1,即已訪問的*/pk+1=s;/*將頂點(diǎn)s加入到p數(shù)組中*/ path(g,i,j,k+1);/*遞歸調(diào)用之*/ vi

36、siteds=0;/*重置訪問標(biāo)志位為0，即未訪問的，以便該頂點(diǎn)能被重新使用*/s+;int Addnewsight(int n)int i;char sight100,description1000;int length;printf("請輸入新景點(diǎn)的名稱：n");scanf("%s",&sight);printf("請輸入新景點(diǎn)的相關(guān)信息：n");scanf("%s",&description);strcpy(G.vexn.sight,sight); strcpy(G.vexn.descript

37、ion,description);G.vexn.number=n;for(i=0;i<n;i+) system("cls"); narrate();printf("請輸入此景點(diǎn)到第%d個(gè)景點(diǎn)的距離（單位：m）（同一景點(diǎn)或不可到達(dá)用20000表示）：n",i);scanf("%d",&length);if(length!=20000)G.arcnum+;G.arcsni.adj=G.arcsin.adj=length;n+;G.vexnum+;return n;int Deletesight(int n)int i;int

38、 j;char c;int num;char name20;system("cls"); c=SearchMenu(); switch (c) case '1': system("cls"); narrate(); printf("nntt請輸入您要?jiǎng)h除景點(diǎn)的編號："); scanf("%d",&num); for(i=0;i<NUM;i+) if(num=G.vexi.number) for(j=0;j<NUM;j+) if(G.arcsij.adj!=20000) G.arc

39、num-; G.arcsij.adj=G.arcsji.adj=20000; for(;num<NUM;num+)strcpy(G.vexnum.sight,G.vexnum+1.sight);strcpy(G.vexnum.description,G.vexnum+1.description); n-; printf("nttt按任意鍵返回."); getchar(); getchar(); break; if(i=NUM) printf("nnttt沒有找到！"); printf("nnttt按任意鍵返回."); getch

40、ar(); getchar(); break; case '2': system("cls"); narrate(); printf("nntt請輸入您要?jiǎng)h除景點(diǎn)的名稱："); scanf("%s",name); for(i=0;i<NUM;i+) if(!strcmp(name,G.vexi.sight) num=i; for(j=0;j<NUM;j+) if(G.arcsij.adj!=20000) G.arcnum-;G.arcsij.adj=G.arcsji.adj=20000; for(;num&

41、lt;NUM;num+) strcpy(G.vexnum.sight,G.vexnum+1.sight); strcpy(G.vexnum.description,G.vexnum+1.description); n-; printf("nttt按任意鍵返回."); getchar(); getchar(); break; if(i=NUM) printf("nnttt沒有找到！"); printf("nnttt按任意鍵返回."); getchar(); getchar(); break; return n;char Changeme

42、nu()char c; int flag; do flag=1; system("cls"); narrate(); printf("ntttn"); printf("ttt n"); printf("ttt 1、修改景點(diǎn)信息 n"); printf("ttt 2、修改道路信息 n"); printf("ttt e、返回 n"); printf("ttt n"); printf("tttn"); printf("tttt請輸入您的選擇："); scanf("%c",&c); if(c='1'|c='2'|c='e') flag=0; while(flag); return c;char Sightmenu()char c;int flag;doflag=1;system("cls"); narrate(); printf("ntttn"); printf("ttt n"); printf("ttt 1、修改景點(diǎn)名稱 n"); printf