校園導(dǎo)游咨詢(xún)程序

1、實(shí)驗(yàn)三：校園導(dǎo)游咨詢(xún)一、 設(shè)計(jì)方案簡(jiǎn)介設(shè)計(jì)一個(gè)校園導(dǎo)游程序，為來(lái)訪的客人提供各種信息查詢(xún)服務(wù)。1）設(shè)計(jì)你所在學(xué)校的校園平面圖，2）為來(lái)訪客人提供圖中任意景點(diǎn)相關(guān)信息的查詢(xún)。3）為來(lái)訪客人提供圖中任意景點(diǎn)的問(wèn)路查詢(xún)，即查詢(xún)?nèi)我鈨蓚€(gè)景點(diǎn)之間的一條最短的簡(jiǎn)單路徑。二、 設(shè)計(jì)題目實(shí)現(xiàn):實(shí)際需求1）設(shè)計(jì)你所在學(xué)校的校園平面圖，所含景點(diǎn)不少于10個(gè)。以圖中頂點(diǎn)表示校園內(nèi)各景點(diǎn)，存放景點(diǎn)名稱(chēng)、代號(hào)、簡(jiǎn)介等信息：以邊表示路徑，存放路徑長(zhǎng)度等相關(guān)信息。2）為來(lái)訪客人提供圖中任意景點(diǎn)相關(guān)信息的查詢(xún)。3）為來(lái)訪客人提供圖中任意景點(diǎn)的問(wèn)路查詢(xún)，即查詢(xún)?nèi)我鈨蓚€(gè)景點(diǎn)之間的一條最短的簡(jiǎn)單路徑。2）概要設(shè)計(jì)1、 校園全景一覽

2、圖、顯示出校園的平面圖。2、 提供校園中任意景點(diǎn)問(wèn)路查詢(xún)，即求任意兩個(gè)景點(diǎn)之間的所有路徑。3、提供校園圖中多個(gè)景點(diǎn)的最佳訪問(wèn)路線查詢(xún)，即求途徑這過(guò)個(gè)景點(diǎn)的最佳（短）路徑。1功能模塊圖；void Map();/校園地圖void CreateGraph();/創(chuàng)建圖void OutputPlace();/輸出景點(diǎn)列表void SearchPlace();/查詢(xún)景點(diǎn)信息void SearchPath();/查詢(xún)最短路徑void Shortpath(int i);/計(jì)算最短路徑void Output(int sight1,int sight2);/輸出函數(shù)2各個(gè)模塊詳細(xì)的功能描述。Map();/顯示校

3、園整體的地圖、包含學(xué)校各景點(diǎn)的詳細(xì)位置CreateGraph();/創(chuàng)建圖、主要用來(lái)保存各景點(diǎn)信息OutputPlace();/輸出景點(diǎn)列表、供選擇景點(diǎn)信息查詢(xún)時(shí)使用SearchPlace();/查詢(xún)景點(diǎn)信息、景點(diǎn)的名稱(chēng)及介紹SearchPath();/查詢(xún)最短路徑、兩景點(diǎn)間最短距離Shortpath(int i);/計(jì)算兩景點(diǎn)間最短路徑Output(int sight1,int sight2);/輸出兩景點(diǎn)最短路徑及信息四詳細(xì)設(shè)計(jì)Main()1功能函數(shù)的調(diào)用關(guān)系圖 CreateGraph() SearchPlace() Map() SearchPath()Outputplace()Short

