(完整word版)数据结构-校园导游程序(附源码)(word文档良心出品)

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

2、1) 将导游图看作一张带权无向图， 顶点表示公园的各个景点, 路，边上的权值表示距离为此图选择适当的数据结构。 (2) 把各种路径都显示给游客，由游客自己选择浏览路线。 边表示各景点之间的道 (3)画出景点分布图于屏幕上。 3.概要设计 数据类型定义 #inelude #inelude /图的邻接矩阵存储表示 #define Maxi nt 32767 #defi ne MVNurlh00 /顶点类型为字符型 typedef int ArcType; using namespaeestd; int i, j; int S100, D100, min, Path100; int N = 49;

3、int besteost = Maxlnt; int eurrentcost; int eurrentMaxlnt ; int best Maxi nt; struet AMGraphd /极大值 /最大顶点数 /边的权值为整型 /记录目前最少运费或代价 /当前运费或代价 /当前路径 /记录最佳路径 string vexs MVNum int arcs MVNub MVNu; int vex num; int arcnum; stri ng info MVNum G； 主函数调用其它函数 /顶点表 /邻接矩阵 /图的当前点数 /边数 /景点介绍 show LocateVen find Loca

4、teVeK 4.详细设计 #inelude #inelude /图的邻接矩阵存储表示 #defi ne MaxI nt 32767 #defi ne MVNumoo /顶点类型为字符型 typedef int ArcType; using namespacestd; int i, j; int S100, D100, min, Path100; int N = 49; int bestcost = Maxlnt; int currentcost; int current Maxlnt ; int best MaxInt; struct AMGraphd string vexs MVNum in

