數(shù)據(jù)結(jié)構(gòu)-校園導(dǎo)游程序(附源碼)

1、石家莊鐵道大學(xué)實(shí)習(xí)報(bào)告實(shí)習(xí)報(bào)告實(shí)驗(yàn)名稱：校園導(dǎo)游程序 日期：2017年 7月 7日姓名：李琛 學(xué)號(hào)：20153204 班級(jí)：信1501-2 指導(dǎo)教師：陳娜 1實(shí)驗(yàn)題目 校園導(dǎo)游程序 問題描述 用無向網(wǎng)表示學(xué)校的校園景點(diǎn)平面圖，圖中頂點(diǎn)表示主要景點(diǎn)，存放景點(diǎn)的編號(hào)、名 稱、簡(jiǎn)介等信息，圖中的邊表示景點(diǎn)間的道路，存放路徑長(zhǎng)度等信息。要求能夠回答有關(guān)景 點(diǎn)介紹、游覽路徑等問題。2需求分析 游客通過終端可詢問： （1）從某一景點(diǎn)到另一景點(diǎn)的最短路徑。 （2）游客從公園進(jìn)入，選取一條最佳路線。 （3）使游客可以不重復(fù)地瀏覽各景點(diǎn)，最后回到出口（出口就在入口旁邊）。 基本要求 （1）將導(dǎo)游圖看作一張帶權(quán)無

2、向圖，頂點(diǎn)表示公園的各個(gè)景點(diǎn)，邊表示各景點(diǎn)之間的 道路，邊上的權(quán)值表示距離為此圖選擇適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)。 （2）把各種路徑都顯示給游客，由游客自己選擇瀏覽路線。 （3）畫出景點(diǎn)分布圖于屏幕上。3概要設(shè)計(jì) 數(shù)據(jù)類型定義#include<iostream>#include<string>/圖的鄰接矩陣存儲(chǔ)表示#define MaxInt 32767 /極大值#define MVNum 100 /最大頂點(diǎn)數(shù) /頂點(diǎn)類型為字符型typedef int ArcType; /邊的權(quán)值為整型using namespace std;int i, j;int S100, D100, min,

3、 Path100;int N = 49;int bestcost = MaxInt; /記錄目前最少運(yùn)費(fèi)或代價(jià) int currentcost; /當(dāng)前運(yùn)費(fèi)或代價(jià) int currentMaxInt; /當(dāng)前路徑 int bestMaxInt; /記錄最佳路徑 struct AMGraphdstring vexsMVNum; /頂點(diǎn)表int arcsMVNumMVNum; /鄰接矩陣int vexnum; /圖的當(dāng)前點(diǎn)數(shù)int arcnum; /邊數(shù)string infoMVNum; /景點(diǎn)介紹G;主函數(shù)調(diào)用其它函數(shù)4詳細(xì)設(shè)計(jì) #include<iostream>#include&

4、lt;string>/圖的鄰接矩陣存儲(chǔ)表示#define MaxInt 32767 /極大值#define MVNum 100 /最大頂點(diǎn)數(shù) /頂點(diǎn)類型為字符型typedef int ArcType; /邊的權(quán)值為整型using namespace std;int i, j;int S100, D100, min, Path100;int N = 49;int bestcost = MaxInt; /記錄目前最少運(yùn)費(fèi)或代價(jià) int currentcost; /當(dāng)前運(yùn)費(fèi)或代價(jià) int currentMaxInt; /當(dāng)前路徑 int bestMaxInt; /記錄最佳路徑 struct A

5、MGraphdstring vexsMVNum; /頂點(diǎn)表int arcsMVNumMVNum; /鄰接矩陣int vexnum; /圖的當(dāng)前點(diǎn)數(shù)int arcnum; /邊數(shù)string infoMVNum; /景點(diǎn)介紹G;/-void swap(int& a, int& b)int temp = a;a = b;b = temp;void backtrack(int t)/其實(shí)就是一個(gè)排列問題。 int j;if (t = N)/到了最后一層。 if (G.arcscurrentt - 1currentt + G.arcscurrentt1 + currentcost<

6、;bestcost)bestcost = G.arcscurrentt - 1currentt + G.arcscurrentt1 + currentcost;for (j = 1; j <= N; j+)bestj = currentj;for (j = t; j <= N; j+)/排列。 swap(currentt, currentj);if (G.arcscurrentt - 1currentt + currentcost<bestcost)/其實(shí)currentcost就是包括了1->(t-1)的代價(jià)或運(yùn)費(fèi) currentcost += G.arcscurren