4、path(i);Output(i,j);2各功能函數(shù)的數(shù)據(jù)流程圖全局變量Graph G;int pathNUMNUM;int DNUM;3 重點(diǎn)設(shè)計(jì)及編碼 重點(diǎn)設(shè)計(jì)：求最短路徑 編碼：void Shortpath(int num)/迪杰斯特拉算法最短路徑 int v,w,i,t;/i、w和v為計(jì)數(shù)變量/t表示景點(diǎn)個(gè)數(shù)int finalNUM; /標(biāo)志數(shù)組、用來(lái)存放頂點(diǎn)的信息int min;/記錄權(quán)值、最終輸出路徑for(v=0;vNUM;v+)finalv=0; /假設(shè)從頂點(diǎn)num到頂點(diǎn)v沒(méi)有最短路徑Dv=G.arcnumv.length;/將num到其余頂點(diǎn)的最短路徑長(zhǎng)度初始化為權(quán)值for(

5、w=0;wNUM;w+) pathvw=0;/初始化從v到w的路徑值if(DvMAX) /存在路徑pathvnum=1; /存在標(biāo)志置為一pathvv=1; /自身到自身Dnum=0;/初始化新路徑 finalnum=1; /初始化num頂點(diǎn)屬于final集合 /開(kāi)始主循環(huán),每一次求得num到某個(gè)頂點(diǎn)的最短路徑，并將其加入到final集合 for(i=0;iNUM;+i) / 其余G.vexnum-1個(gè)頂點(diǎn) min=MAX; /當(dāng)前所知離頂點(diǎn)num的最近距離for(w=0;wNUM;+w)if(!finalw) /w頂點(diǎn)在v-s中 if(Dwmin) /w頂點(diǎn)離num頂點(diǎn)更近 v=w;min=

6、Dw; finalv=1; /離num頂點(diǎn)更近的v加入到s集合 for(w=0;wNUM;+w) /更新當(dāng)前最短路徑極其距離 if(!finalw&(min+G.arcvw.length)Dw)/不在s集合，并且比以前所找到的路徑都短就更新當(dāng)前路徑 Dw=min+G.arcvw.length;/更新路徑for(t=0;tNUM;t+)pathwt=pathvt;pathww=1;void Output(int sight1,int sight2) / 輸出函數(shù) int a,b,c,d,q=0;/a、b、c和d為計(jì)數(shù)變量/q控制計(jì)數(shù)變量、用于換行a=sight2; /將景點(diǎn)二賦值給a if(a!

7、=sight1) / 如果景點(diǎn)二不和景點(diǎn)一輸入重合，則進(jìn)行. printf(tttttt從%s到%s的最短路徑是:nnttttt,G.,G.);/輸出提示信息/輸出sight1到sight2的最短路徑長(zhǎng)度，存放在D數(shù)組中printf(t%s,G.); /輸出景點(diǎn)一的名稱(chēng) d=sight1; /將景點(diǎn)一的編號(hào)賦值給dfor(c=0;cNUM;+c)gate:; /標(biāo)號(hào)，可以作為goto語(yǔ)句跳轉(zhuǎn)的位置 pathasight1=0; for(b=0;bNUM;b+) if(G.arcdb.lengt

8、h%s,G.); /輸出此節(jié)點(diǎn)的名稱(chēng) q=q+1; /計(jì)數(shù)變量加一，滿8控制輸出時(shí)的換行 pathab=0; d=b; /將b作為出發(fā)點(diǎn)進(jìn)行下一次循環(huán)輸出，如此反復(fù) if(q%14=0) printf(n); goto gate; printf(nntttttt最短距離為 %dm.nnt,Da); 五測(cè)試數(shù)據(jù)及運(yùn)行結(jié)果系統(tǒng)主界面學(xué)校平面圖學(xué)校景點(diǎn)圖最短路徑信息查詢(xún)異常信息三、 設(shè)計(jì)評(píng)述:設(shè)計(jì)者對(duì)本設(shè)計(jì)的評(píng)述及通過(guò)設(shè)計(jì)的收獲體會(huì)1 改進(jìn)方案系統(tǒng)還有部分漏洞未能修復(fù)、不夠絕對(duì)的穩(wěn)定、還需改進(jìn)！求最短路徑時(shí)可以采用比較簡(jiǎn)單的哈密爾頓算法。 本次課程設(shè)計(jì)僅完成了要求的基本功能、

