数据结构课设 全国交通系统文档

1、数据结构课设 课程名称 数据结构课设 题目名称 全国交通系统 学生学院 计算机 专业班级 学 号 学生姓名 指导教师 蒋 2016 年 11 月28 日一 需求分析1） 程序任务要求问题描述出于不同目的的旅客对交通工具有不同的要求。例如，因公出差的旅客希望在旅途中的时间尽可能短，出门旅游的游客则期望旅费尽可能省，而老年旅客则要求中转次数最少。编制一个全国城市间的交通咨询程序，为旅客提供两种或三种最优决策的交通咨询。基本要求提供对城市信息进行编辑（如：添加或删除）的功能。城市之间有两种交通工具：火车和飞机。提供对列车时刻表和飞机航班进行编辑（增设或删除）的功能。提供两种最优决策：最快到达或最省钱

2、到达。全程只考虑一种交通工具。旅途中耗费的总时间应该包括中转站的等候时间。咨询以用户和计算机的对话方式进行。由用户输入起始站、终点站、最优决策原则和交通工具，输出信息为：最快需要多长时间才能到达或者最少需要多少旅费才能到达，并详细说明依次于何时乘坐哪一趟列车或哪一次班机到何地。选做内容增加旅途中转次数最少的最优决策。二 设计概要1) 数据类型的定义本程序运用了关于图这种数据结构。ADT Graph数据对象 V：V 是具有相同特性的数据元素的集合，称为顶点集。数据关系 R：R=VRVR=<v,w>|v, wV且 P(v,w),<v,w> 表示从 v 到 w的弧。谓词 P(

3、v,w) 定义了弧 <v,w>的意义或信息 基本操作 P：CreateGraph(&G,V,VR);初始条件： V是图的顶点集， VR是图中弧的集合。操作结果：按 V和 VR的定义构造图 G。LocateVet(G,u);初始条件：图 G存在， u 和 G中顶点有相同的特征。操作结果：若 G中存在顶点 u，则返回该顶点在图中的位置，否则返回其他信息。InsertVex(&G,v);初始条件：图 G存在， v 和图中顶点有相同特征。操作结果：在图 G中添加新顶点 v。DeleteVex(&G,v);初始条件：图 G存在， v 是 G中某个顶点。操作结果：删除

4、G中顶点 v 及相关弧。InsertArc(&G,v,w);初始条件：图 G存在， v 和 w是 G中两个顶点。操作结果：在 G中增添弧 <v,w>，若 G是无向的则还增加对称弧<w,w> 。DeleteArc(&G,v,w);初始条件：图 G存在， v 和 w是 G中两个顶点。操作结果：在 G中删除弧 <v,w>，若 G是无向的，则还删除对称弧<w,v>。 ADT Graph其他的抽象数据类型定义如下：typedef structint number;float expenditure;int begintime2;int ar

5、rivetime2;Vehide; /飞机或列车运行信息typedef structVehide stataMAX_ROUTE_NUM;int last; /航班次或列车次infolist; /弧的权的信息（车次或航班信息）typedef struct ArcNodeint adjvex;struct ArcNode *nextarc;infolist info;ArcNode; /邻接表节点，存入弧（交通路线）的信息typedef struct VNodechar cityname10;ArcNode *planefirstarc, *trainfirstarc;VNode, AdjList

6、MAX_VERTEX_NUM;/顶点数组元素typedef structAdjList vertices;int vexnum, planearcnum, trainarcnum;ALGraph; /图结构typedef struct Nodeint adjvex;int route;struct Node *next;Node;/辅助节点的存储结构typedef struct QNodeint adjvex;struct QNode *next;QNode;/队列节点，节点元素为int型typedef structQNode *front;QNode *rear;LinkQueue;/队列结

7、构typedef struct TimeNodeint adjvex;int route;int begintime2;int arrivetime2;struct TimeNode *childMAX_ROUTE_NUM;TimeNode, *TimeTree; /求最短时间辅助树struct arcint co; /列车或飞机编号char vt10; /起始城市char vh10;/到达城市int bt2; /起始时间int at2;/到达时间float mo;/费用aMAX_ARC_SIZE;/存放边信息2) 操作函数void Administer(ALGraph *G); /*管理员操

8、作*/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 createtr

9、ainfile();/*创建列车路线文档*/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

10、);void EntertrainArc(ALGraph *G);void EnterVertex(ALGraph *G);voidExpenditureDispose(int k, infolist(*arcs)MAX_VERTEX_NUM, ALGraph G, int v0, intv1, float *M, int *final);/*求取费用最少路线*/void flightedit(ALGraph *G);void initgraph(ALGraph *G); /*初始化交通系统*/void InitQueue(LinkQueue *Q);int IsEmpty(LinkQueue

11、 *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

12、, int *final); /*求取用时最少的路线*/voidTimeTreeDispose(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);void LogIn(ALGraph *G);/*登录管

13、理员界面*/3） 主程序的流程以及各程序模块之间的调用关系三. 详细设计1） 伪码算法int main()界面初始化；输入操作命令；While （“命令” ！= “退出”）接受命令（用户输入要实现功能） ；进入各个处理命令函数；void TransferDispose(int k,infolist(*arcs)MAX_VERTEX_NUM, ALGraph G, int v0, int v1)/求中转站最少路径 该函数要用到存储路径的链式节点数组*p和辅助队列； V0入队 While（队列不为空） If（v0的下一个连接顶点w未被访问）将v0，w按顺序存到链式数组元素pw中If（w=v1）输出

