《朱超 c++课设.》由会员分享，可在线阅读，更多相关《朱超 c++课设.（19页珍藏版）》请在金锄头文库上搜索。
1、沈阳理工大学课程设计专用纸 I 摘 要 本文实现了图的最短路径存储及 BFC 遍历，采用 Visual C+ 6.0 的控制台工程和 MFC 工程分别实现了邻接矩阵在桌面上的的显示以及实现对图的广度遍历程序，图是 一种比较复杂的非线性数据结构，广度优先搜索（BFS）是图的遍历的方法之一，它的 目的是系统地展开并检查图中的所有节点，以找寻结果。而采用邻接矩阵可以实现图 的最短路径存储，提高程序的优越性。 关键词：邻接矩阵；类的成员函数；广度优先搜索；控制台工程；MFC 图形界面 沈阳理工大学课程设计专用纸 II 目 录 1 需求分析1 2算法基本原理1 3类设计2 3.1 类的概述2 3.2 类
2、的接口设计 2 3.3 类的成员函数的设计 3 4基于控制台的应用程序8 4.1 主函数设计 8 4.2 运行结果及分析 9 5基于 MFC 的应用程序.9 5.1 图形界面设计 10 5.2 程序代码设计 12 5.3 运行结果及分析 15 结 论.16 参考文献.17 沈阳理工大学课程设计专用纸 0 1 需求分析 图作为一种非线性数据结构，被广泛应用与多个技术领域本设计依靠类的成员函 数完成以下功能：采用图的邻接矩阵实现最短路径问题中图的存储；采用循环队列实 现图的广度优先搜索（BFS） 。采用 Visual C+ 6.0 的控制台工程和 MFC 工程分别实现 邻接矩阵在桌面上的显示以及实
3、现对图的广度遍历程序。 2 算法基本原理 (1) 邻接矩阵是表示节点之间的相邻接关系的矩阵。若 G 是有 n 个节点的图，则 G 的邻接矩阵是如下定义的 n X n 矩阵。如图所示图 2 的邻接矩阵如下： 图 1 无向图 G 图 2 G 的邻接矩阵 (2) 广度优先搜索遍历类似于树的按层次遍历的过程。假设从图中某顶点 v 之出 发，在访问了 v 之后依次访问 v 的各个未曾访问过的邻接点，然后分别从这些邻 接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点”先于“后被 访问的顶点的邻接点”被访问，直至图中所有已被访问的顶点的邻接点都被访问 到。若此时图中尚有顶点未被访问，则另选图中一个
4、未曾被访问的顶点做起始点， 重复上述过程，直至图中所有顶点都被访问到为止。换句话说，广度优先搜索遍 历图的过程是以 v 为起始点，由近至远，依次访问和 v 有路径相通且路径长度为 1,2,.的顶点。例如，对图 4 所示无向图进行广度优先搜索遍历的过程：首先访 问 1 和 1 的邻接点 2 和 3，然后依次访问 2 的邻接点 4 和 5 及 3 的邻接点 6 和 7， 最后访问 4 的邻接点 8.由于这些顶点的邻接点均已被访问，并且图中所有顶点都 被访问，由此完成了图的遍历。得到的顶点访问序列为：1-2-3-4-5-6-7- 8。 1 4 3 20 1 1 1 1 0 1 0 1 1 0 1 1
5、 0 1 0 沈阳理工大学课程设计专用纸 1 图 3 无向图 3 类设计 3.1 类的概述 本设计面临的计算问题的关键是矩阵运算。本题设计的关键，是对图的广度优先 搜 索算法的设计，由于使用循环队列存储，就要将广度优先搜索的算法扩展到矩阵 中。 首先，应设计无向图类 graph，然后设计成员变量，最后还要设计成员函数，实现 对邻接矩阵的输出 cout()，广度优先搜索函数 BFS()，然后用队列循环。考虑到图的初 始化比较复杂，需要输入矩阵信息，还要设计函数()实现对矩阵的初始化。 3.2 类的接口设计 #include #define Length 10 #define ERROR 0 #d
6、efine TRUE 1 using namespace std; 沈阳理工大学课程设计专用纸 2 class XU_DL private: int *item; int front; int rear; int maxlength; public: XU_DL(int length=Length) /对队列的初始化 if(lengthgraphi*m+j; for(i=0;in; Graph a(n); a.Set_Data(); cout“广度优先搜索的序列为:“; a.bfs1(0); return 0; 沈阳理工大学课程设计专用纸 8 4.2 程序运行结果及分析 程序运行结果如图 4
7、所示。 图 4 程序运行结果 由图 4 中得出，程序运行后首先创建了图类的对象，调用构造函数，产生一个顶点数 为 5，边数为 6 的无向图，然后初始化这个图，从键盘输入矩阵信息，在主函数中直接调 用邻接矩阵输出函数和广度优先搜索结果。 5 基于 MFC 的应用程序 5.1 图形界面设计 首先在 VC 中建立 MFC AppWizard(exe)工程，名称为 BFS，并在向导的 Step1 中 选择 Dialog based，即建立基于对话框的应用程序，如下图 5 所示。 沈阳理工大学课程设计专用纸 9 图 5 建立 MFC AppWizard(exe)工程 打开 MFC AppWizard(e
8、xe)工程，根据要求建立基本对话框，如图 6 所示。 图 6 建立基本对话框的应用程序 将对话框资源中的默认对话框利用工具箱改造成如下界面，如图 7 所示。 沈阳理工大学课程设计专用纸 10 图 7 对话框 图 7 所示的界面中包含了 1 个 Static Text 控件，3 个 Button 控件，和 12 个 Edit Box 控件，控件的基本信息如下表 1 所示。 表 1 控件基本信息 控件类别控件 ID控件 Caption 说明 Static Text IDC_STATI C 5 顶点 6 条 边无向图 IDC_BUTT ON_LJ 邻接矩阵 IDC_BUTT ON_SD 深度优先遍
9、历 Botton IDC_BUTT ON_Exit 退出 IDC_EDIT_ 12 IDC_EDIT_ 15 Edit Box IDC_EDIT_ 23 邻接矩阵的 权值 沈阳理工大学课程设计专用纸 11 IDC_EDIT_ 25 IDC_EDIT_ 34 IDC_EDIT_ 35 IDC_EDIT_ 45 5.2 程序代码设计 为了能够将对话框界面上的控件能够与代码联系起来，需要为 12 个 Edit Box 控件 建立 Member Variables，按 Ctrl+w 键进入 MFC ClassWizard 界面，选择 Member Variables 选项卡，可显示成员变量设置界面，如
10、图 8 所示。 图 8 成员变量设置界面 通过该界面设置与 24 个 Edit Box 控件对应的成员变量，具体如表 2 所示。 表 2 控件基本信息 控件 ID成员变量类型成员变量名称 IDC_EDIT_12 IDC_EDIT_45intm_e12m_e45 沈阳理工大学课程设计专用纸 12 IDC_EDIT_LJCStringm_LJ IDC_EDIT_SDCStringm_SD 下面是编写代码的重要阶段，可以借鉴在设计基于 DOS 界面的控制台应用程序的 代码，并将其作必要的改写，具体改写的步骤与内容如下。 (1)将 BFS.cpp 文件重新命名为 BFS.h，并将其加入MFC工程。 (
11、2)修改 BFS.h 文件具体包括： 将显示矩阵 printf()函数注释掉，在图形界面的程序上已经不需要个函数承担 输出功能了； 将主函数注释掉，已经不需要主函数进行操作了； 将深度优先搜索函数 BFS()和 dfs()的 cout 语句去掉，不需要也不能够使用 cout 流实现输出； 将 graph 类的所有成员改为公共的，方便给 graph 类的成员变量赋值 在 graph 类中声明一个 CString 型的变量 Dstr，用来保存函数输出结果的字符 串； 在函数 dfs 内声明一个 CString 型变量 temp，用来临时存储函数输出的结果， 并添加以下语句 temp.Format(
12、“%d,“,i+1)；Dstr+=temp； (3)在对话框类的实现文件 CBFS_MFCDlg.cpp 中加入#include “BFS.h“，以实 现在该文件中可使用 graph 类。 (4)在对话框类的实现文件 CBFS_MFCDlg.cpp 中加入 graph g(5,6);,构造一个 5 顶点的无向图； (5)编写邻接矩阵按钮的消息处理函数，实现图的邻接矩阵在界面上的显示， 具体代码如下： void CBFS_MFCDlg:OnButtonLj() / TODO: Add your control notification handler code here CString str1
13、010; UpdateData(); g.e01=m_e12;g.e10=m_e12; 沈阳理工大学课程设计专用纸 13 g.e02=m_e13;g.e20=m_e13; g.e03=m_e14;g.e30=m_e14; g.e04=m_e15;g.e40=m_e15; g.e12=m_e23;g.e21=m_e23; g.e13=m_e24;g.e31=m_e24; g.e14=m_e25;g.e41=m_e25; g.e23=m_e34;g.e32=m_e34; g.e24=m_e35;g.e42=m_e35; g.e34=m_e45;g.e43=m_e45; m_LJ=“; Update
14、Data(0); for (int i=0;i5;i+) for (int j=0;j5;j+) strij.Format(“%i,“,g.eij); m_LJ+=strij; m_LJ+=“rn“; UpdateData(0); (6)编写深度优先遍历按钮的消息处理函数，实现对图的深度遍历，并显示到 界面上，具体代码如下： void CDFS_MFCDlg:OnButtonSd() / TODO: Add your control notification handler code here CString str1010; UpdateData(); g.e01=m_e12;g.e10=m
15、_e12; g.e02=m_e13;g.e20=m_e13; g.e03=m_e14;g.e30=m_e14; g.e04=m_e15;g.e40=m_e15; g.e12=m_e23;g.e21=m_e23; g.e13=m_e24;g.e31=m_e24; g.e14=m_e25;g.e41=m_e25; g.e23=m_e34;g.e32=m_e34; g.e24=m_e35;g.e42=m_e35; 沈阳理工大学课程设计专用纸 14 g.e34=m_e45;g.e43=m_e45; g.Dstr=“; g.DFS(); m_SD=“; UpdateData(0); m_SD=g.Dstr; UpdateData(0); (7)退出按钮代码如下： void CGuassLineGUIDlg:OnBUTTONExit() / TODO: Add your control notification handler code here OnOK(); 5.3 运行结果及分析 运行程序后，首先出现的界面如图 9 所示。 图 9 程序初始运行界面 在编辑框输入邻接矩阵的权值后，单击邻接矩阵按钮，可将这个 5 顶点的无向图 邻接矩阵在界面上
