全国交通咨询模拟
void chan1(int n,tra1 tra[15][15],char d[15][15][5],int i,int j) /* 将字符串 d[i][j]转换为tra[i][j]中里程或航班或车次，n 分别为里程、各航班、各列车班次的功能号，全屏幕编辑用，由编辑里程、各航班、各列车班次的交通信息函数 traffic 调用，不作基本要求 */
void traffic(int n) /* 全屏幕编辑里程、各航班、各列车班次的交通信息, n分别为里程、各航班、各列车班次的功能号，并把里程、各航班、各列车班次的交通信息存于文件\的后面，由菜单函数 menu 调用 */
void initstack(stack *s) /* 初始化栈 s */ int empty(stack s) /* 判断栈是否为空 */ void push(int n,stack *s) /* 入栈 */ void pop(int *n,stack *s) /* 出栈 */
void fast(int n) /* 最快到达决策，n 为是坐飞机还是火车到达的功能号，由菜单函数 menu 调用*/
void province(int n) /* 最省到达决策，n 为是坐飞机还是火车到达的功能号。其算法步骤和算法 fast 类似，只要在算法中时间和费用互换即可，由菜单函数menu 调用 */
void quit() /* 退出系统，由菜单函数 menu 调用 */
void menu() /* 菜单函数 *//* 用三维字符数组构造“平面”菜单，用字符屏幕、I/O 等函数控制菜单，对选 中 的各 功 能模 块 ，分 别执 行 city()、 traffic(int n)、 fast(int n) 、province(int n)和 quit()函数，在这里不作为基本要求，操作步骤略 */
int LocateVertex(ALGaph *G,char *v)/*找出城市名在图中对应结点位置*/ void creatplanefile()/*创建航班算法*/
void DeleteVertex(ALGraph *G) /* 删除城市结点算法*/
void ExpenditureDispose( )/* 求城市 v0，v1 之间的最少费用算法*/
void TransferDispose( )/* 求最少中转次数算法:城市 v0 到城市 v1 的最少中转次数*/
void TimeDispose( )/* 求城市 v0，v1 之间的最少时间算法*/
5
全国交通咨询模拟
第三章 概要设计
3.1.数据结构的设计
(1) 数据存储。城市信息(城市名、代码)、交通信息(城市间的里程、各航班和
列车时刻)存储于磁盘文件。建议把城市信息存于文件前面，交通信息存于文件 的后面，用 fread 和 fwrite 函数操作。
(2) 数据的逻辑结构。根据设计任务的描述，其城市之间的旅游交通问题是典型 的图结构，可看作为有向图，图的顶点是城市，边是城市之间所耗费的时间（要 包括中转站的等候时间）或旅费。
(3) 数据的存储结构。采用邻接表和邻接矩阵都可作为数据的存储结构，但当邻 接边不多时，宜采用邻接表，以提高空间的存储效率。这里建议采用邻接表作为 数据的存储结构。
(4) 用不同的功能模块对城市信息和交通信息进行编辑。添加、修改、删除功能 可用菜单方式或命令提示方式。只要能方便的对城市信息和交通信息进行管理即 可，但要注意人机界面，具体实现由学生自行设计，也可参考有关程序(届时在 网上提供)。这些工作有不小的工作量。 (5) 最优决策功能模块(fast or province)。
① 读入城市信息和交通信息，用邻接表生成含权网络，表头数组中的元素存放 城市名及对方城市到达该元素所代表城市的所有信息；表头数组中的元素所对应 的单链表存放与该元素所代表的城市有交通联系的城市(代码、里程、航班、列 车车次)。
② 根据具体最优决策的要求，用 Dijkstra 算法求出出发城市到其它各城市的最 优值(最短时间或最小的费用)，搜索过程中所经过城市的局部最优信息都保存在 邻接表的表头数组中。其目的城市所代表的元素中就保存了所需的最优决策结 果。这过程中，要用队列或栈保存局部最优决策值(局部最短的时间或最省的费 用)变小的城市，其相应的初始值可为∞，并在表头数组对应的城市元素中保存 响应的信息。开始时，栈(队)中只有出发地城市，随着对栈(队)顶(首)城市有交 通联系的城市求得决策值(最短时间或最小的费用)，若该值是局部最优值且该城 市不在栈(队)中，则进栈(队)，直至栈(队)为空。
③ 输出结果。从目的城市出发，搜索到出发城市，所经过的城市均入栈，再逐 一出栈中的城市，输出保存在表头数组中对应城市的信息(对方城市的出发信
6
全国交通咨询模拟
息，里程、时间、费用等)及最终结果。即输出依次于何时何地乘坐几点的飞机 或火车于何时到达何地；最终所需的最快需要多长时间才能到达及旅费，或者最 少需要多少旅费才能到达及时间。
(6) 主程序可以有系统界面、菜单；也可用命令提示方式；选择功能模块执行， 要求在程序运行过程中可以反复操作
3.2．设计概要
3.2.1.抽象数据类型
本程序运用了关于图这种数据结构。 ADT Graph{
数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。 数据关系R： R={VR}
VR={
int main()
{
界面初始化； 输入操作命令；
While（“命令” ！= “退出”） {
接受命令（用户输入要实现功能）； 进入各个处理命令函数；
} }
3.2.3创建交通图算法的伪码描述如下：
int LocateVertex(ALGaph*G,char*v)/*找出城市名在图中对应结点位置*/
{
for(k=0;k<图G中的结点个数G->vexnum;k++) if(第k个结点中的城市名与传过来的城市名相同)
{
j=k;/*记录位置*/ break;
7
全国交通咨询模拟
}
返回k的数值； }
int CreatGraph(ALGraph*G)
{
if(打开城市文件，文件指针返回值为空）
{
输出错误文件信息； 程序返回值为0； }
while(文件不为空）
{
将文件指针所指的字符串读到城市名数组city[i]中；i++; } 关闭文件； j=0;
while(j<城市个数）
{
将city[i]中的内容复制到图的结构体的结点数组中;图的结构体其他项负初值;j++; }
G->vexnum=i;
打开航班信息文件\
将文件中的内容以块为单位读到缓冲区数组a中； 关闭文件；] a的计数变量k=0; 弧的计数变量arc_num=0; while(k<信息个数)
{
调用函数LocateVertex(G,a[k].vt)得到起始结点的位置i；调用
8