7、tt - 1currentt;backtrack(t + 1);/遞歸回溯 currentcost -= G.arcscurrentt - 1currentt;swap(currentt, currentj);/-void all()int i;for (i = 1; i <= N; i+)currenti = i;backtrack(2);/樹的第一層已經(jīng)找到了，所以從第二層開始 cout << "最少的運(yùn)費(fèi)為:" << bestcost << endl;cout << "最佳路徑為: "for (

8、i = 1; i <= N; i+)cout << besti << "->"cout << best1 << endl;/-/頂點(diǎn)定位int LocateVex(AMGraphd G, string u)int i = 0;while (G.vexsi != u) i+;return i;int CreateUD(AMGraphd &G)G.vexs0 = "正門" G.info0 = "學(xué)校正門"G.vexs1 = "二教" G.info1 =

9、 "學(xué)校的第二教學(xué)樓"G.vexs2 = "一教" G.info2 = "學(xué)校的第一教學(xué)樓"G.vexs3 = "四教" G.info3 = "學(xué)校的第四教學(xué)樓，蘇式建筑"G.vexs4 = "校醫(yī)院" G.info4 = "學(xué)生就醫(yī)的地方，現(xiàn)已搬遷"G.vexs5 = "春暉樓" G.info5 = "學(xué)校辦公場(chǎng)所"G.vexs6 = "三教" G.info6 = "第三教學(xué)樓，階梯教

10、室"G.vexs7 = "沁園" G.info7 = "有噴泉、小廣場(chǎng)和一個(gè)世紀(jì)鐘"G.vexs8 = "翠園" G.info8 = "與沁園相望，有比較多的植物"G.vexs9 = "大禮堂" G.info9 = "學(xué)校大禮堂，晚會(huì)、話劇等節(jié)目的表演場(chǎng)所"G.vexs10 = "澤園" G.info10 = "學(xué)校一景，有個(gè)涼亭"G.vexs11 = "綜餐" G.info11 = "綜合餐廳，

11、有兩層，消費(fèi)水平較高"G.vexs12 = "體育館" G.info12 = "室內(nèi)運(yùn)動(dòng)場(chǎng)所"G.vexs13 = "圖書館" G.info13 = "學(xué)校圖書館，有五層書庫，自習(xí)室，電子閱覽室等"G.vexs14 = "信息樓" G.info14 = "信息科學(xué)與技術(shù)學(xué)院，學(xué)院樓不大"G.vexs15 = "五教" G.info15 = "第五教學(xué)樓，蘇式建筑"G.vexs16 = "基教" G.info

12、16 = "新建的基礎(chǔ)教學(xué)樓，18層和地下兩層，環(huán)境比較好"G.vexs17 = "4/5/7/8棟" G.info17 = "學(xué)生宿舍"G.vexs18 = "學(xué)二" G.info18 = "學(xué)二餐廳，上下兩層"G.vexs19 = "游泳館" G.info19 = "學(xué)校游泳館，收費(fèi)的"G.vexs20 = "三實(shí)驗(yàn)樓" G.info20 = "第三實(shí)驗(yàn)樓"G.vexs21 = "超市" G.

13、info21 = "學(xué)校超市，銀行都在這"G.vexs22 = "九棟" G.info22 = "最大的學(xué)生宿舍樓"G.vexs23 = "學(xué)一" G.info23 = "學(xué)一餐廳，地上兩層，地下一層，共三層"G.vexs24 = "西操" G.info24 = "學(xué)校西邊的操場(chǎng)，塑膠操場(chǎng)，比較大"G.vexs25 = "機(jī)械樓" G.info25 = "機(jī)械學(xué)院的樓"G.vexs26 = "九實(shí)驗(yàn)樓&qu

14、ot; G.info26 = "第九實(shí)驗(yàn)樓，主要是計(jì)算機(jī)上機(jī)"G.vexs27 = "交通樓" G.info27 = "交通學(xué)院的樓"G.vexs28 = "1棟" G.info28 = "學(xué)生第一宿舍樓"G.vexs29 = "10/11棟" G.info29 = "學(xué)生宿舍"G.vexs30 = "土木樓" G.info30 = "土木學(xué)院的樓"G.vexs31 = "招待所" G.info3

15、0 = "鐵道大學(xué)的招待所"G.vexnum = 32;G.arcnum = 49;for (i = 0; i < G.vexnum; +i) /權(quán)值初始化為最大值for (j = 0; j < G.arcnum; +j)G.arcsij = MaxInt;G.arcs02 =1 ; G.arcs12 =2 ; G.arcs16 = 1; G.arcs27 =1 ; G.arcs23 =2 ; G.arcs38 = 1; G.arcs34 =1 ; G.arcs49 =1 ; G.arcs45 = 3; G.arcs510 = 1;G.arcs20 = 1; G

