數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)圖

1、實(shí)驗(yàn)7：圖的應(yīng)用一、實(shí)驗(yàn)?zāi)康膱D是應(yīng)用極為廣泛的數(shù)據(jù)結(jié)構(gòu)，也是這門課程的重點(diǎn)，繼續(xù)使學(xué)生更了解數(shù)據(jù)結(jié)構(gòu)加操作的程序設(shè)計(jì)觀點(diǎn)。二、問題描述給出一張某公園的導(dǎo)游圖，游客通過終端詢問可知：a) 從某一景點(diǎn)到另一個(gè)景點(diǎn)的最短路徑。b) 游客從公園大門進(jìn)入，選一條最佳路線，使游客可以不重復(fù)的游覽各景點(diǎn)，最后回到出口。三、實(shí)驗(yàn)要求1、將導(dǎo)游圖看作一張帶權(quán)無向圖，頂點(diǎn)表示公園的各個(gè)景點(diǎn)，邊表示各景點(diǎn)之間的道路，邊上的權(quán)值表示距離，選擇適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)。2、為游客提供圖中任意景點(diǎn)相關(guān)信息的查詢；1、 為游客提供任意兩個(gè)景點(diǎn)之間的一條最短的簡(jiǎn)單路徑。2、 為游客選擇最佳游覽路徑。 四、實(shí)驗(yàn)環(huán)境PC微機(jī)DOS操作系統(tǒng)

2、或 Windows 操作系統(tǒng)Turbo C 程序集成環(huán)境或 Visual C+ 程序集成環(huán)境 五、實(shí)驗(yàn)步驟1、設(shè)計(jì)公園平面圖，圖中頂點(diǎn)表示公園的各個(gè)景點(diǎn)，存放名稱、代號(hào)、簡(jiǎn)介等信息；邊表示各景點(diǎn)之間的道路，邊上的權(quán)值表示距離，選擇適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)；2、設(shè)計(jì)圖的最短路徑算法，如果有幾條路徑長(zhǎng)度相同，選擇途徑景點(diǎn)較少的路徑給游客；3、設(shè)計(jì)圖的深度優(yōu)先搜索算法，如果有多種路徑可選，則選帶權(quán)路徑最短的路線給游客；4、選擇適當(dāng)語言實(shí)現(xiàn)算法；3、 調(diào)試程序。 六、測(cè)試數(shù)據(jù) 可根據(jù)實(shí)際情況指定。 測(cè)試數(shù)據(jù)見南昌大學(xué)平面示意圖。七、實(shí)驗(yàn)報(bào)告要求1、 問題描述； 該程序包擴(kuò)以下內(nèi)容： （1）設(shè)計(jì)學(xué)校的校園平面圖，

3、所含景點(diǎn)為9個(gè)。（2）以圖中頂點(diǎn)表示校內(nèi)各景點(diǎn)，存放景點(diǎn)名稱、代號(hào)、間介等信息；以邊表示路徑，存放路徑長(zhǎng)度等相關(guān)信息。（3）為來訪客人提供圖中任意景點(diǎn)相關(guān)信息的查詢。（4）提供途中任意景點(diǎn)問路查詢，即求任意兩個(gè)景點(diǎn)間的一條最短的簡(jiǎn)單路徑。（5）提供途中任意景點(diǎn)問路查詢，即求任意兩個(gè)景點(diǎn)間的所有路徑。（6）提供校園圖中多個(gè)景點(diǎn)的最佳訪問路線查詢，即求途經(jīng)這多個(gè)景點(diǎn)的最佳（短）路徑。設(shè)計(jì)思路：對(duì)系統(tǒng)功能抽象，分析問題描述。首先，平面圖用輸出模擬；存儲(chǔ)景點(diǎn)信息采用結(jié)構(gòu)體；對(duì)各景點(diǎn)用字母代替，字母組成圖，通過對(duì)圖的操作，狄克斯特拉算法求出指定最短路徑及一點(diǎn)到其它所有點(diǎn)的最短路徑，遞歸進(jìn)行圖的遍歷求兩點(diǎn)

