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

北京理工大学珠海学院课程设计说明书_2014_2015_学年第_ 1 _学期题目: 北理珠校园导游咨询与最短路径 学 院： 计算机学院 专业班级： 学 号： 学生姓名： 指导教师： 王琳 成 绩： 时 间： 2014年12月30日 2014 年 12 月 30 日设计任务书2014 2015学年 第1学期学生姓名： 专业班级： 指导教师： 王琳 工作部门： 计算机学院 一、课程设计题目北理珠校园导游咨询与最短路径二、课程设计内容（含技术指标）【问题描述】从北京理工大学珠海学院的平面图中选取有代表性景点（10-15个），抽象成一个无向带权图。以图中顶点表示景点，边上的权值表示两地之间距离。本程序的目的是为用户提供路径咨询。根据用户指定的始点和终点输出相应路径，或者根据用户指定的景点输出景点的信息。【任务要求】从北京理工大学珠海学院的平面图中选取有代表性景点（10-15个），抽象成一个无向带权图。以图中顶点表示校内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等信息。为来访客人提供图中任意景点相关信息的查询。为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。区分汽车线路与步行线路。【测试数据】北理珠校园导游图（距离可估计）。三、进度安排1初步设计：写出初步设计思路，进行修改完善，并进行初步设计。2详细设计：根据确定的设计思想，进一步完善初步设计内容，按要求编写出数据结构类型定义、各算法程序、主函数。编译分析调试错误。3测试分析：设计几组数据进行测试分析，查找存在的设计缺陷，完善程序。4报告撰写：根据上面设计过程和结果，按照要求写出设计报告。5答辩考核验收：教师按组（人）检查验收，并提出相关问题，以便检验设计完成情况。四、基本要求1在设计时，要严格按照题意要求独立进行设计，不能随意更改。若确因条件所限，必须要改变课题要求时，应在征得指导教师同意的前提下进行。 2在设计完成后，应当场运行和答辩，由指导教师验收，只有在验收合格后才能算设计部分的结束。 3设计结束后要写出课程设计报告，以作为整个课程设计评分的书面依据和存档材料。设计报告以规定格式的电子文档书写、打印并装订，报告格式严格按照模板要求撰写，排版及图、表要清楚、工整。从总体来说，所设计的程序应该全部符合要求，问题模型、求解算法以及存储结构清晰；具有友好、清晰的界面；设计要包括所需要的辅助程序，如必要的数据输入、输出、显示和错误检测功能；操作使用要简便；程序的整体结构及局部结构要合理；设计报告要符合规范。 课程负责人签名： 年 月 日课程设计分工安排姓名课程设计负责工作备注成绩评定表姓 名成绩评定权重总分总成绩（五分制）平时成绩20报告成绩50答辩成绩30摘 要 通过数据结构“图”构成抽象数据类型，该系统运用了数组表示法（领结矩阵）初始化图，分别存储数据元素（景点）和数据元素（路段）之间的关系，迪杰斯特拉算法来描述各景点所有游览路径，佛洛依德算法设计景点之间的最短路径，结合上述算法设计了一个校园导航与最短路径系统，供来访北理珠的客人使用，为其提供方便。关键词：概要设计 详细设计 软件测试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问题的描述从北京理工大学珠海学院的平面图中选取有代表性景点（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个景点的编号为istrcpy_s(G.vexs0.name, 北理图书馆); 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.概要设计 2.1要点描述 用图的算法进行构造，用邻接表建立图，图的每一个顶点代表相应的景点。然后再用深度优先遍历进行搜索，查找所需的路径。再用迪杰特斯拉算法求出一个景点到其他景点之间的最佳路径。然后再用弗洛伊德算法求出要查询的出发点到目的地的最短路径。2.2模块分解 （1） 主菜单（Menu）：存放着所有的选择供用户查询。用户可通过输入编号来查询自己想要获得的信息 （2） 浏览校园全景（Browser）：采用深度遍历图进行所有景点浏览，将遍历景点信息输出。（3）查看各景点游览路线（ShortestPath_DIJ）：用户输入一个景点，采用迪杰斯特拉算法将从该景点起所有路径查出并输出在屏幕上。（4）选择出发点和目的地(Floyd)：用户输入一个出发点和一个目的地编号，采用弗洛伊德算法求出发点到目的地的最短路径。（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.查看景点信息 n);printf( 5.显示此图的邻接矩阵 n);printf( 6.退出系统 n);printf( n);printf(选项-:);浏览校园全景（Browser）:void Browser(MGraph *G)int v;printf(编号景点名称简介 n); for (v = 0; vvexnum; v+)printf(%-4d%-16s%-56sn, G-vexsv.num, G-vexsv.name, G-vexsv.introduction);查看各景点游览路线（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 (v0G-vexnum)printf(景点编号不存在!请重新输入景点编号:);scanf_s(%d, &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集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.adjarcsvw.adj;for (x = 0; xvexnum; x+)pwx = pvx;pww = 1; /用来更新到每一个顶点的最短路径for (v = 0; vvexnum; v+)if (v0 != v) printf(%s, G-vexsv0.name); /输出字符串for (w = 0; wvexnum; w+)if (pvw & w != v0) printf(-%s, G-vexsw.name);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+) /各对结点之间初始已知路径及距离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)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-vexsk.name);for (u = 0; uvexnum; u+)if (pkju & k != u&j != u)printf(-%s, G-vexsu.name);printf(-%s, G-vexsj.name);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(%-4d%-16s%-56sn, G-vexsk.num, G-vexsk.name, G-vexsk.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( );else printf(%-7d, G-arcsvw.adj);t+;if (t%G-vexnum = 0)printf(n);4.软件测试校园全景：选择出发点和目的地：邻接矩阵：5.参考文献严蔚敏吴伟民编著，数据结构（C语言版），清华大学出版社，2010年耿国华等.数据结构C语言描述.西安：西安电子科技大学出版社，2002殷人昆.数据结构用面向对象方法与C+语言描述.北京：清华大学出版社，200756.代码#include stdafx.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;/简介infotype; /数据域typedef structinfotype 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(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;Menu();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(&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; iG.vexnum; i+)G.vexsi.num = i; /第i个景点的编号为istrcpy_s(G.vexs0.name, 北理图书馆); /strcpy的头文件是string.hstrcpy_s(G.vexs0.introduction, 图书馆是学校的文献信息中心，是为学校教学的学术性机构。);strcpy_s(G.vexs1.name, 第一饭堂);strcpy_s(G.vexs1.introduction, 位于田径场对面，提供诸多款饭菜供学生选择。 );strcpy_s(G.vexs2.name, 教工餐厅);strcpy_s(G.vexs2.introduction, 临近明德楼的一个餐厅，为师生们提供最便捷的伙食 );strcpy_s(G.vexs3.name, 零食前线);strcpy_s(G.vexs3.introduction, 位于学生住宅区中间地段，销售各式零食以及日用产品 );strcpy_s(G.vexs4.name, 第二饭堂);strcpy_s(G.vexs4.introduction, 位于学生住宅中间地段，为附近的学生提供多样的伙食选择 );strcpy_s(G.vexs5.name, 第三饭堂);strcpy_s(G.vexs5.introduction, 位于学生住宅末尾地段，环境别具一格，也是一种选择 );strcpy_s(G.vexs6.name, 快递中心);strcpy_s(G.vexs6.introduction, 学校成立的快递服务中心，满足广大师生收发包裹的需求 );strcpy_s(G.vexs7.name, 学生餐厅);strcpy_s(G.vexs7.introduction, 位于快递中心旁，为附近的学生提供多样的伙食选择 );strcpy_s(G.vexs8.name, 游泳池);strcpy_s(G.vexs8.introduction, 位于学校后山坡路段，拥有三个水池，于2014年10月建成。 );strcpy_s(G.vexs9.name, 明德楼);strcpy_s(G.vexs9.introduction, 广大学生上课的地点，分四栋教学楼，各式教学设备都齐全。);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.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.arcs78.adj = 120;G.arcs89.adj = 300;for (i = 0; iG.vexnum; i+)for (j = 0; jG.vexnum; j+)G.arcsji.adj = G.arcsij.adj; /无向网return G;void Menu() /定义主菜单printf( 北京理工大学珠海学院导游图 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(n);printf(编号景点名称 简介 n);for (v = 0; vvexnum; v+)printf(%-4d%-16s%-56sn, G-vexsv.num, G-vexsv.name, G-vexsv.introduction);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当前求得最短路径上的顶点/finalv为1当且仅当v属于s(s是已求得最短路径的终点的集合)，即已经求得从v0到v的最短路径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不属于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集/开始主循环，每次求得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.adjarcsvw.adj;for (x = 0; xvexnum; x+)pwx = pvx;pww = 1; /用来更新到每一个顶点的最短路径for (v = 0; vvexnum; v+)if (v0 != v) printf(%s, G-vexsv0.name); /输出字符串for (w = 0; wvexnum; w+)if (pvw & w != v0) printf(-%s, G-vexsw.name);t+;if (tG-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; 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的一条路径更短Dvw = Dvu + Duw; /修改权值for (i = 0; ivexnum; i+)pvwi = pvui | puwi;while (flag)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-vexsk.name);for (u = 0; uvexnum; u+)if (pkju & k != u&j != u)printf(-%s, G-vexsu.name);printf(-%s, G-vexsj.name);printf( 总路线长%dmn, Dkj);/Floyd endvoid 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(n);printf(编号景点名称 简介 n);printf(%-4d%-16s%-56sn, G-vexsk.num, G-vexsk.name, G-vexsk.introduction);printf(n);/Search endvoid 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( );else printf(%-7d, G-arcsvw.adj);t+;if (t%G-vexnum = 0)printf(n);答辩记录表专业学院专业姓名学号课程设计题目答辩日期答辩时间答辩提问及其回答记录