9、由于平時(shí)掌握的不夠好以及時(shí)間關(guān)系未能完成選作功能、這是一大缺陷！另外通過(guò)本次課程設(shè)計(jì)也更好的掌握了平時(shí)所學(xué)的知識(shí)、通過(guò)實(shí)踐學(xué)到了許多課本上沒(méi)有的知識(shí)！2 體會(huì)以后要加強(qiáng)動(dòng)手時(shí)間能力、多與同學(xué)交流算法精髓！在編寫(xiě)程序中盡量做到獨(dú)立完成、對(duì)于自己想要完成的問(wèn)題要主動(dòng)編程完成、這樣自己是一個(gè)很大的提升、也能學(xué)到很多的知識(shí)、熟練編程！報(bào)告最后有兩部分附錄附錄一：參考資料1、C語(yǔ)言程序設(shè)計(jì)（譚浩強(qiáng)版）2、數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版） 編著：嚴(yán)蔚敏、吳偉民 清華大學(xué)出版社附錄二：源程序 （將所有的源程序附在最后的附錄中）/ 查詢(xún)景點(diǎn)信息.cpp : Defines the entry point for the

10、console application./#include stdafx.h#include stdio.h#include #include #include #include #include #define NUM 20#define MAX #define FALSE 0#define TURE 1typedef struct ArcNode int length; /路徑長(zhǎng)度 ArcNode, *ArcLink; /邊結(jié)點(diǎn)的定義typedef struct VertexNode int number; /景點(diǎn)的編號(hào) char *name; /景點(diǎn)的名稱(chēng) char *info; /景點(diǎn)

11、的簡(jiǎn)介 VertexNode; /頂點(diǎn)結(jié)點(diǎn)的定義typedef struct Graph VertexNode vertexNUM; ArcNode arcNUMNUM; int vexnum,arcnum; /圖的頂點(diǎn)數(shù)，邊數(shù) Graph; /圖的定義Graph G;int pathNUMNUM;int DNUM;void CreateGraph();/創(chuàng)建圖void Map();/學(xué)校地圖void outputplace();/輸出校園景點(diǎn)名稱(chēng)void searchplace();/查詢(xún)景點(diǎn)信息void searchpath();/查詢(xún)最短路徑void shortestpath_DIJ(i

12、nt num);/迪杰斯特拉算法最短路徑void output(int sight1,int sight2);/輸出函數(shù)void CreateGraph()/創(chuàng)建圖int i,j;G.vexnum=12;G.arcnum=17;for(i=1;iNUM;i+) G.vertexi.number=i;G.=太原理工大學(xué)正門(mén);G.=學(xué)校正門(mén)位于學(xué)校的正南方向、是進(jìn)入學(xué)校前的第一道亮麗ntt的風(fēng)景線!n;G.=電機(jī)館;G.=電機(jī)館是數(shù)學(xué)系，電子信息系，自動(dòng)化，通訊等學(xué)院的學(xué)院樓!n;G.vertex3.n

13、ame=科學(xué)樓;G.=科學(xué)樓是我?？蒲袡C(jī)構(gòu)場(chǎng)所，也是山西省網(wǎng)關(guān)所在地!n;G.=多學(xué)科樓;G.=科學(xué)樓是計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，軟件學(xué)院，電子信息學(xué)院，ntt土木，建筑的學(xué)院樓，也是我校最好的學(xué)院樓!n;G.=圖書(shū)館;G.=太原理工圖書(shū)館經(jīng)歷了初創(chuàng)時(shí)期，發(fā)展時(shí)期，面向現(xiàn)代化的轉(zhuǎn)型時(shí)期。ntt如今，她已經(jīng)發(fā)展成為資源豐富，現(xiàn)代化，綜合性，開(kāi)放式的圖書(shū)館!n;G.=機(jī)械館;G.=機(jī)械館是我校百年高校最有力的體現(xiàn)!ntt是歐式風(fēng)格建筑，

14、外觀宏偉氣派ntt為機(jī)械學(xué)院的學(xué)院樓!n;G.=籃球場(chǎng);G.=籃球場(chǎng)全橡膠場(chǎng)，每天這里打球人員特多，我校籃球隊(duì)ntt在歷年的CUBA聯(lián)賽上取得佳績(jī)，是我們引以為豪的校隊(duì)!n;G.=清澤餐廳;G.=清澤餐廳是我校最現(xiàn)代化的食堂，提供各種美食!n;G.=學(xué)生宿舍;G.=這里是我校學(xué)生宿舍集中所在地，包括本科生，研究生宿舍，ntt是我們?cè)趯W(xué)校的家!n;G.=文體中心;G.=文體中心包括體育館，體育場(chǎng)，各種體