4、所有路徑。由此可實(shí)現(xiàn)以上所有功能。2、 圖的建立圖的建立：這是一個(gè)無向帶權(quán)圖，實(shí)際上無向帶權(quán)圖與有向帶權(quán)圖相似，采用鄰接矩陣存儲(chǔ)比較方便。鄰接矩陣的結(jié)點(diǎn)結(jié)構(gòu)體如下：其賦值如下：3、 圖的最短路徑算法算法思想：設(shè)置兩個(gè)結(jié)點(diǎn)集合S和T，集合S中存放已找到的最短路徑的結(jié)點(diǎn)，集合T中存放當(dāng)前還沒找到的最短路徑的結(jié)點(diǎn)。初始狀態(tài)時(shí)，集合S中只包含源點(diǎn)，沒為v0，然后不斷的從集合T中選擇到源點(diǎn)v0的路徑長(zhǎng)度最短的結(jié)點(diǎn)u加入到集合S中，集合S中每加入一新的結(jié)點(diǎn)u，都要修改源點(diǎn)v0到集合T中剩余結(jié)點(diǎn)的當(dāng)前最短路徑長(zhǎng)度值，集合T中各點(diǎn)的新的當(dāng)前最短路徑長(zhǎng)度值為原來的當(dāng)前最短路徑長(zhǎng)度值，與結(jié)點(diǎn)u的最短路徑長(zhǎng)度值加上

5、結(jié)點(diǎn)u到該結(jié)點(diǎn)的路徑長(zhǎng)度值（即為從源點(diǎn)結(jié)點(diǎn)u到達(dá)該結(jié)點(diǎn)的路徑長(zhǎng)度）中的較小者。此過程不斷重復(fù)，直到集合T中的對(duì)號(hào)點(diǎn)全部加到集合S中為止。算法實(shí)現(xiàn)如下： void Dijkstra(MGraph g,int v, int to) /Dijkstra g圖中v為起點(diǎn)求出到所有點(diǎn)的最短路徑 int distMAXV,pathMAXV; /dist存路徑 path存頂點(diǎn)int sMAXV; /標(biāo)記int mindis,i,j,u; for(i=0;ig.n;i+) disti=g.edgesvi; si=0; if(g.edgesviINF) pathi=v; else pathi=-1; sv=1;

6、pathv=0; for(i=0;ig.n;i+) mindis=INF; for(j=0;jg.n;j+) if(sj=0&distjmindis) u=j; mindis=distj; su=1; for(j=0;jg.n;j+) if(sj=0) if(g.edgesujINF&distu+g.edgesujdistj) distj=distu+g.edgesuj; pathj=u; Dispath(dist,path,s,g.n,v,to); 4、 公園平面圖； 5、 程序的測(cè)試結(jié)果和問題（0） 進(jìn)入系統(tǒng)（1） 瀏覽學(xué)校景點(diǎn)（2） 查找單個(gè)景點(diǎn)（3） 查看學(xué)校平面示意圖（4） 推薦路線

7、（5） 景點(diǎn)最短路線（6） 兩點(diǎn)所有路徑（7） 退出6、 實(shí)驗(yàn)總結(jié)。 身是數(shù)據(jù)結(jié)構(gòu)中最復(fù)雜的一種，所以其有關(guān)操作的算法自然也就相對(duì)于其他數(shù)據(jù)結(jié)構(gòu)更為復(fù)雜，也更為巧妙，最充分體現(xiàn)了數(shù)據(jù)結(jié)構(gòu)對(duì)算法的描述作用。實(shí)驗(yàn)中，圖的存儲(chǔ)是以鄰接矩陣來表示的，鄰接矩陣存儲(chǔ)易于理解，方便存儲(chǔ)，但是修改起來就有問題了，所以我沒能將思考題1給做出來。實(shí)驗(yàn)中的一個(gè)重要算法，Dijkstra算法是圖在日常應(yīng)用中最突出的例子，基于此，我加深了對(duì)該算法的認(rèn)知，雖然現(xiàn)在自己寫出來仍熱有難度，但是理解了思想就離成功不遠(yuǎn)了。最后，聲明一下，這個(gè)程序的大部分出于網(wǎng)上，自己只是做到了，理解、修改、整理再創(chuàng)作的過程。八、思考題1、 擴(kuò)充

