全国交通咨询 模拟系统.doc

实习报告：5.8全国交通咨询模拟 题目： 编制一个为客户进行全国交通系统（飞机/火车）按最快到达和费用最少咨询的程序 需求分析： 图的建立： 提供城市信息编辑功能（添加删除） 城市之间两种交通工具：火车和飞机。提供对列车时刻表和飞机航班进行编辑（增设或删除） 咨询系统： 供两种最优策略：最快到达和最省钱到达。全程只考虑一种交通工具。 由用户输入起始站、终点站、最优策略原则和交通工具，输出信息：最快需要多长时间才能到达或者最少需要多少旅费才能到达，并详细说明一次于何时乘坐哪一趟列车或哪一次班机到何地。 概要设计： 抽象数据类型 ADT Graph{ 数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。 数据关系R： R={VR} VR={(v,w)|v,w∈V,VR} 基本操作P： GreateGraph（G, V, VR） 初始条件：V是图的顶点集，VR是图中边的集合 操作结果：按V和VR的定义构造图G DestoryGraph (G) 初始条件：图G存在 操作结果：销毁图G LocateVex（G, u） 初始条件：图G存在，u和G中顶点有相同特征 操作结果：若G中存在顶点u，则返回该顶点在图中的位置；否则返回其他信息 LocateEdge (G, v , w, name) //new,根据本题两顶点间有多条边，而特别确定的基本操作 初始条件：图G存在，u和w是G中两个顶点 操作结果：若存在(v,w)，其信息中的名称为name，则返回存在，否则返回不存在 InsertVex (G, v) 初始条件：图G存在，v和途中顶点有相同特征 操作结果：在图G中添加新顶点v DeleteVex (G, v) 初始条件：图G存在，v是G中某个顶点 操作结果：删除G中顶点v及其相关的边 InsertEdge (G, v, w) 初始条件： 图G存在，v和w是G中两个顶点 操作结果： 在G中添加边 (v, w) DeleteEdge (G, v, w) 初始条件： 图G存在，v和w是G中两个顶点 操作结果： 在G中删除边（v, w） GetTimeShortestPath（G, st, nd, Path） 初始条件：图G存在，st和nd是G中两个顶点 操作结果：若st和nd之间存在路径，则以Path返回两点之间一条所需时间最少的路径，否则返回其他信息 GetMoneyLeastPath (G, st, nd, Path) 初始条件：图G存在，st和nd是G中两个顶点 操作结果：若st和nd之间存在路径，则以Path返回两点之间一条所需费用最少的路径，否则返回其他信息 GetChangeLeastPath (G, st, nd, Path) //选做内容，没有实现 初始条件：图G存在，st和nd是G中两个顶点 操作结果：若st和nd之间存在路径，则以Path返回两点之间一条所需费用最少的路径，否则返回其他信息 }//ADT Graph 详细设计 顶点、边和图类型 #define MAXVTXNUM 30 //图中顶点数的最大值 typedef struct { int ivex; //起始点号 int jvex; //终点号 char Number[10]; // 车次号 int Money; //费用 int StratTime; //起始时间（秒） int EndTime; //终止时间（秒） int Time; //中途时间（秒） }EdgeType; //Edge类型 typedef struct EdgeNode { EdgeType elem; EdgeNode *nextEdge; }EdgeNode, *EdgePtr; //边的结点类型，指向边的指针 typedef struct { char cityName[10]; int cityNumber; EdgePtr firstEdge; //指向的一条依附该顶点的边的指针 }Vnode; //City类型 typedef struct { Vnode Adjlist[MAXVTXNUM]; //邻接表 int vexNum, edgeNum; //图重的顶点数和边数 int Flag[MAXVTXNUM]; //0表示已经不存在,1表示存在 }Graph