《数据结构课程设计报告之模拟一个全国城市间的交通咨询程序》由会员分享，可在线阅读，更多相关《数据结构课程设计报告之模拟一个全国城市间的交通咨询程序（55页珍藏版）》请在金锄头文库上搜索。
1、分类号 编号 华北水利水电学院 North China Institute of Water Conservancy and Hydroelectric Power 课 程 设 计题目:全国交通资讯系统 院 系 信息工程学院 专 业 计算机科学与技术专业 姓 名 指 导 教 师 杨彬 2013年6月28日 目录1.需求分析1问题描述11.1基本要求22概要设计32.1 数据结构32.2 程序模块53.详细设计63.1用到的各种函数63.2函数调用关系图83.3测试与分析84.用户说明书135.总结165.1李明月的总结165.2刘璐璐的总结175.3吕竹青的总结18参考文献：19附录：程序源代
2、码191.需求分析 问题描述设计、模拟一个全国城市间的交通咨询程序，为旅客提供三种最优咨询方案：（1）时间最短；（2）费用最小；（3）中转次数最少。 1.1基本要求1.1.1输入输出的形式和输入值的范围 在程序中输入城市名称时，需输入10个字母以内的字母串；输入列车或飞机编号时需输入一个整型数据；输入列车或飞机的费用时需输入一个实型数据；输入列车或飞机开始时间和到达时间时均需输入两个整型数据（以hh：mm的形式）；在选择功能时，应输入与所选功能对应的一个整型数据。1.1.2 输出形式程序的输出信息主要是：最快需要多少时间才能到达，或最少需要多少旅费才能到达，或最少需要多少次中转到达，并详细说明
3、依次于何时乘坐哪一趟列车或哪一次班机到何地。 1.1.3程序所能达到的功能程序的功能包括：提供对城市信息的编辑，提供列车时刻表和飞机航班表的编辑，提供三种最优决策：最快到达、最省钱到达、最少中转次数到达，显示编辑的全国交通系统。1.1.4任务分配 在本程序中，我们一共划分了三个模块。管理员模块的初始化数据，城市信息的编辑，以及显示交通系统和整体的界面由李明月完成。航班班次以及列车车次添加删除以及数据结构的初步实现由吕竹青完成。对于最少时间，最少花费以及最少的中转次数这三个函数的实现由刘璐璐进行完成。 2概要设计2.1 数据结构#define MAX_VERTEX_NUM 18/城市节点数#de
4、fine MAX_ARC_SIZE 100#define MAX_ROUTE_NUM 5/路线数#define False 0#define True 1#define INFINITY 10000struct Vehide int number;/航班号,火车号 float expenditure;/费用 int begintime2;/出发时间 int arrivetime2;/到达时间;/航班、列车信息节点 struct infolist Vehide stataMAX_ROUTE_NUM;/一个出发地到达目的地所对应的航班数或列车车次数 int last;/顺序表所对应的下标，从0开始
5、;/顺序表表示struct ArcNodeint adjvex;/节点下标 ArcNode *nextarc; /节点的下一个指针域 infolist info;/节点的数据域;/邻接表中各个节点信息typedef struct VNode char cityname10;/城市名 ArcNode *planefirstarc,*trainfirstarc;/航班链、列车链 VNode,AdjListMAX_VERTEX_NUM;struct ALGraphAdjList vertices; int vexnum,planearcnum,trainarcnum;/城市数、航班数、列车数;str
6、uct Nodeint adjvex; int route; Node *next;/临时建立的一个邻接表，用来求最少中转次数和最少费用struct QNodeint adjvex; struct QNode *next;/链队节点信息struct LinkQueueQNode *front; QNode *rear;/链队信息typedef struct TimeNodeint adjvex; int route; int begintime2; int arrivetime2; struct TimeNode *childMAX_ROUTE_NUM;TimeNode,*TimeTree;s
7、truct arcint co; char vt10;/出发地名字 char vh10;/目的地名字 int bt2;/出发时间 int at2;/到达时间 float mo;/费用aMAX_ARC_SIZE;char cityMAX_VERTEX_NUM10;int TTime2;int time2;int time12;int time22;int cMAX_VERTEX_NUM;int dMAX_VERTEX_NUM;2.2 程序模块主要包括管理员编辑模块和用户查询模块以及显示全国交通信息模块。 2.2.1各模块之间的调用关系以及算法设计3.详细设计3.1用到的各种函数void Admi
8、nister(ALGraph *G); /void CityEdit(ALGraph *G); /城市编辑void CreateCityFile();void CreateGraph(ALGraph *G);void CreatePlaneFile();void CreateTrainFile();int DeleteplaneArc(ALGraph *G);void DeleteQueue(LinkQueue *Q,int *x);int DeletetrainArc(ALGraph *G);void DeleteVertex(ALGraph *G);void DemandDispose(i
9、nt n,ALGraph G);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
10、*G);void InitQueue(LinkQueue *Q);int IsEmpty(LinkQueue *Q);int LocateVertex(ALGraph *G,char *v);void MinExpenditure(infolist arcs,float *expenditure,int *route);void PrintGraph(ALGraph *G);int save(ALGraph *G);void trainedit(ALGraph *G);void TransferDispose(int k,infolist (*arcs)MAX_VERTEX_NUM,ALGra
11、ph G,int v0,int v1);void CopyTimeTree(TimeTree p,TimeTree q);void DestoryTimeTree(TimeTree p);void MinTime(infolist arcs,int *time,int *route);void VisitTimeTree(TimeTree p);void TimeDispose(int k,infolist (*arcs)MAX_VERTEX_NUM,ALGraph G,int v0,int v1,int (*T)2,int *final);void TimeTreeDispose(Node
12、*head,infolist (*arcs)MAX_VERTEX_NUM);void trainedit(ALGraph *G);void CreateTimeTree(TimeTree p,int i,int j,LinkQueue *Q,infolist (*arcs)MAX_VERTEX_NUM);void UserDemand(ALGraph G);3.2函数调用关系图3.3测试与分析3.3.1测试数据与截图1.管理员操作界面2.对整个结构进行初始化3.对城市，飞机班次，列车车次的编辑对城市的编辑：对航班的编辑：对列车的编辑：1.用户操作界面1.查询最少费用2.查询最短时间3.查询最少
13、的中转次数3.3.2测试分析1.1.1 考虑到道路网多是稀疏网，故采用了邻接表作存储结构，其空间复杂度位O(e)，此时的时间复杂度也为O（e）。构建邻接表的时间复杂度位O(n+e)，输出路径的时间复杂度为O（n2）。由此，本交通资讯系统的时间复杂度位O（n2）。1.1.2 本程序在求最短路径时使用了迪杰斯特拉算法，主要考虑在本程序的初级阶段，并不需要大量的查询，更多会是图信息的添加和修改，重在算法的理解和掌握，因此采用了算法复杂度相对较低的迪杰斯特拉算法。当然，从性能上来说，当交通图基本稳定，而且城市信息基本完善的时候，使用佛洛伊德把所有的最短路径信息存储起来可能会更方便一点，后续的查询的时间复杂度也会相对降低。由此可见，在选用算法时，不能单纯地只考虑算法的时间复杂度，有时还必须综合考虑各种因素。航班时刻表 机 号 出 发 地 到 达 地出发时间到达时间费 用 6320北京上海上海北京16：2018：00 17：2519：05680元2104北京乌鲁木齐乌鲁木齐 北京8：0010：459：5511：401150元201北京西安 西安 北京15：2512：3517：0014：15930元2323西安广州 广州 西安7：1510：159：35
