[工学]全国交通咨询模拟.doc

课程设计 课程名称：　　数　据　结　构　　　 实验名称：　全国交通咨询模拟　　 实验类型：　设　　　　　计　　　 系 别：　电子信息工程学院 学生姓名：　　李晗、刘畅 指导教师：　　余　先　伦　　　 2012年5月8 一、需求分析 该程序所做的工作的是模拟全国交通咨询，为旅客提供三种最优决策的交通咨询。此程序规定： 在程序中输入城市名称时，需输入10个字母以内的字母串；输入列车或飞机编号时需输入一个整型数据；输入列车或飞机的费用时需输入一个实型数据；输入列车或飞机开始时间和到达时间时均需输入两个整型数据（以hh：mm的形式）；在选择功能时，应输入与所选功能对应的一个整型数据。 程序的输出信息主要是：最快需要多少时间才能到达，或最少需要多少旅费才能到达，或最少需要多少次中转到达，并详细说明依次于何时乘坐哪一趟列车或哪一次班机到何地。 程序的功能包括：提供对城市信息的编辑，提供列车时刻表和飞机航班表的编辑，提供三种最优决策：最快到达、最省钱到达、最少中转次数到达。 二、E-R流程图 2.算法的描述 本程序运用了图的知识，构造无了向带权费用图和无向带权时间图。（如图1，图2所示） 图1. 十三城市之间火车费用表（权值表示费用） 图2. 十三城市之间火车行驶时间表 （权值表示时间） 三、概要设计 系统用到的抽象数据类型定义： 1．ADT Graph{ 数据对象V：一个集合，该集合中的所有元素具有相同的特性 数据关系R：R={VR} VR={x,y|P(x,y)^(x,y属于V)} 基本操作： initgraph(G)； CreateGraph(G)； EnterVertex(G)； DeleteVertex(G)； EnterplaneArc(G)； DeleteplanArc(G)； EntertrainArc(G)； DeletetrainArc(G)； }ADT Graph 2．ADT LinkQueue{ 数据元素：可以是任意类型的数据，但必须属于同一个数据对象 关系：队列中数据元素之间是线性关系。 基本操作： InitQueue(Q)； IsEmpty(Q)； EnterQueue(Q,x)； DeleteQueue(Q,y)； }ADT LinkQueue 3．ADT TimeTree{ 数据对象D：一个集合，该集合中的所有元素具有相同的特性 数据关系R：若D为空，则为空树。若D中仅含有一个数据元素，则R为空集，否则R={H}，H为如下二元关系： 在D中存在唯一的称为根的数据元素root，它在关系H中没有前驱 除root以外，D中每个结点在关系H下有且仅有一个前驱。 基本操作： CreateTimeTree(p,i,j,Q,infolist arcs)； CopyTimeTree(p,q)； VisitTimeTree(p)； }ADT TimeTree 系统中子程序及功能要求： 1．Administer(ALGraph *G)：提供管理员管理城市交通系统的界面，通过该子程序可调用其他管理交通系统的子程序。 2．initgraph(ALGraph *G)：初始化交通系统的子程序 3．createcityfile( )：创建城市文件的子程序 4．createplanefile( )：创建航班文件的子程序 5．createtrainfile( )：创建列车时刻表文件的子程序 6．LocateVertex(ALGraph *G,char *v)：提供城市名在城市交通系统中相应的编号 7．CreateGraph(ALGraph *G)：创建城市交通系统 8．cityedit(ALGraph *G)：提供城市编辑功能 9．EnterVertex(ALGraph *G)：提供在城市交通系统中加入城市的功能 10．DeleteVertex(ALGraph *G)：提供在城市交通系统中删除城市的功能 11．flightedit(ALGraph *G)：提供航班编辑功能 12．EnterplaneArc(ALGraph *G)：提供在城市交通系统中加入航班的功能 13．DeleteplaneArc(ALGraph *G)：提供在城市交通系统中删除航班的功能 14：trainedit(ALGraph *G):提供列车车次的编辑功能 15．EntertrainArc(ALGraph *G)：提供在城市交通系统中加入列车车次的功能 16．DeletetrainArc(ALGraph *G)：提供在城市交通系统中删除列车车次的功能 17．UserDemand(ALGraph G)：提供用户咨询的界面 18．Demand