数据结构课程设计-Floyd算法求解最短路径.doc

数据结构课程设计报告撰写要求

（一）纸张与页面要求
1．采用国际标准A4型打印纸或复印纸，纵向打印。
2．封页和页面按照下面模板书写（正文为：小四宋体1.5倍行距）。
3．图表及图表标题按照模板中的表示书写。
（二） 课设报告书的内容应包括以下各个部分：（按照以下顺序装订）
1.封页(见课设模版)
2、学术诚信声明，所有学生必须本人签字，否则教师拒绝给予成绩。
2.任务书(学生教师均要签字,信息填写完整)
3.目录
4.正文一般应包括以下内容:
（1)题目介绍和功能要求（或描述）
课程设计任务的详细描述(注意不能直接抄任务书),将内容做更详细的具体的分析与描述；
（2) 系统功能模块结构图
绘制系统功能结构框图及主要模块的功能说明；
（3) 使用的数据结构的描述: 数据结构设计及用法说明;
（4) 涉及到的函数的描述 ;
（5) 主要算法描述( 程序流程图)
（6) 给出程序测试/运行的结果
设计多组数据加以描述（包括输入数据和输出结果）
（7) 课程设计的总结及体会
（8) 参考文献
格式要求：[1]作者，等. 书名.出版地：出版社，出版年
5.附录：程序清单 (应带有必要的注释)

沈阳航空航天大学

课 程 设 计 报 告

课程设计名称：数据结构课程设计
课程设计题目：利用弗洛伊德（Floyd)算法求解最短路径

院（系）：计算机学院
专 业：计算机科学与技术(物联网方向)
班 级：34010105
学 号：
姓 名：
指导教师：
说明：结论（优秀、良好、中等、及格、不及格）作为相关教环节考核必要依据；格式不符合要求；数据不实,不予通过。报告和电子数据必须作为实验现象重复的关键依据。

沈阳航空航天大学课程设计报告
学术诚信声明
本人声明：所呈交的报告（含电子版及数据文件）是我个人在导师指导下独立进行设计工作及取得的研究结果。尽我所知，除了文中特别加以标注或致谢中所罗列的内容以外，报告中不包含其他人己经发表或撰写过的研究结果，也不包含其它教育机构使用过的材料。与我一同工作的同学对本研究所做的任何贡献均己在报告中做了明确的说明并表示了谢意。报告资料及实验数据若有不实之处，本人愿意接受本教学环节“不及格”和“重修或重做”的评分结论并承担相关一切后果。

本人签名: 日期： 2015 年 1 月 5 日

沈阳航空航天大学
课程设计任务书
课程设计名称
数据结构课程设计
专业
计算机科学与技术（物联网方向）
学生姓名
孙思
班级
34010105
学号
2013040101204
题目名称

起止日期
2015
年
1
月
5
日起至
2015
年
1
月
16
日止

课设内容和要求：
给出一张无向图，图上每一个顶点表示一个城市，顶点之间的边表示城市之间存在路径，边上的权值表示城市间的路经长度。利用弗洛伊德（Floyd）算法求解最短路径求解任意两个城市之间的最短路径问题。
参考资料：
《算法与数据结构》
《C语言程序设计》
教研室审核意见： 教研室主任签字：
指导教师（签名）

年

月

日
学 生（签名）

年

月

日
目 录

第一章 需求设计
1.1 题目介绍 1
1.2 功能要求 2
第二章 程序设计 3
2.1 详细设计 3
2.1.1 总体模块图 3
2.1.2 函数描述 4
2.2 主要算法描述 5
第三章 使用说明 6
3.1 用法说明 9
第四章 程序测试 11
4.1 运行结果 11
4.2 存在的缺陷 12
参考文献 13
附 录（关键部分程序清单） 14