5、t arcs MVNum MVNu; int vex num; int arcnum; stri ng info MVNum /记录目前最少运费或代价 /当前运费或代价 /当前路径 /记录最佳路径 G; /极大值 /最大顶点数 /边的权值为整型 /顶点表 /邻接矩阵 /图的当前点数 /边数 /景点介绍 / void swap( int a = b; b = temp; void backtrack( int t)其实就是一个排列问题。 int j; if ( t = N) / 到了最后一层。 if (G.arcscurrent t - 1currentt + G.arcscurrent t1

6、+ curre ntcostvbestcost) t1 + bestcost = G.arcscurre nt t - 1curre nt t + G.arcscurre nt curre ntcost; for (j = 1; j = N; j+) bestj = curre ntj; for (j = t; j (t-1)的代价或运费 curre ntcost += G.arcscurre nt backtrack( t + 1); / 递归回溯 curre ntcost -= G.arcscurre nt swap(current t, currentj); t - 1curre nt

7、t - 1curre nt t; t; / void all() int i; for (i = 1; i = N; i+) curre nti = i; backtrack(2); /树的第一层已经找到了，所以从第二层开始 cout 最少的运费为： bestcost endl; cout 最佳路径为：； for (i = 1; i = N; i+) cout besti ; cout best1 endl; / /顶点定位 int LocateVex( AMGraphdG stringu) int i = 0; while ( Gvexsi != u) i+; return i; int C

8、reateUD( AMGraphd Gvexs1 =二教; Gi nfo1 学校的第二教学楼; Gvexs2 =一教; Gin fo2 学校的第一教学楼; Gvexs3 =四教; Gi nfo3 学校的第四教学楼，苏式建筑; Gvexs4 =校医院;Ginfo4 学生就医的地方，现已搬迁; Gvexs5 =春晖楼“ ;Ginfo5 学校办公场所“； Gvexs 6 =三教; Ginfo6 第三教学楼，阶梯教室; Gvexs7 =沁园; Gin fo7 有喷泉、小广场和一个世纪钟; Gvexs 8 =翠园; Gi nfo8 与沁园相望，有比较多的植物； Gvexs9 =大礼堂“ ;Ginfo9

9、学校大礼堂，晚会、话剧等节目的表演场所; Gvexs10 =泽园; Gi nfo10 学校一景，有个凉亭; Gvexs11 =综餐； Gi nfo11 综合餐厅，有两层，消费水平较咼; Gvexs12 =体育馆 ;Ginfo12 室内运动场所; Gvexs13 =图书馆 ;Ginfo13 学校图书馆，有五层书库，自习室，电子阅览室等 Gvexs14 =信息楼 ;Ginfo14 信息科学与技术学院，学院楼不大“； Gvexs15 =五教; Gi nfo15 第五教学楼，苏式建筑; Gvexs16 =基教; Gi nfo16 新建的基础教学楼，18层和地下两层，环境比较好 Gvexs17 =4/5

10、/7/8 栋;G.info17学生宿舍; Gvexs18 学二; Gi nfo18 学二餐厅，上下两层; Gvexs19 =游泳馆 ;Ginfo19 学校游泳馆，收费的; Gvexs20 =三实验楼;Ginfo20 =第三实验楼“； Gvexs21 =超市;Ginfo21= 学校超市，银行都在这; Gvexs22 =九栋;Ginfo22= 最大的学生宿舍楼; Gvexs23 =学一;Ginfo23= 学一餐厅，地上两层，地下一层，共三层 Gvexs24 =西操;Ginfo24= 学校西边的操场，塑胶操场，比较大“ Gvexs25 =机械楼;Ginfo25 =机械学院的楼; Gvexs26 =九

11、实验楼;Ginfo26 =第九实验楼，主要是计算机上机“ Gvexs27 =交通楼;Ginfo27 =交通学院的楼; Gvexs28 =1 栋;Ginfo28= 学生第一宿舍楼; Gvexs29 =10/11 栋;Ginfo29 =学生宿舍; Gvexs30 =土木楼;Ginfo30 =土木学院的楼; Gvexs31 =招待所;Ginfo30 =铁道大学的招待所; Gvex num = 32; Garc num = 49; for (i = 0; i Gvexnum; +i)/权值初始化为最大值 for (j = 0; j Garcnum; +j) Garcsij =MaxInt; =2 ;

12、=1 Garcs02 1 ; Garcs38 一 1; Garcs12 2 ; Garcs34 1 ; Garcs16 一 1; Garcs49 1 ; Garcs27 1 Garcs45 一 3; ;Garcs23 Garcs510 Garcs20 一 1; Garcs21 一 2; Garcs61 一 1; Garcs72 一 1 ;Garcs32 =2; 1 Garcs83 一 1; Garcs43 一 1; Garcs94 一 1; Garcs54 一 3; Garcs105 Garcs672 ; Garcs612 :1; Garcs7131 ;Garcs78 2 ; Garcs815

13、 1 ; 一 2 Garcs89一1 1 ; Garcs916一 1; Garcs910一 3; Garcs1017 1 ; Garcs1011 =2; Garcs76一 2; Garcs126 :1; Garcs137一 1 ;Garcs87 一 2; Garcs158 一 1; 一 2 Garcs98一 1; Garcs169 一 1; Garcs109一 3; Garcs1710 一 1; Garcs1110 Garcs1118 一 2 !;Garcs1213 一 2;Garcs1219 一 1;Garcs1320 一 1; Garcs1314一 1; Garcs1415一 1; Gar

14、cs1527一 2; Garcs1516 一 1; Garcs1621 一 1; Garcs1617 一 1; Garcs1811 一 2 !;Garcs1312 一 2;Garcs1912 一 1;Garcs2013 一 1; Garcs1413一 1; Garcs1514一 1; Garcs2715一 2; Garcs1615 一 1; Garcs2116 一 1; Garcs1716 一 1; Garcs1722 1 ;Garcs1718 一 1;Garcs1823 一 1;Garcs1920 一 2; Garcs19251 ; Garcs2026一 1; Garcs2128一 1; G

15、arcs2122 一 2; Garcs2229 一 1; Garcs2223 一 : 2; Garcs2217 一 1 ;Garcs1817 一 1;Garcs2318 一 1;Garcs2019 一 2; Garcs2519一 1; Garcs2620一 1; Garcs2821一 1; Garcs2221 一 2; Garcs2922 =1;Garcs2322 = 2; Garcs2425 = 1;Garcs2526 = 2;Garcs2630 = 1;Garcs2627 =2 ; Garcs2728= 1; Garcs2829= 2; Garcs2430= 5; Garcs031= 2;

16、 Garcs431 =3; Garcs2524 = 1;Garcs2625 = 2;Garcs3026 = 1;Garcs2726 = 2; Garcs2827= 1; Garcs2928= 2; Garcs3024= 5; Garcs310= 2; Garcs314 =3; return 0; void find() int ff; stri ng ss; cout 请输入景点 ss; ff= LocateVex(G, ss); / 起点 cout ss 的简介为： endl; cout G.infoff endl; cout endl; void show() cout 土木楼“ en d

17、l; cout | | I! en dl; cout 西操 - 机械楼 -九实验楼 交通楼1 栋 10/11 栋“ en dl; cout | | | | | en dl; cout I! 游泳馆 -三实验楼 | 超市 九栋 学一 en dl; cout | | | | | endl; cout 体育馆- -图书馆- 信息楼 -五教- -基教 4/5/7/8 栋-学二 en dl; cout | | | | | | I! en dl; cout 三教- 沁园 翠园- -大礼堂 泽园- -综餐“ en dl; cout | | | | | I! en dl; cout 二教- -一教 四教- -

18、校医院 春晖楼 en dl; cout | | en dl; 正门 招待所 cout en dl; void xuanze() stri ng a; stri ng b; cout a; cout b; int i, n, v, v0, w, z; v0 = LocateVex(G, a);/ 起点 z = LocateVex(G, b);/ 终点 n = G.vex num; for (v = 0; v n; v+) Sv = false ; Dv = G.arcsvOv; if (Dv MaxInt) Pathv = v0; else Pathv = -1; Sv0 = true ; Dv

19、0 = 0; for (i = 1; i n; i+) min = Maxlnt; for (w = 0; w n; w+) if (!Sw min = Dw; Sv = true ; for (w = 0; w n; w+) if (!Sw Pathw = v; cout endl; cout 路线为： endl; int s = z; cout G.vexsz -; while (Paths!= v0) cout G.vexsPaths -; s = Paths; cout G.vexsvO; cout endl; cout 最短距离为：v Dz *100 m endl; cout end

20、l; void main() CreateUD(G); int q=1; while (q != 0) cout endl; cout I 校园导航 | en dl; cout 卜 1 、显示地图 I en dl; cout 卜 2 、导航 I en dl; cout 卜 3 、遍历校园 I en dl; cout 卜 4 、景点查询- I en dl; cout 卜 0 、退岀 I en dl; cout q; cout endl; switch (q) case 1: show(); break; case 2: xuanze();break; case 3: all(); break; case 4: find(); break; 5. 调试分析 这个代码是使用的之前的迪杰斯特克算法，就是在输出路径这里不知道该如何