交通咨询系统设计报告

下载可编辑

重庆科技学院

《数据结构》课程设计

报告

学院:_电气与信息工程学院_专业班级:计科2

学生姓名:学号:

设计地点（单位）___计算机基础自主学习中心____

设计题目:________交通咨询系统设计_______

完成日期：2012年7月6日

指导教师评语:_______________________________________

________________________________________________________________________________________________

________________________________________________________________________________________________

.专业.整理.

下载可编辑

____________________

成绩（五级记分制）:________________

指导教师（签字）:________________

重庆科技学院

课程设计任务书

设计题目：交通咨询系统的设计

学生姓名

课程名称

地点

设

人们在出差、旅游出行时，往往关心节省交通费用或节省所需要的时间等问题。

计

内

容

及

要

求

设

计

测试数据要求：

交通图中顶点数不少于16个，边数不少于20，每条边有三个权值（里程、交通

可以用一个图结构来表示交通网络，图中顶点表示城市，边表示城市之间的交通情

况，其权值可代表里程、交通费用或时间。设计一个交通咨询系统，能让旅客咨询从

任一个城市到另一个城市之间的最短路径（里程）、最少交通费用或最少时间等问

题。

该设计的内容主要分两部分：一是建立交通网络图的存储结构；二是实现求两个

城市顶点之间的最短路径算法。

要求表示城市之间的交通关系的边的信息中包括里程、费用、时间三个值。程序

可实现求任两个城市之间的最短里程、最少时间或最少费用的路线。建立图的存储结

构时要求从文本文件中读入顶点和边的信息。

数据结构课程设计专业班级计

计算机基础自主学习中心起止时间2012.6.25-2012.7.6

.专业.整理.

下载可编辑

参

数

费用、时间）。

2012.6.25完成任务的讲解、并接受课程设计任务，选定课程设计的题目

2012.6.26了解任务的算法、并画出算法的程序流程图，对任务的关键技术进行验

证、并确定解决办法

进

2012.6.27-2012.6.29程序设计及编码，上机调试

度

2012.7.02对程序进行调试，设计测试用例进行测试

要

2012.7.03整理课程设计的过程、并进行总结，完善程序功能

求

2012.7.04编写课程设计报告初稿

2012.7.05完善课程设计报告、并准备答辨

2012.7.06提交课程设计报告和程序，进行答辨

参

考

资

料

其

它

1．严蔚敏吴伟民，数据结构，清华大学出版社，2007.3

2．程杰，大话数据结构，清华大学出版社，2011.6

3．（美）StephenPrata,CPrimerPlus中文版（第五版），人民邮电出版社，2005.2

说

明

1.本表应在每次实施前一周由负责教师填写二份，学院审批后交学院教务办备案，一

份由负责教师留用。2.若填写内容较多可另纸附后。3.一题多名学生共用的，在设计

内容、参数、要求等方面应有所区别。

系主任：雷亮指导教师：黄永文/王双明/熊茜/彭军/王成敏

2012年6月20日

摘要

.专业.整理.

下载可编辑

在交通网络非常发达，人们在出差、旅游出行时，往往关心节省交通费用或节省

所需要的时间等问题。对于这样一个人们关心的问题，可以用一个图结构来表示交通

网络，利用计算机建立一个交通咨询系统。图中顶点表示城市，边表示城市之间的交

通情况，其权值可代表里程、交通费用或时间。比如任意一个城市到其他城市的最短

路径，任意两个城市之间的最短路径问题。

本次设计的交通咨询系统主要是运用C语言的数据结构来完成交通图的存储、图

中顶点的单源最短路径和任意一对顶点间的最短路径问题。

关键词：数字结构C语言交通咨询最短路径

.专业.整理.

下载可编辑

目录

1设计内容和要求....................................................................................................................................1

1.1问题描述...............................................................................................................................1

1.2需求分析.................................................................................................................................1

2课程需求分析........................................................................................................................................2

2.1算法思路...............................................................................................................................2

2.2数据结构体...........................................................................................................................2

2.3基本操作...............................................................................................................................4

2.4算法应用...............................................................................................................................4

.专业.整理.

下载可编辑

2.5程序设计流程图..................................................................................................................5

3功能模块详细设计...............................................................................................................................6

3.1测试数据...............................................................................................................................6

3.2程序调试...............................................................................................................................7

4课程总结与体会...............................................................................................................................24

5参考文献...............................................................................................................................................26

6致谢.......................................................................................................................................................27

.专业.整理.

