河南工程学院数据结构实训报告

河河 南南 工工 程程 学学 院院 实实 习习 报报 告告 课 程 数据结构 院 系 计算机学院 专 业 计算机科学与技术 班 级 班 姓 名 学 号 年 6 月 27 日 实 习 训 报 告 评 语 等 级 评阅人 职称 年月日 河南工程学院 实 习 训 报 告 实习内容 校园导航系统 实习时间 自 6 月 24 日 至 6 月 28 日 共5 天 实习地点 实习单位 计算机学院 指导教师 院长 I 目目 录录 一 设计目标 1 二 课题分析与设计 1 1 课题需求分析 1 2 算法设计 1 3 存储结构设计 1 4 程序流程图 9 三 程序清单 10 四 测试 20 1 测试数据 20 2 测试结果及分析 21 总结 24 1 一 一 设计目标设计目标 1 对自己学过的知识进一步的加深理解 对数据结构的算法思想要有更深 的理解 2 通过课程设计 学会通过系统分析 系统设计 编程调试 写实验报告 等环节 进一步掌握应用系统设计的方法和步骤 灵活运用并深刻理解典型数 据结构在软件开发中的应用 3 学会综合运用数据结构课程中学到的几种典型数据结构 如图 链表 存储结构 以及程序设计语言 C 语言 自行实现一个较为完整的应用系统的 设计与开发 二 二 课题分析与设计课题分析与设计 1 课题需求分析课题需求分析 1 1 运行环境 运行环境 Microsoft Visual C 6 0 2 2 程序所实现的功能 程序所实现的功能 设计你的学校的平面图 至少包括 10 个以上的景点 场所 每两个景点间 可以有不同的路 且路长也可能不同 找出从任意景点到达另一景点的最佳 路径 最短路径 3 3 程序的输入和包含输入的数据格式和说明 程序的输入和包含输入的数据格式和说明 用户只需要按照页面的提示输入需要操作的序号 然后按回车确认即可 4 4 程序的输出格式和说明 程序的输出格式和说明 当用户输入所要查询的地点序号 并且回车后 屏幕自动生成所 查询路径 的最短路线和距离 2 算法算法设计设计 1 1 主要函数的说明 主要函数的说明 define Max 32767 用 Max 来表示权值为此时的两点间直接不可达 2 define NUM 18 选取了学校的十八个地点用数组存储 其中数组第一 个元素不存储地点以方便操作 typedef struct VertexType int number char sight VertexType 定义顶点的结构体类型 number 表示顶点编号 字符数组 表示顶点的名称 typedef struct VertexType vex NUM int arcs NUM NUM int vexnum MGraph 定义图的结构体类型 vex NUM 数组存储顶点 arcsp NUM NUM 矩阵存储边的权值 vexnum 表示顶点的个数 MGraph G 生成 G 表示结构体变量 MGraph int P NUM NUM 定义全局变量 P NUM NUM 存储点之间的最短路径 long int D NUM 定义全局变量 D NUM 存储点之间最短路径的权值 void Dijkstra int num 通过迪杰斯特拉算法求 num 点到其余点的最 短路径 并将最短路径保存在数组 P NUM NUM 中 将最短路径的权值保存在 数组 D NUM 中 int v w i t int final NUM int min for v 1 v NUM v final v 0 置空最短路径终点集 D v G arcs num v 置初始的最短路径长度 3 for w 1 w NUM w P v w 0 置空最短路径 if D v 32767 P v num 1 P v v 1 D num 0 final num 1 初始化 num 顶点属于 S 集 for i 1 i NUM i 开始循环 每次求得 num 到某个顶点的最短路径 并 添加到 S 集 min Max min 为当前所知的 num 到顶点的最短距离 for w 1 w NUM w if final w w 顶点在 V S 集中 if D w min v w min D w final v 1 与 num 相距最近的顶点并入 S 集 for w 1 w NUM w 更新最短路径 if final w for t 0 t NUM t P w t P v t 4 P w w 1 char Menu 主菜单显示于操作界面从而让用户选择查询路径功能或 者查询地点信息功能 char c int flag 定义标志 flag 确定循环条件 do flag 1 Map printf t t 1 查询地点路径 n printf t t 2 地点信息简介 n printf t t e 退出 n printf t 河南工程学院 n printf t t t 请输入您的选择 scanf c if c 1 c 2 c e flag 0 while flag return c void Display int sight1 int sight2 输出函数用于通过数组 P NUM NUM 提取出从点 sight1 到点 sight2 的最短路径 从 D NUM 中输出 点 sight1 到点 sight2 的最短路径的权值 int a b c d q 0 5 a sight2 if a sight1 printf n t 从 s 到 s 的最短路径是 G vex sight1 sight G vex sight2 sight printf t 最短距离为 dm n n t D a 从 D NUM 中提取出 sight1 到 sight2 的最短距离的权值输出 printf t s G vex sight1 sight d sight1 for c 0 c NUM c P a sight1 0 for b 0 b NUM b if G arcs d b s G vex b sight 通过 P NUM NUM 确 定 sight1 到 sight2 的最短路径 q q 1 P a b 0 d b if q 8 0 printf n void main 主函数 6 int v0 v1 char e char ck CreateMGraph NUM Do 用 do while 循环确保循环至少进行一次 system cls 用 system cls 清屏使屏幕简洁 ck Menu switch ck 用 switch 语句确定用户选择功能 case 1 gate 门函数使程序退回到 gate 位置 system cls Map do printf n n t t t 请选择出发地序号 1 17 scanf d if v017 printf n n t t t t 输入错误 n while v017 do printf t t t 请选择目的地序号 1 17 scanf d if v117 v1 v0 printf n n t t t t 输入错误 n while v117 v1 v0 Dijkstra v0 7 Display v0 v1 printf n n t t t t 请按任意键继续 按 e 退回首页 n getchar scanf c if e e 当标识符 e 等于 e 时跳出语句 break goto gate case 2 system cls Info printf n n t t t t 请按回车键退回首页 n getchar getchar break while ck e 当标识符 ck 不等于 e 时继续循环 2 时间复杂度分析时间复杂度分析 1 Void CreateMGraph int v 其中为顶点赋值用了一次 for 循环 为邻接矩阵赋值用了两次 for 循环且 相互嵌套 故时间复杂度为 O 2 nn 2 void Dijkstra int num 其中为置空初始值用了两次 for 循环且相互嵌套 更新路径长度用了四次 for 循环且相互嵌套 故其时间复杂度为 O 24 nn 3 Void Display int sight1 int sight2 其中输出最短路径用了两次 for 循环且相互嵌套 故时间复杂度为 O 2 n 8 3 存储结构设计存储结构设计 结构体的定义 typedef struct VertexType int number char sight VertexType typedef struct VertexType vex NUM int arcs NUM NUM int vexnum MGraph 常量的定义 define Max 32767 define NUM 1 各个函数的定义 void CreateMGraph int v 创建图的函数 其中 v 表示图中的顶点数 void Map 地图展示函数 用于输出河南工程学院的平面简略图 char Menu 主菜单显示于操作界面 void Info 资料介绍函数 用于当用户选择查询地点资料时输出地点的 资料信息 void Dijkstra int num 迪杰斯特拉函数 void Display int sight1 int sight2 地图展示函数 void main 主函数的定义 9 4 程序流程图程序流程图 欢迎使用河南工程学院校园导航系统 1 查询 地点 之间 最短 路径 2 河南 工程 学院 景点 介绍 e 退 出 请选 择出 发地 序号 1 17 请选 择目 的地 序号 1 17 按回 车键 返回 首页 按 回 车 键 继 续 按 e 退 回 首 页 10 三 三 程序清单程序清单 include include include define Max 32767 define NUM 18 typedef struct VertexType int number char sight VertexType typedef struct VertexType vex NUM int arcs NUM NUM int vexnum MGraph MGraph G int P NUM NUM long int D NUM void CreateMGraph int v 创建图的函数 int i j G vexnum v for i 1 i G vexnum i G vex i number i G vex 0 sight 各个景点名字 G vex 1 sight 河南工程学院南大门 G vex 2 sight 南苑宾馆 G vex 3 sight 人工湖 11 G vex 4 sight 东门 G vex 5 sight 图书馆 G vex 6 sight 二号实验楼 G vex 7 sight 大西门 G vex 8 sight 巴士停车站 G vex 9 sight 体育活动中心 G vex 10 sight 学生活动中心 G vex 11 sight 小东门 G vex 12 sight 圣源餐厅 G vex 13 sight 商业中心 后勤中心 G vex 14 sight 西区操场 G vex 15 sight 小西门 G vex 16 sight B 区宿舍 G vex 17 sight A 区宿舍 for i 1 i G vexnum i for j 1 j G vexnum j G arcs i j Max G arcs 1 2 G arcs 2 1 30 G arcs 3 2 G arcs 2 3 100 G arcs 4 3 G arcs 3 4 50 G arcs 4 10 G arcs 10 4 200 G arcs 5 3 G arcs 3 5 100 G arcs 5 6 G arcs 6 5 100 G arcs 5 9 G arcs 9 5 100 G arcs 6 8 G arcs 8 6 100 G arcs 6 7 G arcs 7 6 50 G arcs 8 9 G arcs 9 8 100 G arcs 8 16 G arcs 16 8 70 12 G arcs 9 16 G arcs 16 9 50 G arcs 14 16 G arcs 16 14 70 G arcs 14 15 G arcs 15 14 80 G arcs 9 10 G arcs 10 9 100 G arcs 9 17 G arcs 17 9 70 G arcs 17 12 G arcs 12 17 30 G arcs 17 11 G arcs 11 17 20 G arcs 12 13 G arcs 13 12 20 G arcs 12 11 G arcs 11 12 20 G arcs 10 17 G arcs 17 10 70 void Map 地图展示函数 system color 0a printf 欢迎使用河南工程学院地图导航系统 n printf 设计者 n printf 北 n printf 乒乓 13 商业中心 后勤中 心 n printf 球场 n printf 12 圣 源 餐 厅 n printf 15 小西门 篮 n printf B 0 4 11 小东门 n printf 球 A 0 6 A 0 4 n 13 printf 西 B 0 3 B 0 6 17 A 区宿舍楼 n printf 区 16 B 区 宿舍楼 场 A 0 5 A 0 3 n printf 14 操 B 0 2 B 0 5 n printf 场 A 0 2 n printf B 0 1 n printf 9 体育 活动 中心 A 0 1 n printf 8 巴士 10 学生活动中 心 n printf 停车站 n printf n printf 六号教学楼 n printf 绿 n printf 三号 五号教学楼 n printf 实验楼 地 n printf 四号教学楼 n printf 大 n 14 printf 7 西 5 图书馆 n printf 门 n printf 三号教学楼 n printf 6 二号 人 n printf 实验楼 二号教学楼 3 工 n printf 湖 n printf 一号教学楼 n printf 4 东门 n printf n printf 2 南苑 宾馆 n printf n printf 1 河南工程学院大门 n void Info 资料介绍函数 printf 1 河南工程学院南大门 西校区的正门 门口有个大型喷泉 n printf 2 人工湖 人工开凿的湖 也是学校唯一的湖 n 15 printf 3 大西门 直接通至 107 国道 n printf 4 图书馆 河南工程学院的标志 西校区的核心建筑 n printf 5 学生活动中心 一楼大礼堂可举办各种大型晚会 n printf 6 体育活动中心 有室内篮球馆 游泳馆 乒乓球馆等 n printf 7 二号实验楼 二号及其北面的三号实验楼是同学们进行各项试验的地方 n printf 8 巴士停车站 学校内部的公交车 可以到达东区 终点站是东区 n printf 9 东门 可直接通过此到达东区 n printf 10 南苑宾馆 接待外宾 n printf 11 小东门 可以到达学校对面的商业区 只能过人 不能过车 n printf 12 圣源餐厅 学校唯一的餐厅 有三层 有全国各地的饭菜 n printf 13 商业中心 后勤中心 商业中心有学校的超市 同学们可以在商业中心购 买生活用品和学习用品 后勤中心是为同学们的生活提供服务 n printf 14 操场 学校可以在此举办运动会等活动 同学们也可以在这里进行体育活 动 n printf 15 小西门 可以到达学校对面的商业区 只能过人 不能过车 n printf 16 B 区宿舍 B 区共有六栋宿舍楼 其中 B01 B04 四栋是女生宿舍楼 B05 B06 两栋是男生宿舍楼 n printf 17 A 区宿舍 A 区共有六栋宿舍楼 且都是男生宿舍楼 n void Dijkstra int num 迪杰斯特拉算法最短路径 int v w i t int final NUM int min for v 1 v NUM v final v 0 16 D v G arcs num v for w 1 w NUM w P v w 0 if D v Max P v num 1 P v v 1 D num 0 final num 1 for i 1 i NUM i min Max for w 1 w NUM w if final w if D w min v w min D w final v 1 for w 1 w NUM w if final w for t 0 t NUM t P w t P v t P w w 1 17 char Menu 主菜单 char c int flag do system cls flag 1 Map printf t t n printf t t 1 查询地点之间最短路径 n printf t t 2 河南工程学院景点介绍 n printf t t e 退出 n printf t t t 请输入您的选择 scanf c if c 1 c 2 c e flag 0 while flag return c void Display int sight1 int sight2 输出函数 int a b c d q 0 a sight2 if a sight1 printf n t 从 s 到 s 的最短路径是 G vex sight1 sight G vex sight2 sight 18 printf t 最短距离为 dm n n t D a printf t s G vex sight1 sight d sight1 for c 0 c NUM c P a sight1 0 for b 0 b NUM b if G arcs d b s G vex b sight q q 1 P a b 0 d b if q 8 0 printf n void main 主函数 int v0 v1 char e char ck CreateMGraph NUM do system cls 19 ck Menu switch ck case 1 gate system cls Map do printf n n t t t 请选择出发地序号 1 17 scanf d if v017 printf n n t t t t 输入错误 请重新输入 n while v017 do printf t t t 请选择目的地序号 1 17 scanf d if v117 v1 v0 printf n n t t t t 输入错误 请重新输入 n while v117 v1 v0 Dijkstra v0 Display v0 v1 printf n n t t t t 按回车键继续 按 e 退回首页 n getchar scanf c if e e break goto gate case 2 20 system cls Info printf n n t t t t 按回车键返回首页 n getchar getchar break while ck e 四 四 测试测试 1 测试数据测试数据 运行程序 打开程序所显示的界面 输入 1 回车 进入查询地点之间最短路径界面 输入 2 回车 进入河南 工程学院景点介绍界面 当用户进入最短距离查询界面后 如输入起始地点序号 1 河南工程学 院大门 和终点序号后 5 图书馆 屏幕上自动生成这两条路径之间的最 短距离 230 米 和最短路径河南工程学院大门 南苑宾馆 人工湖 图书馆 当用户输入起始地点序号 7 大西门 和终点序号后 13 后勤中心 屏幕上自动生成多条路径中的最短路径距离 450 米 和最短路径大西