数据结构-校园导游程序(附源码)

1、石家庄铁道大学实习报告实习报告实验名称：校园导游程序 日期：2017年 7月 7日姓名：李琛 学号：20153204 班级：信1501-2 指导教师：陈娜 1实验题目 校园导游程序 问题描述 用无向网表示学校的校园景点平面图，图中顶点表示主要景点，存放景点的编号、名 称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。要求能够回答有关景 点介绍、游览路径等问题。2需求分析 游客通过终端可询问： （1）从某一景点到另一景点的最短路径。 （2）游客从公园进入，选取一条最佳路线。 （3）使游客可以不重复地浏览各景点，最后回到出口（出口就在入口旁边）。 基本要求 （1）将导游图看作一张带权无

2、向图，顶点表示公园的各个景点，边表示各景点之间的 道路，边上的权值表示距离为此图选择适当的数据结构。 （2）把各种路径都显示给游客，由游客自己选择浏览路线。 （3）画出景点分布图于屏幕上。3概要设计 数据类型定义#include<iostream>#include<string>/图的邻接矩阵存储表示#define MaxInt 32767 /极大值#define MVNum 100 /最大顶点数 /顶点类型为字符型typedef int ArcType; /边的权值为整型using namespace std;int i, j;int S100, D100, min,

3、 Path100;int N = 49;int bestcost = MaxInt; /记录目前最少运费或代价 int currentcost; /当前运费或代价 int currentMaxInt; /当前路径 int bestMaxInt; /记录最佳路径 struct AMGraphdstring vexsMVNum; /顶点表int arcsMVNumMVNum; /邻接矩阵int vexnum; /图的当前点数int arcnum; /边数string infoMVNum; /景点介绍G;主函数调用其它函数4详细设计 #include<iostream>#include&

4、lt;string>/图的邻接矩阵存储表示#define MaxInt 32767 /极大值#define MVNum 100 /最大顶点数 /顶点类型为字符型typedef int ArcType; /边的权值为整型using namespace std;int i, j;int S100, D100, min, Path100;int N = 49;int bestcost = MaxInt; /记录目前最少运费或代价 int currentcost; /当前运费或代价 int currentMaxInt; /当前路径 int bestMaxInt; /记录最佳路径 struct A

5、MGraphdstring vexsMVNum; /顶点表int arcsMVNumMVNum; /邻接矩阵int vexnum; /图的当前点数int arcnum; /边数string infoMVNum; /景点介绍G;/-void swap(int& a, int& b)int temp = a;a = b;b = temp;void backtrack(int t)/其实就是一个排列问题。 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)/其实currentcost就是包括了1->(t-1)的代价或运费 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);/树的第一层已经找到了，所以从第二层开始 cout << "最少的运费为:" << bestcost << endl;cout << "最佳路径为: "for (

8、i = 1; i <= N; i+)cout << besti << "->"cout << best1 << endl;/-/顶点定位int LocateVex(AMGraphd G, string u)int i = 0;while (G.vexsi != u) i+;return i;int CreateUD(AMGraphd &G)G.vexs0 = "正门" G.info0 = "学校正门"G.vexs1 = "二教" G.info1 =

9、 "学校的第二教学楼"G.vexs2 = "一教" G.info2 = "学校的第一教学楼"G.vexs3 = "四教" G.info3 = "学校的第四教学楼，苏式建筑"G.vexs4 = "校医院" G.info4 = "学生就医的地方，现已搬迁"G.vexs5 = "春晖楼" G.info5 = "学校办公场所"G.vexs6 = "三教" G.info6 = "第三教学楼，阶梯教

10、室"G.vexs7 = "沁园" G.info7 = "有喷泉、小广场和一个世纪钟"G.vexs8 = "翠园" G.info8 = "与沁园相望，有比较多的植物"G.vexs9 = "大礼堂" G.info9 = "学校大礼堂，晚会、话剧等节目的表演场所"G.vexs10 = "泽园" G.info10 = "学校一景，有个凉亭"G.vexs11 = "综餐" G.info11 = "综合餐厅，

11、有两层，消费水平较高"G.vexs12 = "体育馆" G.info12 = "室内运动场所"G.vexs13 = "图书馆" G.info13 = "学校图书馆，有五层书库，自习室，电子阅览室等"G.vexs14 = "信息楼" G.info14 = "信息科学与技术学院，学院楼不大"G.vexs15 = "五教" G.info15 = "第五教学楼，苏式建筑"G.vexs16 = "基教" G.info

12、16 = "新建的基础教学楼，18层和地下两层，环境比较好"G.vexs17 = "4/5/7/8栋" G.info17 = "学生宿舍"G.vexs18 = "学二" G.info18 = "学二餐厅，上下两层"G.vexs19 = "游泳馆" G.info19 = "学校游泳馆，收费的"G.vexs20 = "三实验楼" G.info20 = "第三实验楼"G.vexs21 = "超市" G.

13、info21 = "学校超市，银行都在这"G.vexs22 = "九栋" G.info22 = "最大的学生宿舍楼"G.vexs23 = "学一" G.info23 = "学一餐厅，地上两层，地下一层，共三层"G.vexs24 = "西操" G.info24 = "学校西边的操场，塑胶操场，比较大"G.vexs25 = "机械楼" G.info25 = "机械学院的楼"G.vexs26 = "九实验楼&qu

14、ot; G.info26 = "第九实验楼，主要是计算机上机"G.vexs27 = "交通楼" G.info27 = "交通学院的楼"G.vexs28 = "1栋" G.info28 = "学生第一宿舍楼"G.vexs29 = "10/11栋" G.info29 = "学生宿舍"G.vexs30 = "土木楼" G.info30 = "土木学院的楼"G.vexs31 = "招待所" G.info3

15、0 = "铁道大学的招待所"G.vexnum = 32;G.arcnum = 49;for (i = 0; i < G.vexnum; +i) /权值初始化为最大值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 << "请输入景点" << endl;cin >> ss;ff= LocateVex(G, ss);/起点cout << ss << "的简介为：&

21、quot; << endl;cout << G.infoff << endl;cout << endl;void show()cout << " -土木楼 " << endl;cout << " | | " << endl;cout << "西操 -机械楼 - 九实验楼 -交通楼 - 1栋 - 10/11栋 " << endl;cout << " | | | | | " <<

22、; endl;cout << " 游泳馆 - 三实验楼 | 超市 - 九栋 - 学一 " << endl;cout << " | | | | | | " << endl;cout << " 体育馆 - 图书馆 - 信息楼 - 五教 - 基教 - 4/5/7/8栋 - 学二 " << endl;cout << " | | | | | | " << endl;cout << " 三教 - 沁园 - 翠园

23、 - 大礼堂 - 泽园 - 综餐 " << endl;cout << " | | | | | " << endl;cout << " 二教 - 一教 - 四教 - 校医院 - 春晖楼" << endl;cout << " | | " << endl;cout << " 正门 - 招待所" << endl;void xuanze()string a;string b;cout << &qu

24、ot;请输入当前位置："cin >> a;cout << "请输入终点位置："cin >> b;int i, n, v, v0, w, z;v0 = LocateVex(G, a);/起点z = LocateVex(G, b);/终点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 << "