数据结构课程设计全国交通咨询系统.doc

太原工业学院
计算机工程系

数据结构课程设计

设计题目：全国交通网络咨询系统

1

班 级： 计算机科学与技术
学 号： 132054103
姓 名： 陈敏
指导教师： 刘海静

年 月 日

目录
一、 课程设计题目…………………………………………………1
二、 需求分析………………………………………………………1
三、 测试数据………………………………………………………2
四、 概要设计………………………………………………………2
五、 调用关系图……………………………………………………3
六、 程序代码………………………………………………………3
七、 测试结果………………………………………………………14
八、 心得体会及总结………………………………………………14

数据结构课程设计
一、课程设计题目
全国交通网络咨询系统
二、 需求分析
1、实现功能
对城市信息(城市名、城市间的里程)进行编辑：具备添加、修改、删除功能；
对城市间的交通工具：火车。对列车时刻表进行编辑：里程、和列车班次的添加、修改、删除；
提供两种最优决策：最快到达或最省钱到达。全程只考虑一种交通工具，可以不考虑回程；
咨询以用户和计算机对话方式进行，要注意人机交互的屏幕界面。由用户选择最优决策原则和交通工具，输入起始站、终点站、出发时间，输出信息：最快需要多长时间才能到达及旅费，或者最少需要多少旅费才能到达及时间，并详细说明依次于何时何地乘坐哪一趟列车何时到达何地。
2、 设计思路
（1) 数据存储。城市信息(城市名、代码)、交通信息(城市间的里程、各航班和列车时刻)存储于磁盘文件。在实验中本想用文本储存数据，但操作不熟悉，而是改用图的邻接矩阵储存原始信息，而后用数组进行添加删改
(2) 数据的逻辑结构。根据设计任务的描述，其城市之间的旅游交通问题是典型的图结构，可看作为无向图，图的顶点是城市，边是城市之间所耗费的时间（要包括中转站的时间）或旅费。
(3) 数据的存储结构。采用邻接表和邻接矩阵都可作为数据的存储结构，这里建议采用邻接矩阵作为数据的存储结构。
(4) 用不同的功能模块对城市信息和交通信息进行编辑。添加、修改、删除功能可用菜单方式或命令提示方式。只要能方便的对城市信息和交通信息进行管理即可，但要注意人机界面，具体实现由学生自行设计，也可参考有关程序(届时在网上提供)。这些工作有不小的工作量。
(5) 最优决策功能模块
① 读入城市信息和交通信息，用邻接表生成含权网络，表头数组中的元素存放城市名及对方城市到达该元素所代表城市的所有信息；表头数组中的元素所对应的单链表存放与该元素所代表的城市有交通联系的城市(代码、里程、列车车次)。
② 根据具体最优决策的要求，用floyd算法求出出发城市到其它各城市的最优值(最短时间或最小的费用)，搜索过程中所经过城市的局部最优信息都保存在邻接表的表头数组中。其目的城市所代表的元素中就保存了所需的最优决策结果。其相应的初始值可为∞，并在表头数组对应的城市元素中保存响应的信息。
③ 主程序可以有系统界面、菜单；也可用命令提示方式；选择功能模块执行，要求在程序运行过程中可以反复操作。

三、测试数据：
704
651
349
1579
1385
2368
812
511
2553
北京
徐州
西安
成都
郑州
广州
上海

四、概要设计
本程序运用了关于图这种数据结构。

它的抽象数据类型定义如下：
typedef struct unDiGraph
{
int numVerts; //结点
costAdj cost; //邻接矩阵
}unDiGraph,*UNG;
基本操作：
unDiGraph* CreateCostG()
操作结果：构造带权(费用)图。
unDiGraph* CreateTimeG()
操作结果：构造带权（时间）图。
构造飞机带权(费用)图。
PathMat *Floyed(unDiGraph *D)
操作结果：Floyed函数 求任意两点的最短路径。

五、调用关系图
unDiGraph（图）

Floyed函数 求任意两点的最短路径

CreateTimeG（构造带权时间）
CreateCostG（构造带权 费用）