下载可编辑

.专业.整理.

下载可编辑

1设计内容和要求

1.1问题描述：

设计、实现一个全国大城市间的交通咨询程序，为旅客提供三种最优决策方

案：（1）时间最短（2）费用最小（3）里程最少。

1.2需求分析：

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

通咨询。此程序规定：

（1）在程序中输入城市名称时，需输入20个字符以内的字符串；输入费用时需

输入一个实型数据；输入时间时需输入一个整型数据；在选择功能时，应输入与所选

功能对应的一个整型数据。

（2）程序的输出信息主要是：最快需要多少时间才能到达，或最少需要多少

旅费才能到达，或两城市间需要走过的最短路程，并详细说明如何坐车才能最省。

（3）程序的功能包括：提供对城市信息的编辑，对两城市间时间、花费、还有

路程的编辑，提供三种最优决策：最快到达、最省钱到达、最少路程到达。

.专业.整理.

下载可编辑

2课程需求分析

2.1算法思路

(1)数据存储。城市信息、交通信息(城市间的里程、旅费和时间)存储于磁盘文

件。建议把城市信息、交通信息还有城市和交通信息数目分开存于三个文件中，用

fread和fwrite函数操作。

(2)数据的逻辑结构。根据设计任务的描述，其城市之间的旅游交通问题是典型的

图结构，可看作为有向图，图的顶点是城市，边是城市之间所耗费的时间、旅费、里

程。

(3)数据的存储结构。采用邻接矩阵作为数据的存储结构，提高空间的存储效率。

(4)用不同的功能模块对城市信息和交通信息进行编辑，可用菜单方式或命令提示

方式。只要能方便的对城市信息和交通信息进行管理即可。

(6)主程序可以有系统界面、菜单；也可用命令提示方式；选择功能模块执行，

要求在程序运行过程中可以反复操作。

2.2数据结构体

typedefstructlu/*交通信息数据类型*/

{

.专业.整理.

下载可编辑

intdistance;/*城市间里程*/

intcost;/*城市间旅费*/

inttime;/*城市间时间*/

}lu,lujin[max][max];

typedefstructcity/*城市数据类型*/

{

charname[20];/*城市名称*/

}citys[max];

typedefstruct/*网络图的数据类型*/

{

citysclist;/*城市信息*/

lujinarcs;/*边的信息*/

intc_n,l_n;/*边和顶点数目*/

}Graph;

typedefstruct/*最短路径*/

{

charadjvex;

intmincost;/*最少旅费*/

intmindistance;/*最短里程*/

.专业.整理.

下载可编辑

intmintime;/*最少时间*/

}closedge;

2.3基本操作

voidzairu(Graph*G);/*导入文件中的信息，能否是程序运行*/

voidAdminister(GraphG);/*管理员操作界面，由主函数调用*/

voidshow(GraphG);/*显示系统中的全部城市信息和交通信息*/

intinsertcity(Graph*G);/*增加城市信息*/

intinsertlu(Graph*G);/*增加交通信息*/

intLocated(Graph*G,char*p);/*返回邻接矩阵的位置下标，系统中的关键*/

voidbaocun(GraphG);/*将城市信息、交通信息保存在文件中*/

intserchlu(Graph*G);/*搜索交通信息*/

voidmindistance(Graph*G,intv0,intv1);/*最少里程计算，迪杰斯特拉算法*/

voidmincost(Graph*G,intv0,intv1);/*最少旅费计算，迪杰斯特拉算法*/

voidmintime(Graph*G,intv0,intv1);/*最少时间计算，迪杰斯特拉算法*/

2.4算法应用

在判断源点到其余各点的最短路径时运用迪杰斯特拉算法：

一般情况下，假设S为以求得最短路径的终点的集合，则可证明：下一条最短路

径（设其终点为x）或者是弧(v,k)，或者是中奖只经过S中的顶点而最后到达顶点x的

路径。这可用反证法来证明，假设此路径上有一个顶点不在S中，则说明存在一条终

点不在S而长度比此路径短的路径。但是，这是不可能的。因为我们是按照路径长度

递增的次序来产生各最短路径的，故长度比此路径段的所有路径均已产生，它们的终

点必定在S中，即假设不成立。

因此，在一般情况下，下一条长度次短的最短路径的长度必是

.专业.整理.

下载可编辑

D[j]Min{D[i]|v

i

VS}

其中，D[i]或者是弧

v,v

i



上的权值，或者是D[k](v

k

S)和弧v

k

