全国交通咨询模拟 - 图文

一．需求分析

1．程序设计任务：

从中国地图平面图中选取部分城市，抽象为程序所需要图的结点，并以城市间的列车路线和飞机路线，作为图结点中的弧信息，设计一个全国交通咨询模拟系统。利用该系统实现两种最优决策：最快到达或最省钱到达。 2. 明确规定：

(1)输入形式和输入值的范围：

每条飞机弧或者火车弧涉及的信息量很多，包括：起始城市、目的城市、出发时间、到达时间、班次以及费用。作为管理员要输入的信息包括以上信息，而作为用户或者客户，要输入的信息有起始城市和目的城市，并选择何种最优决策。 (2)输出形式：

按用户提供的最优决策的不同而输出不同的信息，其中输出的所搭飞机或火车的班次及其起始地点和终点、起始时间和出发时间还有相关的最优信息，比如最快经多少时间到达、最省钱多少钱到达和最少经多少中转站到达。 (3)程序所能达到的功能

a.该系统有供用户选择的菜单和交互性。可以对城市、列车车次和飞机航班进行编辑，添加或删除。

b.建立一个全国交通咨询系统，该系统具备自动查找任意两城市间铁路、飞机交通的最短路径和最少花费及中转次数最少等功能。 c.初始化交通系统有两种方式，键盘和文档。

二．设计概要

1.抽象数据类型

本程序运用了关于图这种数据结构。 ADT Graph{

数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。 数据关系R： R={VR}

VR={|v,w∈V且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,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和图中顶点有相同特征。 操作结果：在图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一次且仅一次。一旦visit()失败，则操作失败。

BFSTraverse(G,Visit());

初始条件：图G存在，Visit是顶点的应用函数。

操作结果：对图进行广度优先遍历。在遍历过程中对每个顶点调用函

数Visit一次且仅一次。一旦visit()失败，则操作失败。

}ADT Graph

其他的抽象数据类型定义如下：

typedef struct {int number;

float expenditure; int begintime[2]; int arrivetime[2]; }Vehide; typedef struct

{Vehide stata[MAX_ROUTE_NUM]; int last; }infolist;

typedef struct ArcNode {int adjvex;

struct ArcNode *nextarc; infolist info; }ArcNode;

typedef struct VNode {char cityname[10];

ArcNode *planefirstarc,*trainfirstarc; }VNode,AdjList[MAX_VERTEX_NUM]; typedef struct {AdjList vertices;

int vexnum,planearcnum,trainarcnum; }ALGraph;

typedef struct Node {int adjvex; int route;

struct Node *next; }Node;

typedef struct QNode {int adjvex;

struct QNode *next; }QNode; typedef struct {QNode *front; QNode *rear; }LinkQueue;

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];

基本操作：

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]); 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 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 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,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);

主程序的流程以及各程序模块之间的调用关系 初始化交通系统initgraph 城市编辑 cityedit 飞机航班编辑Administer 用户咨询 UserDemand 列车车次编辑 Administer 返回上一级菜单 管理员管理 Administer 管理员管理 Administer 用户咨询 UserDemand 显示交通系统 PrintGraph 退出 主函数main（）

最少旅行费用ExpenditureDispos最少旅行时间 TimeDispose 显示交通系统 PrintGraph 最少中转次数 TransferDispos返回上一级菜单

新增车次 删除车次 火车列次编辑 trainedit 新增航班 删除航班 飞机航班编辑 planeedit 新增城市 删除城市 键盘 初始化交通系统initgraph 城市编辑 cityedit 文档 三．详细设计

1.主程序伪代码

int main() {

界面初始化； 输入操作命令； While（“命令” ！= “退出”） {

接受命令（用户输入要实现功能）； 进入各个处理命令函数；

} }

2. 函数和过程的调用关系图

Administer

UserDemand Main()

createcityfile createplanefile initgraph createtrainfile CreateGraph EnterVertex cityedit DeleteVertex EnterplaneArc flightedit DeleteplaneArEntertrainArc trainedit DeletetrainArc ExpenditureDispose MinExpenditure MinTime TimeDispose TimeTreeDispose InitQueue TransferDispose EnterQueue DeleteQueue

TimeTreeDispose InitQueue EnterQueue DeleteQueue CreateTimeTree CopyTimeTree

VisitTimeTree DestoryTimeTree 四．调试分析：

⑴ 调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析： 在调试的过程中碰到了一下问题： a. 引用形参应用不当；

b. 文件操作中遇到读入错误或找不到文件； 解决方案：

a. 对引用形参了解的不是很透彻，导致错误，通过查阅相关书籍如《C++ Primer》和请教编程能力较高的人，最终解决问题。

b. 通过参考谭浩强编著的《C程序设计》中的文件操作，文件格式和相关文件路径的设置，最终解决问题。