19
沈阳航空航天大学课程设计报告
第一章 需求设计
1.1 题目介绍
给出一张无向图，图上每一个顶点表示一个城市，顶点之间的边表示城市之间存在路径，边上的权值表示城市间的路经长度。利用弗洛伊德（Floyd）算法求解最短路径求解任意两个城市之间的最短路径问题。
将问题分解为三个方面，第一个方面是对于无向图的存储问题，第二个方面是实现弗洛伊德（Floyd）算法求解最短路径，第三个方面是将最短路径输出。首先对于图的建立选择合适的存储结构，考虑到之后要用的弗洛伊德算法所以选择采用邻接矩阵存储无向图。然后采用弗洛伊德算法，该算法又叫插点法。是利用三重循环产生一个存储每个结点最短距离的矩阵，基本思想是设置一个n阶矩阵D(k)，D(k)[i][j]表示从i到j的路径长度，k表示运算步骤。用两个顶点之间边的权值作为路径长度，无边连接记做无穷，多次循环，向原路径加入新的顶点，若增加的顶点使得路径比原路径短，则用新路径代替原始路径，将顶点信息存储在另一个三维数组p中，p[v][w][u]存储的是由i到j路径经过的所有顶点。三重循环执行完毕最短路径的信息存储在两个数组中。最后将最短路径的信息输出。

1.2 功能要求
一个无向图用每个顶点代表城市，顶点之间边的权重表示城市之间的路径，将顶点信息和边的信息输入程序，即可得到每两个城市之间的最短路径长度值以及这条路径经过的城市。可以为建址问题提供参考。
设计环境：（1）WINDOWS 7系统
（2）VisualC++开发环境
开发语言：C语言

沈阳航空航天大学课程设计报告
第二章 程序设计
2.1 详细设计
2.1.1功能模块图
用弗洛伊德算法求解最短路径

主
函
数
输
出
最
短
路
径
信
息
调
用
弗
洛
伊
德
算
法
输
入
无
向
图
顶
点
及
权
值

图2.1功能模块图

2.1.2 函数描述
Find：根据名称得到指定顶点在顶点集合中的下标，利用此函数找到顶点所在位置，进而对无向图赋权值。

Create：创建无向图的邻接矩阵，因为每条边都有权值，创建的是无向网的邻接矩阵，用权值代替1，没有边连接则为无穷。

FLOYD：设置一个n阶矩阵D(k)，D(k)[i][j]表示从i到j的路径长度，k表示运算步骤。用两个顶点之间边的权值作为路径长度，无边连接记做无穷，多次循环，向原路径加入新的顶点，若增加的顶点使得路径比原路径短，则用新路径代替原始路径，将顶点信息存储在另一个三维数组p中，p[v][w][u]存储的是由i到j路径经过的所有顶点。三重循环执行完毕最短路径的信息存储在两个数组中。

主函数：在主函数里定义一个无向图，一个三维矩阵p，二维矩阵D，对各个函数进行调用，实现无向网的建立，运用弗洛伊德算法求解出最短路径，将路径长度以及经过的顶点信息输出。
2.2 主要算法描述

图2.2.1 FLOYD函数

图2.2.2 Find函数

图2.2.3 Main函数

图2.2.4 Create函数

沈阳航空航天大学课程设计报告
第三章 使用说明
3.1 用法说明
1. 将顶点数和边数输出，中间用空格隔开。

图3.1.1

2. 输入顶点信息。

图3.1.2

3. 依次输入每条边连接的两个顶点用空格间隔，边的权值。

图3.1.3

4. 得到每两个顶点城市间的最短距离以及经过的城市。

图3.1.4
.4

沈阳航空航天大学课程设计报告
第四章 程序测试
4.1 运行结果

图4.1

4.2 存在的缺陷
1. 无向图的顶点信息只能用一个字符表示。将存储顶点信息的字符型改为字符数组就可以完善该缺陷。
2. 将两点的最短路径输出时只能显示经过的顶点有哪些，无法显示真实的路径顺序。
3. 输入无向图信息只能用手动输入，无法用文件直接写入。
4. 输入不符合要求的数据会使程序自动停止。

沈阳航空航天大学课程设计报告
参考文献
[1] 张长海.C语言程序设计[M].北京：高等教育出版社，2006
[2] 吴启武.C语言课程设计案例精编.北京:清华大学出版社,2011.
[3] 郭翠英.C语言课程设计案例精编.北京:中国水利水电出版社,2004.
[4] 姜灵芝, 余键.C语言课程设计案例精编.北京:清华大学出版社,2008.
[5] 黄明, 梁旭, 万洪莉.C语言课程设计.北京:电子工业出版社,2006