,v

i

上的权值之

和。

（1）假设用带权的邻接矩阵arcs来表示带权有向图，arcs[i][j]表示弧v上

的权值。若存在，则置arcs[i][j]为∞(在计算机上可用允许的最大值代替)。S为

已到从v出发的最短路径的终点的集合，他的初始状态为空集。那么，从v出发到图

上其余个顶点(终点)vi可能达到的最短路径长度的初值为：

D[i]arc[Locate

（2）选择

v

j

，使得

Vex(G,v)[i]v

i

V

D[i]Min{D[i]|v

i

VS}

v

j

就是当前求得的一条从v出发的最短路径的终点。令

SS{j}

(3)修改从v出发到集合V-S上任一顶点

v

k

可达的最短路径长度。如果

D[i]arcs[j][k]D[k]

则修改

D[k]

为

D[k]D[j]arcs[j][k]

(4)重复操作(2)、(3)共n-1次。由此求得从v到图上其余各点的最短路径是依路径

长度递增的序列。

2.5程序设计流程图：

.专业.整理.

下载可编辑

交通咨询系统

图2.1程序设计流程图

管理员

显示所有交通路线

添加城市

用户退出

返回上一

添加交通查询最少查询最短查询最短返回上一3功能模块详细设计

级菜单

路线花费路线时间路线里程路线级菜单

3.1测试数据

表3.1城市信息

北京

重庆

九江

天津

成都

武汉

石家庄

郑州

广安

济南

徐州

无锡

表3.2交通信息表

起始

重庆

重庆

广安

北京

济南

成都

浙江

目的

广安

成都

成都

天津

天津

南京

郑州

旅费（元）

50

100

60

100

200

500

300

时间（小时）

1

2

1

1

2

20

30

里程（公里）

300

500

100

250

300

700

1000

.专业.整理.

下载可编辑

九江

南京

石家庄

浙江

重庆

成都

无锡

徐州

上海

济南

天津

广安

上海

武汉

无锡

北京

徐州

南京

郑州

北京

上海

温州

重庆

武汉

济南

重庆

200

100

100

300

500

400

700

200

100

150

530

300

534

10

5

5

24

23

30

40

15

8

15

28

23

28

500

200

300

1500

2000

2400

3500

895

300

500

2593

1842

1434

3.2程序调试

1.主界面包括四个选项：选项一：管理员管理界面，选择该项可进行城市交通系统

的管理；选项二：用户咨询界面，选择该项可进行最少费用、最少时间、最短里程的

决策咨询；选项三：显示城市交通系统，选择该项可显示城市交通系统的所有信息，

包括城市、交通路线信息；选项四：退出程序，选择该项将退出程序。

.专业.整理.

下载可编辑

图3.1程序主界面

在该系统运行的开始会从文件读取交通信息，如果文件不存在会导致程序运行错

误！出现下图情况：

图3.2文件不存在

该函数代码如下：

voidzairu(Graph*G)//读取文本中的信息

{

FILE*fpout,*fpin;

intcnum,lnum;

.专业.整理.

下载可编辑

charFromc[20],Toc[20];

intt,i,j;

for(i=0;i

for(j=0;j

{

}

G->arcs[i][j].distance=G->arcs[j][i].distance=zuida;

G->arcs[i][j].cost=G->arcs[j][i].cost=zuida;

G->arcs[i][j].time=G->arcs[j][i].time=zuida;

fpout=fopen("","r");

assert(fpout);

if(fscanf(fpout,"%d%d",&cnum,&lnum)==2)

{

G->c_n=cnum;

G->l_n=lnum;

fclose(fpout);

//读取城市顶点信息

fpout=fopen("","r");

for(t=0;tc_n;t++)

fscanf(fpout,"%s",G->clist[t].name);

fclose(fpout);

//读取边的信息.(起点、终点、距离(千米)、花费(元)、时间(分钟))

.专业.整理.

下载可编辑

fpout=fopen("","r");

for(t=0;tl_n;t++)

{

fscanf(fpout,"%s%s",Fromc,Toc);

i=Located(G,Fromc);

j=Located(G,Toc);

fscanf(fpout,"%d%d%d",&G->arcs[i][j].distance,

&G->arcs[i][j].cost,&G->arcs[i][j].time);

}

else

{

fpin=fopen("","w");

assert(fpin);

fprintf(fpin,"00");

G->l_n=0;

G->c_n=0;

fclose(fpin);

}

fclose(fpout);

G->arcs[j][i].distance=G->arcs[i][j].distance;

G->arcs[j][i].cost=G->arcs[i][j].cost;

G->arcs[j][i].time=G->arcs[i][j].time;

.专业.整理.

下载可编辑

}

}

2．管理员管理

界面首先出现登陆界面，采用加密技术，初始密码为admin，菜单项包括5个

选项：选项一：增加城市信息；选项二：增加交通路线信息；选项三：保存新增信

息，返回上一级菜单，可返回主界面。

.专业.整理.

下载可编辑

图3.3管理员界面

在该界面中调用了三个重要函数，对城市、交通信息进行编辑和保存。

intinsertcity(Graph*G)//增加城市

{

charname[20];

printf("输入要增加的城市:");

scanf("%s",name);

getchar();

if(G->c_n==0)

{

}

else

{

for(inti=0;ic_n;i++)

if(strcmp(G->clist[i].name,name)==0)

return-1;

strcpy(G->clist[0].name,name);

G->c_n++;

else

strcpy(G->clist[G->c_n].name,name);

.专业.整理.

下载可编辑

}

}

G->c_n++;

return1;

图3.4增加城市

intinsertlu(Graph*G)//增加城市交通信息

{

charFromc[20],Toc[20];

inti,j;

intd,c,t;

printf("输入增加路径的出发城市、目的城市、距离(公里)、花费(元)、时间

(小时):n");

scanf("%s%s%d%d%d",Fromc,Toc,&d,&c,&t);

.专业.整理.

下载可编辑

}

getchar();

i=Located(G,Fromc);

j=Located(G,Toc);

if(i==-1||j==-1)

return-1;

else

{

}

return1;

G->arcs[i][j].distance=G->arcs[j][i].distance=d;

G->arcs[i][j].cost=G->arcs[j][i].cost=c;

G->arcs[i][j].time=G->arcs[j][i].time=t;

G->l_n++;

.专业.整理.

下载可编辑

图3.5增加交通信息

voidbaocun(GraphG)//保存新增信息于文件中

{

FILE*fpin;

inti,m,k;

//边和顶点的个数

fpin=fopen("","w");

assert(fpin);

fprintf(fpin,"%d%d",G.c_n,G.l_n);

fclose(fpin);

//顶点信息.

fpin=fopen("","w");

assert(fpin);

for(i=0;i

{

fprintf(fpin,"%s",[i].name);

m=i%10;

if(m==0)

.专业.整理.

下载可编辑

}

printf("n");

fclose(fpin);

//边的信息.

fpin=fopen("","w");

assert(fpin);

for(i=0;i

{

for(k=i+1;k

{

if([i][k].distance!=zuida)

fprintf(fpin,"%s%s%d%d%dn",[i].name,

[k].name,[i][k].distance,[i][k].cost,[i][k].time);

}

保存文件在该系统中是一个重要的组成部分，用于对城市和交通信息的保存，

将其储存在文件之中！

3.用户查询路线

进入该界面，提示输入要查询的两个城市，然后系统进入查询方法界面如下

图：

}

fclose(fpin);

}

.专业.整理.

下载可编辑

图3.6查方法

该系统的查方法，每一种查最短路径的算法都是运用迪杰斯特拉算法，该

代码如下：

voidmindistance(Graph*G,intv0,intv1)//最短距离

{

int*d;

intvd,w,i,j,v;

intmind,*pred,*finald;

finald=(int*)malloc(G->c_n*sizeof(int));//判断顶点是否已求出最短路径

.专业.整理.

下载可编辑

d=(int*)malloc(G->c_n*sizeof(int));//储存起始点到各点的最短路径

pred=(int*)malloc(G->c_n*sizeof(int));//最后用于输出最短路径

for(v=0;vc_n;v++)

{

}

d[v0]=0;//到起始点无路径

finald[v0]=1;//v0放入到final数组里

for(i=1;ic_n;i++)//从1开始、因为起始点已经在final里面、剩下n-1个

finald[v]=0;

d[v]=G->arcs[v0][v].cost;

if(d[v]

pred[v]=v0;

else

pred[v]=-1;

顶点、循环n-1次。

{

mind=zuida;

for(w=0;wc_n;w++)

{

if(!finald[w])//没有放进final里面的终点进行选择最短路径出来.

{

.专业.整理.

下载可编辑

}

if(d[w]

{

}

mind=d[w];

vd=w;

}//到最短路径终点G->vexs[v]

finald[vd]=1;//放入final中

for(w=0;wc_n;w++)

{

if(!finald[w]&&(mind+G->arcs[vd][w].distance

到每个终点[w]当前的最短路径.若该终点已在final里面、

}

if(pred[v1]!=-1)

{

printf("%s到%s",G->clist[v0].name,G->clist[v1].name);

printf("最短路程为(公里):%dtt",d[v1]);

}

{//跳出if语句、

}

d[w]=mind+G->arcs[vd][w].distance;

pred[w]=vd;

.专业.整理.

下载可编辑

}

}

printf("%s",G->clist[v0].name);

j=pred[v1];

while(j!=v0)

{

}

printf("-->%sn",G->clist[v1].name);

printf("-->%s",G->clist[j].name);

j=pred[j];

else

printf("%s到%s没有信息.n",G->clist[v0].name,G->clist[v1].name);

该代码在系统中是核心算法！

.专业.整理.

下载可编辑

图3.7最短路径

4.显示所有交通信息

图3.8交通信息

.专业.整理.

下载可编辑

该函数代码如下：

voidshow(GraphG)

{

inti,k;

system("cls");

printf("nn目前交通系统中含有%d个城市，%d条旅游路径nnn",

G.c_n,G.l_n);

);

printf("城市tt城市tt距离(公里)t花费(元)t时间(小时)

printf("各大城市:n");

for(i=0;i

{

}

printf("%s",[i].name);

if((i+1)%10==0)

printf("n");

printf("nn************************************************************nn"

n");

for(i=0;i

for(k=i+1;k

if([i][k].distance!=zuida)

.专业.整理.

下载可编辑

printf("%stt%stt%dtt%dtt%dn",

[i][k].distance,[i][k].cost,[i].name,

[i][k].time);

}

[k].name,

system("pause");

该短代码中主要是读取三个文件，然后分别将信息输出在屏幕上！

5.在该系统中还有一段代码，是该程序的核心内容，用于返回网络图结构中位

置下标；代码如下：

intLocated(Graph*G,char*p)//返回数据位置

{

}

inti;

for(i=0;ic_n;i++)

if(strcmp(G->clist[i].name,p)==0)

returni;

return-1;

.专业.整理.

下载可编辑

.专业.整理.

4课程总结与体会

下载可编辑

该系统虽然已满足此次任务要求，但是还有许多需要修改增加的地方：

1.在系统运行时，如无文件就不能运行。可以让系统自行创建文件。

2.在对城市和交通信息进行编辑时不能对其进行删除和修改

3.在对信息编辑时可同时进行保存

在这次数据结构课程设计中，自己的C语言知识和数据结构知识得到了巩固，编

程能力也有了一定的提高。同时也学会了解决问题的方法。总结起来，自己主要有以下几

点体会：

1.必须牢固掌握基础知识。由于C语言知识，有所遗忘，且未掌握好这学期所学的

《数据结构》这门课，所以在实习开始不知如何下手，但在后来的实习过程中自己通过看

书和课外资料，并请教其他同学，慢慢地C语言和数据结构知识有所熟悉。这时才逐渐有

了思路。

2.必须培养严谨的科学态度。自己在编程时经常因为一些类似于“少了分号”的小错误

而导致错误，不够认真细致，这给自己带来了许多麻烦。编程是一件十分严谨的事情，

不能有一点的粗心

3.这次课程设计也让我充分认识到《数据结构》这门课的重要性。它给我们一个思想和

大纲，让我们在编程时容易到思路，不至于无章可循。同时它也有广泛的实际应用。

总之，在这次实习中，自己的C语言以及数据结构知识得到提高，编程能力也得到

了提高。

.专业.整理.

下载可编辑

5参考文献

【1】严蔚敏，吴伟民，《数据结构（C语言版）》，清华大学出版社，1997.4；

【2】周学毛，《新编C语言程序设计教程》，西安电子科技大学出版社，2005.7；

【3】苏仕华，《数据结构课程设计》，机械工业出版社，2005

【4】滕国文，《数据结构课程设计》，清华大学出版社，2010年

【5】MarkAllenWeiss，《数据结构与算法分析：C语言描述》，机械工业出版社，

2004年

.专业.整理.

下载可编辑

6致谢

通过此次的课程设计，我不仅学会了很多有关数据结构的算法思路。

此次课程设计要细心指导，以师所授的数据结构知识，还有一些同学和学长的帮

助，由于他们的指导与帮助才完成了课程设计。谢谢！

.专业.整理.

下载可编辑

.专业.整理.