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

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

3、cost = MaxInt; /记录目前最少运费或代价 int currentcost; /当前运费或代价 int currentMaxInt; /当前路径 int bestMaxInt; /记录最佳路径 struct AMGraphd string vexsMVNum; /顶点表 int arcsMVNumMVNum; /邻接矩阵 int vexnum; /图的当前点数 int arcnum; /边数 string infoMVNum; /景点介绍G;主函数调用其它函数4详细设计 #include#include/图的邻接矩阵存储表示#define MaxInt 32767 /极大值#def

4、ine 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 AMGraphd string vexsMVNum; /顶点表 int arcsMVNumMVNum; /邻

5、接矩阵 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 + currentcostbestcost) bestcost = G.arcscurrentt - 1currentt + G.arc

6、scurrentt1 + currentcost; for (j = 1; j = N; j+) bestj = currentj; for (j = t; j = N; j+)/排列。 swap(currentt, currentj); if (G.arcscurrentt - 1currentt + currentcost(t-1)的代价或运费 currentcost += G.arcscurrentt - 1currentt; backtrack(t + 1);/递归回溯 currentcost -= G.arcscurrentt - 1currentt; swap(currentt,

7、currentj); /-void all() int i; for (i = 1; i = N; i+) currenti = i; backtrack(2);/树的第一层已经找到了，所以从第二层开始 cout 最少的运费为: bestcost endl; cout 最佳路径为: ; for (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(AMG

8、raphd &G) G.vexs0 = 正门; G.info0 = 学校正门; G.vexs1 = 二教; G.info1 = 学校的第二教学楼; G.vexs2 = 一教; G.info2 = 学校的第一教学楼; G.vexs3 = 四教; G.info3 = 学校的第四教学楼，苏式建筑; G.vexs4 = 校医院; G.info4 = 学生就医的地方，现已搬迁; G.vexs5 = 春晖楼; G.info5 = 学校办公场所; G.vexs6 = 三教; G.info6 = 第三教学楼，阶梯教室; G.vexs7 = 沁园; G.info7 = 有喷泉、小广场和一个世纪钟; G.vexs

9、8 = 翠园; G.info8 = 与沁园相望，有比较多的植物; G.vexs9 = 大礼堂; G.info9 = 学校大礼堂，晚会、话剧等节目的表演场所; G.vexs10 = 泽园; G.info10 = 学校一景，有个凉亭; G.vexs11 = 综餐; G.info11 = 综合餐厅，有两层，消费水平较高; G.vexs12 = 体育馆; G.info12 = 室内运动场所; G.vexs13 = 图书馆; G.info13 = 学校图书馆，有五层书库，自习室，电子阅览室等; G.vexs14 = 信息楼; G.info14 = 信息科学与技术学院，学院楼不大; G.vexs15 =

10、五教; G.info15 = 第五教学楼，苏式建筑; G.vexs16 = 基教; G.info16 = 新建的基础教学楼，18层和地下两层，环境比较好; G.vexs17 = 4/5/7/8栋; G.info17 = 学生宿舍; G.vexs18 = 学二; G.info18 = 学二餐厅，上下两层; G.vexs19 = 游泳馆; G.info19 = 学校游泳馆，收费的; G.vexs20 = 三实验楼; G.info20 = 第三实验楼; G.vexs21 = 超市; G.info21 = 学校超市，银行都在这; G.vexs22 = 九栋; G.info22 = 最大的学生宿舍楼;

11、G.vexs23 = 学一; G.info23 = 学一餐厅，地上两层，地下一层，共三层; G.vexs24 = 西操; G.info24 = 学校西边的操场，塑胶操场，比较大; G.vexs25 = 机械楼; G.info25 = 机械学院的楼; G.vexs26 = 九实验楼; G.info26 = 第九实验楼，主要是计算机上机; G.vexs27 = 交通楼; G.info27 = 交通学院的楼; G.vexs28 = 1栋; G.info28 = 学生第一宿舍楼; G.vexs29 = 10/11栋; G.info29 = 学生宿舍; G.vexs30 = 土木楼; G.info30

12、= 土木学院的楼; G.vexs31 = 招待所; G.info30 = 铁道大学的招待所; 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.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.arc