全国交通咨询模拟数据结构优秀课程设计.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中子结点到V0dist值（其值为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");
printf("请按任何键以继续……");
getchar();
system("cls");
printf("\n\n\n\n\n\n\n 请选择程序功效:\n");
printf(" *********************************