沈阳航空航天大学课程设计报告
附 录（关键部分程序清单）
#include "stdio.h"
#include "stdlib.h"
#define MAX 20
#define INFINITY 9999
typedef bool PathMatrix[MAX][MAX][MAX];
typedef int DistanceMatrix[MAX][MAX];
typedef struct
{
int vexnum,arcnum;
char vexs[MAX];
int arcs[MAX][MAX];
}MGraph;

int Find(char vex, MGraph MG)//根据名称得到指定顶点在顶点集合中的下标 vex表示顶点
{ // return 如果找到则返回下标，否则返回０
int i;
for (i=0;i<MG.vexnum;i++) {
if (MG.vexs[i] == vex) {
return i;
}
}
return 0;
}

void Create(MGraph &G)
{
int i,j,k,v1,v2,w;
printf("请输入顶点数和边数:");
scanf("%d %d",&G.vexnum,&G.arcnum);
getchar();
for(i=0;i<G.vexnum;i++)
{
printf("请输入第%d个结点：",i+1);
scanf("%c",&G.vexs[i]);
getchar();
}
for(i=0;i<G.vexnum;i++)
for(j=0;j<G.vexnum;j++)
G.arcs[i][j]=INFINITY;
for(k=0;k<G.arcnum;k++)
{
char c1,c2;
printf("请输入与第%d条边相连的两条边v1 v2:",k+1);
scanf("%c",&c1);
getchar();
scanf("%c",&c2);
printf("请输入该边的权重：");
scanf("%d",&w);
getchar();
v1=Find(c1,G);
v2=Find(c2,G);
G.arcs[v1][v2]=w;
G.arcs[v2][v1]=w;

}
}

void FLOYD(MGraph G,PathMatrix &P,DistanceMatrix &D)
{
int v,w,u,i;
for(v=0;v<G.vexnum;++v)
for(w=0;w<G.vexnum;++w)
{
D[v][w]=G.arcs[v][w];
for(u=0;u<G.vexnum;++u)
P[v][w][u]=false;
if (D[v][w]<INFINITY)
{
P[v][w][v]=true;
P[v][w][w]=true;
}
}
for(u=0;u<G.vexnum;++u)
for(v=0;v<G.vexnum;++v)
for(w=0;w<G.vexnum;++w)
if (D[v][u]+D[u][w]<D[v][w])
{
D[v][w]=D[v][u]+D[u][w];
for(i=0;i<G.vexnum;++i)
P[v][w][i]=P[v][u][i]||P[u][w][i];
}
}

int main()
{
MGraph G;
int i,j,k;
Create(G);
PathMatrix p;
DistanceMatrix D;
FLOYD(G,p,D);
for(i=0;i<G.vexnum;i++)
for(j=0;j<G.vexnum;j++)
{
if(i==j)
continue;
else{
printf("%c 到%c 经过的顶点有:",G.vexs[i],G.vexs[j]);
for(k=0;k<G.vexnum;k++)
{
if(p[i][j][k]==0)
continue;
else
printf("%c ",G.vexs[k]);
}
printf("最短路径长度为: %d\n\n",D[i][j]);

}
}
return 0;
}

沈阳航空航天大学课程设计报告
课程设计总结：
此次课程设计中，我了解到了许多以前不太会的知识，也在对程序的不断的调试中认识到调试时的细心是很重要的，这些都让我受益匪浅。譬如，getchar()的使用，用在输入字符型数据的时候，getchar()可以将空格吸收从而避免将空格带入数据中。
在这次课程设计中，我还理解了数据结构给成个程序带来的简洁性以及函数的调用，数据结构将繁琐的程序分成几个部分，看起来简单易懂。这些都是我在以前的学习中不理解的，让我在这次课程设计中学习新知识的同时也感受到很多快乐，对C语言及以后要学习的一些专业课程也产生了浓厚的兴趣，同时我也意识到有很多知识是我不了解的，我还需要更努力的学习，来丰富学习生活，充实自我。
我会在以后的学习中尝试更多挑战，培养自己的能力。这次课程设计激发了我的兴趣，虽然只是简单的程序设计，但我也感受到了程序做完之后的兴奋与自豪，我会更加努力的。