交通咨询系统设计

交通咨询系统设计

专 业 计算机科学与技术 班 级 姓 名 指导教师 日 期

目录

一．前言.................................................................................................................1

1．1设计要求......................................................................................................1 1．2设计思想 ....................................................................................................1 1．3设计要求......................................................................................................1

二．程序流程图.................................................................................................1

三．程序源代码.................................................................................................2

四．编译与运行.................................................................................................6

五．参考文献......................................................................................................9

六． 评语..............................................................................................................10

评 语 评阅人： 日期：

摘要

数据结构主要是一门研究非数值计算的程序设计问题中的计算机操作对象以及它们之间的关系和操作等的学科。数据结构在计算机科学与技术中是一门综合性的专业基础课，其研究不仅涉及到计算机硬件的研究范围，而且和计算机软件的研究有着更密切的关系。不论是编译程序过程还是操作系统都涉及到数据元素在存储器中的分配问题。在计算机科学与技术中，数据结构不仅是一般程序性的基础，而且也是其他系统程序和大型程序的重要基础。

在交通网络非常发达，交通工具和交通方式不断更新的今天，人们在出差、旅游或做其它出行时，不仅关心节省费用，而且对里程和所需时间等问题也感兴趣。对于这样一个人们关心的问题，可用一个图结构来表示交通网络系统，利用计算机建立一个交通咨询系统。图中顶点表示城市之间的交通关系。这个交通系统可以回答旅客提出的各种问题。比如任意一个城市到其他城市的最短路径，任意两个城市之间的最短路径问题。

本次设计的交通咨询系统主要是运用C语言来完成交通图的存储、图中顶点的单源最短路径和任意一对顶点间的最短路径问题。

设计者 2011. 7. 5

一. 前言:

1.设计内容：设计一个交通咨询系统，能让旅客咨询任一个城市到另一个城市之间的最短里程或最低花费或最少时间等问题。对于不同咨询要求，可输入城市间的路程或所需费用或所需时间。

该交通咨询系统设计共三部分，一是建立交通网络图的存储结构；二是解决单源路径问题；最后再实现两个城市之间的最短路径问题。

2.设计思想：用邻接矩阵来存储交通网络图的信息，运用迪杰斯特拉算法实现图上单源最短路径问题，然后运用费洛伊德算法实现图中任意一对顶点间最短路径问题，这样就会实现旅客所要咨询的问题。

3.设计要求：该交通咨询系统要完成城市网络图的存储，并要实现求任意一个城市顶点到其他城市顶点的最短路径问题，还要实现任意两个城市顶点间的 最短路径问题。故设计要分成三部分，一是建立交通网络图的存储结构；二是 解决单源路径问题；最后再实现两个城市之间的最短路径问题。

二．程序流程图：

三. 程序源代码:

#include #include

#define MVNum 100 //最大顶点数 #define Maxint 35000 enum boolean{FALSE,TRUE}; typedef char Vertextype; typedef int Adjmatrix; typedef struct {

Vertextype vexs[MVNum]; //顶点数组， 类型假定为char型 Adjmatrix arcs[MVNum] [MVNum]; // 邻接矩阵， 假定为int型

} MGraph;

int D1[MVNum], p1[MVNum];

int D[MVNum][MVNum],p[MVNum][MVNum]; //文件名save.c

void CreateMGraph(MGraph *G,int n,int e)

