数据结构课程设计《全国交通系统参考报告》

课程设计模板--交通咨询

《数据结构》课程设计报告

题目：全国交通咨询日期：2003.12.6

年级：2001班级：3班

姓名：陈勇学号：200131832

一．实习目的

通过实习，了解并初步掌握设计、实现较大系统的完整过程，包括系统分析、编码设计、系统集成、以及调试分析，熟练掌握数据结构的选择、设计、实现以及操作方法，为进一步的应用开发打好基础。

二．问题描述

设计、实现一个全国大城市间的交通咨询程序，为旅客提供三种最优决策方案：（1）时间最短（2）费用最小（3）中转次数最少。

三．需求分析

该程序所做的工作的是模拟全国交通咨询，为旅客提供三种最优决策的交通咨询。此程序规定：

（1）在程序中输入城市名称时，需输入10个字母以内的字母串；输入列车或飞机编号时需输入一个整型数据；输入列车或飞机的费用时需输入一个实型数

据；输入列车或飞机开始时间和到达时间时均需输入两个整型数据（以hh：

mm的形式）；在选择功能时，应输入与所选功能对应的一个整型数据。

（2）程序的输出信息主要是：最快需要多少时间才能到达，或最少需要多少旅费才能到达，或最少需要多少次中转到达，并详细说明依次于何时乘坐哪一趟

列车或哪一次班机到何地。

（3）程序的功能包括：提供对城市信息的编辑，提供列车时刻表和飞机航班表的编辑，提供三种最优决策：最快到达、最省钱到达、最少中转次数到达。

四．概要设计

系统用到的抽象数据类型定义：

1．ADT Graph{

数据对象V：一个集合，该集合中的所有元素具有相同的特性

数据关系R：R={VR}

VR={|P(x,y)^(x,y属于V)}

基本操作：

（1）initgraph(&G)；

（2）CreateGraph(&G)；

（3）EnterVertex(&G)；

（4）DeleteVertex(&G)；

（5）EnterplaneArc(&G)；

（6）DeleteplanArc(&G)；

（7）EntertrainArc(&G)；

（8）DeletetrainArc(&G)；

}ADT Graph

2．ADT LinkQueue{

数据元素：可以是任意类型的数据，但必须属于同一个数据对象

关系：队列中数据元素之间是线性关系。

基本操作：

（1）InitQueue(&Q)；

（2）IsEmpty(&Q)；

（3）EnterQueue(&Q,x)；

（4）DeleteQueue(&Q,&y)；

}ADT LinkQueue

3．ADT TimeTree{

数据对象D：一个集合，该集合中的所有元素具有相同的特性

数据关系R：若D为空，则为空树。若D中仅含有一个数据元素，则R为空集，

否则R={H}，H为如下二元关系：

（1）在D中存在唯一的称为根的数据元素root，它在关系

H中没有前驱

（2）除root以外，D中每个结点在关系H下有且仅有一个

前驱。

基本操作：

（1）CreateTimeTree(p,i,j,&Q,infolist arcs)；

（2）CopyTimeTree(p,q)；

（3）VisitTimeTree(p)；

}ADT TimeTree

系统中子程序及功能要求：

1．Administer(ALGraph *G)：提供管理员管理城市交通系统的界面，通过该子程

序可调用其他管理交通系统的子程序。

2．initgraph(ALGraph *G)：初始化交通系统的子程序

3．createcityfile( )：创建城市文件的子程序

4．createplanefile( )：创建航班文件的子程序

5．createtrainfile( )：创建列车时刻表文件的子程序

6．LocateVertex(ALGraph *G,char *v)：提供城市名在城市交通系统中相应的编

号

7．CreateGraph(ALGraph *G)：创建城市交通系统

8．cityedit(ALGraph *G)：提供城市编辑功能

9．EnterVertex(ALGraph *G)：提供在城市交通系统中加入城市的功能

10．DeleteVertex(ALGraph *G)：提供在城市交通系统中删除城市的功

能

11．flightedit(ALGraph *G)：提供航班编辑功能

12．EnterplaneArc(ALGraph *G)：提供在城市交通系统中加入航班的功

