北理珠校园导游咨询与最短路径

1、精品文档北京理工大学珠海学院课程设计说明书_2014_2015_学年第_1 _ 学期题目：北理珠校园导游咨询与最短路径学 院：计算机学院专业班级：学 号：学生姓名：指导教师：王琳成 绩：时 间：2014 年12月30日2014 年12 月30 日设计任务书20142015学年 第1学期学生姓名： 专业班级：指导教师：王琳工作部门：计算机学院一、课程设计题目北理珠校园导游咨询与最短路径二、课程设计内容（含技术指标）【问题描述】从北京理工大学珠海学院的平面图中选取有代表性景点（10-15个），抽象 成一个无向带权图。以图中顶点表示景点，边上的权值表 示两地之间距离。本程序的目的是为用户提供路径咨询

2、。 根据用户指定的始点和终 点输出相应路径，或者根据用户指定的景点输出景点的信息。【任务要求】从北京理工大学珠海学院的平面图中选取有代表性景点（10-15个），抽象成一个无向带权图。以图中顶点表示校内各景点，存放景 点名称、代号、简介等信息；以边表示路径，存放路径长度等信息。为来访客人提供图中任意景点相关信息的查询。为来访客人提供图中任意景点的问路查询， 即查询任意两个景点 之间的一条最短的简单路径。区分汽车线路与步行线路。【测试数据】北理珠校园导游图（距离可估计）。三、进度安排1 .初步设计：写出初步设计思路，进行修改完善，并进行初步设计。2 详细设计： 根据确定的设计思想， 进一步完善初步

3、设计内容，按要求编写出数据结构类型定义、各算法程序、主函数。编译分析调试错误。3测试分析：设计几组数据进行测试分析，查找存在的设计缺陷，完善程序。4报告撰写：根据上面设计过程和结果，按照要求写出设计报告。5 答辩考核验收： 教师按组 （人） 检查验收， 并提出相关问题，以便检验设计完成情况。四、基本要求1在设计时，要严格按照题意要求独立进行设计，不能随意更改。若确因条件所限，必须要改变课题要求时，应在征得指导教师同意的前提下进行。2在设计完成后，应当场运行和答辩，由指导教师验收，只有在验收合格后才能算设计部分的结束。3设计结束后要写出课程设计报告，以作为整个课程设计评分的书面依据和存档材料。

4、设计报告以规定格式的电子文档书写、 打印并装订，报告格式严格按照模板要求撰写，排版及图、表要清楚、工整。从总体来说，所设计的程序应该全部符合要求，问题模型、求解算法以及存储结构清晰；具有友好、清晰的界面；设计要包括所需要的辅助程序，如必要的数据输入、输出、显示和错误检测功能；操作使用要简便； 程序的整体结构及局部结构要合理； 设计报告要符合规范。课程负责人签名：年月日课程设计分工安排姓名课程设计负责工作备注9 欢迎下载 。成绩评定表姓名成绩评定权重总分总成绩（五分制）平时成绩20报告成绩50答辩成绩30摘要通过数据结构“图”构成抽象数据类型，该系统运用了数组表示法（领结矩阵）初始化图，分别存储

5、数据元素（景点）和数据元素（路段）之间的关系，迪杰斯特拉算法来描述各景点所有游览路径， 佛洛依德算法设计景点之间的最短路径， 结合上述算法设计了一个校园导航与最短路径系统， 供来访北理珠的客人使用，为其提供方便。关键词：概要设计详细设计 软件测试目录课程设计说明书 1设计任务书 2成绩评定表 6摘要 7目录 81 .前言 91.1 问题的描述 91.2 算法输入 91.3 算法输出 92 .概要设计 112.1 要点描述 112.2 模块分解 113 .详细设计 123.1 算法程序流程图 123.2 界面设计 134 .软件测试 175 .参考文献 196 .心得体会 错误！未定义书签。答辩

6、记录表 281 .前 言1.1 问题的描述从北京理工大学珠海学院的平面图中选取有代表性景点（ 10-15 个） ，抽象成一个无向带权图。 以图中顶点表示景点， 边上的权值表示两地之间距离。 本程序的目的是为用户提供路径咨询。 根据用户指定的始点和终点输出相应路径， 或者根据用户指定的景点输出景点的信息1.2 算法输入mgraph creatgraph(void) / 初始化mgraph g;int i, j;g.vexnum = 10; /14个顶点g.arcnum = 16; /14条弧for (i = 0; ig.vexnum; i+)g.vexsi.num = i; / 第 i 个景点的