{ //采用邻接矩阵表示法构造有向图G,n,e表示图的当前顶点数和边数

int i,j,k,w;

for(i=1;i<=n;i++) //输入顶点信息

G->vexs[i]=(char)i;

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

G->arcs[i][j]=Maxint; // 初始化邻接矩阵 printf (\"输入%d条边的i,j及w: \\n\

for(k=1;k<=e;k++)

{ //读入e条边,建立邻接矩阵

scanf(\"%d,%d,%d\

G->arcs[i][j]=w;

}

printf (\"有向图的存储结构建立完毕！ \\n\"); }

//文件名:dijkstra.c(迪杰斯特拉算法） void Dijkstra(MGraph *G, int v1,int n)

{ //用Dijkstra算法求有向图G的v1顶点到其他顶点v的最短路径p[v]及其权D[v]

//设G是有向图的邻接矩阵，若边不存在，则G[i][j]=Maxint //S[v]为真当且仅当v属于S，及以求的从v1到v的最短路径

int D2[MVNum], p2[MVNum]; int v,i,w,min;

enum boolean S[MVNum]; for(v=1;v<=n;v++) { // 初始化S和D

S[v]=FALSE; //置空最短路径终点集 D2[v]=G->arcs[v1][v]; //置初始的最短路径值 if(D2[v]< Maxint)

p2[v]=v1; //v1是的前趋（双亲）

else

p2[v]=0; //v 无前趋

} // End_for

D2[v1]=0;S[v1]=TRUE; //S集初始时只有源点， 源点到源点的距离为0 //开始循环，每次求的V1到某个V顶点的最短路径，并加V到S集中 for(i=2;imin=Maxint; // 当前所知离v1顶点的最近距离，设初值为∞

for(w=1;w<=n;w++) //对所有顶点检查

if(!S[w] && D2[w]{ //找离v1最近的顶点w，并将其赋给v，距离赋给min v=w; //在S集之外的离v1最近的顶点序号

min=D2[w]; //最近的距离

} //W顶点距离V1顶点更近 S[v]=TRUE; //将v并入S集

for(w=1;w<=n;w++) //更新当前最短路径及距离

if(!S[w]&&(D2[v]+G->arcs[v][w]D2[w]=D2[v]+G->arcs[v][w]; //更新D2[w] p2[w]=v;

} //End_if

} //End_for

printf (\"路径长度 路径\\n\"); for(i=1;i<=n;i++)

{ printf (\"%5d\ printf (\"%5d\ while(v!=0) { } }

//文件名 floyd.c(费洛伊德算法） void Floyd(MGraph *G, int n) {

int i, j, k;

for(i=1;i<=n;i++) //设置路径长度D和路径path初值

for(j=1;j<=n;j++) {

if(G->arcs[i][j]!=Maxint)

}

printf(\"\\n\");

printf (\"<-%d\v=p2[v];

}

}

p[i][j]=j; //j是i的后继

else

p[i][j]=0;

D[i][j]=G->arcs[i][j];

for(k=1;k<=n;k++) {

{ //做K次迭代，每次均试图将顶点K扩充到当前求得的从i到j的最短路径pij上

}

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

{ if(D[i][k]+D[k][j]D[i][j]=D[i][k]+D[k][j]; //修改长度 p[i][j]=p[i][k]; } }

void main() { MGraph * G; int n, e, v, w, k;

int xz=1;

G=(MGraph *)malloc(sizeof(MGraph)); printf(\"输入图中顶点个数和边数n,e: \"); scanf(\"%d,%d\

CreateMGraph(G, n, e); //建立图的存储结构 while(xz!=0) {

printf(\" 求城市之间的最断路径 \\n\"); printf(\"-------------------------------\\n\");

printf(\"1.求一个城市到所有城市的最短路径\\n\");

printf(\"2.求任意的两个城市之间的最短路径\\n\");

printf(\"--------------------------------\\n\");

printf(\" 请选择：1 或 2， 选择0 ：退出： \"); scanf(\"%d\ if(xz==2) { Floyd(G,n); //调用费洛伊德算法 printf(\"输入起点和终点: v,w:\"); scanf(\"%d,%d\

k=p[v][w]; //k为起点v的后继顶点 if(k==0) printf(\"顶点%d 到 %d 无路径! \\n\ else { printf(\"从顶点%d到%d的最短路径是: %d\ } while(k!=w) { printf(\"-->%d\输出后继顶点 k=p[k][w]; //继续找下一个后继顶点 } printf(\"-->%d\ // 输出终点w printf(\" 路径长度:%d\\n\ }

if(xz==1) { printf(\"求单源路径，输入起点 v :\"); scanf(\"%d\ Dijkstra(G,v,n); //调用迪杰斯特拉算法 } }

printf(\"结束求最短路径，再见！\\n\"); }

五. 编译及运行:

编译: 在第一次编译时出现了很多错误，是因为我对C语言的不

熟练，比如调用费洛伊德算法时出现了调用的错误，找了好久，才改正过来，还有就是for语句的运用，由于本次程序要用很多for循环，我把一次for循环放到了上面for循环中，导致程序不能正确输出结果。最后把调到外面才OK。

运行结果：下面是城市交通图

北京1704郑州25西安12532511315793494 州651徐8成都523686广州13857上海

五.参考文献:

数据结构（C语言版） 编著 严蔚敏 吴伟民 清华大学出版社 1997

数据结构课程设计 编著 苏仕华 机械工业出版社 2005 数据结构—用c语言描述 编著 蔡明志 中国水利水电出版社 2006 《数据结构》学习指导与训练 编著 蒋盛益 中国水利水电出版社 2003