8、景點(diǎn)數(shù)和道路。2、 試著提供圖的多個(gè)景點(diǎn)的最佳訪問路線查詢。九、附錄 本部分包含三個(gè)文件，sight.h主要是對(duì)景區(qū)的構(gòu)建，描述和展示。graph.h則主要對(duì)景區(qū)的操作算法。main.cpp為程序主程序，簡(jiǎn)單地調(diào)用graph.h中的操作，程序力求交互性好，界面友好，但是是基于DOS，所以再美化也是不盡如人意的。以下為程序源碼，可能由于粘貼過程中，可能會(huì)導(dǎo)致部分源碼出現(xiàn)不整齊。sight.h/景點(diǎn)及景點(diǎn)的相關(guān)函數(shù)#ifndef Sighth#define Sighth#include#include#include#include#includeconio.h#includevoid stcpy

9、(char str1,char str2 )/定義定符串賦值int i,len;len=strlen(str2);for(i=0;ilen;i+) str1i=str2i; str1len=0; /字符串1結(jié)束class Sight/定義景點(diǎn)類public:char SN;char pl_name20; /景點(diǎn)名稱char pl_sy1000; /景點(diǎn)簡(jiǎn)介Sight(char s,char pl,char ps) SN=s; stcpy(pl_name,pl); stcpy(pl_sy,ps);friend void browse(); /瀏覽友元函數(shù);/定義景點(diǎn) Sight A(A,學(xué)校大門

10、,大門由集散廣場(chǎng)、大門、游廊、門衛(wèi)室、門前廣場(chǎng)、清水平臺(tái)及水景區(qū)組成。學(xué)校大門是亞洲最大的校門。);Sight B(B,和平女神像,世界和平自由女神像位于大門前的集散廣場(chǎng),作品由著名藝術(shù)家南昌大學(xué)遙遠(yuǎn)教授設(shè)計(jì)，以紀(jì)念諾曼底登陸60周年，現(xiàn)已成為世界和平的象征。);Sight C(C,體育館,南昌大學(xué)前湖校區(qū)體育館內(nèi)部主要分為比賽館、訓(xùn)練館和功能設(shè)施用房，宛如伏在南昌大學(xué)美麗校園山丘上的一塊巨石。); Sight D(D,游泳館,又稱錢紅游泳俱樂部，以服務(wù)廣大昌大學(xué)子及教職員工為主旨，同時(shí)對(duì)外開放經(jīng)營，集教學(xué)、健身、休閑、娛樂為一體的服務(wù)機(jī)構(gòu)。);Sight E(E,商業(yè)街,我們學(xué)校最繁華的商業(yè)

11、街，是大家主要的消費(fèi)場(chǎng)所,從生活用品到小吃零食,各色風(fēng)味,商業(yè)街連著后街構(gòu)成了我們最好的消費(fèi)園地。);Sight F(F,教學(xué)主樓,這是紅黃色相間雄偉的建筑,由南昌大學(xué)建筑設(shè)計(jì)院設(shè)計(jì)，位于前湖校區(qū)北部，占地面積2.5公頃，東西兩面為天然的潤(rùn)溪湖，西北兩面為校園道路。);Sight G(G,正氣廣場(chǎng),正氣廣場(chǎng)是一座半徑為92米，占地3萬平方米的圓形下沉式（深六米）萬人廣場(chǎng)，依臨正氣龍。);Sight H(H,圖書館,南昌大學(xué)圖書館現(xiàn)有館舍面積6萬余平方米， 我們的圖書館集借、藏、閱多功能服務(wù)為一體。); Sight I(I,天健園,天健園在校車的終點(diǎn)站，這里是理工科學(xué)生的宿舍樓，服務(wù)大樓則主要提

12、供各種服務(wù)，包括購物、打印、理發(fā)、各色小吃之類，但倘若你要極致的享受，還是去商業(yè)街吧!); void Gprint()/地圖cout*南昌大學(xué)前湖校區(qū)平面示意圖(單位：M)*endl;coutendl;cout D游泳館 C體育館 endl; cout 150 endl; cout endl; cout 250 endl; cout E商業(yè)街 F教學(xué)主樓 endl;cout 200 A B endl;cout G正氣廣場(chǎng) 學(xué) 和 endl; cout 校 平 endl;cout 800 400 200 100 女 endl;cout 400 大 神 endl;cout 門 像 endl;cou

