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

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