16、.arcs21 = 2; G.arcs61 = 1; G.arcs72 = 1; G.arcs32 = 2; G.arcs83 = 1; G.arcs43 = 1; G.arcs94 = 1; G.arcs54 = 3; G.arcs105 = 1;G.arcs67 =2 ; G.arcs612 = 1; G.arcs713 =1 ; G.arcs78 =2 ; G.arcs815 =1 ; G.arcs89 =1 ; G.arcs916 = 1; G.arcs910 = 3; G.arcs1017 =1 ; G.arcs1011 = 2;G.arcs76 = 2; G.arcs126 = 1

17、; G.arcs137 = 1; G.arcs87 = 2; G.arcs158 = 1; G.arcs98 = 1; G.arcs169 = 1; G.arcs109 = 3; G.arcs1710 = 1; G.arcs1110 = 2;G.arcs1118 = 2; G.arcs1213 = 2; G.arcs1219 = 1; G.arcs1320 = 1; G.arcs1314 = 1; G.arcs1415 = 1; G.arcs1527 = 2; G.arcs1516 = 1; G.arcs1621 = 1; G.arcs1617 = 1;G.arcs1811 = 2; G.ar

18、cs1312 = 2; G.arcs1912 = 1; G.arcs2013 = 1; G.arcs1413 = 1; G.arcs1514 = 1; G.arcs2715 = 2; G.arcs1615 = 1; G.arcs2116 = 1; G.arcs1716 = 1;G.arcs1722 =1 ; G.arcs1718 = 1; G.arcs1823 = 1; G.arcs1920 = 2; G.arcs1925 =1 ; G.arcs2026 = 1; G.arcs2128 = 1; G.arcs2122 = 2; G.arcs2229 = 1; G.arcs2223 = 2;G.

19、arcs2217 = 1; G.arcs1817 = 1; G.arcs2318 = 1; G.arcs2019 = 2; G.arcs2519 = 1; G.arcs2620 = 1; G.arcs2821 = 1; G.arcs2221 = 2; G.arcs2922 = 1; G.arcs2322 = 2;G.arcs2425 = 1; G.arcs2526 = 2; G.arcs2630 = 1; G.arcs2627 =2 ; G.arcs2728 = 1; G.arcs2829 = 2; G.arcs2430 = 5; G.arcs031 = 2; G.arcs431 = 3;G.

20、arcs2524 = 1; G.arcs2625 = 2; G.arcs3026 = 1; G.arcs2726 = 2; G.arcs2827 = 1; G.arcs2928 = 2; G.arcs3024 = 5; G.arcs310 = 2; G.arcs314 = 3;return 0;void find()int ff;string ss;cout << "請(qǐng)輸入景點(diǎn)" << endl;cin >> ss;ff= LocateVex(G, ss);/起點(diǎn)cout << ss << "的簡(jiǎn)介為：&

21、quot; << endl;cout << G.infoff << endl;cout << endl;void show()cout << " -土木樓 " << endl;cout << " | | " << endl;cout << "西操 -機(jī)械樓 - 九實(shí)驗(yàn)樓 -交通樓 - 1棟 - 10/11棟 " << endl;cout << " | | | | | " <<

22、; endl;cout << " 游泳館 - 三實(shí)驗(yàn)樓 | 超市 - 九棟 - 學(xué)一 " << endl;cout << " | | | | | | " << endl;cout << " 體育館 - 圖書館 - 信息樓 - 五教 - 基教 - 4/5/7/8棟 - 學(xué)二 " << endl;cout << " | | | | | | " << endl;cout << " 三教 - 沁園 - 翠園

23、 - 大禮堂 - 澤園 - 綜餐 " << endl;cout << " | | | | | " << endl;cout << " 二教 - 一教 - 四教 - 校醫(yī)院 - 春暉樓" << endl;cout << " | | " << endl;cout << " 正門 - 招待所" << endl;void xuanze()string a;string b;cout << &qu

24、ot;請(qǐng)輸入當(dāng)前位置："cin >> a;cout << "請(qǐng)輸入終點(diǎn)位置："cin >> b;int i, n, v, v0, w, z;v0 = LocateVex(G, a);/起點(diǎn)z = LocateVex(G, b);/終點(diǎn)n = G.vexnum;for (v = 0; v < n; v+)Sv = false;Dv = G.arcsv0v;if (Dv < MaxInt)Pathv = v0;elsePathv = -1;Sv0 = true;Dv0 = 0;for (i = 1; i < n;

25、i+)min = MaxInt;for (w = 0; w < n; w+)if (!Sw && Dw < min)v = w;min = Dw;Sv = true;for (w = 0; w < n; w+)if (!Sw && (Dv + G.arcsvw < Dw)Dw = Dv + G.arcsvw;Pathw = v;cout << endl;cout << "路線為：" << endl;int s = z;cout << G.vexsz << " <- "while (Paths!= v0)cout << G.vexsPaths << "