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

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

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

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

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

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

6、（10-15个），抽象成一个无向带权图。以图中顶点表示景点，边上的权值表示两地之间距离。本程序的目的是为用户提供路径咨询。根据用户指定的始点和终点输出相应路径，或者根据用户指定的景点输出景点的信息1.2算法输入MGraph CreatGraph(void) /初始化MGraph G;int i, j;G.vexnum = 10; /14个顶点G.arcnum = 16; /14条弧for (i = 0; i<G.vexnum; i+)G.vexsi.num = i; /第i个景点的编号为istrcpy_s(G., "北理图书馆"); 1.3算法输出

7、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.概要设计 2.1要点描述 用图的算法进行构造，用邻接表建立图，图的每一个顶点代表相应的景点。然后再用深度优先遍历进

8、行搜索，查找所需的路径。再用迪杰特斯拉算法求出一个景点到其他景点之间的最佳路径。然后再用弗洛伊德算法求出要查询的出发点到目的地的最短路径。2.2模块分解 （1） 主菜单（Menu）：存放着所有的选择供用户查询。用户可通过输入编号来查询自己想要获得的信息 （2） 浏览校园全景（Browser）：采用深度遍历图进行所有景点浏览，将遍历景点信息输出。（3）查看各景点游览路线（ShortestPath_DIJ）：用户输入一个景点，采用迪杰斯特拉算法将从该景点起所有路径查出并输出在屏幕上。（4）选择出发点和目的地(Floyd)：用户输入一个出发点和一个目的地编号，采用弗洛伊德算法求出发点到目的地的最短路

9、径。（5）查看景点信息(Search)：直接输入编号进行单个景点查询。（6）显示图的邻接矩阵(print)（7）退出系统(exit) 3.详细设计3.1算法程序流程图3.2界面设计主菜单（Menu）: void Menu() /定义主菜单printf("n 北京理工大学珠海学院导游图 n");printf(" n");printf(" 1.浏览校园全景 n");printf(" 2.查看各景点所有游览路线 n");printf(" 3.选择出发点和目的地 n");printf(" 4.

10、查看景点信息 n");printf(" 5.显示此图的邻接矩阵 n");printf(" 6.退出系统 n");printf(" n");printf("选项-:");浏览校园全景（Browser）:void Browser(MGraph *G)int v;printf("编号景点名称简介 n"); for (v = 0; v<G->vexnum; v+)printf("%-4d%-16s%-56sn", G->vexsv.num, G->v

11、, G->roduction);查看各景点游览路线（ShortestPath_DIJ）：void ShortestPath_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 (v0<0 | v0>G->vexnum

12、)printf("景点编号不存在!请重新输入景点编号:");scanf_s("%d", &v0);if (v0 >= 0 && v0<G->vexnum)flag = 0;for (v = 0; v<G->vexnum; v+)finalv = 0; /v不属于s，即v顶点还没有走过Dv = G->arcsv0v.adj; /v0到v的弧权值for (w = 0; w<G->vexnum; w+)pvw = 0; /设置空路径if (Dv<INFINITY)pvv0 = 1;

