(完整word版)全国交通咨询模拟数据结构课程设计.docx资源-CSDN文库

版权申诉

5星 · 超过95%的资源 187 浏览量 2022-10-29 20:02:10 上传评论 2 收藏 257KB DOCX 举报

资源推荐

资源详情

资源评论

(完整 word 版)全国交通咨询模拟数据结构课程设计

数据结构课程设计报告

题目：

全国交通咨询模拟

一．需求分析

1．程序设计任务：

从中国地图平面图中选取部分城市，抽象为程序所需要图的结点，并以城市间的列车路线

和飞机路线，作为图结点中的弧信息，设计一个全国交通咨询模拟系统。利用该系统实现两种

最优决策：最快到达或最省钱到达。

2. 明确规定：

(1)输入形式和输入值的范围：

每条飞机弧或者火车弧涉及的信息量很多，包括：起始城市、目的城市、出发时间、到达

时间、班次以及费用。作为管理员要输入的信息包括以上信息，而作为用户或者客户，要输入

- 0 -

(完整 word 版)全国交通咨询模拟数据结构课程设计

式或命令提示方式。只要能方便的对城市信息和交通信息进行管理即可，但要注意人机界面。

(5) 最优决策功能模块(fast or province)。

① 读入城市信息和交通信息，用邻接表生成含权网络，表头数组中的元素存放城市名及

对方城市到达该元素所代表城市的所有信息；表头数组中的元素所对应的单链表存放与该元素

所代表的城市有交通联系的城市(代码、里程、航班、列车车次)。

② 根据具体最优决策的要求，用 Dijkstra 算法求出出发城市到其它各城市的最优值(最短

时间或最小的费用)，搜索过程中所经过城市的局部最优信息都保存在邻接表的表头数组中。其

目的城市所代表的元素中就保存了所需的最优决策结果。这过程中，要用队列或栈保存局部最

优决策值(局部最短的时间或最省的费用)变小的城市，其相应的初始值可为∞，并在表头数组对

应的城市元素中保存响应的信息。开始时，栈 (队列)中只有出发地城市，随着对栈 (队列)顶(首)

城市有交通联系的城市求得决策值 (最短时间或最小的费用)，若该值是局部最优值且该城市不在

栈(队列)中，则进栈(队列)，直至栈(队列)为空，本题采用队列实现。

③ 输出结果：从目的城市出发，搜索到出发城市，所经过的城市均入栈(队列)，再逐一出

栈栈(队列)中的城市，输出保存在表头数组中对应城市的信息 (对方城市的出发信息，里程、时

间、费用等)及最终结果。即输出依次于何时何地乘坐几点的飞机或火车于何时到达何地；最终

所需的最快需要多长时间才能到达及旅费，或者最少需要多少旅费才能到达及时间。

(6) 主程序可以有系统界面、菜单；也可用命令提示方式；选择功能模块执行，要求在程序

运行过程中可以反复操作。

(2).详细设计思想：

本题所要求的交通系统是一个有向带权图结构，考虑到要求该系统有动态增加飞机和列车

航班的功能，因而采用邻接表的形式存储：对每个顶点建立一个单链表，单链表中的子结点表

示以该顶点连接的弧，单链表中子结点的顺序可以按权值递增的顺序排列，表头结点按顺序存

储。题目中提到要提供三种策略，最快到达，最省钱到达和最少中转次数策略，前两种策略采

- 2 -

(完整 word 版)全国交通咨询模拟数据结构课程设计

用迪杰斯特拉算法思想，其中最快到达的权值为到达两城市所需的最短时间，最省钱到达的权

值为到达两城市所需的费用，后一种采用广度优先算法的思想，只需求的两城市所在的层数，

就可以求的到达两城市所需的最少中转次数。

迪杰斯特拉（Dijkstra）算法的基本思想是：

设置两个顶点的集合 S 和 T＝V－S，集合 S 中存放已找到最短路径的顶点，集合 T 存放当前还

未找到最短路径的顶点。初始状态时，集合 S 中只包含源点 v0，然后不断从集合 T 中选取到顶

点 v0 路径长度最短的顶点 u 加入到集合 S 中，集合 S 每加入一个新的顶点 u，都要修改顶点

v0 到集合 T 中剩余顶点的最短路径长度值，集合 T 中各顶点新的最短路径长度值为原来的最短

路径长度值与顶点 u 的最短路径长度值加上 u 到该顶点的路径长度值中的较小值。此过程不断

重复，直到集合 T 的顶点全部加入到 S 中为止。

下面讨论基于邻接表的存储结构求两点间最短路径的方法：

根据迪杰斯特拉(Dijkstra)算法所依据的原理：若按长度递增的次序生成从源点 V0 到其它顶点

的最短路径，则当前正在生成的最短路径上除终点以外，其余顶点的最短路径均已生成（将源

点的最短路径看作是已生成的源点到其自身的长度为 0 的路径）。

按照这一思想，构造以下算法：

设 S=S’=U={}，建立数组 PATH[n]，用来存储 V0 到各终点的最短路径，初值均置为空集。

建立数组 BOOL F[n] ，F[i]表示序号为 i 的表头结点的单链表中所有子结点已或未全部找到，初

值置为 FALSE。建立数组 float dist[n]，dist[i]表示序号为 i 的表头结点到 V0 的最短权值（这

里是时间或费用），显然 dist[V0]=0,其他顶点的 dist 初值置为∞。建立数组 BOOL IS[n]，IS[i]

表示序号为 i 的顶点是否在 S 中，初值均置为 FALSE。

(1)VX=V0；最短的最短路径为 PATH[0]=[V0]

(2)S=S+VX；（集合的并计算）

IS[VX]=TRUE；

- 3 -

剩余62页未读，继续阅读

内容反馈

版权申诉

m0_65207763

2023-01-09

文档中没有给完整的源代码呀
m0_74993569

2023-07-03

资源质量不错，和资源描述一致，内容详细，对我很有用。
Xxuan__

2023-12-06

这个资源总结的也太全面了吧，内容详实，对我帮助很大。
m0_71566549

2023-01-13

实在是宝藏资源、宝藏分享者！感谢大佬~
BuG17

2023-05-31

这个资源值得下载，资源内容详细全面，与描述一致，受益匪浅。

前往

页

G11176593

粉丝: 6643
资源: 3万+

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈

feedback-tip