„„„„„„„„大学
算法与数据结构 课程设计报告
题 目： 交通咨询系统
设 计 者： 25045012
专业班级： 本网络
学 号：
指导教师：
所属系部： 计算机科学与技术系
2012年06月03日
目 录
1 问题描述及要求.................................................... 1 2 需求分析.......................................................... 1 3 算法思想描述...................................................... 1 4 概要设计.......................................................... 4 5 详细设计.......................................................... 5 6 测试数据及分析.................................................... 9 7课程设计总结 ..................................................... 11 8 参考资料......................................................... 11
这是我老师给我的题目我所真实上交的作品，在VC++6.0上完美运行，文档上也有截图。对于上传分享了这作品，我想说明两点：
一是我这个程序，不是绝对原创，但是所参考的那个程序是不完美的——首先界面并不友好，我已经重新设计了文字提示界面；原程序有个bug，就是在目的地和出发地重合的时候显示距离是无穷大，正确明显为0，我在老师的帮助下进行了修改算法解决了这个问题，在此我感谢我的指导老师龙老师认真负责对我进行指导，也很感谢原程序的作者为我提供程序主体和基本思路。这个word文档的其他部分90%是自己完成的（不否认有部分是参考了别人的）。
二是若有人想借鉴本作品，希望改得体无完肤，因为程序的算法和提示语我的个人风格很浓，容易辨认，如果你的老师不巧只需浏览了一次，真的可以一眼辨认你是网上抄的。
——写给 想借鉴本文档的 网友
交通咨询系统
1 问题描述及要求
设计一个交通咨询系统,能让旅客咨询从任一个城市定点到另一个城市定点之间的最短路径或最低花费或最少时间等问题。对于不同的咨询要求、可输入城市间的路程或所需时间或所需花费。 设计要求：
1. 建立交通网络网的存储结构。 2. 总体设计要画流程图。 3. 提供程序测试方案。 4. 界面友好。
2 需求分析
根据要求，需要在系统中建立无向图。系统应该有高度灵活性，可以由用户根据当前交通网络图输入初始数据，并且可以更改。系统根据用户的输入建立无向图的结构，并通过狄克斯特拉算法和弗洛伊德算法实现要求，并提供两种功能供用户选择。
3 算法思想描述
首先总体的思想步骤是：
4 概要设计
系统应该分为三个部分，一是建立交通网络图的存储结构；二是解决单源最短路径问题；最后再实现两个城市顶点之间的最短路径问题。 1、 建立图的存储结构：无向图
首先定义交通图的存储结构。邻接矩阵是表示图形中顶点之间相邻关系的矩阵。设G=（V，E）是具有n个顶点的图，则G的邻接矩阵是具有如下定义的n阶方阵。
⎧Wij，若(vi,vj)或∈E(G);⎨
0或∞，当不满足上述条件时。
A[i，j]=⎩
一个图的邻接矩阵表示是唯一的。图的邻接矩阵表示，除了需要用一个二维数
组存储顶点之间相邻关系的邻接矩阵外，通常还需要使用一个具有n个元素的一维数组来存储顶点信息，其中下标为i的元素存储顶点vi的信息
2、 单源最短路径：狄克斯特拉算法
初始化S和D，置空最短路径终点集，置初始的最短路径值；
S[v1]=TRUE；D[v1]=0；//S集初始时只有源点，源点到源点的距离为0； while（S集中顶点数
开始循环，每次求得v1到某个v顶点的最短路径，并加v到S集中； S[v]=TRUE；
更新当前最短路径及距离；
}
3、 任意一对顶点间最短路径：弗洛伊德算法 假设
为从到的只以
集合中的节点为中间节点的最短路径的长度。
1. 若最短路径经过点k，则2. 若最短路径不经过点k，则因此，最短路径
。
；
。
5 详细设计
程序源代码如下： //交通咨询系统 #include #include
#define Num 300 //定义常量Num #define Maxint 32767
enum boolean{FALSE,TRUE}; //定义布尔类型 typedef char VertexType; typedef int Adjmatrix; typedef struct {
VertexType vexs[Num]; Adjmatrix arcs[Num][Num]; }MGraph;
int D1[Num],P1[Num];
int D[Num][Num],P[Num][Num];
void CreateMGraph(MGraph *G,int n,int e); //构建城市的无向图的声明 void Dijkstra(MGraph *G,int v1,int n); //狄克斯特拉算法的声明 void Floyd(MGraph *G,int n); //弗洛伊德算法的声明 void main()
{ MGraph *G; //定义无向图G int n,e,v,w,k; int m=1;
G=(MGraph *)malloc(sizeof(MGraph));
printf("欢迎使用【交通咨询系统】！本系统约定：\n1.记一个城市为一个点，点用从1开始按顺序的编号表示，两个城市的连线为一条边；\n2.程序要求输入的文本都是按回车进行确认；\n3.程序输入输出均不带单位，单位默认为“公里”。\n\n"); printf("系统需要知道地图的结构，请输入顶点个数和边数，用“,”号隔开：\n"); scanf("%d,%d",&n,&e);
CreateMGraph(G,n,e); //调用CreateMGraph有向图函数 while(m!=0){
printf("===============================================================================\n"); printf("请输入数字：\n"); printf("0 : 退出\n");
printf("1 : 求一个城市到其他所有城市的最短路径\n"); printf("2 : 求任意的两个城市之间的最短路径\n"); scanf("%d",&m); if(m==2){ Floyd(G,n);
printf("请输入起点和终点，用“,”号隔开：\n"); scanf("%d,%d",&v,&w); k=P[v][w]; if(k==0)
printf("\n输出的结果：\n顶点%d到%d无路径!\n",v,w); else {
printf("\n输出的结果：\n从顶点%d到%d的最短路径是: %d",v,w,v); while(k!=w){ printf("→%d",k); k=P[k][w]; }
printf("→%d",w);
printf("\n 路径长度: %d\n",D[v][w]); } } else if(m==1){
printf("请输入起点编号：\n"); scanf("%d",&v); Dijkstra(G,v,n); } }
printf("程序已结束！谢谢您的使用！\n");
void CreateMGraph(MGraph *G,int n,int e) //构建城市的无向图 {
int i,j,k,w;
for(i=1;ivexs[i]=(char)i; for(i=1;i
for(j=1;j
G->arcs[i][j]=Maxint; //距离初始化 if(i==j)
G->arcs[i][j]=0; }
printf("\n请输入%d条边的两端点序号和长度，用“,”号隔开\n例如：1号城市到2号城市的长度为3，则输入1,2,3）: \n",e); for(k=1;k
scanf("%d,%d,%d",&i,&j,&w);
G->arcs[i][j]=w; //建立城市之间的距离 G->arcs[j][i]=w; }
printf("\n地图的结构建立成功！\n"); }
void Dijkstra(MGraph *G,int v1,int n) //狄克斯特拉算法求一个城市到任意一个城市的距离 {
int D2[Num],P2[Num]; int v,i,w,min;
enum boolean S[Num];
for (v=1;v
S[v]=FALSE; //s[]置空 D2[v]=G->arcs[v1][v]; //距离初始化
if(D2[v]
}
else
P2[v]=0;
P2[v1]=0;S[v1]=TRUE; //源点V1放入s中 for(i=2;i
min=Maxint; //Maxint置最小长度初值 for(w=1;w
if(!S[w]&&D2[w]
for(w=1;w
if(!S[w]&&(D2[v]+G->arcs[v][w]
}
{ }
D2[w]=D2[v]+G->arcs[v][w]; P2[w]=v;
printf("\n输出的结果：\n");
printf("路径长度 路径\n"); //输出最短路径 for(i=1;i
printf("←%d",v); v=P2[v];
}
printf("\n"); } }
void Floyd(MGraph *G,int n) //用弗洛伊德算法求任意两顶点最短距离 {
int i,j,k; //定义三个变量 for(i=1;i
} for(j=1;jarcs[i][j]!=Maxint) //距离初始化 else P[i][j]=0; P[i][j]=j; //路径初始化 D[i][j]=G->arcs[i][j];
6 测试数据及分析
假如某交通网络上有4个城市（序号为1,2,3,4），4个城市之中有5条道路（不同长度），交通网络图如下图所示：
打开本系统，界面如图：
输入4,5之后按下键盘上的回车键：
根据交通网络图输入线路数据后按回车：
选择1回车后，再输入城市2，求得出的结果如下：
选择2后，要计算1到3的最短距离和路径，输入1,3，得到结果，并与输入3,1的输出结果作对比如下：
7课程设计总结
在我对作品完成了最后的调试和运行之后，紧张的一个星期的课程设计终于暂时告一段落。这个课程设计的课题虽然总体来说难度不大，因为在书上可以找到很多例子供参考。但是由于平时经常不认真听课，虽然看得明例题，但是要用到自己的作品中还是造有一定的压力。对此我因为过去的学习态度而懊悔。但是课程设计是个锻炼自己的极好机会，缺失的知识现在得补上！并且设计的过程是发现自身知识空点的最好的机会，以往不会遇到的情况，在实践练习中一一浮出水面，面对着它们，虽然短短一个星期，但是也经历了很多挫折，有过气馁，但是真正的迈过去以后才感觉到畅快和欣喜，所以遇到的问题，我想到的放弃念头很快被打消，坚持到了作品完成。
课程设计具的实践意义，正如军事锻炼是对我们精神意志的磨练，它是对我们的一次考核和知识补充，对未来工作的演习。老师也为了我们能顺利完成作品，悉心指导，孜孜不倦，所以面对这次课程设计，我感到充实和感谢！
8 参考资料
[1] 徐凤生，《数据结构与算法C语言版》，机械工业出版社，2010
„„„„„„„„大学
算法与数据结构 课程设计报告
题 目： 交通咨询系统
设 计 者： 25045012
专业班级： 本网络
学 号：
指导教师：
所属系部： 计算机科学与技术系
2012年06月03日
目 录
1 问题描述及要求.................................................... 1 2 需求分析.......................................................... 1 3 算法思想描述...................................................... 1 4 概要设计.......................................................... 4 5 详细设计.......................................................... 5 6 测试数据及分析.................................................... 9 7课程设计总结 ..................................................... 11 8 参考资料......................................................... 11
这是我老师给我的题目我所真实上交的作品，在VC++6.0上完美运行，文档上也有截图。对于上传分享了这作品，我想说明两点：
一是我这个程序，不是绝对原创，但是所参考的那个程序是不完美的——首先界面并不友好，我已经重新设计了文字提示界面；原程序有个bug，就是在目的地和出发地重合的时候显示距离是无穷大，正确明显为0，我在老师的帮助下进行了修改算法解决了这个问题，在此我感谢我的指导老师龙老师认真负责对我进行指导，也很感谢原程序的作者为我提供程序主体和基本思路。这个word文档的其他部分90%是自己完成的（不否认有部分是参考了别人的）。
二是若有人想借鉴本作品，希望改得体无完肤，因为程序的算法和提示语我的个人风格很浓，容易辨认，如果你的老师不巧只需浏览了一次，真的可以一眼辨认你是网上抄的。
——写给 想借鉴本文档的 网友
交通咨询系统
1 问题描述及要求
设计一个交通咨询系统,能让旅客咨询从任一个城市定点到另一个城市定点之间的最短路径或最低花费或最少时间等问题。对于不同的咨询要求、可输入城市间的路程或所需时间或所需花费。 设计要求：
1. 建立交通网络网的存储结构。 2. 总体设计要画流程图。 3. 提供程序测试方案。 4. 界面友好。
2 需求分析
根据要求，需要在系统中建立无向图。系统应该有高度灵活性，可以由用户根据当前交通网络图输入初始数据，并且可以更改。系统根据用户的输入建立无向图的结构，并通过狄克斯特拉算法和弗洛伊德算法实现要求，并提供两种功能供用户选择。
3 算法思想描述
首先总体的思想步骤是：
4 概要设计
系统应该分为三个部分，一是建立交通网络图的存储结构；二是解决单源最短路径问题；最后再实现两个城市顶点之间的最短路径问题。 1、 建立图的存储结构：无向图
首先定义交通图的存储结构。邻接矩阵是表示图形中顶点之间相邻关系的矩阵。设G=（V，E）是具有n个顶点的图，则G的邻接矩阵是具有如下定义的n阶方阵。
⎧Wij，若(vi,vj)或∈E(G);⎨
0或∞，当不满足上述条件时。
A[i，j]=⎩
一个图的邻接矩阵表示是唯一的。图的邻接矩阵表示，除了需要用一个二维数
组存储顶点之间相邻关系的邻接矩阵外，通常还需要使用一个具有n个元素的一维数组来存储顶点信息，其中下标为i的元素存储顶点vi的信息
2、 单源最短路径：狄克斯特拉算法
初始化S和D，置空最短路径终点集，置初始的最短路径值；
S[v1]=TRUE；D[v1]=0；//S集初始时只有源点，源点到源点的距离为0； while（S集中顶点数
开始循环，每次求得v1到某个v顶点的最短路径，并加v到S集中； S[v]=TRUE；
更新当前最短路径及距离；
}
3、 任意一对顶点间最短路径：弗洛伊德算法 假设
为从到的只以
集合中的节点为中间节点的最短路径的长度。
1. 若最短路径经过点k，则2. 若最短路径不经过点k，则因此，最短路径
。
；
。
5 详细设计
程序源代码如下： //交通咨询系统 #include #include
#define Num 300 //定义常量Num #define Maxint 32767
enum boolean{FALSE,TRUE}; //定义布尔类型 typedef char VertexType; typedef int Adjmatrix; typedef struct {
VertexType vexs[Num]; Adjmatrix arcs[Num][Num]; }MGraph;
int D1[Num],P1[Num];
int D[Num][Num],P[Num][Num];
void CreateMGraph(MGraph *G,int n,int e); //构建城市的无向图的声明 void Dijkstra(MGraph *G,int v1,int n); //狄克斯特拉算法的声明 void Floyd(MGraph *G,int n); //弗洛伊德算法的声明 void main()
{ MGraph *G; //定义无向图G int n,e,v,w,k; int m=1;
G=(MGraph *)malloc(sizeof(MGraph));
printf("欢迎使用【交通咨询系统】！本系统约定：\n1.记一个城市为一个点，点用从1开始按顺序的编号表示，两个城市的连线为一条边；\n2.程序要求输入的文本都是按回车进行确认；\n3.程序输入输出均不带单位，单位默认为“公里”。\n\n"); printf("系统需要知道地图的结构，请输入顶点个数和边数，用“,”号隔开：\n"); scanf("%d,%d",&n,&e);
CreateMGraph(G,n,e); //调用CreateMGraph有向图函数 while(m!=0){
printf("===============================================================================\n"); printf("请输入数字：\n"); printf("0 : 退出\n");
printf("1 : 求一个城市到其他所有城市的最短路径\n"); printf("2 : 求任意的两个城市之间的最短路径\n"); scanf("%d",&m); if(m==2){ Floyd(G,n);
printf("请输入起点和终点，用“,”号隔开：\n"); scanf("%d,%d",&v,&w); k=P[v][w]; if(k==0)
printf("\n输出的结果：\n顶点%d到%d无路径!\n",v,w); else {
printf("\n输出的结果：\n从顶点%d到%d的最短路径是: %d",v,w,v); while(k!=w){ printf("→%d",k); k=P[k][w]; }
printf("→%d",w);
printf("\n 路径长度: %d\n",D[v][w]); } } else if(m==1){
printf("请输入起点编号：\n"); scanf("%d",&v); Dijkstra(G,v,n); } }
printf("程序已结束！谢谢您的使用！\n");
void CreateMGraph(MGraph *G,int n,int e) //构建城市的无向图 {
int i,j,k,w;
for(i=1;ivexs[i]=(char)i; for(i=1;i
for(j=1;j
G->arcs[i][j]=Maxint; //距离初始化 if(i==j)
G->arcs[i][j]=0; }
printf("\n请输入%d条边的两端点序号和长度，用“,”号隔开\n例如：1号城市到2号城市的长度为3，则输入1,2,3）: \n",e); for(k=1;k
scanf("%d,%d,%d",&i,&j,&w);
G->arcs[i][j]=w; //建立城市之间的距离 G->arcs[j][i]=w; }
printf("\n地图的结构建立成功！\n"); }
void Dijkstra(MGraph *G,int v1,int n) //狄克斯特拉算法求一个城市到任意一个城市的距离 {
int D2[Num],P2[Num]; int v,i,w,min;
enum boolean S[Num];
for (v=1;v
S[v]=FALSE; //s[]置空 D2[v]=G->arcs[v1][v]; //距离初始化
if(D2[v]
}
else
P2[v]=0;
P2[v1]=0;S[v1]=TRUE; //源点V1放入s中 for(i=2;i
min=Maxint; //Maxint置最小长度初值 for(w=1;w
if(!S[w]&&D2[w]
for(w=1;w
if(!S[w]&&(D2[v]+G->arcs[v][w]
}
{ }
D2[w]=D2[v]+G->arcs[v][w]; P2[w]=v;
printf("\n输出的结果：\n");
printf("路径长度 路径\n"); //输出最短路径 for(i=1;i
printf("←%d",v); v=P2[v];
}
printf("\n"); } }
void Floyd(MGraph *G,int n) //用弗洛伊德算法求任意两顶点最短距离 {
int i,j,k; //定义三个变量 for(i=1;i
} for(j=1;jarcs[i][j]!=Maxint) //距离初始化 else P[i][j]=0; P[i][j]=j; //路径初始化 D[i][j]=G->arcs[i][j];
6 测试数据及分析
假如某交通网络上有4个城市（序号为1,2,3,4），4个城市之中有5条道路（不同长度），交通网络图如下图所示：
打开本系统，界面如图：
输入4,5之后按下键盘上的回车键：
根据交通网络图输入线路数据后按回车：
选择1回车后，再输入城市2，求得出的结果如下：
选择2后，要计算1到3的最短距离和路径，输入1,3，得到结果，并与输入3,1的输出结果作对比如下：
7课程设计总结
在我对作品完成了最后的调试和运行之后，紧张的一个星期的课程设计终于暂时告一段落。这个课程设计的课题虽然总体来说难度不大，因为在书上可以找到很多例子供参考。但是由于平时经常不认真听课，虽然看得明例题，但是要用到自己的作品中还是造有一定的压力。对此我因为过去的学习态度而懊悔。但是课程设计是个锻炼自己的极好机会，缺失的知识现在得补上！并且设计的过程是发现自身知识空点的最好的机会，以往不会遇到的情况，在实践练习中一一浮出水面，面对着它们，虽然短短一个星期，但是也经历了很多挫折，有过气馁，但是真正的迈过去以后才感觉到畅快和欣喜，所以遇到的问题，我想到的放弃念头很快被打消，坚持到了作品完成。
课程设计具的实践意义，正如军事锻炼是对我们精神意志的磨练，它是对我们的一次考核和知识补充，对未来工作的演习。老师也为了我们能顺利完成作品，悉心指导，孜孜不倦，所以面对这次课程设计，我感到充实和感谢！
8 参考资料
[1] 徐凤生，《数据结构与算法C语言版》，机械工业出版社，2010