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

软软 件件 学学 院院 课程设计报告书课程设计报告书 课程名称课程名称 数据结构数据结构 设计题目设计题目 校园导航系统校园导航系统 专业班级专业班级 软件软件 11 0411 04 班班 学学 号号 10200104291020010429 姓姓 名名 张鸿雷张鸿雷 指导教师指导教师 刘亮刘亮 20132013 年年 1 1 月月 1 目目 录录 1 1 设计时间设计时间 2 2 2 2 设计目的设计目的 2 2 3 3 设计任务设计任务 2 2 4 4 设计内容设计内容 2 2 4 14 1 需求分析需求分析 2 2 4 24 2 总体设计总体设计 3 3 4 34 3 详细设计详细设计 5 5 4 44 4 测试与分析测试与分析 1616 4 4 14 4 1 测试测试 1616 4 4 24 4 2 分析分析 1818 4 54 5 附录附录 1 18 8 5 5 总结与展望总结与展望 2 25 5 参考文献参考文献 2 26 6 成绩评定成绩评定 2 26 6 2 1 设计时间设计时间 2013 年 1 月 20 日至 2013 年 1 月 23 日 2 设计目的设计目的 数据结构是计算机专业的核心课程 是计算机科学的算法理论基础和软件设计 的技术基础 数据结构是实践性很强的课程 课程设计是加强学生实践能力的一个 强有力手段 2 3 设计任务设计任务 要求学生掌握数据结构的应用 算法的编写 类 C 语言的算法转换成 C 程序并 上机调试的基本方法 课程设计要求学生在完成程序设计的同时能够写出比较规范 的设计报告 严格实施课程设计这一环节 对于学生基本程序设计素养的培养和软 件工作者工作作风的训练 将起到显著的促进作用 1 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 之间进行选择 要实现两点之间最短路径导 航 需输入起点和终点号 输入的起点和终点号在所给景点号里选择 要实现某点 3 到其他点的最短路径 需输入这个顶点号 顶点号也是在所给的景点号里选择 3 输出的形式 学校的所有景点 某个景点到其他景点的最短路径 或者两个景点之间的最短路径 4 测试数据 输入导航功能 x 输入起始点和终点号 0 和 16 输出正确的最短路径和路径长度 重新选择导航功能 选择导航功能 y 输入 出发点 2 输出景点 2 的简介 选择导 航功能 3 退出导航系统 若要实现导航功能 x 时输入错误 输出时就无路经 重新 输入起始点 结束点 若要实现功能 2 时输入错误 就会提示不存在这个地方 4 2 总体设计总体设计 1 说明本程序中用到的所有抽象数据类型的定义 2 ADT Graph 数据对象 V V 是具有相同特性的数据元素的集合 称为顶点集 数据关系 R R VR VR v w v w V 且 P v w 表示从 v 到 w 的弧 谓词 P v w 定义了弧 的意义和信息 3 基本操作 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已创建 操作结果 选择相应的功能 4 2 说明主程序的流程 开始 导航功能 选择 x 选择 y 选择 1 选择 z 构造有向网 G 两点间最短路径 结束 退出导航系统 输出导航结果 浏览景点以及简介 图 4 2 2 主程序流程图 开始 结束 5 3 各程序模块之间的层次 调用 关系 主程序模块 求最短路径模块 构建有向网模块 图 4 2 3 各程序模块之间的层次 调用 关系 4 3 详细设计详细设计 从流程图中可以看出来 主函数读取用户指令 根据指令调用函数 最终得到 用户想要查询的信息 1 1 采用邻接表存储结构 定义的抽象数据类型 1 typedef struct ArCell存放构造图的权值 int adj ArCell AdjMatrix MAX VERTEX NUM MAX VERTEX NUM 2 typedef struct 图中顶点表示主要景点 存放景点的编号 名称 简介等信 息 char name 30 int num char introduction 100 infotype 3 typedef struct infotype vexs MAX VERTEX NUM AdjMatrix arcs int vexnum arcnum 6 MGraph MGraph b 2 主程序以及主要函数 2 1 主函数 void main void system color 5f 修改控制台的颜色信息 改为白字蓝底的模式 system mode con cols 140 lines 130 设置批处理运行时窗口大小的 cmd 2 cmd函数通过这个函数实现选择服务项目的内容 void cmd void char k b InitGraph show1 Menu while 1 scanf n c switch k case x system cls show1 Menu list ShortestPath DIJ printf 欢迎您的使用 7 n printf n请您继续选择服务 break case y system cls Menu list Search printf 欢迎您的使用 n printf n请您继续选择服务 break case z system cls printf n printf 感谢使用 n printf 辽宁工程技术大学 n printf 智能导航系统 n printf n exit 0 default printf 输入信息错误 n请输入x或y或z n break 3 计算最短路径的迪杰斯特拉算法实现 1 void ShortestPath DIJ MGraph G int v w i min t 0 x flag 1 v0 v1 have 100 k int final 20 D 20 p 23 23 8 while flag printf 请输入起始景点编号 n scanf d if v0G vexnum printf 景点编号不存在 printf 请输入终止景点编号 n scanf d if v1G vexnum printf 景点编号不存在 if v0 0 for v 0 vvexnum v final v 0 D v G arcs v0 v adj for w 0 wvexnum w p v w INFINITY if D v INFINITY p v v0 1 p v v 1 D v0 0 final v0 1 9 have 0 v0 for i 1 ivexnum i min INFINITY for w 0 wvexnum w if final w if D w min v w min D w final v 1 have k v k for w 0 wvexnum w if final w for x 0 xvexnum x p w x p v x p w w 1 for i 0 ivexnum i if p v1 have i 1 printf s G vexs have i name if v1 v0 1 printf n路径长度 d n G arcs v0 v1 10 else printf n路径长度 d n D v1 ShortestPath DIJ end 4 查找函数的建立实现用户对景点查找的实现 void Search MGraph G int k flag 1 while flag printf 请输入要查询的景点编号 scanf d if kG vexnum printf 景点编号不存在 请重新输入景点编号 scanf d if k 0 printf n printf 编号 景点名称 简介 n printf 4d 16s 58s n G vexs k num G vexs k name G vexs k introduction printf n Search end 5 对要进行浏览的地区的平面图输出 11 void show1 printf t t 欢迎使用辽宁工程技术大学智能导航系统 n printf t t t辽宁工程技术大学葫芦岛校区平面图 n n printf t 学校北门 n printf t n printf t 行政楼 静远楼 n printf t n printf t 耘慧楼 n printf t n printf t n printf t 体育场 尔雅楼 n printf t n printf t 二食堂 n printf t n printf t D楼 n printf t E楼 n printf t C楼 n printf t n printf t 小体育场 篮球场 综合楼 小拱桥 n printf t n printf t 一食堂 n printf t 浴池 B楼 A楼 n 6 用户根据显示的学校景点序号 查询景点信息 void list printf 学校景点列表 n printf 0 学校南门 12 printf 1 静远楼 printf 2 耘慧楼 printf 3 尔雅楼 printf 4 小拱桥 n printf 5 A楼 printf 6 B楼 printf 7 一食堂 printf 8 综合楼 n printf 9 行政楼 printf 10 体育场 printf 11 二食堂 printf 12 D楼 printf 13 E楼 n printf 14 C楼 printf 15 浴池 printf 16 篮球场 足球场 n n 7 目录函数对本系统提供的服务进行提示 以便用户使用 void Menu printf n 辽宁工程技术大学葫芦岛校区导游图 n printf n printf x 选择出发点和目的地 n printf y 查看景点信息 n printf z 退出系统 n printf n printf 请选择服务 13 8 对无向网的构建以便于实现本系统的功能 MGraph InitGraph void MGraph G int i j G vexnum 17 顶点是17个 G arcnum 25 弧线有25个 for i 0 i G vexnum i G vexs i num i strcpy G vexs 0 name 学校北门 strcpy G vexs 0 introduction 学校的正门 行政楼高高耸立 气势宏伟 strcpy G vexs 1 name 静远楼 strcpy G vexs 1 introduction 电控 电信学院用楼 设有图书馆 阅览室等 strcpy G vexs 2 name 耘慧楼 strcpy G vexs 2 introduction 软件 工商学院用楼 设有若干机房 为同学提 供更多方便 strcpy G vexs 3 name 尔雅楼 strcpy G vexs 3 introduction 学生上课 自习的地方 strcpy G vexs 4 name 小拱桥 strcpy G vexs 4 introduction 连接生活区和教学区的桥 strcpy G vexs 5 name A楼 strcpy G vexs 5 introduction 男生宿舍 strcpy G vexs 6 name B楼 strcpy G vexs 6 introduction 女生宿舍 strcpy G vexs 7 name 一食堂 strcpy G vexs 7 introduction 食堂 可用饭卡吃饭 strcpy G vexs 8 name 综合楼 strcpy G vexs 8 introduction 校区内的百货大楼 14 strcpy G vexs 9 name 行政楼 strcpy G vexs 9 introduction 学校行政办公场所 校区最高的建筑 strcpy G vexs 10 name 体育场 strcpy G vexs 10 introduction 运动会举办地 strcpy G vexs 11 name 二食堂 strcpy G vexs 11 introduction 校区最实惠的食堂 内有回民餐厅 strcpy G vexs 12 name D楼 strcpy G vexs 12 introduction 男生宿舍 strcpy G vexs 13 name E楼 strcpy G vexs 13 introduction 男生宿舍 strcpy G vexs 14 name C楼 strcpy G vexs 14 introduction 女生宿舍 strcpy G vexs 15 name 浴池 strcpy G vexs 15 introduction 学生洗澡的地方 strcpy G vexs 16 name 篮球场 足球场 strcpy G vexs 16 introduction 比赛以及学生运动的地方 for i 0 i G vexnum i for j 0 j G vexnum j G arcs i j adj INFINITY G arcs 0 1 adj 50 G arcs 1 2 adj 15 G arcs 1 3 adj 40 G arcs 2 3 adj 30 G arcs 0 3 adj 90 G arcs 3 4 adj 30 G arcs 4 9 adj 1000 G arcs 4 5 adj 20 G arcs 5 6 adj 10 G arcs 6 7 adj 8 15 G arcs 6 8 adj 12 G arcs 7 8 adj 7 G arcs 0 9 adj 30 G arcs 9 10 adj 500 G arcs 10 11 adj 25 G arcs 11 12 adj 8 G arcs 12 13 adj 5 G arcs 13 14 adj 10 G arcs 12 14 adj 10 G arcs 14 15 adj 150 G arcs 15 16 adj 3 G arcs 5 15 adj 150 G arcs 4 15 adj 30 G arcs 1 11 adj 300 G arcs 8 14 adj 40 for i 0 i G vexnum i for j 0 j G vexnum j G arcs j i adj G arcs i j adj return G InitGraph end 16 3 函数的调用关系图 3 InitGraph menu 选择 x 选择 y cmd 图 4 3 3 函数的调用关系图 1 4 4 测试与分析测试与分析 4 4 1 测试测试 输入导航功能 x Search 路径长度 ArCell AdjMatrix MAX VERTEX NUM MAX VERTEX NUM typedef struct 图中顶点表示主要景点 存放景点的编号 名称 简介等信息 char name 30 int num char introduction 100 简介 infotype typedef struct infotype vexs MAX VERTEX NUM AdjMatrix arcs int vexnum arcnum MGraph MGraph b void cmd void MGraph InitGraph void void show1 void list void Menu void void ShortestPath DIJ MGraph G void Search MGraph G int LocateVex MGraph G char v 主函数 void main void 19 system color 5f 修改控制台的颜色信息 改为白字蓝底的模式 system mode con cols 140 lines 130 设置批处理运行时窗口大小的 cmd 自定义函数 cmd函数 根据目录选择要进行的项目 void cmd void char k b InitGraph show1 Menu while 1 scanf n c switch k case x system cls show1 Menu list ShortestPath DIJ printf 欢迎您的使用 n printf n请您继续选择服务 break case y system cls Menu list Search printf 欢迎您的使用 n printf n请您继续选择服务 break case z system cls printf n printf 感谢使用 n printf 辽宁工程技术大学 n printf 智能导航系统 n printf n exit 0 20 default printf 输入信息错误 n请输入x或y或z n break 迪杰斯特拉算法来计算出起点到各个顶点之间的最短路径 v0为起点 void ShortestPath DIJ MGraph G int v w i min t 0 x flag 1 v0 v1 have 100 k int final 20 D 20 p 23 23 while flag printf 请输入起始景点编号 n scanf d if v0G vexnum printf 景点编号不存在 printf 请输入终止景点编号 n scanf d if v1G vexnum printf 景点编号不存在 if v0 0 for v 0 vvexnum v final v 0 D v G arcs v0 v adj for w 0 wvexnum w p v w INFINITY if D v INFINITY p v v0 1 p v v 1 D v0 0 final v0 1 have 0 v0 for i 1 ivexnum i 21 min INFINITY for w 0 wvexnum w if final w if D w min v w min D w final v 1 have k v k for w 0 wvexnum w if final w for x 0 xvexnum x p w x p v x p w w 1 for i 0 ivexnum i if p v1 have i 1 printf s G vexs have i name if v1 v0 1 printf n路径长度 d n G arcs v0 v1 else printf n路径长度 d n D v1 ShortestPath DIJ end 查找函数的建立 void Search MGraph G int k flag 1 while flag printf 请输入要查询的景点编号 scanf d if kG vexnum printf 景点编号不存在 请重新输入景点编号 scanf d 22 if k 0 printf n printf 编号 景点名称 简介 n printf 4d 16s 58s n G vexs k num G vexs k name G vexs k introduction printf n Search end void show1 printf t t 欢迎使用辽宁工程技术大学智能导航系统 n printf t t t辽宁工程技术大学葫芦岛校区平面图 n n printf t 学校北门 n printf t n printf t 行政楼 静远楼 n printf t n printf t 耘慧楼 n printf t n printf t n printf t 体育场 尔雅楼 n printf t n printf t 二食堂 n printf t n printf t D楼 n printf t E楼 n printf t C楼 n printf t n printf t 小体育场 篮球场 综合楼 小拱桥 n printf t n printf t 一食堂 n printf t 浴池 B楼 A楼 n void list printf 学校景点列表 n printf 0 学校南门 printf 1 静远楼 printf 2 耘慧楼 printf 3 尔雅楼 23 printf 4 小拱桥 n printf 5 A楼 printf 6 B楼 printf 7 一食堂 printf 8 综合楼 n printf 9 行政楼 printf 10 体育场 printf 11 二食堂 printf 12 D楼 printf 13 E楼 n printf 14 C楼 printf 15 浴池 printf 16 篮球场 足球场 n n 目录函数的构建 void Menu printf n 辽宁工程技术大学葫芦岛校区导游图 n printf n printf x 选择出发点和目的地 n printf y 查看景点信息 n printf z 退出系统 n printf n printf 请选择服务 MGraph函数 图的构建 MGraph InitGraph void MGraph G int i j G vexnum 17 顶点是17个 G arcnum 25 弧线有25个 for i 0 i G vexnum i G vexs i num i strcpy G vexs 0 name 学校北门 strcpy G vexs 0 introduction 学校的正门 行政楼高高耸立 气势宏伟 strcpy G vexs 1 name 静远楼 strcpy G vexs 1 introduction 电控 电信学院用楼 设有图书馆 阅览室等 strcpy G vexs 2 name 耘慧楼 strcpy G vexs 2 introduction 软件 工商学院用楼 设有若干机房 为同学提 供更多方便 strcpy G vexs 3 name 尔雅楼 strcpy G vexs 3 introduction 学生上课 自习的地方 24 strcpy G vexs 4 name 小拱桥 strcpy G vexs 4 introduction 连接生活区和教学区的桥 strcpy G vexs 5 name A楼 strcpy G vexs 5 introduction 男生宿舍 strcpy G vexs 6 name B楼 strcpy G vexs 6 introduction 女生宿舍 strcpy G vexs 7 name 一食堂 strcpy G vexs 7 introduction 食堂 可用饭卡吃饭 strcpy G vexs 8 name 综合楼 strcpy G vexs 8 introduction 校区内的百货大楼 strcpy G vexs 9 name 行政楼 strcpy G vexs 9 introduction 学校行政办公场所 校区最高的建筑 strcpy G vexs 10 name 体育场 strcpy G vexs 10 introduction 运动会举办地 strcpy G vexs 11 name 二食堂 strcpy G vexs 11 introduction 校区最实惠的食堂 内有回民餐厅 strcpy G vexs 12 name D楼 strcpy G vexs 12 introduction 男生宿舍 strcpy G vexs 13 name E楼 strcpy G vexs 13 introduction 男生宿舍 strcpy G vexs 14 name C楼 strcpy G vexs 14 introduction 女生宿舍 strcpy G vexs 15 name 浴池 strcpy G vexs 15 introduction 学生洗澡的地方 strcpy G