15、育娛樂(lè)場(chǎng)所，供學(xué)生ntt體育鍛煉的地方!n;G.=國(guó)際交流中心;G.=國(guó)際交流中心是外國(guó)留學(xué)生居住學(xué)習(xí)科研的場(chǎng)所!n;for(i=0;iNUM;+i)for(j=0;j0 & num=G.vexnum) /判定信息輸入正確for(i=1;i11):); scanf(%d,&i); printf(tt最終景點(diǎn)編號(hào)(1-11):); scanf(%d,&j); getchar();if(iG.vexnum | iG.vexnum | j0 | i=j) printf(tt輸入信息錯(cuò)誤!nn); else shortestpath_DIJ(i);o

16、utput(i,j);printf(ntt是否繼續(xù)查詢(xún)最短路徑(y/n):);c=getchar(); getchar(); system(cls);void shortestpath_DIJ(int num)/迪杰斯特拉算法最短路徑int v,w,i,t;/i、w和v為計(jì)數(shù)變量/t表示景點(diǎn)個(gè)數(shù)int finalNUM; /標(biāo)志數(shù)組、用來(lái)存放頂點(diǎn)的信息int min;/記錄權(quán)值、最終輸出路徑for(v=0;vNUM;v+)finalv=FALSE; /假設(shè)從頂點(diǎn)num到頂點(diǎn)v沒(méi)有最短路徑Dv=G.arcnumv.length;/將num到其余頂點(diǎn)的最短路徑長(zhǎng)度初始化為權(quán)值for(w=0;wNU

17、M;w+) pathvw=FALSE;/初始化從v到w的路徑值if(DvMAX) /存在路徑pathvnum=TURE; /存在標(biāo)志置為一pathvv=TURE; /自身到自身Dnum=0;/初始化新路徑 finalnum=TURE; /初始化num頂點(diǎn)屬于final集合 /開(kāi)始主循環(huán),每一次求得num到某個(gè)頂點(diǎn)的最短路徑，并將其加入到final集合 for(i=0;iNUM;+i) / 其余G.vexnum-1個(gè)頂點(diǎn) min=MAX; /當(dāng)前所知離頂點(diǎn)num的最近距離for(w=0;wNUM;+w)if(!finalw) /w頂點(diǎn)在v-s中 if(Dwmin) /w頂點(diǎn)離num頂點(diǎn)更近 v=

18、w;min=Dw; finalv=TURE; /離num頂點(diǎn)更近的v加入到s集合 for(w=0;wNUM;+w) /更新當(dāng)前最短路徑極其距離 if(!finalw&(min+G.arcvw.length)Dw)/不在s集合，并且比以前所找到的路徑都短就更新當(dāng)前路徑 Dw=min+G.arcvw.length;/更新路徑for(t=0;tNUM;t+)pathwt=pathvt;pathww=TURE;void output(int sight1,int sight2)/輸出函數(shù) int a,b,c,d,q=0;/a、b、c和d為計(jì)數(shù)變量/q控制計(jì)數(shù)變量、用于換行a=sight2; /將景點(diǎn)二

19、賦值給a if(a!=sight1) / 如果景點(diǎn)二不和景點(diǎn)一輸入重合，則進(jìn)行. printf(tt從%s到%s的最短路徑是:nntt,G.,G.);/輸出提示信息/輸出sight1到sight2的最短路徑長(zhǎng)度，存放在D數(shù)組中printf(%s,G.); /輸出景點(diǎn)一的名稱(chēng) d=sight1; /將景點(diǎn)一的編號(hào)賦值給dfor(c=0;cNUM;+c)gate:; /標(biāo)號(hào)，可以作為goto語(yǔ)句跳轉(zhuǎn)的位置 pathasight1=FALSE; for(b=0;bNUM;b+) if(G.arcdb.length%s,G.); /輸出此節(jié)點(diǎn)的名稱(chēng) q=q+1; /計(jì)數(shù)變量加一，滿8控制輸出時(shí)的換行 pathab=FALSE; d=b; /將b作為出發(fā)點(diǎn)進(jìn)行下一次循環(huán)輸出，如此反復(fù) i