校园导游咨询.doc

_课程设计(论文)任务书 软 件 学 院 学院 软 件+电气 专业 班一、课程设计(论文)题目 校园导游咨询 二、课程设计(论文)工作自 2011 年 12 月 26 日起至 2011 年 12 月 30 日止 三、课程设计(论文) 地点: 创 新 大 楼 机 房 四、课程设计(论文)内容要求：1本课程设计的目的训练学生灵活应用所学数据结构知识，独立完成问题分析，结合数据结构理论知识，编写程序求解指定问题；初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；提高综合运用所学的理论知识和方法独立分析和解决问题的能力，巩固、深化学生的理论知识，提升编程水平。2课程设计的任务及要求1）基本要求：要求从分析题目的需求入手，按设计抽象数据类型、构思算法、通过设计实现抽象数据类型、编写上机程序和上机调试等若干步骤完成题目，最终写出完整的报告；在程序设计阶段应尽量利用已有的标准函数，加大代码的重用率；程序设计语言推荐使用C/C+，程序书写规范，源程序需加必要的注释；每位同学需提交可独立运行的程序和规范的课程设计报告。2）课程设计论文编写要求理论设计部分以课程设计论文的形式提交，格式必须按照课程设计论文标准格式进行书写和装订；课程设计报告（论文）包括中文目录、设计任务、需求分析、概要设计、详细设计、编码实现、调试分析、课设总结、谢辞、参考文献、附录等；设计部分应包含系统功能模块图，调试分析应包括运行截图等。3）课程设计评分标准： 学习态度：10分；系统设计：20分；编程调试：20分；回答问题：20分；论文撰写：30分。4）参考文献：严蔚敏,吴伟民. 数据结构(C语言版)M. 清华大学出版社. 2010.3 严蔚敏,吴伟民. 数据结构题集(C语言版)M. 清华大学出版社. 1999.2何钦铭,冯燕等. 数据结构课程设计M. 浙江大学出版社. 2007.85）课程设计进度安排准备阶段（4学时）：选择设计题目、了解设计目的要求、查阅相关资料；程序模块设计分析阶段（4学时）：程序概要设计、详细设计；代码编写调试阶段（8学时）：程序模块代码编写、调试、测试；撰写论文阶段（4学时）：总结课程设计任务和设计内容，撰写课程设计论文。学生签名： 2011 年 12 月 26 日6）课程设计题目具体要求：（1）设计华东交通大学的校园平面图，所含景点不少于10个。以图中顶点表示校内各景点； （2）存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息； （3）为来访客人提供图中任意景点相关信息的查询； （4）为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径课程设计(论文)评审意见（1）学习态度（10分）：优（）、良（）、中（）、一般（）、差（）； （2）系统设计（20分）：优（ ）、良（）、中（）、一般（）、差（）； （3）编程调试（20分）：优（）、良（）、中（）、一般（）、差（）；（4）回答问题（20分）：优（）、良（）、中（）、一般（）、差（）；（5）论文撰写（30分）：优（）、良（）、中（）、一般（）、差（）；（6）格式规范性及考勤是否降等级：是（）、否（）评阅人： 王英华 职称： 讲师 2012 年 1 月 4 日目录一、题目要求01二、需求分析02三、概要设计02四、详细设计04五、编码实现05六、调试运行08七、课设总结09八、参考文献09一、 题目要求1、问题描述：设计一个校园导游程序，为来访的客人提供各种信息查询服务。2、基本要求：设计华东交通大学的校园平面图，所含景点不少于10个。以图中顶点表示校内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。为来访客人提供图中任意景点相关信息的查询。为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。二、需求分析1、从华东交通大学平面图中选取10个大家熟悉的景点，抽象成一个无向带权图。以图中顶点表示景点，边上的权值表示两地的距离。 2、本程序的目的是为用户提供路径咨询和景点查询。根据用户指定的始点和终点输出相应路径或者根据用户指定的景点输出景点的信息。三、概要设计寻找最短路径是图论中的一个经典问题，对于这个经典问题已经提出了许多不同的解决方案。用确定的带权边可以表示如下信息，诸如城市之间的距离，确定任务的执行时间段，两地之间信息传输的开销，两地之间物质运输总量等等。当确定从顶点V到顶点U间的最短路径时，中间顶点W的相关距离信息要记录下来。这个信息记录了与顶点V 相关联的标记，这个路径中，该标记只表示顶点V到顶点W的距离或者从顶点W的前驱顶点到V的距离。查找最短路径的方法要依据这些标记。根据这些标记校正的次数，解决最短路径的方法分为两类：标记设置法和标记校正法。对于标记设置法，遍历经过的每一个顶点都要被处理，给每一个顶点设置一个值，也就是设置标记，该值一直到运行结束都保持不变。这样使得此方法只能处理包含正权的图。第二类型包括标记校正法，在使用该方法时要允许处理过程中对标记进行修改。这两种方法都能运用于负权的图和含反向循环的图中（反向环是指构成此环的边的权数累加到了一个负值），这两种方法都可以保证，对所有得顶点而言，一旦图处理完成后，当前距离就表示该顶点对于所有顶点的最短路径。然而大多数标记设置法和标记校正法都可以归纳为同一类，因为他们都可以用来寻找从一个顶点到其他所有顶点间的最短路径。本文采用的数据结构：/*包含头文件*/#include#include/*定义符号常量*/#define MaxVertexNum 20 /*景点个数最大20*/#define MAXCOST 1000 /*定义路径的无穷大*/#define T 10 /*目前景点个数*/*定义全局变量*/int shortestMaxVertexNumMaxVertexNum; /*定义全局变量存贮最小路径*/int pathMaxVertexNumMaxVertexNum; /*定义存贮路径*/*自定义函数原型说明*/void introduce()void floyd()void display(int i,int j)int shortestdistance()四、详细设计1、顶点，边和图类型#define MaxVertexNum 20 /*景点个数最大20*/#define MAXCOST 1000 /*定义路径的无穷大*/#define T 10 /*目前景点个数*/typedef struct char name20; /*景点名称*/ char number15; /*景点代号*/ char introduce100; /*景点简介*/Elemtype;typedef struct int num; /*顶点编号*/ Elemtype date; /*顶点信息*/Vertex; /*定义顶点*/2、路径类型typedef struct Vertex vexsMaxVertexNum; /*存放顶点的一维数组,数组第零个单元没有用上*/ unsigned int edgesMaxVertexNumMaxVertexNum; /*存放路径的长度*/ int n,e;MGraph;MGraph MGr; /*全局变量,定义MGr为MGraph类型*/int shortestMaxVertexNumMaxVertexNum; /*定义全局变量存贮最小路径*/int pathMaxVertexNumMaxVertexNum; /*定义存贮路径*/五、编码实现#define MaxVertexNum 20 /*景点个数最大20*/#define MAXCOST 1000 /*定义路径的无穷大*/#define T 10 /*目前景点个数*/typedef struct char name20; /*景点名称*/ char number15; /*景点代号*/ char introduce100; /*景点简介*/Elemtype;typedef struct int num; /*顶点编号*/ Elemtype date; /*顶点信息*/Vertex; /*定义顶点*/typedef struct Vertex vexsMaxVertexNum; /*存放顶点的一维数组,数组第零个单元没有用上*/ unsigned int edgesMaxVertexNumMaxVertexNum; /*存放路径的长度*/ int n,e;MGraph;MGraph MGr; /*全局变量,定义MGr为MGraph类型*/int shortestMaxVertexNumMaxVertexNum; /*定义全局变量存贮最小路径*/int pathMaxVertexNumMaxVertexNum; /*定义存贮路径*/void floyd() int i,j,k; for(i=1;i=T;i+) for(j=1;j=T;j+) shortestij=MGr.edgesij; pathij=0; /*初始化数组*/ for(k=1;k=T;k+) for(i=1;i=T;i+) for(j=1;j(shortestik+shortestkj) shortestij=shortestik+shortestkj; pathij=k; pathji=k;/*记录经过的路径*/ /end_if /end_forvoid display(int i,int j)/* 打印两个景点的路径及最短距离 */ int a,b; a=i; b=j; cout您要查询的两景点间最短路径是:nn; if(shortestij!=MaxVertexNum) if(ij) coutb; while(pathij!=0) /* 把i到j的路径上所有经过的景点按逆序打印出来*/ cout-pathij; if(ij) j=pathij; else i=pathji; cout-a; coutnn; coutab最短距离是shortestab米nn; else couta; while(pathij!=0) /* 把i到j的路径上所有经过的景点按顺序打印出来*/ coutpathij; if(ij) j=pathij; else i=pathji; coutb; coutnn; coutab最短距离是:shortestab米nnendl; else cout输入错误！不存在此路！nn; /*display*/void main() char k; init(); cout*n; cout* *n; cout* *n; cout* 欢迎使用校园导游咨询 *n; cout* *n; cout*n; while(1) cout1.景点信息查询请按 i 键n; cout2.景点最短路径查询请按 s 键n; cout3.退出系统请按 e 键n; coutk; switch(k) case i: cout景点简介查询（请输入110）。; introduce();break; case s: cout景点最短路径查询。; shortestdistance(); break; case e: exit(0); system(pause);六、调试运行七、课设总结通过对校园导游咨询程序的分析与解答，我