全国交通咨询模拟数据结构课件教育设计.doc

数据结构课程设计报告

题目：全国交通咨询模拟

一．需求分析
1．程序设计任务：
从中国地图平面图中选取部分城市，抽象为程序所需要图的结点，并以城市间的列车路线和飞机路线，作为图结点中的弧信息，设计一个全国交通咨询模拟系统。利用该系统实现两种最优决策：最快到达或最省钱到达。
2. 明确规定：
(1)输入形式和输入值的范围：
每条飞机弧或者火车弧涉及的信息量很多，包括：起始城市、目的城市、出发时间、到达时间、班次以及费用。作为管理员要输入的信息包括以上信息，而作为用户或者客户，要输入的信息有起始城市和目的城市，并选择何种最优决策。
(2)输出形式：
按用户提供的最优决策的不同而输出不同的信息，其中输出的所搭飞机或火车的班次及其起始地点和终点、起始时间和出发时间还有相关的最优信息，比如最快经多少时间到达、最省钱多少钱到达和最少经多少中转站到达。
(3)程序所能达到的功能
a.该系统有供用户选择的菜单和交互性。可以对城市、列车车次和飞机航班进行编辑，添加或删除。
b.建立一个全国交通咨询系统，该系统具备自动查找任意两城市间铁路、飞机交通的最短路径和最少花费及中转次数最少等功能。
c.初始化交通系统有两种方式，键盘和文档。
二．设计概要
1. 算法设计
(1)、总体设计
(1) 数据存储:城市信息(城市名、代码)、交通信息(城市间的里程、各航班和列车时刻)存储于磁盘文件。建议把城市信息存于文件前面，交通信息存于文件的后面，用fread和fwrite函数操作。
(2) 数据的逻辑结构:根据设计任务的描述，其城市之间的旅游交通问题是典型的图结构，可看作为有向图，图的顶点是城市，边是城市之间所耗费的时间（要包括中转站的等候时间）或旅费。
(3) 数据的存储结构:采用邻接表和邻接矩阵都可作为数据的存储结构，但当邻接边不多时，宜采用邻接表，以提高空间的存储效率。这里采用邻接表作为数据的存储结构。
(4) 用不同的功能模块对城市信息和交通信息进行编辑。添加、修改、删除功能可用菜单方式或命令提示方式。只要能方便的对城市信息和交通信息进行管理即可，但要注意人机界面。
(5) 最优决策功能模块(fast or province)。
① 读入城市信息和交通信息，用邻接表生成含权网络，表头数组中的元素存放城市名及对方城市到达该元素所代表城市的所有信息；表头数组中的元素所对应的单链表存放与该元素所代表的城市有交通联系的城市(代码、里程、航班、列车车次)。
② 根据具体最优决策的要求，用Dijkstra算法求出出发城市到其它各城市的最优值(最短时间或最小的费用)，搜索过程中所经过城市的局部最优信息都保存在邻接表的表头数组中。其目的城市所代表的元素中就保存了所需的最优决策结果。这过程中，要用队列或栈保存局部最优决策值(局部最短的时间或最省的费用)变小的城市，其相应的初始值可为∞，并在表头数组对应的城市元素中保存响应的信息。开始时，栈(队列)中只有出发地城市，随着对栈(队列)顶(首)城市有交通联系的城市求得决策值(最短时间或最小的费用)，若该值是局部最优值且该城市不在栈(队列)中，则进栈(队列)，直至栈(队列)为空，本题采用队列实现。
③ 输出结果：从目的城市出发，搜索到出发城市，所经过的城市均入栈(队列)，再逐一出栈栈(队列)中的城市，输出保存在表头数组中对应城市的信息(对方城市的出发信息，里程、时间、费用等)及最终结果。即输出依次于何时何地乘坐几点的飞机或火车于何时到达何地；最终所需的最快需要多长时间才能到达及旅费，或者最少需要多少旅费才能到达及时间。
(6) 主程序可以有系统界面、菜单；也可用命令提示方式；选择功能模块执行，要求在程序运行过程中可以反复操作。
(2).详细设计思想：
本题所要求的交通系统是一个有向带权图结构，考虑到要求该系统有动态增加飞机和列车航班的功能，因而采用邻接表的形式存储：对每个顶点建立一个单链表，单链表中的子结点表示以该顶点连接的弧，单链表中子结点的顺序可以按权值递增的顺序排列，表头结点按顺序存储。题目中提到要提供三种策略，最快到达，最省钱到达和最少中转次数策略，前两种策略采用迪杰斯特拉算法思想，其中最快到达的权值为到达两城市所需的最短时间，最省钱到达的权值为到达两城市所需的费用，后一种采用广度优先算法的思想，只需求的两城市所在的层数，就可以求的到达两城市所需的最少中转次数。
迪杰斯特拉（Dijkstra）算法的基本思想是：
设置两个顶点的集合S和T＝V－S，集合S中存放已找到最短路径的顶点，集合T存放当前还未找到最短路径的顶点。初始状态时，集合S中只包含源点v0，然后不断从集合T中选取到顶点v0路径长度最短的顶点u加入到集合S中，集合S每加入一个新的顶点u，都要修改顶点v0到集合T中剩余顶点的最短路径长度值，集合T中各顶点新的最短路径长度值为原来的最短路径长度值与顶点u的最短路径长度值加上u到该顶点的路径长度值中的较小值。此过程不断重复，直到集合T的顶点全部加入到S中为止。
下面讨论基于邻接表的存储结构求两点间最短路径的方法：
  根据迪杰斯特拉(Dijkstra)算法所依据的原理：若按长度递增的次序生成从源点V0到其它顶点的最短路径，则当前正在生成的最短路径上除终点以外，其余顶点的最短路径均已生成（将源点的最短路径看作是已生成的源点到其自身的长度为0的路径）。
  按照这一思想，构造以下算法：
  设S=S’=U={}，建立数组PATH[n]，用来存储V0到各终点的最短路径，初值均置为空集。建立数组BOOL F[n]，F[i]表示序号为i的表头结点的单链表中所有子结点已或未全部找到，初值置为FALSE。建立数组float dist[n]，dist[i]表示序号为i的表头结点到V0的最短权值（这里是时间或费用），显然dist[V0]=0,其他顶点的dist初值置为∞。建立数组BOOL IS[n]，IS[i]表示序号为i的顶点是否在S中，初值均置为FALSE。
  (1)VX=V0；最短的最短路径为PATH[0]=[V0]
     (2)S=S+VX；（集合的并计算）
