《数据结构课程设计分析报告》由会员分享，可在线阅读，更多相关《数据结构课程设计分析报告（147页珍藏版）》请在金锄头文库上搜索。
1、n数据结构课程设计报告 题目：全国交通咨询模拟 学 院 信息 专 业 计算机科学与技术 年级班不 计科0902 学 号 0912300213 学生姓名 陈佳丽 指导教师 章志勇 一需求分析1程序设计任务： 从中国地图平面图中选取部分都市，抽象为程序所需要图的结点，并以都市间的列车路线和飞机路线，作为图结点中的弧信息，设计一个全国交通咨询模拟系统。利用该系统实现两种最优决策：最快到达或最省钞票到达。2. 明确规定：(1)输入形式和输入值的范围： 每条飞机弧或者火车弧涉及的信息量专门多，包括：起始都市、目的都市、动身时刻、到达时刻、班次以及费用。作为治理员要输入的信息包括以上信息，而作为用户或者客
2、户，要输入的信息有起始都市和目的都市，并选择何种最优决策。 (2)输出形式：按用户提供的最优决策的不同而输出不同的信息，其中输出的所搭飞机或火车的班次及其起始地点和终点、起始时刻和动身时刻还有相关的最优信息，比如最快经多少时刻到达、最省钞票多少钞票到达和最少经多少中转站到达。(3)程序所能达到的功能a.该系统有供用户选择的菜单和交互性。能够对都市、列车车次和飞机航班进行编辑，添加或删除。b.建立一个全国交通咨询系统，该系统具备自动查找任意两都市间铁路、飞机交通的最短路径和最少花费及中转次数最少等功能。c.初始化交通系统有两种方式，键盘和文档。二设计概要1.抽象数据类型本程序运用了关于图这种数据
3、结构。ADT Graph 数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。 数据关系R： R=VR VR=|v,wV且P(v,w),表示从v到w的弧。 谓词P(v,w)定义了弧的意义或信息 差不多操作P： CreateGraph(&G,V,VR); 初始条件：V是图的顶点集，VR是图中弧的集合。 操作结果：按V和VR的定义构造图G。 DestroyGraph(&G); 初始条件：图G存在。 操作结果：销毁图G。 LocateVet(G,u); 初始条件：图G存在，u和G中顶点有相同的特征。 操作结果：若G中存在顶点u，则返回该顶点在图中的位置， 否则返回其他信息。 GetVex(G,
4、v); 初始条件：图G存在，v是G中某个顶点。 操作结果：返回v的值。PutVex(&G,v,value); 初始条件：图G存在，v是G中某个顶点。 操作结果：对v赋值value。FirstAdjVex(G,v); 初始条件：图G存在，v是G中某个顶点。 操作结果：返回v的第一个邻接顶点。若顶点在G中没有邻接 顶点，则返回“空”。NextAdjVex(G,v,w); 初始条件：图G存在，v是G中某个顶点，w是v的邻接顶点， 操作结果：返回v的(相关于w的)下一个邻接顶点。若w是v 的最后一个邻接点，则返回“空”。InsertVex(&G,v); 初始条件：图G存在，v和图中顶点有相同特征。 操
5、作结果：在图G中添加新顶点v。DeleteVex(&G,v); 初始条件：图G存在，v是G中某个顶点。 操作结果：删除G中顶点v及相关弧。InsertArc(&G,v,w); 初始条件：图G存在，v和w是G中两个顶点。 操作结果：在G中增添弧，若G是无向的则还增加对称弧 。DeleteArc(&G,v,w); 初始条件：图G存在，v和w是G中两个顶点。 操作结果：在G中删除弧，若G是无向的，则还删除对称 弧。DFSTraverse(G,Visit(); 初始条件：图G存在，Visit是顶点的应用函数。 操作结果：对图进行深度优先遍历。在遍历过程中对每个顶点调用函数Visit一次且仅一次。一旦v
6、isit()失败，则操作失败。BFSTraverse(G,Visit(); 初始条件：图G存在，Visit是顶点的应用函数。 操作结果：对图进行广度优先遍历。在遍历过程中对每个顶点调用函数Visit一次且仅一次。一旦visit()失败，则操作失败。 ADT Graph其他的抽象数据类型定义如下：typedef structint number; float expenditure; int begintime2; int arrivetime2;Vehide;typedef structVehide stataMAX_ROUTE_NUM; int last;infolist;typedef s
7、truct ArcNodeint adjvex; struct ArcNode *nextarc; infolist info;ArcNode;typedef struct VNodechar cityname10; ArcNode *planefirstarc,*trainfirstarc;VNode,AdjListMAX_VERTEX_NUM;typedef structAdjList vertices; int vexnum,planearcnum,trainarcnum;ALGraph;typedef struct Nodeint adjvex; int route; struct N
8、ode *next;Node;typedef struct QNodeint adjvex; struct QNode *next;QNode;typedef structQNode *front; QNode *rear;LinkQueue;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
9、bt2; int at2; float mo;aMAX_ARC_SIZE;差不多操作：void Administer(ALGraph *G);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);
10、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 DestoryTimeTree(TimeTree p);void EnterplaneArc(ALGraph *G);void EnterQueue(LinkQueue *Q,int x);void Entert
11、rainArc(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
12、);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,int *final);void TimeTreeDispose(Node *head,inf
13、olist (*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);主程序的流程以及各程序模块之间的调用关系退出显示交通系统PrintGraph用户咨询UserDemand治理员治理Administer主函数main（） 返回上一级菜单列车车次编辑Administer飞机航班编辑Administer都市编辑cityedit治理员治理Administer初始化交通系统initgraph返回上一级菜单最少中转次数TransferDispose最少旅行时刻TimeDispose用户咨询UserDemand最少旅行费用ExpenditureDisposeUserDemand显示都市显示飞机航班显示列车车次返回上一级菜单显示交通系统Pri