能

13．DeleteplaneArc(ALGraph *G)：提供在城市交通系统中删除航班的

功能

14：trainedit(ALGraph *G):提供列车车次的编辑功能

15．EntertrainArc(ALGraph *G)：提供在城市交通系统中加入列车车次

的功能

16．DeletetrainArc(ALGraph *G)：提供在城市交通系统中删除列车车

次的功能

17．UserDemand(ALGraph G)：提供用户咨询的界面

18．DemandDispose(int n,ALGraph G)：通过该子程序调用其他咨询子程序

19．InitQueue(LinkQueue *Q)：初始化队列

20．EnterQueue(LinkQueue *Q,int x)：入队操作

21．DeleteQueue(LinkQueue *Q,int *x)：出队操作

22．IsEmpty(LinkQueue *Q)：队列判空操作

23．TransferDispose(int k,infolist(*arcs)[MAX_VERTEX_NUM],

(*arcs)[MAX_VERTEX_NUM] ,ALGraph G,ALGraph G,int v0,int v1)

：提供最少中转次数决策的功能

24．MinExpenditure(infolist arcs,float *expenditure,

float *route)：提供两个城市之间最少费用的功能

25．ExpenditureDispose(int k, infolist (*arcs)[MAX_VERTEX_NUM] ,ALGraph G, int v0,int v1,float *D,int *final)

：提供最少费用决策的功能

26．MinTime(infolist arcs,float *time,float *route)

：提供两个城市之间最短时间的功能

27．TimeTreeDispose(Node *head,infolist

(*arcs)[MAX_VERTEX_NUM])

：提供两个之间相隔一个以上城市的城市间的最短时间的功能

28．CreateTimeTree(TimeTree p,int i,int j,

LinkQueue *Q,infolist(*arcs)[MAX_VERTEX_NUM])：创建时间树

29．CopyTimeTree(TimeTree p,TimeTree q)：复制时间树

30．VisitTimeTree(TimeTree p)：访问时间树

31．DestoryTimeTree(TimeTree p)：销毁时间树

32．TimeDispose(int k,infolist (*arcs)[MAX_VERTEX_NUM],

ALGraphG,int v0,int v1,float *D,int *final)

：提供最少时间决策的功能

33：PrintGraph(ALGraph *G)：显示整个城市交通系统

各程序模块之间的调用关系（子程序编号见上）：

主函数可调用子程序1，17，33

子程序1可调用子程序2，8，11，14

子程序2可调用子程序3，4，5，7

子程序7，12，13，15，16可调用子程序6

子程序8可调用子程序9，10

子程序11可调用子程序12，13

子程序14可调用子程序15，16

子程序17可调用子程序18

子程序18可调用子程序23，25，32

子程序23可调用子程序19，29，21，22

子程序25可调用子程序24

子程序32可调用子程序26，27

子程序27可调用子程序28，30，31

子程序28可调用子程序29

五．详细设计

创建交通图算法的伪码描述如下：

int LocateVertex(ALGaph *G,char *v)/*找出城市名在图中对应结

点位置*/

{

for(k=0;k<图G中的结点个数G->vexnum;k++)

if(第k个结点中的城市名与传过来的城市名相同)

{

j=k;/*记录位置*/

break;

}

}

返回k 的数值；

}

int CreatGraph(ALGraph *G)

