数据结构课设 全国交通系统文档
- 格式：docx
- 大小：470.69 KB
- 文档页数：17
数据结构课设
课程名称数据结构课设
题目名称全国交通系统
学生学院计算机
专业班级
学 号
学生姓名
指导教师蒋
2016 年11月28日
一． 需求分析
1）程序任务要求
[问题描述]
出于不同目的的旅客对交通工具有不同的要求。例如，因公出差的旅客希望在旅途中的时间尽可能短，出门旅游的游客则期望旅费尽可能省，而老年旅客则要求中转次数最少。编制一个全国城市间的交通咨询程序，为旅客提供两种或三种最优决策的交通咨询。
[基本要求]
① 提供对城市信息进行编辑（如：添加或删除）的功能。
② 城市之间有两种交通工具：火车和飞机。提供对列车时刻表和飞机航班进行编辑（增设或删除）的功能。
③ 提供两种最优决策：最快到达或最省钱到达。全程只考虑一种交通工具。
④ 旅途中耗费的总时间应该包括中转站的等候时间。
⑤ 咨询以用户和计算机的对话方式进行。由用户输入起始站、终点站、最优决策原则和交通工具，输出信息为：最快需要多长时间才能到达或者最少需要多少旅费才能到达，并详细说明依次于何时乘坐哪一趟列车或哪一次班机到何地。
[选做内容]
增加旅途中转次数最少的最优决策。
二． 设计概要
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。
LocateVet(G,u);
初始条件：图 G存在， u 和 G中顶点有相同的特征。
操作结果：若 G中存在顶点 u，则返回该顶点在图中的位置，
否则返回其他信息。
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是无向的，则还删除对称弧。
} ADT Graph
其他的抽象数据类型定义如下：
typedef struct
{
int number;
float expenditure;
intbegintime[2];
intarrivetime[2];
}Vehide; //飞机或列车运行信息
typedef struct
{
Vehidestata[MAX_ROUTE_NUM];
int last; //航班次或列车次
}infolist; //弧的权的信息（车次或航班信息）
typedef struct ArcNode
{
intadjvex;
struct ArcNode *nextarc;
infolist info;
}ArcNode; //邻接表节点，存入弧（交通路线）的信息
typedef struct VNode
{
char cityname[10];
ArcNode *planefirstarc, *trainfirstarc;
}VNode, AdjList[MAX_VERTEX_NUM];//顶点数组元素
typedef struct
{
AdjList vertices;
intvexnum, planearcnum, trainarcnum;
}ALGraph; //图结构
typedef struct Node
{
intadjvex;
int route;
struct Node *next;
}Node;//辅助节点的存储结构
typedef struct QNode
{
intadjvex;
struct QNode *next;
}QNode;//队列节点，节点元素为int型
typedef struct
{
QNode *front;
QNode *rear;
}LinkQueue;//队列结构
typedef struct TimeNode
{
intadjvex;
int route;
intbegintime[2];
intarrivetime[2];
struct TimeNode *child[MAX_ROUTE_NUM];
}TimeNode, *TimeTree; //求最短时间辅助树
struct arc
{
int co; //列车或飞机编号
char vt[10]; //起始城市
char vh[10];//到达城市
intbt[2]; //起始时间
int at[2];//到达时间
float mo;//费用
}a[MAX_ARC_SIZE];//存放边信息
2) 操作函数
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, inti, int j, LinkQueue *Q, infolist
(*arcs)[MAX_VERTEX_NUM]);
void createtrainfile();/*创建列车路线文档*/
intDeleteplaneArc(ALGraph *G);
void DeleteQueue(LinkQueue *Q, int *x);
intDeletetrainArc(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);
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);
intIsEmpty(LinkQueue *Q);
intLocateVertex(ALGraph *G, char *v);
void MinExpenditure(infolist arcs, float *expenditure, int *route);
void MinTime(infolist arcs, int *time, int *route);
void PrintGraph(ALGraph *G);
intsave(ALGraph *G);
void TimeDispose(int k, infolist(*arcs)[MAX_VERTEX_NUM],
ALGraph G, int v0, int v1, int(*T)[2], 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);/*登录管理员界面*/
3）主程序的流程以及各程序模块之间的调用关系
三. 详细设计
1） 伪码算法
intmain() {