IS[VX]=TRUE；
S’=S’+VX ；
    (3)对S’中的所有顶点：
{
do{ 由邻接表中该表头结点开始依次找单链表的下一子结点(沿链域指针依次访问)；
if(该子结点∈S)//IS[该子结点的邻接点序号]==TRUE
if（子结点链域指针指向NULL）
F=TRUE；S’=S’-该表头结点；
break；
else continue；
else break；
}
while();
如F=FALSE,则U=U+该子结点；
}
如果S’=空集，则结束；
(4)下一次短路径的终点必∈U。比较U中子结点到V0的dist值（其值为U中结点的弧的权值+其表头结点的dist值），由dist值最小的子结点的邻接点域确定次短路径的终点VX， PATH[ VX]=PATH[该子结点的表头结点]+[VX]（集合的并计算）。dist[VX]=VX所属子结点的弧的权值+其表头结点的dist值。
U={}；
如果VX为所要找的顶点，则结束；
回到2执行。
广度优先搜索遍历图类似于树的按层次遍历，其基本思想是：首先访问图中某指定的起始点Vi并将其标记为已访问过，然后由Vi出发访问与它相邻接的所有顶点Vj、 Vk……，并均标记为已访问过，然后再按照Vj、Vk……的次序，访问每一个顶点的所有未被访问过的邻接顶点，并均标记为已访问过，下一步再从这些顶点出发访问与它们相邻接的尚未被访问的顶点，如此做下去，直到所有的顶点均被访问过为止。