13、pvv = 1; /v0是从v0到v的顶点，v是从v0到v的顶点Dv0 = 0; finalv0 = 1; /初始化，v0到v0的带权路径长度为0，最短路径,v0顶点属于s集for (i = 1; i<G->vexnum; i+) /其余G.vexnum-1个顶点min = INFINITY; /当前所知离v0顶点的最近距离for (w = 0; w<G->vexnum; w+)if (!finalw) /w顶点在v-s中if (Dw<min) v = w; min = Dw; /w顶点离v0顶点更近finalv = 1; /离v0顶点最近的v加入s集for (w

14、 = 0; w<G->vexnum; w+) /更新当前的最短路径及距离if (!finalw && (min + G->arcsvw.adj<Dw) /修改Dw和Pw，w属于v-sDw = min + G->arcsvw.adj;for (x = 0; x<G->vexnum; x+)pwx = pvx;pww = 1; /用来更新到每一个顶点的最短路径for (v = 0; v<G->vexnum; v+)if (v0 != v) printf("%s", G->); /输

15、出字符串for (w = 0; w<G->vexnum; w+)if (pvw && w != v0) printf("->%s", G->);t+;if (t>G->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

16、;for (v = 0; v<G->vexnum; v+) /各对结点之间初始已知路径及距离for (w = 0; w<G->vexnum; w+)Dvw = G->arcsvw.adj;for (u = 0; u<G->vexnum; u+)pvwu = 0;if (Dvw<INFINITY)pvwv = 1; pvww = 1;for (u = 0; u<G->vexnum; u+)for (v = 0; v<G->vexnum; v+)for (w = 0; w<G->vexnum; w+)if (Dvu

17、 + Duw<Dvw) /从v经u到w的一条路径更短Dvw = Dvu + Duw; /修改权值for (i = 0; i<G->vexnum; i+)pvwi = pvui | puwi;while (flag)printf("请输入出发点和目的地的编号:");scanf_s("%d%d", &k, &j);if (k<0 | k>G->vexnum | j<0 | j>G->vexnum)printf("景点编号不存在!请重新输入出发点和目的地的编号:");sc

18、anf_s("%d%d", &k, &j);if (k >= 0 && k<G->vexnum&&j >= 0 && j<G->vexnum)flag = 0;printf("%s", G->);for (u = 0; u<G->vexnum; u+)if (pkju && k != u&&j != u)printf("->%s", G->vexsu.na

19、me);printf("->%s", G->);printf(" 总路线长%dmn", Dkj);/Floyd end查看景点信息(Search)：void Search(MGraph *G)int k, flag = 1;while (flag)printf("请输入要查询的景点编号:");scanf_s("%d", &k);if (k<0 | k>G->vexnum)printf("景点编号不存在!请重新输入景点编号:");scanf

20、_s("%d", &k);if (k >= 0 && k < G->vexnum)flag = 0;printf("%-4d%-16s%-56sn", G->vexsk.num, G->, G->roduction);/Search end显示图的邻接矩阵(print):void printMatrix(MGraph *G)int v, w, t = 0;printf("图的邻接矩阵为：n");for (v = 0; v<G->

21、;vexnum; v+)for (w = 0; w<G->vexnum; w+)if (G->arcsvw.adj = INFINITY)printf(" ");else printf("%-7d", G->arcsvw.adj);t+;if (t%G->vexnum = 0)printf("n");4.软件测试校园全景：选择出发点和目的地：邻接矩阵：5.参考文献严蔚敏 吴伟民编著， 数据结构（C语言版），清华大学出版社，2010年耿国华等.数据结构C语言描述.西安：西安电子科技大学出

22、版社，2002殷人昆.数据结构用面向对象方法与C+语言描述.北京：清华大学出版社，200756.代码#include "stdafx.h"#include<stdlib.h> /头文件#include<conio.h>#include<string.h>#define INFINITY 10000 /*无穷大*/#define MAX_VERTEX_NUM 40#define MAX 40typedef struct ArCell /对弧的定义int adj; /路径长度ArCell, AdjMatrixMAX_VERTEX_NUMMAX

23、_VERTEX_NUM; /一个二维数组,数组里元素类型为整型typedef struct /图中顶点表示主要景点，存放景点的编号、名称、简介等信息，char name30;int num;char introduction100;/简介infotype; /数据域typedef structinfotype vexsMAX_VERTEX_NUM; /顶点的数据域AdjMatrix arcs; /邻接矩阵int vexnum, arcnum; /图的当前顶点数和弧数MGraph;MGraph b; /全局变量void cmd(void);MGraph CreatGraph(void); /vo

24、id Menu(void); /void Browser(MGraph *G); / void ShortestPath_DIJ(MGraph * G); /void Floyd(MGraph *G); /void Search(MGraph *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;M

25、enu();scanf_s("%d", &i);while (i != 6)switch (i)case 1:system("cls"); Browser(&b); Menu(); break;case 2:system("cls"); ShortestPath_DIJ(&b); Menu(); break;case 3:system("cls"); Floyd(&b); Menu(); break;case 4:system("cls"); Search(&am

26、p;b); Menu(); break;case 5:system("cls"); printMatrix(&b); Menu(); break;case 6:exit(1); break;default:break;scanf_s("%d", &i); /输入的值d赋给iMGraph CreatGraph(void) /初始化MGraph G;int i, j;G.vexnum = 10; /14个顶点G.arcnum = 16; /14条弧for (i = 0; i<G.vexnum; i+)G.vexsi.num = i; /

27、第i个景点的编号为istrcpy_s(G., "北理图书馆"); /strcpy的头文件是string.hstrcpy_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, "位于学生住宅区中间地段，销售各式零食以及日用产品 ");strcpy_s(G., "第二饭堂");strcpy_s(G.roduction, "位于学生住宅中间地段，为附近的学生提供多样的伙食选择 ");strcpy_s(G.ve

29、, "第三饭堂");strcpy_s(G.roduction, "位于学生住宅末尾地段，环境别具一格，也是一种选择 ");strcpy_s(G., "快递中心");strcpy_s(G.roduction, "学校成立的快递服务中心，满足广大师生收发包裹的需求 ");strcpy_s(G., "学生餐厅");strcpy_s(G.roduction, "位于快递中心旁，为附近的

30、学生提供多样的伙食选择 ");strcpy_s(G., "游泳池");strcpy_s(G.roduction, "位于学校后山坡路段，拥有三个水池，于2014年10月建成。 ");strcpy_s(G., "明德楼");strcpy_s(G.roduction, "广大学生上课的地点，分四栋教学楼，各式教学设备都齐全。");for (i = 0; i<G.vexnum; i+)for (j = 0; j<G.vexn

31、um; 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.arcs29.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.arcs

32、78.adj = 120;G.arcs89.adj = 300;for (i = 0; i<G.vexnum; i+)for (j = 0; j<G.vexnum; j+)G.arcsji.adj = G.arcsij.adj; /无向网return G;void Menu() /定义主菜单printf(" 北京理工大学珠海学院导游图 n");printf(" n");printf(" 1.浏览校园全景 n");printf(" 2.查看各景点所有游览路线 n");printf(" 3.选择出

33、发点和目的地 n");printf(" 4.查看景点信息 n");printf(" 5.显示此图的邻接矩阵 n");printf(" 6.退出系统 n");printf(" n");printf("选项-:");void Browser(MGraph *G)int v;printf("n");printf("编号景点名称 简介 n");for (v = 0; v<G->vexnum; v+)printf("%-4d%-16s

34、%-56sn", G->vexsv.num, G->, G->roduction);printf("n");/ 迪杰斯特拉算法来计算出起点到各个顶点之间的最短路径,v0为起点void ShortestPath_DIJ(MGraph * G)int v, w, i, min, t = 0, x, flag = 1, v0; /flag=1保证输入编号有效int final20, D20, p2020;/用迪杰斯特拉算法求网G的v0顶点到其余顶点v的最短路径Pv及带权长度Dv/若Pvw为1，则w是从v0到v当前求

35、得最短路径上的顶点/finalv为1当且仅当v属于s(s是已求得最短路径的终点的集合)，即已经求得从v0到v的最短路径while (flag)printf("请输入一个起始景点编号:");scanf_s("%d", &v0); /输入一个值赋给v0if (v0<0 | v0>G->vexnum)printf("景点编号不存在!请重新输入景点编号:");scanf_s("%d", &v0);if (v0 >= 0 && v0<G->vexnum)fl

36、ag = 0;for (v = 0; v<G->vexnum; v+)finalv = 0; /v不属于s，即v顶点还没有走过Dv = G->arcsv0v.adj; /v0到v的弧权值for (w = 0; w<G->vexnum; w+)pvw = 0; /设置空路径if (Dv<INFINITY)pvv0 = 1; pvv = 1; /v0是从v0到v的顶点，v是从v0到v的顶点Dv0 = 0; finalv0 = 1; /初始化，v0到v0的带权路径长度为0，最短路径,v0顶点属于s集/开始主循环，每次求得v0到某个v顶点的最短路径，并加v到s集fo

37、r (i = 1; i<G->vexnum; i+) /其余G.vexnum-1个顶点min = INFINITY; /当前所知离v0顶点的最近距离for (w = 0; w<G->vexnum; w+)if (!finalw) /w顶点在v-s中if (Dw<min) v = w; min = Dw; /w顶点离v0顶点更近finalv = 1; /离v0顶点最近的v加入s集for (w = 0; w<G->vexnum; w+) /更新当前的最短路径及距离if (!finalw && (min + G->arcsvw.adj&

38、lt;Dw) /修改Dw和Pw，w属于v-sDw = min + G->arcsvw.adj;for (x = 0; x<G->vexnum; x+)pwx = pvx;pww = 1; /用来更新到每一个顶点的最短路径for (v = 0; v<G->vexnum; v+)if (v0 != v) printf("%s", G->); /输出字符串for (w = 0; w<G->vexnum; w+)if (pvw && w != v0) printf("->%s&qu

39、ot;, G->);t+;if (t>G->vexnum - 1 && v0 != v)printf(" 总路线长%dmnn", Dv);/ShortestPath_DIJ endvoid Floyd(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; v<G->vexnum; v+) /

40、各对结点之间初始已知路径及距离for (w = 0; w<G->vexnum; w+)Dvw = G->arcsvw.adj;for (u = 0; u<G->vexnum; u+)pvwu = 0;if (Dvw<INFINITY)pvwv = 1; pvww = 1;for (u = 0; u<G->vexnum; u+)for (v = 0; v<G->vexnum; v+)for (w = 0; w<G->vexnum; w+)if (Dvu + Duw<Dvw) /从v经u到w的一条路径更短Dvw = Dvu + Duw; /修改权值for (i = 0; i<G->vexnum; i+)pvwi = pvui | puwi;while (flag)printf("请输入出发点和