13、t I天健園 H圖書館 endl;cout 300 endl; cout endl; coutendl;void S_print(Sight item)/單個(gè)景點(diǎn)輸出函數(shù)cout item.SN. item.pl_namen 簡(jiǎn)介：item.pl_syendlendl;void browse()/輸出所有景點(diǎn)信息system(cls);cout -南昌大學(xué)景點(diǎn)介紹-endl;S_print(A);S_print(B);S_print(C);S_print(D);S_print(E);S_print(F);S_print(G);S_print(H);S_print(I);system(pause

14、);system(cls);void FunMenue()/功能菜單 cout endl;cout -歡迎使用南昌大學(xué)導(dǎo)游幫助小程序- endl;cout endl;cout 1.瀏覽學(xué)校景點(diǎn) 2.查找單個(gè)景點(diǎn)信息 endl;cout 3.學(xué)校地圖平面示意圖 4.路線推薦 endl;cout 5.景點(diǎn)最短線路 6.兩景點(diǎn)所有路徑 endl;cout 7.退出系統(tǒng) endl;cout endl;void FunMenue2()/景點(diǎn)菜單cout -南昌大學(xué)大學(xué)景點(diǎn)-endl;cout A. 學(xué)校大門 B. 和平女神像endl;cout C. 體 育 館 D. 游 泳 館 endl;cout E.

15、 商 業(yè) 街 F. 教 學(xué) 主 樓endl;cout G. 正 氣 廣 場(chǎng) H. 圖 書 館endl;cout I. 天 健 園 key;switch(key)case A:return A;break;case B:return B;break;case C:return C;break;case D:return D;break;case E:return E;break;case F:return F;break;case G:return G;break;case H:return H;break;case I:return I;break;default:cout您的輸入有誤！請(qǐng)選擇

16、AI！n;system(pause);system(cls);FunMenue2();C_IN2();int Sprint(char item)/對(duì)字母表示的景點(diǎn)輸出switch(item)case A:coutA.SNA.pl_name;break;case B:coutB.SNB.pl_name;break;case C:coutC.SNC.pl_name;break;case D:coutD.SND.pl_name;break;case E:coutE.SNE.pl_name;break;case F:coutF.SNF.pl_name;break;case G:coutG.SNG.pl

17、_name;break;case H:coutH.SNH.pl_name;break;case I:coutI.SNI.pl_name;break;default:cout無此景點(diǎn)n;return 1;break;return 0;#endifgraph.h/構(gòu)造圖 及圖的相關(guān)操作，由狄克斯拉算法改成。#include Sight.h#define MAXV 100 #define INF 32767 typedef int InfoType; /鄰接矩陣存儲(chǔ)方法 typedef struct int edgesMAXVMAXV; int n; MGraph; /狄克斯特拉算法 void Pp

