数据结构课程设计报告-最短路径C++

1/1数据结构课程设计报告_最短路径C++青岛理工高校琴岛学院

设计报告

课题名称：求解最优交通路径

学院：计算机工程系

专业班级：计算机科学与技术

学号：#######

同学：**

指导老师：**

青岛理工高校琴岛学院教务处

2023年7月7日

图1

B.详细功能实现及相应的弗洛伊德算法

首先,建立查询信息对话框，使用户能够录入需要查询的城市，并显示路径长度及最短路径沿途经过的城市。并相应地添加如下变量intm_v0;intm_v1;intm_lj;CStringm_zd;

详细代码如下：

#defineMAXV25//最大顶点个数

#defineINF32767//用32767表示∞

//以下定义邻接矩阵类型

typedefstruct

{intno;//顶点编号

charname[10];//顶点名称

}VertexType;//顶点类型

typedefstruct//图的定义

{intedges[MAXV][MAXV];//邻接矩阵

intvexnum,arcnum;//顶点数，弧数

VertexTypevexs[MAXV];//存放顶点信息

}MGraph;//图的邻接矩阵类型

1.通过函数CreatUDN存放城市路径信息，输入顶点之间的路径长度，创建带权图的邻接矩阵。

voidCTDialog::CreatUDN

{

MGraph*g=(MGraph*)malloc(sizeof(MGraph));

inti,j;

for(i=0;iedges[i][j]=INF;

if(i==j)g->edges[i][j]=0;//初始化置任意两城市之间距离为无穷大，即两城市之间没有直接通路

{

if(i!=j)

m_zd="没有路径";

}

elseif(x==i

CStringzfc;

zfc.Format("%d",i);//输出路径上的起点

m_zd+=zfc;

ppath(path,i,j);//输出路径上的中间点

zfc.Format("-->%d",j);//输出路径上的终点

m_zd+=zfc;

}

}

}

4.输出最短路径函数，递归输出从顶点i到j的最短路径中依次经过的顶点，直到path[i][j]=-1，即没有中间顶点为止。

voidCTDialog::ppath(intpath[MAXV],inti,intj)

{

intk;

k=path[i][j];

if(k==-1)return;

ppath(path,i,k);

CStringzfc;

zfc.Format("-->%d",k);

m_zd+=zfc;

ppath(path,k,j);

}

四．调试分析（调试过程中消失的问题及处理方式）

A.调试消失的界面

1)进入程序弹出查询信息对话框如图2：

图2

2)输入查询信息，显示路径长度及最短路径，假如输入不在0~24之内，提示出错。如图3、图4：

图3图4

3)查询胜利后，可修改城市反复查询。

B．消失的问题及解决方式

1)提出问题：地图导入后，起初无法导入正常导入到VC++6.0，而6.0以上的版本可以，后来导入经过调试无法在界面上显示。

分析问题：VC++6.0版本较低，无法支持辨别率较高的图形。图形无法显示的问题，可能是图形并没有与界面联系起来。

解决方法：在将地图导入之前，将地图的保存为辨别率较低的bmp位图，即可导入到VC++6.0。界面无法显示，是没有将位图画刷选入。添加相关函数pDC->BitBlt(nX,nY,bmpInfo.bmWidth,bmpInfo.bmHeight,&dcMemory,0,0,SRCCOPY)即可显示。

2)提出问题：将C语言代码添加到相关函数中，系统无法识别无法编译。

分析问题：应当添加一些C++可以识别的C的相关信息，使之联系起来。

解决方法：包含进相关头文件，即添加#include、#include。3)提出问题：一开头将主要代码添加到View类中，在对话框接收到参数通过(WPARAMwParam,LPARAMlParam)实现参数的传递，同时却需要在View类中接收和初始化的一些列问题，增加了不必要的麻烦。

分析问题：可以通过其他方式，削减参数传递过程。

解决方法：直接在对话框添加的类TDialog中，添加代码，省去了参数传递的麻烦。

4)提出问题：将课本上的弗洛伊德算法的相关代码添加后，与实际状况不符，课本上的路径都是全部两点之间的，而现实的交通图中是从用户输入的起始点到目的点。

分析问题：在参数传递时传递接收的起始点和目的点，然后只推断这两个点就可以了。

解决方法：修改推断语句，增加可通过的状况，if(x==i&&y==j&&A[i][j]==INF)和if(x==i&&y==j)添加双向的状况。

5)消失问题：将查询后的路径长度和最短路径在地图界面上显示。通过pDC->Textout显示。而输出过程中，需要各个函数的递归实现，通过参数传递，在View中输出，显得不太现实。在TDialog中输出，添加CDC*pDC后，依旧无法显示。包含入相关头文件#include"最短路径View.h"依旧无效。在相关函数中添加代码CDC*pDC=GetDC；也没有得到想要的显示。

分析问题：在现有学问和自己所能查到资料中，这种方法不便实现，即使实现后，只能查一次，反复查找需要刷新屏幕。工作量大。

解决方法：在查询对话框中添加路径长度和最短路径的内容，直接在对话框中显示，即可反复查找，又省去了pDC不能使用的麻烦。

6)