7、编号为 istrcpy_s(g., 北理图书馆);1.3 算法输出初始化图 主界面 浏览全部景点 该点到其它全部路径void cmd(void);mgraph creatgraph(void);/void menu(void);/void browser(mgraph *g);/void shortestpath_dij(mgraph * g);/精品文档void floyd(mgraph *g);/两景点最短路径void search(mgraph *g);/查看景点信息void printmatrix(mgraph *g);/输出领结矩阵# 欢迎下载。精品文档2 . 概

8、要设计2.1 要点描述用图的算法进行构造， 用邻接表建立图， 图的每一个顶点代表相应的景点。然后再用深度优先遍历进行搜索， 查找所需的路径。 再用迪杰特斯拉算法求出一个景点到其他景点之间的最佳路径。 然后再用弗洛伊德算法求出要查询的出发点到目的地的最短路径。2.2 模块分解（ 1） 主菜单（menu） ：存放着所有的选择供用户查询。用户可通过输入编号来查询自己想要获得的信息（ 2） 浏览校园全景（ browser ） ： 采用深度遍历图进行所有景点浏览， 将遍历景点信息输出。（ 3）查看各景点游览路线（shortestpath_dij ） ：用户输入一个景点，采用迪杰斯特拉算法将从该景点起所有

9、路径查出并输出在屏幕上。（ 4） 选择出发点和目的地（floyd） ： 用户输入一个出发点和一个目的地编号， 采用弗洛伊德算法求出发点到目的地的最短路径。（ 5）查看景点信息（search） ：直接输入编号进行单个景点查询。（ 6）显示图的邻接矩阵（print）（ 7）退出系统（exit）13 欢迎下载。3.详细设计3.1 算法程序流程图3.2 界面设计printf(n北京理工大学珠海学院导游图printf(n);printf(1.浏览校园全景n);printf(2.查看各景点所有游览路线n);printf(3.选择出发点和目的地n);printf(4.查看景点信息n);printf(5.显示

10、此图的邻接矩阵n);printf(6.退出系统n);printf(n);printf(选项 -:);主菜单（menu）void menu() / 定义主菜单 n);浏览校园全景(browser ) :void browser(mgraph *g)int v;printf( 编号景点名称简介n);for (v = 0; vvexnum; v+)printf( i %-4d | %-16s | %-56s | n, g-vexsv.num, g-, g-roduction);查看各景点游览路线( shortestpath_dij ) ：void shortes

11、tpath_dij(mgraph * g)int v, w, i, min, t = 0, x, flag = 1, v0; /flag=1保证输入编号有效int final20, d20, p2020;while (flag)printf( 请输入一个起始景点编号:);scanf_s(%d, &v0); / 输入一个值赋给v0if (v0g-vexnum)printf( 景点编号不存在! 请重新输入景点编号:);精品文档scanf_s(%d, &v0);if (v0 = 0 & v0vexnum) flag = 0;for (v = 0; vvexnum; v+)finalv = 0; /v

