一．需求分析
1．程序设计任务：
从中国地图平面图中选取部分城市，抽象为程序所需要图的结点，并以城市间的列车路线和飞机路线，作为图结点中的弧信息，设计一个全国交通咨询模拟系统。利用该系统实现两种最优决策：最快到达或最省钱到达。 2. 明确规定：
(1)输入形式和输入值的范围：
每条飞机弧或者火车弧涉及的信息量很多，包括：起始城市、目的城市、出发时间、到达时间、班次以及费用。作为管理员要输入的信息包括以上信息，而作为用户或者客户，要输入的信息有起始城市和目的城市，并选择何种最优决策。 (2)输出形式：
按用户提供的最优决策的不同而输出不同的信息，其中输出的所搭飞机或火车的班次及其起始地点和终点、起始时间和出发时间还有相关的最优信息，比如最快经多少时间到达、最省钱多少钱到达和最少经多少中转站到达。 (3)程序所能达到的功能
a.该系统有供用户选择的菜单和交互性。可以对城市、列车车次和飞机航班进行编辑，添加或删除。
b.建立一个全国交通咨询系统，该系统具备自动查找任意两城市间铁路、飞机交通的最短路径和最少花费及中转次数最少等功能。 c.初始化交通系统有两种方式，键盘和文档。
二．设计概要
1.抽象数据类型
本程序运用了关于图这种数据结构。 ADT Graph{
数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。 数据关系R： R={VR}
VR={
CreateGraph(&G,V,VR);
初始条件：V是图的顶点集，VR是图中弧的集合。 操作结果：按V和VR的定义构造图G。 DestroyGraph(&G);
初始条件：图G存在。 操作结果：销毁图G。 LocateVet(G,u);
初始条件：图G存在，u和G中顶点有相同的特征。
操作结果：若G中存在顶点u，则返回该顶点在图中的位置， 否则返回其他信息。 GetVex(G,v);
初始条件：图G存在，v是G中某个顶点。 操作结果：返回v的值。
PutVex(&G,v,value);
初始条件：图G存在，v是G中某个顶点。 操作结果：对v赋值value。 FirstAdjVex(G,v);
初始条件：图G存在，v是G中某个顶点。
操作结果：返回v的第一个邻接顶点。若顶点在G中没有邻接 顶点，则返回“空”。 NextAdjVex(G,v,w);
初始条件：图G存在，v是G中某个顶点，w是v的邻接顶点， 操作结果：返回v的(相对于w的)下一个邻接顶点。若w是v 的最后一个邻接点，则返回“空”。
InsertVex(&G,v);
初始条件：图G存在，v和图中顶点有相同特征。 操作结果：在图G中添加新顶点v。 DeleteVex(&G,v);
初始条件：图G存在，v是G中某个顶点。 操作结果：删除G中顶点v及相关弧。 InsertArc(&G,v,w);
初始条件：图G存在，v和w是G中两个顶点。
操作结果：在G中增添弧
初始条件：图G存在，v和w是G中两个顶点。
操作结果：在G中删除弧
初始条件：图G存在，Visit是顶点的应用函数。
操作结果：对图进行深度优先遍历。在遍历过程中对每个顶点调用函
数Visit一次且仅一次。一旦visit()失败，则操作失败。
BFSTraverse(G,Visit());
初始条件：图G存在，Visit是顶点的应用函数。
操作结果：对图进行广度优先遍历。在遍历过程中对每个顶点调用函
数Visit一次且仅一次。一旦visit()失败，则操作失败。
}ADT Graph
其他的抽象数据类型定义如下：
typedef struct {int number;
float expenditure; int begintime[2]; int arrivetime[2]; }Vehide; typedef struct
{Vehide stata[MAX_ROUTE_NUM]; int last; }infolist;
typedef struct ArcNode {int adjvex;
struct ArcNode *nextarc; infolist info; }ArcNode;
typedef struct VNode {char cityname[10];
ArcNode *planefirstarc,*trainfirstarc; }VNode,AdjList[MAX_VERTEX_NUM]; typedef struct {AdjList vertices;
int vexnum,planearcnum,trainarcnum; }ALGraph;
typedef struct Node {int adjvex; int route;
struct Node *next; }Node;
typedef struct QNode {int adjvex;
struct QNode *next; }QNode; typedef struct {QNode *front; QNode *rear; }LinkQueue;
typedef struct TimeNode {int adjvex; int route;
int begintime[2];
int arrivetime[2];
struct TimeNode *child[MAX_ROUTE_NUM]; }TimeNode,*TimeTree; struct arc {int co;
char vt[10]; char vh[10]; int bt[2]; int at[2]; float mo;
}a[MAX_ARC_SIZE];
基本操作：
void Administer(ALGraph *G); void cityedit(ALGraph *G);
void CopyTimeTree(TimeTree p,TimeTree q); void createcityfile();
void CreateGraph(ALGraph *G); void createplanefile(); void CreateTimeTree(TimeTree p,int i,int j,LinkQueue *Q,infolist (*arcs)[MAX_VERTEX_NUM]); void createtrainfile();
int DeleteplaneArc(ALGraph *G);
void DeleteQueue(LinkQueue *Q,int *x); int DeletetrainArc(ALGraph *G); void DeleteVertex(ALGraph *G);
void DemandDispose(int n,ALGraph G); void DestoryTimeTree(TimeTree p); void EnterplaneArc(ALGraph *G); void EnterQueue(LinkQueue *Q,int x); void EntertrainArc(ALGraph *G); void EnterVertex(ALGraph *G);
void ExpenditureDispose(int k,infolist (*arcs)[MAX_VERTEX_NUM],ALGraph G,int v0,int v1,float *M,int *final);
void flightedit(ALGraph *G); void initgraph(ALGraph *G); void InitQueue(LinkQueue *Q); int IsEmpty(LinkQueue *Q);
int LocateVertex(ALGraph *G,char *v);
void MinExpenditure(infolist arcs,float *expenditure,int *route); void MinTime(infolist arcs,int *time,int *route); void PrintGraph(ALGraph *G); int save(ALGraph *G);
void TimeDispose(int k,infolist (*arcs)[MAX_VERTEX_NUM],ALGraph G,int v0,int v1,int (*T)[2],int *final);
void TimeTreeDispose(Node *head,infolist (*arcs)[MAX_VERTEX_NUM]); void trainedit(ALGraph *G);
void TransferDispose(int k,infolist (*arcs)[MAX_VERTEX_NUM],ALGraph G,int v0,int v1); void UserDemand(ALGraph G); void VisitTimeTree(TimeTree p);
主程序的流程以及各程序模块之间的调用关系 初始化交通系统initgraph 城市编辑 cityedit 飞机航班编辑Administer 用户咨询 UserDemand 列车车次编辑 Administer 返回上一级菜单 管理员管理 Administer 管理员管理 Administer 用户咨询 UserDemand 显示交通系统 PrintGraph 退出 主函数main（）
最少旅行费用ExpenditureDispos最少旅行时间 TimeDispose 显示交通系统 PrintGraph 最少中转次数 TransferDispos返回上一级菜单