大数据结构课程设计报告材料之模拟一个全国城市间地交通咨询程序.doc

word分类号 编号华北水利水电学院North China Institute of Water Conservancy and Hydroelectric Power课 程 设 计题目:全国交通资讯系统院 系 信息工程学院 专业 计算机科学与技术专业 姓 名 指 导 教 师 彬 2013年6月28日目录1.需求分析1问题描述1根本要求22概要设计32.1 数据结构32.2 程序模块53.详细设计6用到的各种函数6函数调用关系图8测试与分析84.用户说明书135.总结16明月的总结16璐璐的总结17吕竹青的总结18参考文献：19附录：程序源代码19问题描述设计、模拟一个全国城市间的交通咨询程序，为旅客提供三种最优咨询方案：〔1〕时间最短；〔2〕费用最小；〔3〕中转次数最少输入输出的形式和输入值的围在程序中输入城市名称时，需输入10个字母以的字母串；输入列车或飞机编号时需输入一个整型数据；输入列车或飞机的费用时需输入一个实型数据；输入列车或飞机开始时间和到达时间时均需输入两个整型数据〔以hh：mm的形式〕；在选择功能时，应输入与所选功能对应的一个整型数据。

1.1.2 输出形式程序的输出信息主要是：最快需要多少时间才能到达，或最少需要多少旅费才能到达，或最少需要多少次中转到达，并详细说明依次于何时乘坐哪一趟列车或哪一次班机到何地程序的功能包括：提供对城市信息的编辑，提供列车时刻表和飞机航班表的编辑，提供三种最优决策：最快到达、最省钱到达、最少中转次数到达，显示编辑的全国交通系统 在本程序中，我们一共划分了三个模块管理员模块的初始化数据，城市信息的编辑，以与显示交通系统和整体的界面由明月完成航班班次以与列车车次添加删除以与数据结构的初步实现由吕竹青完成对于最少时间，最少花费以与最少的中转次数这三个函数的实现由璐璐进展完成2概要设计2.1 数据结构#define MAX_VERTEX_NUM 18//城市节点数#define MAX_ARC_SIZE 100#define MAX_ROUTE_NUM 5//路线数#define False 0#define True 1#define INFINITY 10000struct Vehide{ int number;//航班号,火车号 float expenditure;//费用 int begintime[2];//出发时间 int arrivetime[2];//到达时间};//航班、列车信息节点 struct infolist{ Vehide stata[MAX_ROUTE_NUM];//一个出发地到达目的地所对应的航班数或列车车次数 int last;//顺序表所对应的下标，从0开始};//顺序表表示struct Arode{ int adjvex;//节点下标 Arode *nextarc; //节点的下一个指针域 infolist info;//节点的数据域};//邻接表中各个节点信息typedef struct VNode{ char cityname[10];//城市名 Arode *planefirstarc,*trainfirstarc;//航班链、列车链} VNode,AdjList[MAX_VERTEX_NUM];struct ALGraph{ AdjList vertices; int vexnum,planearum,trainarum;//城市数、航班数、列车数};struct Node{int adjvex; int route; Node *next;};//临时建立的一个邻接表，用来求最少中转次数和最少费用struct QNode{int adjvex; struct QNode *next;};//链队节点信息struct LinkQueue{QNode *front; QNode *rear;};//链队信息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];char city[MAX_VERTEX_NUM][10];int TTime[2];int time[2];int time1[2];int time2[2];int c[MAX_VERTEX_NUM];int d[MAX_VERTEX_NUM];2.2 程序模块主要包括管理员编辑模块和用户查询模块以与显示全国交通信息模块。

各模块之间的调用关系以与算法设计用到的各种函数void Administer(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(int 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 *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],ALGraph 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 *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.对城市，飞机班次，列车车次的编辑对城市的编辑：对航班的编辑：对列车的编辑：测试分析1.1.1 考虑到道路网多是稀疏网，故采用了邻接表作存储结构，其空间复杂度位O(e)，此时的时间复杂度也为O〔e〕。

构建邻接表的时间复杂度位O(n+e)，输出路径的时间复杂度为O〔n2〕由此，本交通资讯系统的时间复杂度位O〔n2〕1.1.2 本程序在求最短路径时使用了迪杰斯特拉算法，主要考虑在本程序的初级阶段，并不需要大量的查询，更多会是图信息的添加和修改，重在算法的理解和掌握，因此采用了算法复杂度相对较低的迪杰斯特拉算法当然，从性能上来说，当交通图根本稳定，而且城市信息根本完善的时候，使用佛洛伊德把所有的最短路径信息存储起来可能会更方便一点，后续的查询的时间复杂度也会相对降低由此可见，在选用算法时，不能单纯地只考虑算法的时间复杂度，有时还必须综合考虑各种因素航班时刻表  机  号                      出发地到达地出发时间到达时间费  用  632016：2018：00   17：2519：05680元2104乌鲁木齐乌鲁木齐  8：0010：459：5511：401150元201      15：2512：3517：0014：15930元2323     7：1510：159：3511：351320元173    10：2012：3511：4514：00830元3304    14：1516：2515：4517：55890元82乌鲁木齐  乌鲁木齐  9：3013：0512：1515：501480元4723    7：0511：258：4513 ：05810元列车时刻表车次出发地到达地出发时间到达时间车   费27 13：1521：2405：4113：4221：1205：13。