没有合适的资源?快使用搜索试试~ 我知道了~
数据结构课程设计报告+完整代码+校园导航程序
需积分: 5 0 下载量 194 浏览量
2024-08-06
11:59:45
上传
评论
收藏 2MB PDF 举报
温馨提示
校园导航程序实现的实质其实是对带权无向图进行的各种操作,其中需要的计算机专业课程知识 点主要为: 1. 带权无向图的储存与构造(这里采用的是邻接矩阵)。 2. 图的深层遍历(判断带权无向图两顶点间是否可达和输出任意两顶点间的所有路径)。 3. Dijkstra 算法
资源推荐
资源详情
资源评论
《 数据结构 》课程实习(设计)报告
题目: 校园导航程序
一、引言
校园导航程序实现的实质其实是对带权无向图进行的各种操作,其中需要的计算机专业课程知识
点主要为:
1. 带权无向图的储存与构造(这里采用的是邻接矩阵)。
2. 图的深层遍历(判断带权无向图两顶点间是否可达和输出任意两顶点间的所有路径)。
3. Dijkstra 算法
[1]
(求最短路径)。
二、系统设计与实现
函数的定义:
void initG();// 初始化图
void menu();//显示菜单
void search_info();//建筑信息查询
void add_info();//新增建筑和道路信息
void modify_info();//修改建筑和道路信息
void delete_info();//删除建筑和道路信息
void search_path();//求任意两建筑的路径
void short_path();//求两个建筑之间的最短路径
void is_reach();//判断两个建筑之间是否可达
三、设计过程
1、设计思路
主要设计思想:将校园导航查询程序的所需的地图抽象为一个带权无向图,地图中所有建筑抽象
为图的顶点,建筑之间的道路抽象为顶点间的边。要实现该程序就是要对带权无向图进行各种操作,
如查询顶点信息、查询顶点间的最短路径、增加、删除和更新顶点信息、判断两顶点间是否连通等。
1)操作:查询图中任意两个建筑物间的最短路径
算法:Dijkstra 算法和利用数组模拟栈操作。
2)操作:判断两个建筑物之间是否可达、求两个建筑之间的最短路径
算法:图的深度遍历(DFS)。
2、程序设计流程图
3、函数实现说明
1)void short_path()//求两个建筑之间的最短路径
设计思路与实现步骤:首先判断用户输入的起始和到达顶点是否都存在(若不存在,则直接回到
菜单页面),然后调用 Dijkstra()函数找到两个顶点间的最短路径,然后将路径所经过的所有顶
点下放进数组中,计算顶点个数,然后通过顶点下标循环输出顶点,以此来输出两个建筑间的最短
路径,最后在调用菜单函数 menu()返回菜单,从而继续进行下一个操作。
2)void search_path();//求任意两建筑的路径
设计思路与实现步骤:首先初始化带权无向图的所有顶点(全部置为未访问状态),然后判断用
户输入的起始和到达顶点是否都存在(若不存在,则直接返回到菜单页面),接着调用 DFS()函数
(该函数通过循环遍历图,遇到和起始顶点间存在路径的未访问顶点则将其标记成已访问。如果该顶
点是终点则直接打印,否则就将该顶点下标放入数组。然后递归调用自己,直到找到的顶点等于终点),
最后在调用菜单函数 menu()返回菜单,从而继续进行下一个操作。
3)void is_reach();//判断两个建筑之间是否可达
设计思路与实现步骤:首先判断用户输入的起始和到达顶点是否都存在(若不存在,则直接返回到菜
单页面),然后调用 DFS2()函数(该函数通过循环遍历图,遇到和起始顶点间存在路径的未访问顶
点则将其标记成已访问。如果该顶点是终点,直接返回 1,表明两顶点间可达,否则继续调用自身,
直到找到等于终点的顶点或将全部顶点遍历完成),当 DFS2()函数返回值为 1 则输出两顶点间可达,
否则输出两顶点间不可达,最后在调用菜单函数 menu()返回菜单,从而继续进行下一个操作。
4)void initG();// 初始化图
设计思路与实现步骤:首先定义名为 data 的数据结构(包含建筑的序号、名称和信息)和 AdjGraph
数据结构(包含 data 型的顶点数组、邻接矩阵、图的顶点数和边数),然后按照题目所给的地图信息
填入 data 型的数组中,将建筑之间的道路信息存入邻接矩阵中。
5)void menu();//显示菜单
设计思路与实现步骤:首先通过库函数 printf(),输出一个菜单的基本信息,再从键盘获取一个
对应不同功能的序号,再通过 swith 语句调用各个功能函数。
6)void search_info();//建筑信息查询
设计思路与实现步骤:首先通过库函数 printf()输出一个信息查询的菜单,再从键盘获取需要
查询的建筑的序号或者名称,即可输出相应的建筑信息和道路信息,然后函数可以自己调用自己,从
而实现建筑信息的连续查询。
7)void add_info();//新增建筑和道路信息
设计思路与实现步骤:首先判断要新增的建筑和道路信息是否存在,然后先从键盘获取要新增的
道路名称和相关信息,用 strcpy()函数将相关信息复制到图的顶点信息中,再从键盘获取要新增
的道路信息,然后将其输入邻接矩阵中,即可完成建筑和道路信息的添加。
8)void modify_info();//修改建筑和道路信息
设计思路与实现步骤:修改建筑和道路信息的操作与修改建筑和道路信息类似,故不再进行赘叙。
9)void delete_info();//删除建筑和道路信息
设计思路与实现步骤:首先判断要新增的建筑和道路信息是否存在,然后先从键盘获取要删除的
道路名称和相关信息,然后通过在顶点数组中覆盖指定的建筑顶点下标实现建筑信息删除,再通过将
指定的邻接矩阵长度置为无穷大来实现,最后再调用自身,实现持续删除。
四、程序运行结果和调试分析
1)查询各建筑物的相关信息
剩余32页未读,继续阅读
资源评论
倚楼听风疏雨骤
- 粉丝: 244
- 资源: 8
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功