2.抽象数据类型
本程序运用了关于图这种数据结构。
ADT Graph{
数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。
数据关系R：
R={VR}
VR={<v,w>|v,w∈V且P(v,w),<v,w>表示从v到w的弧。
谓词P(v,w)定义了弧<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中增添弧<v,w>，若G是无向的则还增加对称弧
<w,v>。
DeleteArc(&G,v,w);
初始条件：图G存在，v和w是G中两个顶点。
操作结果：在G中删除弧<v,w>，若G是无向的，则还删除对称
弧<w,v>。
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);

主程序的流程以及各程序模块之间的调用关系
退出
显示交通系统
PrintGraph
用户咨询
UserDemand
管理员管理
Administer
主函数main（）

返回上一级菜单
列车车次编辑
Administer
飞机航班编辑Administer
城市编辑
cityedit
管理员管理
Administer

初始化交通系统initgraph

返回上一级菜单
最少中转次数
TransferDispose
最少旅行时间
TimeDispose
用户咨询
UserDemand

最少旅行费用ExpenditureDispose
UserDemand

显示城市
显示飞机航班

显示列车车次

返回上一级菜单
显示交通系统
PrintGraph

文档
键盘
初始化交通系统initgraph

删除城市
新增城市
城市编辑
cityedit

删除航班
新增航班
飞机航班编辑
planeedit

删除车次
新增车次
火车列次编辑
trainedit

三．详细设计
1.主程序伪代码
int main()
{
界面初始化；
输入操作命令；
While（“命令” ！= “退出”）
{
接受命令（用户输入要实现功能）；
进入各个处理命令函数；
}
}
2. 函数和过程的调用关系图
DeleteQueue
EnterQueue
InitQueue
MinTime
TimeTreeDispose
EnterplaneArc
DeleteplaneArc
EntertrainArc
DeletetrainArc
TransferDispose
TimeDispose
MinExpenditure
ExpenditureDispose
createplanefile
createtrainfile
CreateGraph
initgraph
cityedit
Administer
PrintGraph
EnterVertex
trainedit
DeleteVertex
createcityfile
flightedit

UserDemand

Main()

InitQueue

EnterQueue

DeleteQueue

CreateTimeTree
CopyTimeTree
TimeTreeDispose

VisitTimeTree

DestoryTimeTree

四．调试分析：
⑴ 调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析：
在调试的过程中碰到了一下问题：
a. 引用形参应用不当；
b. 文件操作中遇到读入错误或找不到文件；
解决方案：
a. 对引用形参了解的不是很透彻，导致错误，通过查阅相关书籍如《C++ Primer》和请教编程能力较高的人，最终解决问题。
b. 通过参考谭浩强编著的《C程序设计》中的文件操作，文件格式和相关文件路径的设置，最终解决问题。
⑵ 算法的时空分析（包括基本操作和其他算法的时间复杂度和空间复杂度的分析）和改进设想：
基本操作
时间复杂度
空间复杂度
void Administer(ALGraph *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,int j,LinkQueue *Q,infolist (*arcs)[MAX_VERTEX_NUM])
O(n)
O(n)
void createtrainfile()
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 EnterQueue(LinkQueue *Q,int x)
O(1)
O(1)
void EntertrainArc(ALGraph *G)
O(1)
O(1)
void EnterVertex(ALGraph *G)
O(n)
O(n)
void ExpenditureDispose(int k,infolist (*arcs)[MAX_VERTEX_NUM],ALGraph G,int v0,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 InitQueue(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 TimeDispose(int k,infolist (*arcs)[MAX_VERTEX_NUM],ALGraph G,int v0,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,int v0,int v1)
O(n)
O(n)
void UserDemand(ALGraph G)
O(1)
O(1)
void VisitTimeTree(TimeTree p)
O(n)
O(n)
⑶ 经验和体会：
通过本次课程设计，我学到了一种程序设计方法，就是结构化程序设计方法，在程序设计过程中，我尝试按如下方法进行结构化程序设计：
(1)自顶向下；(2)逐步细化；(3)模块化设计(4)结构化编码。这种设计方法的过程是将问题求解由抽象逐步具体化的过程，而且，用这种方法便于验证算法的正确性。
本次课程设计所使用的是较为复杂的抽象数据类型——图，而且在弧的基础上增加了许多信息，如添加了时间，费用等等，这无疑给编程加大了难度，同时也是相当的具有挑战性。
在编程的过程中，我用到了全局数组，我将数组放在工程的头文件里面，编译的时候报错，说是多重定义。最终放弃了创建工程，而选择了单个文件进行编译和运行，结果顺利通过。
同时，在文件操作方面我也曾遇到问题，就是在程序对文件进行读取的时候报错，无法读取文件，最后查询有关C的工具书，原来是文件路径问题，借助工具书最终解决了文件操作方面的问题。
总之，这次课程设计是对这一个学期以来对数据结构学习成果的一个验证，同时也是理论与实践很好的结合，既对学过的数据结构进行了巩固，也对我的编程能力奠定了坚实的基础。
五．用户使用说明：
1) 打开并运行程序，按任意键进入操作主界面，按提示进行相关操作；
2) 按“1”进入管理员界面，按“2”进入用户咨询界面，按“3”显示交通系统，按“4”则退出。
3) 进入管理员界面可键入“1”初始化交通系统，并选择文档初始化方式(如果是第一次使用该系统建议使用文档初始化交通系统，免得自己进行繁冗的初始化操作)。其余可按提示进行相关操作，不难掌握。
4) 进入用户咨询界面，可根据用户需要进行相关的选择，或是选择“1”(最少旅行费用)；或是选择“2”(最少旅行时间)，又或者是选择“3”(最少旅行中转次数)等。
5) 进入显示交通系统界面，根据用户选择则可显示城市、飞机航班、列车车次等信息。或者返回上一级菜单。

六．附录——源程序
#define MAX_VERTEX_NUM 18
#define NULL 0
#define MAX_ARC_SIZE 100
#define MAX_ROUTE_NUM 5
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<conio.h>
#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
{
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];
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);

int main()
{ALGraph G;
int i;

printf("\n\n\n\n\n\n\n********************************************************************************\n");
printf("********************************************************************************\n");
printf("*~*~*~*~*~ 学院：信息科学与技术学院 ~*~*~*~*~*\n");
printf("*~*~*~*~*~ 专业：通信工程 ~*~*~*~*~*\n");
printf("*~*~*~*~*~ 姓名： ~*~*~*~*~*\n");
printf("*~*~*~*~*~ 学号：0 ~*~*~*~*~*\n");
printf("********************************************************************************\n");
printf("********************************************************************************\n")