{

if(打开城市文件，文件指针返回值为空）

{

输出错误文件信息；

程序返回值为0；

}

while(文件不为空）

{

将文件指针所指的字符串读到城市名数组city[i]中；

i++;

}

关闭文件；

j=0;

while(j<城市个数）

{

将city[i] 中的内容复制到图的结构体的结点数组中;

图的结构体其他项负初值;

j++;

}

G->vexnum=i;

打开航班信息文件"plane.txt";

将文件中的内容以块为单位读到缓冲区数组a中；

关闭文件；]

a的计数变量k=0;

弧的计数变量arc_num=0;

while(k<信息个数)

{

调用函数LocateVertex(G,a[k].vt)得到起始结点的位置i；

调用函数LocateVertex(G,a[k].vt)得到起始结点的位置j；

q=G->vertices[i].planfirstarc;

m=0;

while(q!=NULL)

{

if( 弧q中的邻接顶点与j相等）

{

将数组a[i] 中的内容都复制到弧q中；

m=1;

break;

}

q=q->nextarc;

if(m=0);

{

开辟一个弧结点；

将数组a[i]中的内容都复制到新的弧结点中；

将弧结点连接到适当的位置中去；

arc_num++;

}

k++;

}

G->planarcnum=arc_num;

打开列车信息文件"plane.txt";

将文件中的内容以块为单位读到缓冲区数组a中；

关闭文件；]

a的计数变量k=0;

弧的计数变量arc_num=0;

while(k<信息个数)

{

调用函数LocateVertex(G,a[k].vt)得到起始结点的位置i；

调用函数LocateVertex(G,a[k].vt)得到起始结点的位置j；

q=G->vertices[i].trainfirstarc;

m=0;

while(q!=NULL)

{

if( 弧q中的邻接顶点与j相等）

{

将数组a[i] 中的内容都复制到弧q中；

m=1;

break;

}

q=q->nextarc;

if(m=0);

{

开辟一个弧结点；

将数组a[i]中的内容都复制到新的弧结点中；

将弧结点连接到适当的位置中去；

arc_num++;

}

k++;

}

G->trainarcnum=arc_num;

返回；

}

?创建航班算法的伪码描述如下：

creatplanefile()

{while(flag) /*flag为标志位,初值为1*/

{ 提示“输入航班信息”；

输入航班code;

输入航班的出发城市vt;

输入航班的到达城市vh;

输入机票价格money;

输入航班的出发时间bt;

输入航班的到达时间at;

a.[count].co=code; /* a 为程序头部定义的结构体*/

strcpy(a.[count].vt,vt);

strcpy(a.[count].vh,vh);

a.[count].bt=bt;

a.[count].at=at;

a.[count].mo=money;

计数值count+1;

提示“是否要继续输入航班信息：”；

scanf(“%d”,&flag);

}

if(航班文件不能以读写形式打开)

提示“无法打开文件”；

将计数值count写入航班车文件；

for(i=0;i

if(无法将a[i]写入航班文件)

提示“文件无法写入”；

关闭航班文件；

}

?删除城市结点算法的伪码描述如下：

DeleteVertex(ALGraph *G) /* G是程序头部定义的结构体*/

{

提示“输入删除城市名”；

gets(城市名：v);

提示“是否确定要删除（Y/N）“；

c=getchar();

if(c==’Y’||c==’y’)

{n=0; /*0是记数标志，控制循环次数*/

while(n<图G表头接点总个数&&图G的存储城市名与v不同)

/*G表头结点总个数比实际大1*/

记数值n+1;

if(n = =图G表头结点总个数)

提示“无法找到此城市“；

else

{

i=LocateVertex(G,v);

/*利用G函数找到此城市名所处在G中位置*/

删除从此结点出发的所有航班弧；

删除从此结点出发的所有列车弧；

for(j=i;j<图G表头结点总个数-1；j++)

将G第j个结点的信息依前移1位；

将G第j个结点的信息制空；

/*以下是删除所有指向此结点的航班弧*/

for(k=0;k<图G表头记点总个数-1；k++)

{p指向图G中k结点的第一条飞机弧；

while（p！=NULL）

{ if（该弧指向的顶点位置（p->adjvex ）>i）

{将该弧指向顶点位置-1；

q=p；

p指向下一条飞机弧；

}

else if（该弧指向的顶点位置（p->adjvex ）= = i）

{if（p指向图G中k结点的第一条飞机弧）

{ m=p；

将图G中k结点的第二条飞机弧改为第一弧；

p指向下一条飞机弧；

释放（m）；

}

else

{ 将p的下一条弧赋给q的下一条弧；

m=p；

p指向下一条飞机弧；

释放（q）；

}

}

else

{q=p；

p指向下一条飞机弧；

}

}

}

/*以下是删除所有指向此结点的列车弧*/

for(k=0;k<图G表头记点总个数-1；k++)

{p指向图G中k结点的第一条列车弧；

while（p！=NULL）

{ if（该弧指向的顶点位置（p->adjvex ）>i）

{将该弧指向顶点位置-1；

q=p；

p指向下一条列车弧；

}

else if（该弧指向的顶点位置（p->adjvex ）==i）

{if（p指向图G中k结点的第一条列车弧）

{ m=p；

将图G中k结点的第二条列车弧改为第一弧；

p指向下一条列车弧；

释放（m）；

}

else

{ 将p的下一条弧赋给q的下一条弧；

m=p；

p指向下一条列车弧；

释放（q）；

}

}

else

{q=p；

p指向下一条列车弧；

}

}

}

}

图G表头结点总个数-1；

}

else return；

}

?求城市v0，v1之间的最少费用算法的伪码描述如下：

ExpenditureDispose( )

{for(v=0；v<城市个数；v++)

{城市v还未求得最少费用；

*(D+v)=城市v0到v的最少费用；

将城市v的路径设置为空；

if(*(D+v)

将城市v0和v加入到城市v的路径中；

}

城市v0到城市v0的最少费用为0；

城市v0设为已求得最少费用；

for(i=1；i<城市个数；v++)

{m=INFINITY;

for(w=0；w<城市个数；w++)

if(城市w未求得最少费用)

if(*(D+w)

{v=w;

m=*(D+w);

}

if(v等于v1)

{根据城市v的路径输出从城市v0到城市v1所需经过的城市及路线；

输出最少费用*(D+v1)；

返回；

}

else

{将城市v设为已求得最少费用；

for(w=0；

if(城市w未求得最少费用并且从城市v到w有路径)

{求出从城市v到城市w的最少费用及路线；

if(*(D+w)>m+城市v到w的最少费用)

{*(D+w)=m+城市v到w的最少费用；

将城市w的路径改成城市v的路径并在最后加入城市w；

}

}

}

输出没有列车或飞机从城市v0到v1；

}

?最少中转次数算法的伪码描述如下：

求城市v0到城市v1的最少中转次数

TransferDispose( )

{for(v=0；v

{城市v设为未访问；

城市v的路径设为空；

}

将城市v0设为已访问；

将城市v0入队；

while(队列不空)

{队首城市v出队；

w为与城市v相连的第一个城市；

while(w存在)

{if(城市w未访问)

{将城市w设为已访问；

将城市w的路径改为城市v的路径并在最后加入城市w；

if(w等于v1)

{根据城市w的路径输出从城市v0到城市v1所需经过的城市及路线；

返回；

}

将城市w入队；

}

w等于城市v相连的下一个城市；

}

}

输出没有列车或飞机从城市v0到v1；

}

求城市v0，v1之间的最少时间算法的伪码描述如下：

TimeDispose( )

{for(v=0；v<城市个数；v++)

{城市v还未求得最少时间；

*(D+v)=城市v0到v的最少时间；

将城市v的路径设置为空；

if(*(D+v)

将城市v0和v加入到城市v的路径中；

}

城市v0到城市v0的最少时间为0；

城市v0设为已求得最少时间；

for(i=1；i<城市个数；v++)

{m=INFINITY;

for(w=0；w<城市个数；w++)

if(城市w未求得最少时间)

if(*(D+w)

{v=w;

m=*(D+w);

}

if(v等于v1)

{根据城市v的路径输出从城市v0到城市v1所需经过的城市及路线；

输出最少时间v1；

返回；

}

else

{将城市v设为已求得最少时间；

for(w=0；

if(城市w未求得最少时间并且从城市v到w有路径)

{保存城市w原来的路径；

将城市w的路径设为城市v的路径并在最后加入城市w；

利用时间树求出从城市v0城市w的最少时间及路径；

if(*(D+w)>从城市v0到城市w的最少时间)

*(D+w)=从城市v0到城市w的最少时间；

else

将城市w的路径还原；

}

}

}

}

输出没有列车或飞机从城市v0到v1；

}

六．测试分析

按照附录中的测试数据，得出如下测试、分析结果：

1.操作员管理功能.

1>. 当我们从键盘输入有关图的顶点及弧的信息后,用显示图的函数验证,DOS中显示的

图的信息与从键盘输入的信息相同,表明交通系统可以从键盘正确输入信息.

2>. 我们事先建立了有关图的3 个文本文件(包括city.txt,plan.txt,train.txt),在交通系统程

序中,选择从文本文件输入图的信息后,用显示操作验证,表明文本文件的内容可以正确调入图的结构体中,说明交通系统可以从文本文件中读取信息.

3>. 当从键盘或文本文件初始化交通图后,测试增加或删除城市结点,增加或删除航班或

列车弧,以上各功能都正确.

2. 交通咨询功能.

1>. 火车情况.

1.1>.最少费用.

a.两地间无中转且有多辆火车.

北京----→郑州

输出结果为:

旅行路线是:

乘坐NO.27列车车次在13：15 从Beijing 到zhengzhou.

最少旅行费用是78元.

而若选择NO.41 则花费为80 元.

结果正确.

b.两地之间无中转达且只有一辆火车.

西安----→武汉

输出结果为:

旅行路线是:

乘坐NO.218列车车次在1：34从xi’an到wuhan.

最少旅行费用是178.00 元.

结果正确.

c.两地之间有中转.

昆明----→北京

输出结果为:

旅行路线是:

乘坐NO.323列车车次在16.：31从kunming到Guangzhou.

乘坐NO.59列车车次在3：39从Guangzhou 到shanghai.

乘坐NO.41列车车次在0：35从shanghai 到zhengzhou.

乘坐NO.27列车车次在13：42 从zhengzhou 到Beijing.

最少旅行费用是462 元.

而若选择昆明---→武汉---→兰州---→北京则花费为506 元.

若选择昆明---→武汉---→西安---→郑州---→北京则花费为472 元.

结果正确.

1.2>最短时间.

a. 两地间无中转且有多辆火车.

北京----→郑州

输出结果为:

旅行路线是:

乘坐NO.41列车车次在13：15从Beijing 到zhengzhou.

最少旅行时间是7：57.

结果正确.

b.两地之间无中转达且只有一辆火车.

乌鲁木齐----→兰州

输出结果为:

旅行路线是:

乘坐No.371列车车次在0：35从wulumuqi 到lanzhou.

最少旅行时间是10：48.

结果正确.

c.两地之间有中转.

广州----→兰州

输出结果为:

旅行路线是:

乘坐NO.59列车车次在3：39从guangzhou到shanghai.

乘坐NO.41列车车次在0：35从shanghai到zhengzhou.

乘坐NO.41列车车次在9.40从zhengzhou到Beijing.

乘坐NO.134列车车次在19.24从Beijing到lanzhou.

最少旅行时间是54：49.

结果正确.

1.3>.最短周转次数.

a. 两地可直达且有中转.

昆明---→广州

输出结果为:

旅行路线是:

乘坐NO.323列车车次在16：31从kunming到guangzhou.

最少旅行中转次数是0次 .

而若选择昆明---→武汉---→长沙---→兰州则结果为3.

结果正确.

b.两地间有多条中转路径.

昆明---→上海

输出结果为:

旅行路线是:

乘坐NO.323列车车次在16：31从kunming 到guangzhou.

乘坐NO.59列车车次在3：39从guangzhou 到shanghai.

最少旅行总转次数是1次 .

而若选择昆明---→武汉---→西安---→郑州---→上海则结果为4.

结果正确.

2.飞机情况.

2.1>.两地无直达.

兰州---→武汉

输出结果为:

不存在飞机航班从lanzhou到wuhan.

2.2>.两地无直达.

拉萨---→昆明

a.最少费用:

输出结果为:

乘坐NO.173飞机航班在10：20 从lasa 到kunming.

最少旅行费用是830 元.

结果正确.

b.最短时间:

输出结果为:

乘坐NO.173 飞机航班在10：20 从lasa 到kunming.

最少旅行时间是1：25.

结果正确.

c.最短中转次数.

输出结果为:

乘坐NO.173 飞机航班在10：20 从lasa 到kunming.

最少旅行中转次数是0次.

结果正确.

2.3>两地可中转.

广州----→北京

a.最少费用:

输出结果为:

乘坐NO.2323飞机航班在10：15 从Guangzhou 到xi’an.

乘坐NO.210 飞机航班在12：35 从xi’an 到beijing.

最少旅行费用是2250 元.

结果正确.

b.最短时间:

输出结果为:

乘坐NO.2323 飞机航班在10：15 从Guangzhou 到xi’an.

乘坐NO.210 飞机航班在12：35 从xi’an 到beijing.

最少旅行时间是4：00.

结果正确.

c.最短中转次数.

输出结果为:

乘坐NO.2323 飞机航班在10：15 从Guangzhou 到xi’an.

乘坐NO.210 飞机航班在12：35从xi’an 到beijing.

最少旅行中转次数是1次.

结果正确.

3.打印

打印结果正确;

4.退出

能正确退出

七．使用说明

1．运行程序，首先出现主界面。主界面包括四个选项：选项一：管理员管理界面，选择该项可进行城市交通系统的管理，具体使用说明见说明2；选项二：用户咨

询界面，选择该项可进行最少费用、最少时间、最少中转次数的决策咨询，具体

使用见说明7；选项三：显示城市交通系统程序，选择该项可显示城市交通系统

的所有信息，包括城市、航班和列车车次；选项四：退出程序，选择该项将退出

程序。

2．管理员管理界面包括5个选项：选项一：初始化城市交通系统界面，可进行城市交通系统的初始化，具体使用见说明3；选项二：城市编辑界面，可进行城市的

增加和删除，具体使用见说明4；选项三：航班编辑界面，可进行航班的增加和

删除，具体使用见说明5；选项四：列车车次编辑界面，可进行列车车次的增加

和删除，具体使用见说明6；选项五：返回上一级菜单，可返回主界面。

3．初始化城市交通系统界面包括两个选项：选项一：通过键盘初始化城市交通系统，选择该项后程序将给出输入说明，按输入说明用户需逐

步输入城市、航班、列车车次的信息来对城市交通系统初始化。在输入航班和

列车信息时需注意两点：a.所输入的航班和列车的发车时间均在同一天。b.若

发车时间小于到达时间，则说明列车在同一天到达，若发车时间大于到达时间，

则说明列车在次日达到。飞机航班也是如此；选项二：通过文档初始化城市交

通系统，选择该项可用文档进行初始化，但文档必须存在于程序的同一目录下，

且必须包含CITY，PLANE，TRAIN三个文本文档，否则程序将提示出错。

4．城市编辑界面包括两个选项：选项一：增加城市，可在城市交通系统中加入新的城市，若用户输入的是已有的城市名，程序将提示出错；选项二：删除城市，可

在城市交通系统中删除城市，用户必须输入一个已有的城市名，否则程序提示出

错。

5．航班编辑界面包括两个选项：选项一：增加航班，可在两个城市之间新增航班，选择该项后用户需输入新增航班的编号，起始城市，到达

城市及费用、时间等信息；选项二，删除航班，可删除两个城市间的

一条航班，选择该项后用户需输入要删除航班的编号，起始城市，到

达城市的信息，若航班不存在或编号、城市输入有误，程序将提示错

误。

6．列车车次编辑界面包括两个选项：选项一：增加列车车次，可在两个

城市之间新增列车车次，选择该项后用户需输入新增列车的编号，起

始城市，到达城市及费用、时间等信息；选项二，删除列车车次，可

删除两个城市间的一条列车车次，选择该项后用户需输入要删除车次

的编号，起始城市，到达城市的信息，若列车车次不存在或编号、城

市输入有误，程序将提示错误。

7．用户咨询界面包括四个选项：选项一：最少费用咨询；选项二：最少时间咨询；

选项三：最少中转次数咨询；选项三：返回上级菜单，可返回主界面。选择选项

一、二、三都要求用户输入咨询信息，包括起始城市，到达城市和交通工具。输

入完毕后城市提示用户是否确认，若不确认则要求用户重新输入咨询信息，若确

认则给出用户所需的最优决策信息。

八．附录：测试数据

航班时刻表

九．C语言实现