18、ath(int path,int i,int v) int k; k=pathi; if(k=v) return; Ppath(path,k,v); Sprint(k+A);coutchar(k+A); void Dispath(int dist,int path,int s,int n,int v,int i) /對(duì)最短路徑輸出 if(si=1) cout ;Sprint(v+A);coutchar(v+A)到;Sprint(i+A);coutchar(i+A)n 最短路徑：disti米 n 途經(jīng)： ; Sprint(v+A);coutchar(v+A); Ppath(path,i,v);

19、Sprint(i+A);coutchar(i+A)endl; else cout從char(v+A)到char(i+A)不存在的路徑endl; cout; void Dijkstra(MGraph g,int v, int to) /Dijkstra g圖中v為起點(diǎn)求出到所有點(diǎn)的最短路徑 int distMAXV,pathMAXV; /dist存路徑 path存頂點(diǎn)int sMAXV; /標(biāo)記int mindis,i,j,u; for(i=0;ig.n;i+) disti=g.edgesvi; si=0; if(g.edgesviINF) pathi=v; else pathi=-1; sv=

20、1;pathv=0; for(i=0;ig.n;i+) mindis=INF; for(j=0;jg.n;j+) if(sj=0&distjmindis) u=j; mindis=distj; su=1; for(j=0;jg.n;j+) if(sj=0) if(g.edgesujINF&distu+g.edgesujdistj) distj=distu+g.edgesuj; pathj=u; Dispath(dist,path,s,g.n,v,to); void Dijkstra(MGraph g,int v)/重載，當(dāng)只有一點(diǎn)求最短路徑時(shí)，用到int to;for(to=0;tog.n;t

21、o+)if(to=v)continue; Dijkstra(g,v,to);/int path10;int pathF10=0;int BPsize=0;int EofV(MGraph g,int start)int con=0;for(int j=0;jg.n;j+)if(g.edgesstartj!=0&g.edgesstartjINF)con+;return con;int Nest(MGraph g,int start,int i)int con=0;for(int j=0;jg.n;j+)if(g.edgesstartj!=0&g.edgesstartjINF)con+;if(con

22、=i)return j;return 0;void Print(MGraph g) /打印找到路徑int TVal=0;for(int j=0;jBPsize-1;j+)TVal=TVal+g.edgespathjpathj+1;Sprint(pathj+A);cout;Sprint(pathj+A);coutn總 長(zhǎng)：TVal 米endl;void FindAllWay(MGraph g,int start,int end,int n) /尋找所有路徑int i;if(start=end)pathn=start;BPsize=n+1;Print(g);return ;int num=EofV

23、(g,start);pathn=start;for(i=1;i=num;i+)if(pathFNest(g,start,i)!=1)pathFstart=1;FindAllWay(g,Nest(g,start,i),end,n+1);pathFstart=0;/Shortest函數(shù) int Shortest(int choice) /最短路徑函數(shù) char from,to;int i,j,n; MGraph g; n=9;/圖信息for(i=0;in;i+)for(j=0;jn;j+)if(i!=j)g.edgesij=32767;else g.edgesij=0;g.edges01=g.ed

24、ges10=100;g.edges02=g.edges20=500;g.edges06=g.edges60=200;g.edges07=g.edges70=350;g.edges23=g.edges32=150;g.edges35=g.edges53=250;g.edges45=g.edges54=200;g.edges48=g.edges84=800;g.edges57=g.edges75=600; g.edges67=g.edges76=400;g.edges78=g.edges87=300; g.n=n; if(choice=5) cout請(qǐng)輸入起點(diǎn)和終點(diǎn)：fromto; cout+竭誠為您提供最短路徑+; i=from-A;j=to-A; Dijkstra(g,i,j); coutendl; if(choice=4) cout請(qǐng)輸入起點(diǎn)：from; system(cls); cout+我為您提供這里到學(xué)校其它景點(diǎn)最好選擇+; cout 您選擇了; if(Sprint(from)=1)return 0; cout為