12、 不属于 s ，即 v 顶点还没有走过dv = g-arcsv0v.adj; /v0到 v 的弧权值for (w = 0; wvexnum; w+)pvw = 0;/ 设置空路径if (dvinfinity)pvv0 = 1; pvv = 1; /v0是从 v0 到 v 的顶点， v 是从v0 到 v 的顶点dv0 = 0; finalv0 = 1; /初始化， v0 到 v0 的带权路径长度为 0，最短路径 ,v0 顶点属于 s 集for (i = 1; ivexnum; i+) /其余 g.vexnum-1 个顶点min = infinity; / 当前所知离v0 顶点的最近距离for (

13、w = 0; wvexnum; w+)if (!finalw) /w顶点在 v-s 中if (dwmin) v = w; min = dw; /w顶点离 v0 顶点更近finalv = 1;/ 离 v0 顶点最近的 v 加入 s 集for (w = 0; wvexnum; w+) / 更新当前的最短路径及距离if (!finalw &(min + g-arcsvw.adjarcsvw.adj;for (x = 0; xvexnum; x+) pwx = pvx;pww = 1; / 用来更新到每一个顶点的最短路径for (v = 0; vvexnum; v+)if (v0 != v) prin

14、tf(%s, g-); /输出字符串for (w = 0; wvexnum; w+)if (pvw & w != v0) printf(-%s, g-);t+;if (tg-vexnum - 1 & v0 != v)printf( 总路线长 %dmnn, dv);/shortestpath_dij end选择出发点和目的地(floyd) ：void floyd(mgraph *g)int v, u, i, w, k, j, flag = 1, p101010, d1010;for (v = 0; vvexnum; v+) / 各对结点之间初始已知路径及

15、距离for (w = 0; wvexnum; w+)dvw = g-arcsvw.adj;for (u = 0; uvexnum; u+)pvwu = 0;if (dvwinfinity)pvwv = 1; pvww = 1;for (u = 0; uvexnum; u+)for (v = 0; vvexnum; v+)for (w = 0; wvexnum; w+)if (dvu + duwdvw) /从 v 经 u 到 w 的一条路径更短dvw = dvu + duw; /修改权值for (i = 0; ivexnum; i+)pvwi = pvui | puwi;while (flag)

16、printf( 请输入出发点和目的地的编号:);scanf_s(%d%d, &k, &j);if (kg-vexnum | jg-vexnum)printf( 景点编号不存在! 请重新输入出发点和目的地的编号:);scanf_s(%d%d, &k, &j);if (k = 0 & kvexnum&j = 0 & jvexnum)flag = 0;printf(%s, g-);for (u = 0; uvexnum; u+)if (pkju & k != u&j != u)printf(-%s, g-);printf(-%s, g-);

17、printf( 总路线长 %dmn, dkj);/floyd end查看景点信息 (search) ：void search(mgraph *g)int k, flag = 1;while (flag)printf( 请输入要查询的景点编号:);scanf_s(%d, &k);if (kg-vexnum)printf( 景点编号不存在! 请重新输入景点编号:);scanf_s(%d, &k);if (k = 0 & k vexnum) flag = 0;printf( i %-4d | %-16s | %-56s | n, g-vexsk.num, g-, g-vexsk.

18、introduction);/search end显示图的邻接矩阵(print):void printmatrix(mgraph *g)int v, w, t = 0;printf( 图的邻接矩阵为： n);for (v = 0; vvexnum; v+)for (w = 0; wvexnum; w+)if (g-arcsvw.adj = infinity) printf( 00);else printf(%-7d, g-arcsvw.adj);t+;if (t%g-vexnum = 0)printf(n);15 欢迎下载。精品文档21欢迎下载4.软件测试校园全景：用然书堂厅笈曼堂心厅 电图班

19、僵时近坂中覆池横 总理-工食二三道生泳梅 -,兄教零搞绰快学阴画c win k)ws5y$tem32cmd.exe当书馆圮学校的女献信昆中心，是为学校救学的学术性机构.田泾巧工j面,提供请考款恒第优学生选样、二时隹楼的一个箕厅方师生1_原供量便隹的伙食亚于学生住宅区中间地段，销售各式零食以及日月产品 应干学生住无中山也殷*为啾近的学生提供多样的伏堂认序 也丁学生住宅末尾地匕 法境朱r 格，世是 科达择 挈校成立的憬递服主中心，女足;火师生收发包t：的需求 ef快递中心都 为附近的学生提匚，件的比丈 1-干苧仁后jj皮迎国；现有三个水惘.于“14年4月建或. 大学生上堞的地点，分四日却半楼.台k

20、宣学设备都，：=.北忆埒i大苧出他学院导照区1 .勃战校园全景2 .当百用鼠白手有游也路庄3 .选撵出生小三口好的地* .当至寻尸，信包5,4小图的:工立延年6.退由系统选择出发点和目的地:m if c:wind0wssystenn32cmd exe请输入出发总和目的地的舞号2教工管厅一:第一皈箕第二饮堂 詹踣线女3日刖i北京理工大学珠海学院导游图l浏班校园全景2普看各导.点所有游电路够3选择一发点和目的地4看景点信息5显示一图的邻接矩阵8退出系统选项-:邻接矩阵:cwindowsvyitem32cmd.exe二 g 6 0& 2 1 2% 4 u /?1，正 0 0回e ”样r ei8d 0

21、sebo0220*eos r-rj11?eoxoooc-od30550cx?196occx?e氧。co-r-32g1gg12g21一wa-c5。o8uo530120b3021012。b300kkk3&k北京理工厂4:药学及导游图2：查看各景点所胄游览路陵 学.选要出发点和目仁地 心三皆罩3信息5.总示此屋由鸵接犯降&一退出枭-5 .参考文献严蔚敏 吴伟民编著， 数据结构（c语言版），清华大学出版社，2010年耿国华等.数据结构c语言描述.西安：西安电子科技大学出版社，2002殷人昆.数据结构一一用面向对象方法与c+胡言描述.北京：清华大学出版 社，20076 .代码#include stdaf

22、x.h#include / 头文件#include#include# define infinity 10000/*无穷大*/# define max_vertex_num 40# define max 40typedef struct arcell /对弧的定义int adj; / 路径长度arcell, adjmatrixmax_vertex_nummax_vertex_num; /一个二维数组,数组里元素类型为整型typedef struct /图中顶点表示主要景点，存放景点的编号、名称、简介等信息,char name30;int num;char introduction100;/ 简

23、介infotype; / 数据域typedef struct infotype vexsmax_vertex_num; / 顶点的数据域adjmatrix arcs; / 邻接矩阵int vexnum, arcnum; /图的当前顶点数和弧数mgraph;mgraph b; /全局变量void cmd(void);mgraph creatgraph(void);/void menu(void);/void browser(mgraph *g);/void shortestpath_dij(mgraph * g);/void floyd(mgraph *g);/void search(mgrap

24、h *g);/void printmatrix(mgraph *g);/void main(void) /定义主函数精品文档system(mode con: cols=100 lines=40);cmd(); / 调用 cmd()void cmd(void) / 定义cmd()int i;b = creatgraph();mgraph g;menu();scanf_s(%d, &i);while (i != 6)switch (i)case 1:system(cls);case 2:system(cls);case 3:system(cls);case 4:system(cls); case

25、5:system(cls); case 6:exit(1); break; default:break;browser(&b); menu(); break;shortestpath_dij(&b); menu(); break;floyd(&b); menu(); break;search(&b); menu(); break;scanf_s(%d, &i); /输入的值 d 赋给 imgraph creatgraph(void) mgraph g;int i, j;g.vexnum = 10; /14g.arcnum = 16; /14/初始化个顶点条弧for (i = 0; ig.vex

26、num; i+)g.vexsi.num = i; / strcpy_s(g., strcpy_s(g.roduction, 学术性机构。 );strcpy_s(g., strcpy_s(g.roduction, );第 i 个景点的编号为 i北理图书馆); /strcpy 的头文件是string.h 图书馆是学校的文献信息中心， 是为学校教学的第一饭堂 );位于田径场对面，提供诸多款饭菜供学生选择。printmatrix(&b); menu(); break;strcpy_s(g., strcpy_

27、s(g.roduction, 伙食 );strcpy_s(g., strcpy_s(g.roduction, 用产品 );strcpy_s(g., strcpy_s(g.roduction, 的伙食选择);strcpy_s(g., strcpy_s(g.roduction, 种选择 );strcpy_s(g., strcpy_s(g.roduction, 裹的需求);strcpy_s(g., strcpy_

28、s(g.roduction, 选择 );strcpy_s(g., 教工餐厅 ); 临近明德楼的一个餐厅，零食前线 ); 位于学生住宅区中间地段，第二饭堂 ); 位于学生住宅中间地段，第三饭堂 ); 位于学生住宅末尾地段，环境别具一格，也是一为师生们提供最便捷的销售各式零食以及日为附近的学生提供多样快递中心 ); 学校成立的快递服务中心， 满足广大师生收发包学生餐厅 ); 位于快递中心旁， 为附近的学生提供多样的伙食游泳池 );strcpy_s(g.roduction, 位于学校后山坡路段，拥有三个水池，于2014年 10 月建成。 );

29、strcpy_s(g., 明德楼 );strcpy_s(g.roduction,广大学生上课的地点，分四栋教学楼，各式教学设备都齐全。 );for (i = 0; ig.vexnum; i+)for (j = 0; jg.vexnum; j+)g.arcsij.adj = infinity;g.arcs01.adj = 420;g.arcs02.adj = 480;g.arcs12.adj = 80;g.arcs13.adj = 410;g.arcs14.adj = 220;g.arcs19.adj = 700;g.arcs23.adj = 50;g.ar

30、cs29.adj = 550;g.arcs35.adj = 190;g.arcs45.adj = 320;g.arcs56.adj = 100;g.arcs57.adj = 120;g.arcs58.adj = 210;g.arcs67.adj = 50;g.arcs78.adj = 120;g.arcs89.adj = 300;23 欢迎下载。精品文档for (i = 0; ig.vexnum; i+)for (j = 0; jg.vexnum; j+)g.arcsji.adj = g.arcsij.adj; /无向网return g; void menu() / 定义主菜单 printf(

31、北京理工大学珠海学院导游图n);printf(n);printf(1.浏览校园全景n);printf(2.查看各景点所有游览路线n); printf(3.选择出发点和目的地n); printf(4.查看景点信息n); printf(5.显示此图的邻接矩阵n); printf(6.退出系统n); printf( n);printf(选项-:);void browser(mgraph *g)int v;printf( 11/ 迪杰斯特拉算法来计算出起点到各个顶点之间的最短路径,v0 为起点void shortestpath_dij(mgraph * g)int v, w, i, min, t =

32、0, x, flag = 1, v0; /flag=1保证输入编号有效int final20, d20, p2020;用迪杰斯特拉算法求网g的v0顶点到其余顶点 v的最短路径pv及带权长度dv/若pvw为1,则w是从v0到v当前求得最短路径上的顶点/finalv 为1当且仅当v属于s(s是已求得最短路径的终点的集合)，即已经求得从v0 到 v 的最短路径 while (flag)printf( 请输入一个起始景点编号 :);scanf_s(%d, &v0); / 输入一个值赋给v0if (v0g-vexnum) printf( 景点编号不存在! 请重新输入景点编号:);scanf_s(%d,

33、&v0);if (v0 = 0 & v0vexnum) flag = 0;for (v = 0; vvexnum; v+)finalv = 0; /v 不属于 s ，即 v 顶点还没有走过dv = g-arcsv0v.adj; /v0到 v 的弧权值for (w = 0; wvexnum; w+)pvw = 0;/设置空路径if (dvinfinity) pvv0 = 1; pvv = 1; /v0是从 v0 到 v 的顶点， v 是从 v0 到 v 的顶点dv0 = 0; finalv0 = 1; / 初始化， v0 到 v0 的带权路径长度为0，最短路径,v0顶点属于 s 集/ 开始主循环

34、，每次求得v0 到某个 v 顶点的最短路径，并加v 到 s 集for (i = 1; ivexnum; i+) /其余 g.vexnum-1 个顶点min = infinity; / 当前所知离v0 顶点的最近距离for (w = 0; wvexnum; w+)if (!finalw) /w顶点在 v-s 中if (dwmin) v = w; min = dw; /w顶点离 v0 顶点更近finalv = 1;/离 v0 顶点最近的 v 加入 s 集for (w = 0; wvexnum; w+) / 更新当前的最短路径及距离if (!finalw & (min + g-arcsvw.adja

35、rcsvw.adj;for (x = 0; xvexnum; x+)pwx = pvx;pww = 1; / 用来更新到每一个顶点的最短路径for (v = 0; vvexnum; v+) if (v0 != v) printf(%s, g-); /输出字符串for (w = 0; wvexnum; w+)if (pvw & w != v0) printf(-%s, g-); t+; if (tg-vexnum - 1 & v0 != v)printf( 总路线长 %dmnn, dv);/shortestpath_dij end void floyd(

36、mgraph *g)/ 用 floyd 算法求图中各对顶点 v 和 w 之间的最短路径pvw 及其/ 带权长度 dvw 。若 pvwu 为 1 ，则 u 是从 v 到 w 当前求得最短/ 路径上的顶点。int v, u, i, w, k, j, flag = 1, p101010, d1010;for (v = 0; vvexnum; v+) / 各对结点之间初始已知路径及距离for (w = 0; wvexnum; w+)dvw = g-arcsvw.adj;for (u = 0; uvexnum; u+) pvwu = 0;if (dvwinfinity) pvwv = 1; pvww = 1;for (u = 0; uvexnum; u+)for (v = 0; vvexnum; v+)for (w = 0; wvexnum; w+)if (dvu + duwdvw) /从 v 经 u 到 w 的一条路径更短25 欢迎下