课程设计模板--交通咨询
《数据结构》课程设计报告
一．实习目的
通过实习，了解并初步掌握设计、实现较大系统的完整过程，包括系统分析、
编码设计、系统集成、以及调试分析，熟练掌握数据结构的选择、设计、实现以及
操作方法，为进一步的应用开发打好基础。
二．问题描述
设计、实现一个全国大城市间的交通咨询程序，为旅客提供三种最优决策方案：（1）
时间最短（2）费用最小（3）中转次数最少。
三．需求分析
该程序所做的工作的是模拟全国交通咨询，为旅客提供三种最优决策的交通咨询。此
程序规定：
（1） 在程序中输入城市名称时，需输入 10 个字母以内的字母串；输入列车或飞
机编号时需输入一个整型数据；输入列车或飞机的费用时需输入一个实型数
据；输入列车或飞机开始时间和到达时间时均需输入两个整型数据（以 hh：
mm 的形式）；在选择功能时，应输入与所选功能对应的一个整型数据。
（2） 程序的输出信息主要是：最快需要多少时间才能到达，或最少需要多少旅费
才能到达，或最少需要多少次中转到达，并详细说明依次于何时乘坐哪一趟
列车或哪一次班机到何地。
（3） 程序的功能包括：提供对城市信息的编辑，提供列车时刻表和飞机航班表的
编辑，提供三种最优决策：最快到达、最省钱到达、最少中转次数到达。
四．概要设计
� 系统用到的抽象数据类型定义：
1．ADT Graph{
数据对象 V：一个集合，该集合中的所有元素具有相同的特性
数据关系 R：R={VR}
VR={<x,y>|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)；
2
（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)：初始化队列
3
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++)
4
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);
5
{
开辟一个弧结点；
将数组 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;
