(1) 数据存储。城市信息(城市名、代码)、交通信息(城市间的里程、各航班和列车时刻)存
储于磁盘文件。建议把城市信息存于文件前面,交通信息存于文件的后面,用 fread 和
fwrite 函数操作。
(2) 数据的逻辑结构。根据设计任务的描述,其城市之间的旅游交通问题是典型的图结构 ,
可看作为有向图,图的顶点是城市,边是城市之间所耗费的时间(要包括中转站的等候时
间)或旅费。
(3) 数据的存储结构。采用邻接表和邻接矩阵都可作为数据的存储结构,但当邻接边不多
时,宜采用邻接表,以提高空间的存储效率。这里建议采用邻接表作为数据的存储结构。
(4) 用不同的功能模块对城市信息和交通信息进行编辑。添加、修改、删除功能可用菜单
方式或命令提示方式。只要能方便的对城市信息和交通信息进行管理即可,但要注意人机
界面,具体实现由学生自行设计,也可参考有关程序(届时在网上提供)。这些工作有不小
的工作量。
(5) 最优决策功能模块(fast or province)。
① 读入城市信息和交通信息,用邻接表生成含权网络,表头数组中的元素存放城市名及对
方城市到达该元素所代表城市的所有信息;表头数组中的元素所对应的单链表存放与该元
素所代表的城市有交通联系的城市(代码、里程、航班、列车车次)。
② 根据具体最优决策的要求,用 Dijkstra 算法求出出发城市到其它各城市的最优值(最短
时间或最小的费用),搜索过程中所经过城市的局部最优信息都保存在邻接表的表头数组中。
其目的城市所代表的元素中就保存了所需的最优决策结果。这过程中,要用队列或栈保存
局部最优决策值(局部最短的时间或最省的费用)变小的城市,其相应的初始值可为∞,并
在表头数组对应的城市元素中保存响应的信息。开始时,栈(队)中只有出发地城市,随着
对栈(队)顶(首)城市有交通联系的城市求得决策值(最短时间或最小的费用),若该值是局部
最优值且该城市不在栈(队)中,则进栈(队),直至栈(队)为空。
③ 输出结果。从目的城市出发,搜索到出发城市,所经过的城市均入栈,再逐一出栈栈中
的城市,输出保存在表头数组中对应城市的信息(对方城市的出发信息,里程、时间、费用
等)及最终结果。即输出依次于何时何地乘坐几点的飞机或火车于何时到达何地;最终所需
的最快需要多长时间才能到达及旅费,或者最少需要多少旅费才能到达及时间。
(6) 主程序可以有系统界面、菜单;也可用命令提示方式;选择功能模块执行,要求在程
序运行过程中可以反复操作。
2、数据结构
本程序运用了关于图这种数据结构。
他的抽象数据类型定义如下:
typedef struct unDiGraph
{
int numVerts; //结点
costAdj cost; //邻接矩阵
}unDiGraph,*UNG;
基本操作:
unDiGraph* CreateCostG()
操作结果:构造带权(费用)图。
unDiGraph* CreateTimeG()
评论5