数据结构课程设计--校园导航系统

软 件 学 院

课程设计报告书

课程名称 数据结构 设计题目 校园导航系统 专业班级 软件10-03班 学 号 1020010319 姓 名 滕飞 指导教师 刘玲玲

2012年1月

目 录

1 设计时间 ................................................... 2 2 设计目的 ................................................... 2 3设计任务 ................................................... 2 4 设计内容 ................................................... 2 4.1需求分析 ................................................. 2 4.2总体设计 ................................................. 3 4.3详细设计 ................................................. 5 4.4测试与分析 .............................................. 16 4.4.1测试 ........................................................................................... 16 4.4.2分析 ........................................................................................... 18 4.5 附录 ..................................... 错误！未定义书签。 5 总结与展望 ................................................ 26 参考文献 .................................................... 27 成绩评定 .................................................... 28

1

1 设计时间 2011年1月3日至2011年1月6日 2 设计目的 数据结构是计算机专业的核心课程，是计算机科学的算法理论基础和软件设计的技术基础。数据结构是实践性很强的课程。课程设计是加强学生实践能力的一个强有力手段。 3设计任务 要求学生掌握数据结构的应用、算法的编写、类C语言的算法转换成C程序并上机调试的基本方法。课程设计要求学生在完成程序设计的同时能够写出比较规范的设计报告。严格实施课程设计这一环节，对于学生基本程序设计素养的培养和软件工作者工作作风的训练，将起到显著的促进作用。 4 设计内容 题目：校园导航系统 设计任务： 给出校园各主要建筑的名称信息及有线路联通的建筑之间的距离，利用校园导航系统计算出给定的起点到终点之间的最近距离及线路。 设计要求： 1、 2、 3、 输入各建筑信息及线路信息，构建图。 计算给定起点到终点之间最近距离的进行线路。 输出线路及总距离。 4.1需求分析 1.程序所能达到的功能； (1) CreateDN(MGraph *G) ——创建有向网G，储存学校的各个景点。 (2) ShortPath(MGraph G,int v0,int p[MAX_V][MAX_V],int d[])——求的有向网G中某个顶点到其余顶点的最短路径及其带权长度。 (3) menu()——目录函数，按照要求选择相应的功能。 2、输入的形式和输入值的范围 首先输入导航功能号，只能在x至y之间进行选择；要实现两点之间最短路径导航，需输入起点和终点号，输入的起点和终点号在所给景点号里选择；要实现某点到2

其他点的最短路径，需输入这个顶点号，顶点号也是在所给的景点号里选择。 3、输出的形式 学校的所有景点，某个景点到其他景点的最短路径，或者两个景点之间的最短路径 4、测试数据： 输入导航功能x输入起始点和终点号0和16，输出正确的最短路径和路径长度；重新选择导航功能。选择导航功能y，输入,出发点2，输出景点2的简介。选择导航功能3，退出导航系统。若要实现导航功能x时输入错误，输出时就无路经。重新输入起始点，结束点。若要实现功能2时输入错误，就会提示不存在这个地方。 4.2总体设计 1、说明本程序中用到的所有抽象数据类型的定义 ADT Graph{ 数据对象V:V是具有相同特性的数据元素的集合,称为顶点集. 数据关系R: R={VR} VR={(v,w)|v,w∈V且P(v,w)，表示从v到w的弧，谓词P(v,w)定义了弧的意义和信息} 基本操作P: Int CreateDN(MGraph *G) 操作结果：创造有向网G。} void Shortpath(MGraph G,int v0,int p[MAX_V][MAX_V],int d[]) 初始条件：有向网G已创建。 操作结果：有向网G的V0定点到其余定点V的最短路径P[v]及其带权长度D[v]。 若P[v][w]为True，则w是从V0到V当前求得最短路径上的顶点。 Final[v]为True当且仅当V∈S，即已经求得从V0到V的最短路径。 void menu() 初始条件：有向网G已创建。 操作结果：选择相应的功能。 3

2、说明主程序的流程 开始 构造有向网G 选择x 两点间最短路径 导航功能 选择y 选择z 退出导航系统 浏览景点以及简介 输出导航结果 结束 图4.2-2 主程序流程图 4