⑵ 算法的时空分析（包括基本操作和其他算法的时间复杂度和空间复杂度的分析）和改进设想： 基本操作 时间复杂度 空间复杂度 void Administer(ALGraph *G) O(1) O(1)

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 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 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 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,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)

O(n) O(n) O(n) O(n) O(1) O(n) O(n) O(1) O(n) O(n) O(1) O(n) O(1) O(n) O(1) O(n) O(n) O(1) O(n) O(n) O(1) O(1) O(n) O(n) O(1) O(n) O(1) O(n) O(n) O(1) O(1) O(n) O(1) O(1) O(n) O(1) O(1) O(1) O(1) O(1) O(n) O(n) O(n) O(1) O(1) O(n) O(1) O(n) O(1) O(1) O(1) O(n) O(n) O(n) O(1) O(n) O(n) O(1) O(n) O(n) O(1) O(n) O(1) O(n) O(1) O(n)

⑶ 经验和体会：

通过本次课程设计，我学到了一种程序设计方法，就是结构化程序设计方法，在程序设计过程中，我尝试按如下方法进行结构化程序设计：

(1)自顶向下；(2)逐步细化；(3)模块化设计(4)结构化编码。这种设计方法的过程是将问题求解由抽象逐步具体化的过程，而且，用这种方法便于验证算法的正确性。

本次课程设计所使用的是较为复杂的抽象数据类型——图，而且在弧的基础上增加了许多信息，如添加了时间，费用等等，这无疑给编程加大了难度，同时也是相当的具有挑战性。

在编程的过程中，我用到了全局数组，我将数组放在工程的头文件里面，编译的时候报错，说是多重定义。最终放弃了创建工程，而选择了单个文件进行编译和运行，结果顺利通过。

同时，在文件操作方面我也曾遇到问题，就是在程序对文件进行读取的时候报错，无法读取文件，最后查询有关C的工具书，原来是文件路径问题，借助工具书最终解决了文件操作方面的问题。

总之，这次课程设计是对这一个学期以来对数据结构学习成果的一个验证，同时也是理论与实践很好的结合，既对学过的数据结构进行了巩固，也对我的编程能力奠定了坚实的基础。

五．用户使用说明：

1) 打开并运行程序，按任意键进入操作主界面，按提示进行相关操作；

2) 按“1”进入管理员界面，按“2”进入用户咨询界面，按“3”显示交通系

统，按“4”则退出。

3) 进入管理员界面可键入“1”初始化交通系统，并选择文档初始化方式(如果

是第一次使用该系统建议使用文档初始化交通系统，免得自己进行繁冗的初始化操作)。其余可按提示进行相关操作，不难掌握。

4) 进入用户咨询界面，可根据用户需要进行相关的选择，或是选择“1”(最少

旅行费用)；或是选择“2”(最少旅行时间)，又或者是选择“3”(最少旅行中转次数)等。

5) 进入显示交通系统界面，根据用户选择则可显示城市、飞机航班、列车车次

等信息。或者返回上一级菜单。

六．测试结果：

1. 个人信息界面：

2. 操作主界面：

3. 管理员界面：

4. 交通系统初始化方式选择界面：

5. 城市编辑界面：

6. 飞机航班编辑：

7. 列车车次编辑：

8. 显示交通系统主界面：

9. 显示城市：

10. 显示飞机航班：

11. 显示列车车次：

12． 用户咨询：

13. 选择旅行起始城市：

14. 选择旅行到达城市：

15. 选择旅行的交通工具：

16. 最少旅行费用：

17．最少旅行时间：

18. 最少中转次数：

七．附录——源程序

#define MAX_VERTEX_NUM 18 #define NULL 0

#define MAX_ARC_SIZE 100 #define MAX_ROUTE_NUM 5 #include #include #include #include #define False 0 #define True 1

#define INFINITY 10000 typedef struct { int number; float expenditure; int begintime[2]; int arrivetime[2]; }Vehide;

typedef struct { Vehide stata[MAX_ROUTE_NUM]; int last; }infolist;

typedef struct ArcNode { int adjvex; struct ArcNode *nextarc;

infolist info; }ArcNode;

typedef struct VNode { char cityname[10]; ArcNode *planefirstarc,*trainfirstarc; }VNode,AdjList[MAX_VERTEX_NUM];

typedef struct { AdjList vertices;

int vexnum,planearcnum,trainarcnum; }ALGraph;

typedef struct Node { int adjvex; int route;

struct Node *next; }Node;

typedef struct QNode { int adjvex;

struct QNode *next; }QNode;

typedef struct { QNode *front; QNode *rear; }LinkQueue;

typedef struct TimeNode { int adjvex; int route;

int begintime[2]; int arrivetime[2];

struct TimeNode *child[MAX_ROUTE_NUM]; }TimeNode,*TimeTree;

struct arc

本文来源：https://www.bwwdw.com/article/sts.html