C语言数据结构与算法分析课程设计题目[2023-01-29]

2021-2022 学年第一学期

数据结构与算法分析课程设计题目

课程设计总体要求：

1. 课程设计报告撰写内容包括：题目分析；概要设计；数据结构设计；算法设
   计；实现与结果；结果分析。
2. 课程设计报告里不要附源码，算法说明可用伪代码解释。
3. 核心代码作为附录文件提交到系统。
4. 可运行源码压缩包交给各班学委，学委收齐交给助教。
   一共交三个文件：课程设计报告（提交系统），核心代码（提交源码系统），源码
   文件包（线下）。
5. 公交线路上优化路径的查询（本题目最多可 4 人一组选择）

问题描述:
最短路径问题是图论中的一个经典问题，其中的 Dijkstra 算法一直被认为是图论中的好
算法，但有的时候需要适当地调整 Dijkstra 算法才能完成多种不同的优化路径的查询。
对于某城市的公交线路，乘坐公交的顾客希望在这样的线路上实现各种优化路径的查询。
设该城市的公交线路的输入格式如下：
线路编号:起始站名(该站坐标)；经过的站点 1 名(该站坐标)；经过的站点 2 名(该站坐
标)；…；经过的站点 n 名(该站坐标)；终点站名(该站坐标)。该线路的乘坐价钱、该线路平
均经过多少时间来一辆、车速。
例如，63: A(32,45); B(76,45): C(76,90)：…；N(100,100)。1 元、5 分钟、0.5km/每分钟。
假定线路的乘坐价钱与乘坐站数无关，不考虑公交线路路上的交通堵塞。
对这样的公交线路，需要在其上进行的优化路径查询包括:任何两个站点之间最便宜的
路径、任何两个站点之间最省时间的路径等。
从实际问题中合理定义图模型，掌握 Dijkstra 算法并能用该算法解决一些实际问题。
基本要求:
（1）根据上述公交线路的输入格式，定义并建立合适的图模型。
（2）针对上述公交线路，能查询获得任何两个站点之间最便宜的路径，即输入站名 S、T 后，
可以输出从 S 到 T 的最便宜的路径，输出格式为：线路 x：站名 S，…，站名 M1；换乘线
路 x1：站名 M1，…，站名 M2；…；换乘线路 xn：站名 MK，…，站名 T。共花费 x 元。
（3）针对上述公交线路，能查询获得任何两个站点之间最省时间的路径(不考虑在中间站换
乘下一个线路的等待时间)，即输入站名 S、T 后，可以输出从 S 到 T 的不考虑在中间站换
乘下一个线路的等待时间的最省时间的路径，输出格式为：线路 x：站名 S，…，站名 M1；
换乘路线 x1：站名 M1，…，站名 M2；…；换乘线路 xn：站名 MK，…，站名 T。共花费
x 时间。
（4）针对上述公交线路，能查询获得任何两个站点之间最省时间的路径(要考虑在中间站换
乘下一个线路的等待时间)，即输入站名 S、T 后，可以输出从 S 到 T 的考虑在中间站换乘
下一个线路的等待时间的最省时间的路径，输出格式为：线路 x：站名 S，…，站名 M1；换
乘线路 x1：站名 M1，…，站名 M2；…；换乘线路 xn:站名 MK，…，站名 T。共花费 x 时
间。
实现提示:
需深入考虑，应根据不同的应用目标，即不同的优化查询，来建立合适的图模型。

源码

https://pan.baidu.com/s/1pq1Nwwo0hlc_J84F93HM4A?pwd=1111