六、 程序代码
#include <windows.h>
#include <stdio.h>
#include <crtdbg.h>
#include <string.h>
#include<iostream.h>
#include <malloc.h>
#define INF 10000 //定义一个最大数定为无穷值
#define MAX 7
static int cnumber=7;
static int k=0;
static int v=0,z=0;//定义静态变量
typedef struct zhu//定义结构体zhu
{
int ccost;//定义结构变量
int ctime;
}zhu;
zhu m[20],x[20],n[20];//定义数组为struct zhu 类型数组，且三个数组分别储存添加后的数据，且表示花费m，起点n，和终点x
typedef int costAdj[MAX+1][MAX+1];//定义图的邻接矩阵，并从1开始
int Path[MAX+1][MAX+1];//路程矩阵，表示经过存放的点k
typedef struct unDiGraph
{
int numV;//结点
costAdj cost;//邻接矩阵
}unDiGraph,*UNG;
typedef struct cedit
{
char a[10];
}cedit;
cedit add[10];
costAdj B,L;
//功能一 输出相应的城市信息
int pr(int i,int j)//pr函数表输出功能
{
int h=0;
if (j==0)
{
h=i;
}
else if (j==1)
{
cin>>add[i].a;
}
switch (h){
case(0) : cout<<"";
break;
case(1) : cout<<"成都 ";
break;
case(2) : cout<<"广州 ";
break;
case(3) : cout<<"上海 ";
break;
case(4) : cout<<"徐州 ";
break;
case(5) : cout<<"郑州 ";
break;
case(6) : cout<<"西安 ";
break;
case(7) : cout<<"北京 ";
break;
}
return 1;
}
void pri()//声明pri函数，即利用pr函数输出代码为i的城市信息
{
int i;
cout<<"城市以及其代码"<<endl;
cout<<"**************************************"<<endl;
for(i=1;i<=cnumber;i++)
{
cout<<i<<".";
pr(i,0);
}
cout<<"****************************************"<<endl;
}
//构造CostG图，表示其费用
unDiGraph *CreateCostG(int o)//火车的花费的存贮和编辑功能
{
unDiGraph *G;
int i;
int j;//定义的 i,j做循环变量
int a=0,b=0,f=1,h=1;//f变量初始为1， h初始值为1，a=0,b=0临时表示开始城市代码以及目的城市代码

if(!(G=(unDiGraph *)malloc(sizeof(unDiGraph)))) //为G图分配存储空间。
{
return(NULL);
}
for(i=1;i<=cnumber;i++)
{
for(j=1;j<=cnumber;j++)
{
G->cost[i][j]=INF;//初始化矩阵cost每一项，使其无穷大
}
}
G->numV=cnumber;
G->cost[1][6]=G->cost[6][1]=90;
G->cost[1][2]=G->cost[2][1]=84;
G->cost[2][3]=G->cost[3][2]=51;
G->cost[2][5]=G->cost[5][2]=67;
G->cost[3][4]=G->cost[4][3]=53;
G->cost[4][5]=G->cost[5][4]=40;
G->cost[4][7]=G->cost[7][4]=88;
G->cost[5][6]=G->cost[6][5]=90;
G->cost[5][7]=G->cost[7][5]=67;
G->cost[6][7]=G->cost[7][6]=60;
if (o)
{
while(h==1)//h初始值为1
{
v=v+1;//V为全局静态变量，初始值为0 ,v表示编辑的火车花费的组数，三个编辑数组中的存放代码
pri();
cout<<"火车花费编辑"<<endl;
cout<<"请输入开始城市的代码"<<endl;
cin>>a;
cout<<"请输入目的城市的代码"<<endl;
cin>>b;
cout<<"请输入你的两地花费"<<endl;
cin>>m[v].ccost;
n[v].ccost=a;
x[v].ccost=b;
cout<<"请选择"<<endl;
cout<<"*********************************************************"<<endl;
cout<<"1：继续更改城市费用"<<endl;
cout<<"0:返回上一级菜单"<<endl;
cout<<"*********************************************************"<<endl;
cin>>h;
switch(h) {
case 1:
h=1;
break;
case 0:
h=0;
break;
default:{
cout<<"选择出错"<<endl;
}
}
}

}
f=v+1;//初始定义变量f为1,全局变量v为0，即1=0+1
while (v++) //v++代表的意思
{
G->cost[n[v].ccost][x[v].ccost]=m[v].ccost;
}
v=f;
return(G);
}
//构造TimeG图，表示其花费时间
unDiGraph *CreateTimeG(int o)//火车的时间的存贮和编辑功能
{
unDiGraph *G;
int i,j;//循环变量
int a=0,b=0,f,h=1;//a,b 表增加城市的代码
if(!(G=(unDiGraph *)malloc(sizeof(unDiGraph)))) //为G分配存储空间。
{
return(NULL);
}
for(i=1;i<=cnumber+1;i++)
{
for(j=1;j<=cnumber+1;j++)
{
G->cost[i][j]=INF;//初始化使G->cost[i][j]为无穷。
}
}
G->numV=cnumber;
G->cost[1][6]=G->cost[6][1]=9;
G->cost[1][2]=G->cost[2][1]=8;
G->cost[2][3]=G->cost[3][2]=5;
G->cost[2][5]=G->cost[5][2]=3;
G->cost[3][4]=G->cost[4][3]=5;
G->cost[4][5]=G->cost[5][4]=4;
G->cost[4][7]=G->cost[7][5]=6;
G->cost[5][6]=G->cost[6][5]=9;
G->cost[5][7]=G->cost[7][5]=6;
G->cost[6][7]=G->cost[7][6]=6;
if (o)
{
while(h==1)
{
z=z+1;//全局静态变量，初始值为0.即1=0+1
pri();
cout<<"火车时间编辑"<<endl;
cout<<"请输入开始城市的代码"<<endl;
cin>>a;
cout<<"请输入结尾城市的代码"<<endl;
cin>>b;
cout<<"请输入你的两地时间"<<endl;
cin>>m[z].ctime;
n[z].ctime=a;
x[z].ctime=b;
cout<<"请选择"<<endl;
cout<<"*********************************************************"<<endl;
cout<<"1：继续更改城市时间"<<endl;
cout<<"0:返回上一级菜单"<<endl;
cout<<"*********************************************************"<<endl;
cin>>h;
switch(h) {
case 1:
h=1;
break;
case 0:
h=0;
break;
default:{
cout<<"选择出错"<<endl;
}
}
}
}
f=z+1;//全局静态变量z,初始值为0
while (z++)
{
G->cost[n[z].ctime][x[z].ctime]=m[z].ctime;
}
z=f;
return(G);
}
//Floyed函数 求任意两点的最短路径：
void Floyed(unDiGraph *D,unDiGraph *M)//图D M
{
int i,j,k,n;//i,j为循环变量,k表中间节点的变量
costAdj A,C;//A C为图，临时表示两种最佳路线组成的矩阵，定义costAdj B L
n=cnumber;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
A[i][j]=D->cost[i][j];//初始化矩阵A,C。
C[i][j]=M->cost[i][j];
Path[i][j]=-1; //初始化权矩阵p
}
}
for(k=1;k<=n;k++) //k为逐步加入的中间结点
{
for(i=1;i<=n;i++) //i代表矩阵A中行号
{
for(j=1;j<=n;j++)
{
if(A[i][k]+A[k][j]<A[i][j])
{
A[i][j]=A[i][k]+A[k][j];
C[i][j]=C[i][k]+C[k][j];
Path[i][j]=k;//若i经过k到j比i到j小，则选择经过K个中间点之后，i,j两点的最佳路径。
B[i][j]=A[i][j];//构造A C 两个任意节点上的最优路径所建造的矩阵，并分别赋给B L代表时间与花费
L[i][j]=C[i][j];
}
else
{
B[i][j]=A[i][j];
L[i][j]=C[i][j];
}
}
}
}//end for循环
cout<<"\n最短路径为: "<<endl;
}///end-Floyed
//为了求从i到j的最短路径，只需要调用如下的过程：
void prn_pass(int i,int j)
{
if(Path[i][j]!=-1)
{
prn_pass(i,Path[i][j]);//输出最短路径经过的所有点个数k
pr(Path[i][j],0);
}
}
//求最少时间路径。
void time()
{
int Bcity,Ecity;//起始成市号码和终点城市号码
int l,h=1;//定义变量l h
do {
pri();//输出城市列表及相应代码。
cout<<"请输入起始城市和目的城市的代码，中间以空格隔开"<<endl;
cin>>Bcity;
cin>>Ecity;//输入起始城市和终点城市的代码。
if (!((0<Bcity&&Bcity<cnumber+1)&&(0<Ecity&&Ecity<cnumber+1)&&Bcity!=Ecity))
{
cout<<"\n出错啦!!! 输入城市号码请在1-7之间，且两城市代码不能相等!!"<<endl;
}
Floyed(CreateTimeG(0),CreateCostG(0));//调用Floyed函数。
pr(Bcity,0);// 显示起始城市。
prn_pass(Bcity,Ecity);//调用prn_pass函数，显示最短路径经过的城市。
pr(Ecity,0);//显示终点城市。
if (B[Bcity][Ecity]>8000||L[Bcity][Ecity]>8000)
{
cout<<"两地间还没有线路通过"<<endl;
}
else
{
cout<<"火车花的时间是"<<B[Bcity][Ecity]<<"小时"<<endl;
}
cout<<" 输入0.返回主菜单 "<<endl;
scanf("%d",&l); //
h=l;
} while(h==1);
}
//求最少花费路径。
void money()
{
int Bcity,Ecity;//起始成市号码和终点城市号码
char l,h=1;
do {
pri();//输出城市列表及相应代码。
cout<<"请输入起始城市和目的城市的代码，中间以空格隔开"<<endl;
cin>>Bcity;
cin>>Ecity;//输入起始城市和终点城市的代码。
if (!((0<Bcity&&Bcity<cnumber+1)&&(0<Ecity&&Ecity<cnumber+1)&&Bcity!=Ecity))
{
cout<<"\n出错啦!!! 输入城市号码请在1-7之间，且两城市代码不能相等!!"<<endl; //输入出错
}
Floyed(CreateCostG(0),CreateTimeG(0));//调用Floyed函数。
pr(Bcity,0);//显示起始城市。
prn_pass(Bcity,Ecity);//调用prn_pass函数，显示最短路径经过的城市。
pr(Ecity,0);//显示终点城市。
if (L[Bcity][Ecity]>8000||B[Bcity][Ecity]>8000)
{
cout<<"两地间还没有线路通过"<<endl;
}
else
{
cout<<"火车花的钱是"<<B[Bcity][Ecity]<<"元"<<endl;
}
cout<<" 输入0.返回主菜单"<<endl;
scanf("%d",&l); //
h=l;
} while(h==1);
}
void add_city()//对城市的增加
{
static int i=1;
int j;
cout<<"请输入你要增加的城市的个数"<<endl;
cin>>j;
for (i=1;i<=j;i++)
{
cout<<"请输入你要增加的城市名"<<endl;
pr(i,1);//将添加的内容放置于add数组中，并以i为代码
cnumber=cnumber+1;
}
cout<<"城市增加完毕"<<endl;
}
void chose()//选择最少时间或最小花费
{
int h;
cout<<"1:最小花费"<<endl;
cout<<"2:最小时间"<<endl;
cout<<"请选择："<<endl;
cin>>h;
if (h==1) {
money();
}
else
{
time();
}
}
void edit_line()//增加编辑火车的费用
{
CreateCostG(1);
}
void edit_hour()//增加编辑火车的时间
{
CreateTimeG(1);
}
void administrator()//管理员功能
{
int h=1;
while (h) {
cout<<"************************************************************"<<endl;
cout<<"1:增加城市"<<endl;
cout<<"2:添加或编辑火车费用"<<endl;
cout<<"3:添加或编辑火车时间"<<endl;
cout<<"0:返回主菜单"<<endl;
cout<<"************************************************************"<<endl;
cout<<"请选择"<<endl;
cin>>h;
switch(h) {
case 1 :add_city();
break;
case 2: edit_line();
break;
case 3:edit_hour();
break;
case 0:
h=0;
break;
default:
{
cout<<"选择出错！"<<endl;
}
}
}
}
//主函数
void main()
{
char n;
int x;
while(x!=0)
{
cout<<endl;
cout<<"输入你希望查询的种类代码，你将得到最佳方案!"<<endl;
cout<<" ******************全国交通网络模拟系统******************"<<endl;
cout<<" * 主菜单 *"<<endl;
cout<<" * 1.查看城市 *"<<endl;
cout<<" * 2.选择最短时间路线 *"<<endl;
cout<<" * 3.选择最节约费用路线 *"<<endl;
cout<<" * 4.管理员程序 *"<<endl;
cout<<" * 0.退出程序 *"<<endl;
cout<<" ********************************************************"<<endl;
cout<<endl<<endl<<endl<<endl<<endl;
cout<<"请选择（0-4）..... ";//输入选择菜单。
cin>>n ;

switch(n)//当输入为0-4，则用switch语句进行选择。
{
case '1': pri();//查看城市
break;
case '2' : time(); //当输入为2，则调用time函数。
break;
case '3' : money();//当输入为3，则调用money函数。
break;
case '4':administrator();
break;
case '0'://当输入为0。则确认退出。
x=0;
break;
default :
{
cout<<endl<<"出错啦!!!请在0-4之间选择!!"<<endl<<endl; //输入出错
}
}//end-Switch
}
}
七、测试结果：
开始界面

1、 查看程序

2、 最快到达咨询（举例）

当输入出错时，系统会提示出错信息，并返回输入窗口让用户重新输入。

八、心得体会及总结
通过这次课程设计，我在本次实验中，对于图和最短路径的内容作了进一步加深，但是也发现了自己在“栈”的内容上不熟练，所以讲原本的最优路径的临时存放由原先设想的栈改换成加变量k进行每个节点的循环来找最优路径。本次实验之后，应当利用更多的时间来实践课本内容，以求能熟练上手。
13