14、路径信息W入队 下一个连接顶点（t = t->nextarc;）不存在v0到v1的路线void ExpenditureDispose(int k, infolist(*arcs)MAX_VERTEX_NUM, ALGraph G, int v0, intv1, float *M, int *final)/求费用最少的路线该函数要用到存储路径的链式节点数组*p和float M,MV表示从起始城市V0到V的最少费用，标志数组final,finali=1表示V0到i已求得用费最少的路线，再通过 i求其他最短路线，直到求到目的城市V1，这类似普利姆算法。首先是初始化M,final,p，先求得v0

15、到各个节点的直接最少费用（若存在），for (w = 0; w<G.vexnum; w+)查找M数组未被访问的元素中值最少的元素vIf（v=v0）通过存储路径的链式节点数组*p输出完整路线Else v存在，将v置已访问状态，更新M数组，若v0到w的费用通过前驱v会比原来少，就更新，更新辅助链式存储数组P，将w的前驱节点v加入到pw中不存在v0到v1的路线void TimeDispose(int k, infolist(*arcs)MAX_VERTEX_NUM, ALGraph G, int v0, int v1, int(*T)2, int *final)/求用时最少的路线该函数要用到存

16、储路径的链式节点数组*p和 T，TV表示从起始城市V0到V的最少用时，标志数组final,finali=1表示V0到i已求得用时最少的路线，再通过 i求其他用时最短路线，直到求到目的城市V1，这类似普利姆算法。首先是初始化M,final,p，先求得v0到各个节点的直接最少用时（若存在），for (w = 0; w<G.vexnum; w+)查找T数组未被访问的元素中值最少的元素vIf（v=v0）通过存储路径的链式节点数组*p输出完整路线Else v存在，将v置已访问状态，更新辅助链式存储数组P，将w的前驱节点v加入到pw中，借助辅助时间树更新T数组，若v0到w的用时通过前驱v会比原来少，

17、就更新，不存在v0到v1的路线2） 函数和过程的调用关系图四. 调试分析1） 调试过程中遇到的问题的解决的以及对设计与实现的回顾讨论和分析a. 文件操作中遇到读入错误或找不到文件；解决：通过参考谭浩强编著的C程序设计中的文件操作，文件写入和读取的格式和相关文件路径的设置，最终解决问题b. 获取键盘输入报错解决：通过调试发现是因为粗心大意在用scanf函数是少打取地址符&c. 形参使用不当解决：查看教科书和上午查找相关的用法说明，最终解决问题2） 算法的时空分析基本操作时间复杂度空间复杂度void LogIn(ALGraph *G)O(1)O(1)void Administer(ALGr

18、aph *G)O(1)O(1)void cityedit(ALGraph *G)O(n)O(n)void CopyTimeTree(TimeTree p,TimeTree q)O(n)O(1)void createcityfile()O(n)O(n)void CreateGraph(ALGraph *G)O(n)O(n)void createplanefile()O(1)O(1)void CreateTimeTree(TimeTree p,int i,intj,LinkQueue*Q,infolist(*arcs)MAX_VERTEX_NUM)O(n)O(n)void createtrainf

19、ile()O(1)O(1)int DeleteplaneArc(ALGraph *G)O(n)O(n)void DeleteQueue(LinkQueue *Q,int *x)O(1)O(1)int DeletetrainArc(ALGraph *G)O(n)O(n)void DeleteVertex(ALGraph *G)O(n)O(n)void DemandDispose(int n,ALGraph G)O(1)O(1)void DestoryTimeTree(TimeTree p)O(n)O(1)void EnterplaneArc(ALGraph *G)O(n)O(n)void Ent

20、erQueue(LinkQueue *Q,int x)O(1)O(1)void EntertrainArc(ALGraph *G)O(1)O(1)void EnterVertex(ALGraph *G)O(n)O(n)voidExpenditureDispose(intk,infolist(*arcs)MAX_VERTEX_NUM,ALGraph G,intv0,int v1,float *M,int *final)O(n)O(1)void flightedit(ALGraph *G)O(1)O(1)void initgraph(ALGraph *G)O(1)O(n)void InitQueu

21、e(LinkQueue *Q)O(1)O(1)int IsEmpty(LinkQueue *Q)O(1)O(1)int LocateVertex(ALGraph *G,char *v)O(n)O(1)void MinExpenditure(infolist arcs,float*expenditure,int *route)O(n)O(n)void MinTime(infolist arcs,int *time,int *route)O(n)O(n)void PrintGraph(ALGraph *G)O(1)O(n)int save(ALGraph *G)O(1)O(1)void TimeD

22、ispose(int k,infolist(*arcs)MAX_VERTEX_NUM,ALGraph G,intv0,int v1,int (*T)2,int *final)O(n)O(n)void TimeTreeDispose(Node *head,infolist(*arcs)MAX_VERTEX_NUM)O(n)O(n)void trainedit(ALGraph *G)O(1)O(1)void TransferDispose(int k,infolist(*arcs)MAX_VERTEX_NUM,ALGraph G,intv0,int v1)O(n)O(n)void UserDemand(ALGraph G)O(1)O(1)void VisitTimeTree(Tim