设计四、交通咨询模拟
一、设计目的
掌握线性表、栈、图结构和对文件的操作，学习屏幕编辑和菜单技术，掌握用最短路径及其搜索算法编制较综合性的程序，能用图的邻接存储结构求解最优路线问题，解决有关实际问题。得到软件设计技能的训练。
二、问题描述
交通咨询模拟。根据旅客的不同需要，要考虑到旅客希望在旅途中的时间尽可能短、希望旅费尽可能省等的要求。旅途用火车或飞机作为交通工具。用计算机编制程序，为旅客提供两种最优决策的交通咨询系统。
三、基本要求
1、对城市信息(城市名、城市间的里程)进行编辑：具备添加、修改、删除功能；
2、对城市间的两种交通工具：飞机和火车。对飞机航班和列车时刻表进行编辑：里程、航班和列车班次的添加、修改、删除；
3、提供两种最优决策：最快到达或最省钱到达。全程只考虑一种交通工具，
可以不考虑回程；
4、旅途中的耗费的总时间应包括中转站的等候时间。其中飞机至少二小时，
火车至少一小时；
5、咨询以用户和计算机对话方式进行，要注意人机交互的屏幕界面。由用户选择最优决策原则和交通工具，输入起始站、终点站、出发时间，输出信息：最快需要多长时间才能到达及旅费，或者最少需要多少旅费才能到达及时间，并详细说明依次于何时何地乘坐哪一趟班机或列车何时到达何地。
四、测试数据
附录中提供了15个城市及它们之间的里程(公里)及航班和列车时刻表，其中，城市间的航班最多4个，列车车次最多2个。飞机每小时按飞行800公里计算；火车每小时按开80公里计算；飞机的票价按每元1.2公里计算；火车的票价按每元5公里计算。
这里给出一组测试数据：
飞机最快到达咨询：北京到乌鲁木齐，北京11点出发；
火车最快到达咨询：广州到哈尔滨，广州10点出发；
飞机最省钱到达咨询：乌鲁木齐到南京，乌鲁木齐12点出发；
火车最省钱到达咨询：沈阳到杭州，沈阳12点出发；
五、实现提示
1、算法思路
(1) 数据存储。城市信息(城市名、代码)、交通信息(城市间的里程、各航班和列车时刻)存储于磁盘文件。建议把城市信息存于文件前面，交通信息存于文件的后面，用fread和fwrite函数操作。
(2) 数据的逻辑结构。根据设计任务的描述，其城市之间的旅游交通问题是典型的图结构，可看作为有向图，图的顶点是城市，边是城市之间所耗费的时间（要包括中转站的等候时间）或旅费。
(3) 数据的存储结构。采用邻接表和邻接矩阵都可作为数据的存储结构，但当邻接边不多时，宜采用邻接表，以提高空间的存储效率。这里建议采用邻接表作为数据的存储结构。
(4) 用不同的功能模块对城市信息和交通信息进行编辑。添加、修改、删除功能可用菜单方式或命令提示方式。只要能方便的对城市信息和交通信息进行管理即可，但要注意人机界面，具体实现由学生自行设计，也可参考有关程序(届时在网上提供)。这些工作有不小的工作量。
(5) 最优决策功能模块(fast or province)。
① 读入城市信息和交通信息，用邻接表生成含权网络，表头数组中的元素存放城市名及对方城市到达该元素所代表城市的所有信息；表头数组中的元素所对应的单链表存放与该元素所代表的城市有交通联系的城市(代码、里程、航班、列车车次)。
② 根据具体最优决策的要求，用Dijkstra算法求出出发城市到其它各城市的最优值(最短时间或最小的费用)，搜索过程中所经过城市的局部最优信息都保存在邻接表的表头数组中。其目的城市所代表的元素中就保存了所需的最优决策结果。这过程中，要用队列或栈保存局部最优决策值(局部最短的时间或最省的费用)变小的城市，其相应的初始值可为∞，并在表头数组对应的城市元素中保存响应的信息。开始时，栈(队)中只有出发地城市，随着对栈(队)顶(首)城市有交通联系的城市求得决策值(最短时间或最小的费用)，若该值是局部最优值且该城市不在栈(队)中，则进栈(队)，直至栈(队)为空。
③ 输出结果。从目的城市出发，搜索到出发城市，所经过的城市均入栈，再逐一出栈栈中的城市，输出保存在表头数组中对应城市的信息(对方城市的出发信息，里程、时间、费用等)及最终结果。即输出依次于何时何地乘坐几点的飞机或火车于何时到达何地；最终所需的最快需要多长时间才能到达及旅费，或者最少需要多少旅费才能到达及时间。
(6) 主程序可以有系统界面、菜单；也可用命令提示方式；选择功能模块执行，要求在程序运行过程中可以反复操作。
2、数据结构
typedef struct city /* 城市数据类型 */
{char city[5]; /* 城市名称 */
char code; /* 城市代码 */
}city;
typedef struct tra1 /* 交通信息数据类型 */
{char code; /*城市代码 */
int dist; /* 城市间的里程 */
char p[4]; /* 航班时刻 */
char t[2]; /* 列车时刻 */
}tra1;
typedef struct st /* 栈结构 */
{int stk[14];
int top;
}stack;
typedef struct traffic /* 邻接表中的链表结点结构 */
{char code; /* 城市代码 */
int dist; /* 表头结点的城市到该结点的城市的距离 */
char p[4]; /* 表头结点的城市到该结点的城市的航班时刻 */
char t[2]; /* 表头结点的城市到该结点的城市的列车时刻 */
struct traffic *next; 指向后续结点的指针
}traf;
typedef struct traffic1 /* 邻接表中表头结点结构 */
{char city[5]; /* 城市名称 */
char code; /* 城市代码 */
char code1; /* 对方城市代码 */
int dist; /* 对方城市按最快或最省到达该结点城市的距离 */
int tmbg; /* 对方城市的出发时间 */
float tmed; /* 到达该城市的时间 */
float tm；/* 出发城市最快到达该城市所化的时间或出发城市最省到达该城市所化的钱 */
float tm0; /* 对方城市到达该城市路途所化的时间 */
float tm1; /* 最省到达中出发城市到达该城市所化的时间 */
int numbg; /* 对方城市出发天序数 */
int numed; /* 到达该城市的天序数 */
int flag; /* 该城市是否在栈(队)中的标志 */
int money; /* 对方城市到该城市的飞机或火车票费 */
traf *first; /*该城市指向有交通联系的城市(邻接表中链表结点 的指针) */
}traf1;
3、基本操作
void coverpage() /* 系统封面，由主函数调用。不作为基本要求 */
void city() /* 城市名称编辑，并把城市名称和对应的代码存于文件"tra.rec"的前面，由菜单函数menu调用 */
void chan(int m,int n,char *p) /* 将数值n转化为右端存放的字符串，m分别为里程、各航班、各列车班次的功能号，全屏幕编辑用，由编辑里程、各航班、各列车班次的交通信息函数traffic调用，不作基本要求 */
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分别为里程、各航班、各列车班次的功能号，并把里程、各航班、各列车班次的交通信息存于文件"tra.rec"的后面，由菜单函数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调用*/
{ …
打开数据文件"tra.rec"，读取城市信息并显示；
从文件"tra.rec"读取交通信息，建立邻接表；
输入出发地城市、目的地城市和出发时间；
栈初始化；表头数组元素初始化；出发城市入栈；
while(栈s不空)
{ 栈顶元素出栈给i；
while(i城市所对应的单链表不空(i城市有交通联系的城市))
{ 搜索班次；
if(有班次)
{ 搜索当天或第二天或第三天的班次tim0和该城市出发的天序数temp；
计算出发地城市到目前到达的城市所需的时间或费用tima；
if(tima<原到达的城市所需的时间或费用)
{ 在表头数组到达城市对应的元素里分别存放好对方城市的代码、所需的时间或费用tima、对方城市出发时的时间tim0、对方城市出发时的天序数temp、到达时的天序数、到达时的时间、这次路程所需的费用，这次路程所需的时间，这次路程、到达城市若不在栈内则入栈；
}
}
p=p->next;
}
}
if(目的城市的决策值为∞) 输出“不能到达!”;
else
{ 从目的城市出发，按表头数组中存储的对方城市的代码搜索至出发城市，并将各城市依次入栈；
输出出发地城市、时间、交通工具；
while(栈不空)
输出依次各到达城市的时间、时刻、交通工具、路程、时间、费用和最优决策值(最快需要多长时间到达及旅费，或最少需要多少旅费到达及时间);
}
}
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()函数，在这里不作为基本要求，操作步骤略 */
4、主程序
main()
{ …
执行系统封面函数coverpage()；
执行菜单函数menu()；
}
5、测试并输出结果
运行后显示系统封面，进入菜单并选择“飞机最快到达”咨询后显示文本方式的用户界面，输入出发地城市、目的地城市和出发时间后, 显示输出结果如下。其它输出结果略。
