资源描述：
《数据结构课程设计报告_最短路径C++.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、青岛理工大学琴岛学院设计报告课题名称：求解最优交通路径学院：计算机工程系专业班级：计算机科学与技术学号：#######学生：**指导教师：**青岛理工大学琴岛学院教务处2011年7月7日学生aaaa指导教师aaa课题名称求解最优交通路径设计时间2011/6/27-2011/7/8设计地点7-A-105设计目的（1）用二进制给每个字符进行编码，树中从根到每个叶子都有一条路径，对路径上的各分支约定：指向左子树的分支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列和作为各个对应的字符的编码，将输入的字符用“0”“1”表示出来，译
2、码的过程是输入“0”“1”代码显示输出相对应的字符。(2)要求学生根据离散数学或数据结构中最短路径算法进行程序编写。利用弗洛伊德算法结合实际情况，通过以每个点为源顶点求出每对定点之间的最短路径。通过二维数组A存放当前最短路径长度，最后输出对应的最短路径长度。（3）制作一个查阅词典的雏形，主要利用串的匹配算法KMP算法并结合文件的一些知识。设置目标串和模式串的字符比较，查找出需要查找的单词或者是与需要查找的单词有部分的相同字母的单词。设计内容（包括设计过程、主要收获、存在问题、解决措施、建议，不少于2000字）一、运行环境进入查询界面是否继续查询选择查看
3、各城市对应的编号判断前后两次输入的编号是否在查询范围之内输入要查询的两个城市输出两站点路径及最短距离退出否是YNMicrosoftVisualC++6.0不仅仅是一个编译器。它是一个全面的应用程序开发环境。VisualC++采用的框架是MFC。MFC不仅仅是一个类库。MFC是一个很大的、扩展了的C++类层次结构，它能使开发Windows应用程序变得更加容易。二、系统流程图开始输入要查询的两个城市编号m_v0,m_v1OnOK()接收城市编号CreatUDN()创建界面ShortestPath()计算出最短路径及距离Ppath()计算中间点Output(
4、)输出起点和终点输出最短路径及距离结束一、函数及变量说明(一)相关函数（1）首先创建CreatUDN()函数生成一个拥有25个城市，30条公路的交通图，并录入两城市之间的权值即距离，其中顶点对应于城市，边对应于城市间直接通路，根据实际问题，在生成的交通图中所有的通路都是双向的，即如果A城市到B城市有直接通路，且里程为k千米，则B城市到A城市也有直接通路，并且里程同样为k千米。创建对话框提示用户输入发出城市和终到城市的序号，再调用ShortestPath()函数求出最短路径，由Output()函数输出结果，并利用ppath（）函数输出最短路径沿途经过的点
5、。（2）ShortestPath()利用了数据结构中图论中的最短路径相关的弗洛伊德算法。Output()函数把计算的结果格式化输出。(二)具体实现A.根据要求地图导入及界面设计1.将所给地图保存为bmp文件，在资源Bitmap中导入。并在View类中的OnDraw()函数中添加如下代码：voidCMyView::OnDraw(CDC*pDC){……CBitmapbmp;bmp.LoadBitmap(IDB_BITMAP1);BITMAPbmpInfo;bmp.GetBitmap(&bmpInfo);CDCdcMemory;……pDC->BitBlt(n
6、X,nY,bmpInfo.bmWidth,bmpInfo.bmHeight,&dcMemory,0,0,SRCCOPY);dcMemory.SelectObject(pOldBitmap);……}2.在界面的左侧添加相关提示信息，以便用户将城市与其代号相对应，相关代码如下：voidCMyView::OnDraw(CDC*pDC){……pDC->TextOut(20,40,"城市的代号：");pDC->TextOut(20,60,"0乌鲁木齐");……pDC->TextOut(20,540,"24深圳");……}3.实现界面如图1：图1A.具体功能实现及
7、相应的弗洛伊德算法首先,建立查询信息对话框，使用户能够录入需要查询的城市代号，并显示路径长度及最短路径沿途经过的城市。并相应地添加如下变量intm_v0;intm_v1;intm_lj;CStringm_zd;具体代码如下：#defineMAXV25//最大顶点个数#defineINF32767//用32767表示∞//以下定义邻接矩阵类型typedefstruct{intno;//顶点编号charname[10];//顶点名称}VertexType;//顶点类型typedefstruct//图的定义{intedges[MAXV][MAXV];//邻接
8、矩阵intvexnum,arcnum;//顶点数，弧数VertexTypevexs[MAXV]
