校园导游咨询的实现的程序设计.doc

铜 陵 学 院 数学与计算机科学系 课 程 设 计设计题目： 校园导游咨询系统的实现 系 别 数学与计算机科学系 班级 10信管班 学生姓名 赵梦阳 学号 1006121048 指导教师 杨慧 职称 教师 起止日期：2011年 12 月 19 日起至 2011 年12 月23日止铜 陵 学 院 数据结构 课程设计任务书课程设计题目： 校园导游咨询系统的实现 系 别 数学与计算机科学系 班级 10信管班 学生姓名 赵梦阳 学号 1006121048 指导教师 杨慧 职称 教师 课程设计进行地点： 实验楼C406 任 务 下 达 时 间： 2011年12月19日起止日期：2011 年12 月19 日起至 2011 年12月23日止22一、课程设计的目的1. 设计一个校园导游系统，为来客查询校园的各种信息2. 熟练掌握图的知识、加深课堂所学用于实践二、课程设计要求1、设计你所在学校的校园平面图，所含景点不少于10个。以图中顶点表示校园内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。2、为来访客人提供图中任意景点相关信息的查询。3、为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。三、对课程设计说明书撰写内容、格式、字数的要求1课程设计报告是体现和总结课程设计成果的载体，主要内容包括：设计题目、设计目的、实验器材、设计原理及内容、设计具体步骤、遇到的问题及解决方法、设计总结、参考文献等。一般不应少于3000字。2在适当位置配合相应的实验原理图、实验数据表、问题分析流程图等图表进行说明。应做到文理通顺，内容正确完整，书写工整，装订整齐。3设计总结部分主要写本人完成工作简介以及自己的设计体会，包括通过课程设计学到了什么，哪里遇到了困难，解决的办法以及今后的目标。4课程设计报告打印时采用A4纸，页边距均为20mm，正文采用宋体小四号字，行间距20磅。文中大标题采用黑体小三号字，一级节标题采用黑体四号字，二级节标题采用黑体小四号字，表题与图题采用宋体五号字。5课程设计报告装订顺序为：封面、任务书、成绩评定表、目录、正文、参考文献。四、设计题目五、成绩评定评定成绩根据系统功能、界面效果，系统操作的方便性、灵活性等方面进行，主要从三个方面进行考虑：1、对问题的理解程度；2、成果的好坏；3、设计报告。评定结果：不及格、及格、中、良好、优秀。 六、时间进度安排顺序阶段日期计 划 完 成 内 容备注12011.12.19查阅资料,撰写读书笔记无22011.12.20系统设计,数据结构设计，算法设计无32011.12.21编程并上机调试无42011.12.22撰写报告无52011.12.23验收程序，提交设计报告书无七、主要参考文献1、数据结构-C语言描述（主编：耿国华）高等教育出版社2、数据结构（C语言版） 编著：严蔚敏、吴伟民 清华大学出版社铜 陵 学 院 数 学 与 计 算 机 科 学 系 校园导游咨询的实现 课程设计成绩评定表教研室：实验楼C406 班级： 10信管班 学生姓名： 赵梦阳 指 导 教 师 评 审 意 见评价内容具 体 要 求权重评 分加权分调 研论 证能独立查阅文献,收集资料；能制定课程设计方案和日程安排。0.15432工作能力态 度工作态度认真，遵守纪律，出勤情况是否良好，能够独立完成设计工作， 0.25432工 作 量按期圆满完成规定的设计任务，工作量饱满，难度适宜。0.25432说明书的质 量说明书立论正确，论述充分，结论严谨合理，文字通顺，技术用语准确，符号统一，编号齐全，图表完备，书写工整规范。0.55432指导教师评审成绩（加权分合计乘以12） 分加权分合计指 导 教 师 签 名： 年 月 日评 阅 教 师 评 审 意 见评价内容具 体 要 求权重评 分加权分查 阅文 献查阅文献有一定广泛性；有综合归纳资料的能力0.25432工 作 量工作量饱满，难度适中。0.55432说明书的质 量说明书立论正确，论述充分，结论严谨合理，文字通顺，技术用语准确，符号统一，编号齐全，图表完备，书写工整规范。0.35432评阅教师评审成绩（加权分合计乘以8）分加权分合计评 阅 教 师 签 名： 年 月 日课 程 设 计 总 评 成 绩分摘 要现代快节奏的生活是的都市人越来越渴望亲近自然，因此外出旅游现在被越来越多的都市人所看中，所以如何快速方便的找到我们想要的旅游景点的信息和最短路径就成了一个很重要的问题。本设计基于图的结构，创建了一个旅游图，针对旅客的实际需求，将铜陵学院的景点编号、名称、介绍等信息放入道途的顶点当中并保存在景点文本文件当中。利用迪杰斯特拉算法来求从一个景点到另一个景点的最小距离等等，最后按照显示屏上的提示进行操作。关键词 查找信息、最短距离、校园导游咨询目 录摘要1第1章 引言2第2章 系统分析3第3章 概要设计4第4章 详细设计5第4章 运行与测试6程序代码7结论7致谢8参考文献9第1章 引言课程设计是实践性教学中的一个重要环节，它以某一课程为基础，可以涉及和课程相关的各个方面，是一门独立于课程之外的特殊课程。课程设计是让同学们对所学的课程更全面的学习和应用，理解和掌握课程的相关知识。数据结构是一门重要的专业基础课，是计算机理论和应用的核心基础课程。数据结构课程设计，要求学生在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面，加深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。在这次的课程设计中我选择的题目是校园导游咨询。当到一个陌生的地方去旅游时，人们常常需要一个导游为自己在游玩过程中提供服务，比如介绍参观景点的历史背景等相关信息，推荐到下一个景点的最佳路线，以及解答旅游者提出的关于旅游景点的相关问询，等等。对于刚刚来到大学校园的新生，对校园环境不熟悉的情况也是如此，如果能够提供一个程序让新生或来访的客人自主的与机器“对话”来获得相关信息，将会节省人力和时间，而且所提供的信息也能够保证尽可能的准确、详尽。本实验要求设计一个校园导游程序，为来访的客人提供各种信息查询服务。第2章 系统分析1 本校园景点平面图设计的主要目的是为用户提供以下主要信息：第一，为用户展示一个比较全面的校园全景图，让游客做到对所要浏览的校园心中有数，尽可能做到一目了然；第二，当游客置身于景点中时，可以为用户提供平面中某景点到其余各景点的浏览路线及其各自最短路径，以便使用户更好的完成自己的浏览计划，从而节省时间放松身心；第三，为用户提供平面图中任意场所的问路查询，即查询任意两个景点之间的一条最短的简单路径，旨在为用户的旅游大大提高效率；第四，为用户提供平面图中任意场所的相关信息的查询，简单介绍平面图中各景点的特点，概况和相关职能，让用户有选择的进行浏览；第五，为保证景点平面图的完整和准确，本设计提供了用户更新完善平面图的功能；最后本设计本着完整健壮的追求，设计了退出系统环节，让用户用的更舒心。2 校园平面图设计的基本功能包括：为用户提供当前所在景点到图中任意景点的一条最短路径，及其任意两个场所之间的最短简单路径等等。由于这两个基本功能是基于图结构的实际的景点网络，所以要采用图的邻接矩阵存储结构，又因为校园道路往往是双向通行的，因此该平面图可被看做带各种信息的无向网。故重点是完成计算并记录从某景点到各个场所的最短路径，以及接收用户输入的场所名称，并在计算机的最短路径集合中找到相关项的信息反馈给用户。3 既为校园景点平面图设计，就需要一个模块来为用户提供一个较全面的校园全景图，以及图中各景点信息的查询服务。那么MGraph InitGraph(void)；void Menu()；void Browser(MGraph *G)；这三个函数实现了呈现校园全景图的功能。而void Search(MGraph *G)；int LocateVex(MGraph *G,char* v)；这两个函数主要实现的是定位图中某景点并完成该景点的信息查询功能。4 演示程序是以用户于计算机的对话方式执行，这需要一个模块来完成使用者与计算机语言是转化。5 程序执行时的命令：本程序为了使用时的方便，采用菜单式的方式来完成程序的演示，几乎不用输入什么特殊的命令，只需按提示输入选者即可。（要注意输入时格式，否者可能会引起一些错误）6 测试数据：本设计查询部分的测试数据分为以下三种：1）平面图中各景点的编号，编号范围为0到9十个数字；2）各景点编号的组合，例如2 3，2“Enter”3；3）五个选项编号，范围从1到5五个数字。另外更新部分的测试数据为用户输入的顶点数和弧数范围。第3章 概要设计 1、 校园全景一览图、显示出校园的平面图。2、 提供校园中任意景点问路查询，即求任意两个景点之间的所有路径。3、提供校园图中多个景点的最佳访问路线查询，即求途径这过个景点的最佳（短）路径。1功能模块图；void Map();/校园地图void CreateGraph();/创建图void OutputPlace();/输出景点列表void SearchPlace();/查询景点信息void SearchPath();/查询最短路径void Shortpath(int i);/计算最短路径void Output(int sight1,int sight2);/输出函数2各个模块详细的功能描述。Map();/显示校园整体的地图、包含学校各景点的详细位置CreateGraph();/创建图、主要用来保存各景点信息OutputPlace();/输出景点列表、供选择景点信息查询时使用SearchPlace();/查询景点信息、景点的名称及介绍SearchPath();/查询最短路径、两景点间最短距离Shortpath(int i);/计算两景点间最短路径Output(int sight1,int sight2);/输出两景点最短路径及信息第4章 详细设计1、Main()1功能函数的调用关系图 CreateGraph() SearchPlace() Map() SearchPath()Outputplace()Shortpath(i);Output(i,j);2各功能函数的数据流程图全局变量：Graph G;int pathNUMNUM;int DNUM;3 重点设计及编码 重点设计：求最短路径 编码：void Shortpath(int num)/迪杰斯特拉算法最短路径 int v,w,i,t;/i、w和v为计数变量/t表示景点个数int finalNUM; /标志数组、用来存放顶点的信息int min;/记录权值、最终输出路径for(v=0;vNUM;v+)finalv=0; /假设从顶点num到顶点v没有最短路径Dv=G.arcnumv.length;/将num到其余顶点的最短路径长度初始化为权值for(w=0;wNUM;w+) pathvw=0;/初始化从v到w的路径值if(DvMAX) /存在路径pathvnum=1; /存在标志置为一pathvv=1; /自身到自身Dnum=0;/初始化新路径 finalnum=1; /初始化num顶点属于final集合 /开始主循环,每一次求得num到某个顶点的最短路径，并将其加入到final集合 for(i=0;iNUM;+i) / 其余G.vexnum-1个顶点 min=MAX; /当前所知离顶点num的最近距离for(w=0;wNUM;+w)if(!finalw) /w顶点在v-s中 if(Dwmin) /w顶点离num顶点更近 v=w;min=Dw; finalv=1; /离num顶点更近的v加入到s集合 for(w=0;wNUM;+w) /更新当前最短路径极其距离 if(!finalw&(min+G.arcvw.length)Dw)/不在s集合，并且比以前所找到的路径都短就更新当前路径 Dw=min+G.arcvw.length;/更新路径for(t=0;tNUM;t+)pathwt=pathvt;pathww=1;void Output(int sight1,int sight2) / 输出函数 int a,b,c,d,q=0;/a、b、c和d为计数变量/q控制计数变量、用于换行a=sight2; /将景点二赋值给a if(a!=sight1) / 如果景点二不和景点一输入重合，则进行. printf(tttttt从%s到%s的最短路径是:nnttttt,G.,G.);/输出提示信息/输出sight1到sight2的最短路径长度，存放在D数组中printf(t%s,G.); /输出景点一的名称 d=sight1; /将景点一的编号赋值给dfor(c=0;cNUM;+c)gate:; /标号，可以作为goto语句跳转的位置 pathasight1=0; for(b=0;bNUM;b+) if(G.arcdb.length%s,G.); /输出此节点的名称 q=q+1; /计数变量加一，满8控制输出时的换行 pathab=0; d=b; /将b作为出发点进行下一次循环输出，如此反复 if(q%14=0) printf(n); goto gate; printf(nntttttt最短距离为 %dm.nnt,Da); 第五章 运行与测试1 正常测试数据和运行结果1、系统主界面2、校园全景浏览3、 景点信息查询4、 最短路径查询2 异常测试数据及运行结果1、异常数据2、 异常数据程序代码#include #include #include #include #include #define MAX 100000#define NUM 30#define FALSE 0#define TURE 1typedef struct ArcNode int length; /路径长度 ArcNode, *ArcLink; /边结点的定义typedef struct VertexNode int number; /景点的编号 char *name; /景点的名称 char *info; /景点的简介 VertexNode; /顶点结点的定义typedef struct Graph VertexNode vertexNUM; ArcNode arcNUMNUM; int vexnum,arcnum; /图的顶点数，边数 Graph; /图的定义void Map();/校园地图void CreateGraph();/创建图void OutputPlace();/输出景点列表void SearchPlace();/查询景点信息void SearchPath();/查询最短路径void Shortpath(int i);/计算最短路径void Output(int sight1,int sight2);/输出函数Graph G;int pathNUMNUM;int DNUM;void CreateGraph()/创建图int i,j;G.vexnum=14;G.arcnum=28;for(i=1;iNUM;i+) G.vertexi.number=i;G.=学校正门;G.=学校正门位于学校的正南方向、是进入学校前的第一道亮丽的风景线!n;G.=逸夫楼;G.=逸夫楼是新建的，还未完成。是学校为工科学生所建的!n;G.=教学楼;G.=教学楼是学生学习上课的地方,分A、B、C、D四栋。ntttttt其中C栋楼有5层,1-4层为各种教学使用;5层以英语听力课程教室为主!ntttttt!n;G.=小坡;G.=小坡是进入学校后的第一道风景线,位于学校的正门口;ntttttt环境优雅!n;G.=一食堂;G.=是女生食堂!ntttttt当然也有男生，卫生。食物美味!n;G.=大学生活动中心;G.=大学生活动中心是我校专为学生设计、展现自己各种特长才艺的地方!ntttttt每周这里都会有非常精彩的活动、晚会;乃才艺高人的聚集地!n;G.=工科学生实验楼;G.=工科学生是供我们做实验的地方ntttttt是实践的天堂!n;G.=洗浴中心;G.=洗浴中心是学生洗浴的地方!n;G.=篮球场;G.=篮球场是同学们篮球课程及锻炼球技的地方,也是篮球比赛的重要场所n;G.=系部楼;G.=系部楼是老师办公的地方;ntttttt也是学生领导办公的地方!;G.=塑胶跑道;G.=塑胶跑道主要供学生平时运动、跑步使用;其侧面还有网球场地;ntttttt是同学们课外活动的地点之一!n;G.=篮球场;G.=篮球场是同学们篮球课程及锻炼球技的地方,也是篮球比赛的重要场所!n;G.=女生宿舍;G.=女生宿舍主要是女生居住，当然还有少数男生!n;G.=土操场;G.=土操场主要供学生运动的地方!n;for(i=0;iNUM;+i)for(j=0;j0 & num=G.vexnum) /判定信息输入正确for(i=1;i14):); scanf(%d,&i); printf(tttttt最终景点编号(1-14):); scanf(%d,&j); getchar();if(iG.vexnum | iG.vexnum | j0 | i=j) printf(tttttt输入信息错误!nn); else Shortpath(i);Output(i,j);printf(ntttttt是否继续查询最短路径(y/n):);c=getchar(); getchar(); system(cls);void Shortpath(int num)/迪杰斯特拉算法最短路径 int v,w,i,t;/i、w和v为计数变量/t表示景点个数int finalNUM; /标志数组、用来存放顶点的信息int min;/记录权值、最终输出路径for(v=0;vNUM;v+)finalv=0; /假设从顶点num到顶点v没有最短路径Dv=G.arcnumv.length;/将num到其余顶点的最短路径长度初始化为权值for(w=0;wNUM;w+) pathvw=0;/初始化从v到w的路径值if(DvMAX) /存在路径pathvnum=1; /存在标志置为一pathvv=1; /自身到自身Dnum=0;/初始化新路径 finalnum=1; /初始化num顶点属于final集合 /开始主循环,每一次求得num到某个顶点的最短路径，并将其加入到final集合 for(i=0;iNUM;+i) / 其余G.vexnum-1个顶点 min=MAX; /当前所知离顶点num的最近距离for(w=0;wNUM;+w)if(!finalw) /w顶点在v-s中 if(Dwmin) /w顶点离num顶点更近 v=w;min=Dw; finalv=1; /离num顶点更近的v加入到s集合 for(w=0;wNUM;+w) /更新当前最短路径极其距离 if(!finalw&(min+G.arcvw.length)Dw)/不在s集合，并且比以前所找到的路径都短就更新当前路径 Dw=min+G.arcvw.length;/更新路径for(t=0;tNUM;t+)pathwt=pathvt;pathww=1;void Output(int sight1,int sight2) / 输出函数 int a,b,c,d,q=0;/a、b、c和d为计数变量/q控制计数变量、用于换行a=sight2; /将景点二赋值给a if(a!=sight1) / 如果景点二不和景点一输入重合，则进行. printf(tttttt从%s到%s的最短路径是:nnttttt,G.,G.);/输出提示信息/输出sight1到sight2的最短路径长度，存放在D数组中printf(t%s,G.); /输出景点一的名称 d=sight1; /将景点一的编号赋值给dfor(c=0;cNUM;+c)gate:; /标号，可以作为goto语句跳转的位置 pathasight1=0; for(b=0;bNUM;b+) if(G.arcdb.length%s,G.); /输出此节点的名称 q=q+1; /计数变量加一，满8控制输出时的换行 pathab=0; d=b; /将b作为出发点进行下一次循环输出，如此反复 if(q%14=0) printf(n); goto gate; printf(nntttttt最短距离为 %dm.nnt,Da); void main() int x;system(color 2B);system(mode con: cols=170 lines=160);/调整屏幕显示大小 CreateGraph();printf(nnnnnttttttt欢迎使用西安邮电学