数据结构课程设计报告--Dijkstra算法求最短路径(3)

第五章 测试结果

5.1测试结果：

11

注意问题：

1、输入顶点个数：最大不超过25，请输入罗马数字，若输入其他符号，无意义；

2、以“字母 字母 数字”的格式输入图的信息，输入第一个字母为原点，第二个字母为终点，输入“数字”为权值，最后输入一个“字母”为顶点输入。输入完成；

3、在输入完成后，屏幕显示邻接矩阵与最短路径。

第六章 学习心得体会

通过对本次课程设计的学习与交流，使我学习到一部分很重要的关于编程

方面思想，同时也获得了部分学习其他学科的方法。学习重在于体会，体会这种学科给我带来的思考，给我带来由浅入深的演算心得。做一次课程设计，不仅仅是为了完成某项任务，而在于是否能从这次任务中总结出一些处理同类任务的方法和技巧。每次全力的付出，都会有或多或少的收获。通过对本次课程设计涉及的问题的分析和处理，了解到学习数据结构对编程的技巧和思想方法。以前也了解过数据结构相关的书籍，但没有深入的学习，本次上机课程设计从选题上也把学习的方法应用其中，在编程时算法的理解和分析十分重要，首先的弄懂它的基本框架，用什么来算法来实现，最后通过查找部分资料，修改调试，总结心得，就是一种进步。

第七章 参考文献

6.1：严蔚敏 吴伟明 编著的《数据结构》（C语言版） 6.2：杨晓波 主编 王 弘 王聪华 胡 永 副主编的

12

《数据结构实验指导》（C语言版）

附件：

#include #include

#define MAX_VERTEX_NUM 25 //最大顶点个数 #define INFINITY 3000//最大值

typedef char VertexType;//定义图的顶点为字符型

typedef int VRType; //顶点关系类型 typedef int InfoType;//该弧相关信息

typedef struct ArcCell{ VRType adj;//权值 InfoType *info;//弧相关信息的指针 }ArcCell;

typedef struct{ VertexType vexs[MAX_VERTEX_NUM];//一维数组，存储顶点 ArcCell arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//邻接矩阵 ：二维数组，存储边和弧 int vexnum,arcnum;//图的当前顶点数和弧数 }MGrph; //邻接矩阵表示的图

/* 确定位置函数 */ int LocateVex(MGrph *G,VertexType v) {

int j,b;

for(b=0;bvexnum;b++)//在所有顶点中寻找 if(G->vexs[b]==v)//找到所找的顶点在b位置 { j=b; break; }//if return(j); } //LocateVex

/* 有向图的建立 */ void Creat_YG(MGrph *G) {

13

int i,k,j,n;

VertexType v1,v2; int w=1; printf(\请输入顶点个数和弧数 如括号里的方式（3,3）:\读入顶点个数和弧的个数 scanf(\读出边和弧的信息 printf(\换行输出 for(i=0;ivexnum;i++) { printf(\请输入图的第%d个顶点:\输入指定的顶点 w++; fflush(stdin); scanf(\ printf(\ }

for(i=0;ivexnum;i++) for(j=0;jvexnum;j++) { G->arcs[i][j].adj=INFINITY; G->arcs[i][j].info=NULL; }

for(k=0;karcnum;k++) {//输入各弧并构造邻接矩阵 printf(\请输入边的起点和终点和权值如（v1,v2,n）:\起始点和终点和两点之间对应的权值

fflush(stdin); scanf(\ printf(\ i=LocateVex(G,v1);//确定v1的位置 j=LocateVex(G,v2);//确定v2的位置 G->arcs[i][j].adj=n;//边的权值赋为1，如需要权值操作则相应修改一下即可 G->arcs[i][j].info=NULL;//如需要有相关信息则相对应输入，在这里我设置为空 }//第二个for getchar(); } //Creat_YG

void juzhen(MGrph *G){//用矩阵来存储并显示出结果 int i,j,k;

printf(\邻接矩阵显示：\\n\ printf(\

for(i=0;ivexnum;i++) printf(\ for(j=0;jvexnum;j++) {

14

printf(\ printf(\ for(k=0;kvexnum;k++) {

if(G->arcs[j][k].adj

else printf(\ 3000\无权值的直接输出最大值

}

} }

void Short(MGrph *G,int path[],int i,int w){

//递归函数是用来输出从源点出发到终点之前的顶点 //思想是patn[]数组来表示前驱顶点的位置，然后递归输出每个顶点的前驱 int k; k=path[i];

if(k!=w) Short(G,path,k,w );

printf(\输出k位置的顶点值 }

void ShortestPath(MGrph *G,int w){ //Dijkstrs算法应用 int i,k,m,n,min;

int final[30],path[30],D[30]; //定义三个数组，final[]标记该顶点是否在最短路径上 //path[]用来记录顶点的前驱顶点的位置，D[]是用来记录从源点到该点的最短路径长度

for(i=0;ivexnum;i++) { path[i]=w;//首先把所有顶点的前驱顶点的位置赋值为w位置，也就是源点的位置 final[i]=0;//这是一个标记数组，一开始所有顶点位置对应的数组值全部标记为0 D[i]=G->arcs[w][i].adj;//D[]是用来记录最短路径的长度，一开始把所有顶点到源点的的距离赋值给它 }

D[w]=0;final[w]=1;path[w]=-100;//源点位置的D[w]为0，final[w]=1标记已经入集合，path[w]=-100，表示该前驱为-100 for(m=1;mvexnum;m++) { min=INFINITY;//首先赋值为机内最大值 for(k=0;kvexnum;k++)

15