朱超 c++课设

1、沈阳理工大学课程设计专用纸 I 摘 要本文实现了图的最短路径存储及 BFC 遍历，采用 Visual C+ 6.0 的控制台工程和MFC 工程分别实现了邻接矩阵在桌面上的的显示以及实现对图的广度遍历程序，图是一种比较复杂的非线性数据结构，广度优先搜索（BFS）是图的遍历的方法之一，它的目的是系统地展开并检查图中的所有节点，以找寻结果。而采用邻接矩阵可以实现图的最短路径存储，提高程序的优越性。关键词：邻接矩阵；类的成员函数；广度优先搜索；控制台工程；MFC 图形界面沈阳理工大学课程设计专用纸 II 目 录 1 需求分析.12算法基本原理.13类设计.23.1 类的概述.23.2 类的接口设计 .

2、23.3 类的成员函数的设计 .34基于控制台的应用程序.84.1 主函数设计 .84.2 运行结果及分析 .95基于 MFC 的应用程序.95.1 图形界面设计 .105.2 程序代码设计 .125.3 运行结果及分析 .15结 论.16参考文献.17沈阳理工大学课程设计专用纸 01 需求分析图作为一种非线性数据结构，被广泛应用与多个技术领域本设计依靠类的成员函数完成以下功能：采用图的邻接矩阵实现最短路径问题中图的存储；采用循环队列实现图的广度优先搜索（BFS） 。采用 Visual C+ 6.0 的控制台工程和 MFC 工程分别实现邻接矩阵在桌面上的显示以及实现对图的广度遍历程序。2 算法

3、基本原理(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。14320 1 1 11 0 1 01 1 0 11 0 1 0沈阳理工大学课程设计专用纸 1图 3 无向图3 类设计3.1

5、类的概述本设计面临的计算问题的关键是矩阵运算。本题设计的关键，是对图的广度优先搜 索算法的设计，由于使用循环队列存储，就要将广度优先搜索的算法扩展到矩阵中。 首先，应设计无向图类 graph，然后设计成员变量，最后还要设计成员函数，实现对邻接矩阵的输出 cout()，广度优先搜索函数 BFS()，然后用队列循环。考虑到图的初始化比较复杂，需要输入矩阵信息，还要设计函数()实现对矩阵的初始化。3.2 类的接口设计 #include#define Length 10 #define ERROR 0 #define TRUE 1 using namespace std; 沈阳理工大学课程设计专用纸

6、2 class XU_DL private: int *item; int front; int rear; int maxlength; public: XU_DL(int length=Length) /对队列的初始化 if(lengthLength)length=Length; item=new int length; maxlength=length; front=0; rear=0; 3.3 类的成员函数的设计XU_DL() /析构函数销毁队列 delete item; void ClearXU_DL() /清空队列 front=rear=0; int Getlength() /获得

7、长度 沈阳理工大学课程设计专用纸 3 if(rear=front) return ERROR; return (rear-front)+maxlength)%maxlength; int Inser(int e) /插入数据 e if(rear+1)%maxlength=front)return ERROR; /队满时的判断语句 rear=(rear+1)%maxlength; itemrear=e; return TRUE; int Gethand() /获得队头元素,并删除该数 int e; if(rear=front)return ERROR; /队列为空事的判断语句 e=item(fr

8、ont+1)%maxlength; front+; return e; int Deletedate(int e) /获取数据并删除该数 if(rear=front)return ERROR; /队列为空 front=(front+1)%maxlength; e=itemfront; return TRUE; void Output() if(front=rear)coutThe queue is null!endl;return; coutThe queue length is :Getlength()endl; coutThe queues content is :; 沈阳理工大学课程设计

9、专用纸 4 for(int i=1;iGetlength();i+) coutitemi; coutitemiendl; int Output1(int s,int m) int temp; temp=Gethand(); if(s=m)couttemp; else couttemp; return temp; ; class Graph:public XU_DL private: int n; /结点个数的平方 int m; /节点的个数 int *graph; int *visited; public: Graph(int n1) n=n1*n1; m=n1; graph=new int

10、n; visited=new int n1; void Set_Data() 沈阳理工大学课程设计专用纸 5 /memset(visited,0,sizeof(visited); cout请输入图的关系矩阵,不可达或自身到自身的则为 0，能到达的两点为 1,请按这种方式输入关系矩阵:endl; int i,j; for(i=0;im;i+) for(j=0;jgraphi*m+j; for(i=0;im;i+) visitedi=0; void bfs(int v) /把以某个点的所有相邻的点都包含进去了 int i;bool frag(false); ClearXU_DL(); frag=t

11、rue; while(frag) Inser(v); visitedv=1; for(i=v;im;i+) if(visitedi=0)&graphv*m+i=1)Inser(i);visitedi=1; for(i=0;im;i+) if(visitedi=1)frag=false; else frag=true; v=i; break; 沈阳理工大学课程设计专用纸 6 Output(); void bfs1(int v) /front 的值会改变 int i,j,s=0; bool frag(false); ClearXU_DL(); frag=true; while(frag)

12、Inser(v); visitedv=1; while(Getlength()!=0) s+; i=Output1(s,m); for(j=0;jm;j+) if(visitedj=0)&graphi*m+j=1) Inser(j); visitedj=1; for(i=0;im;i+) if(visitedi=1)frag=false; else 沈阳理工大学课程设计专用纸 7 frag=true; v=i; break; coutendl; ; 4 基于控制台的应用程序由于类的设计较为简单，将类和主函数放在同一个文件中，方便调试，首先声明类，进行类的设计，然后设计主函数，直接在主函

13、数中实现类，并输出邻接矩阵和广度优先搜索结果。4.1 主函数设计int main() int n; coutn; Graph a(n); a.Set_Data(); cout广度优先搜索的序列为:; a.bfs1(0); return 0; 沈阳理工大学课程设计专用纸 84.2 程序运行结果及分析 程序运行结果如图 4 所示。 图 4 程序运行结果由图 4 中得出，程序运行后首先创建了图类的对象，调用构造函数，产生一个顶点数为 5，边数为 6 的无向图，然后初始化这个图，从键盘输入矩阵信息，在主函数中直接调用邻接矩阵输出函数和广度优先搜索结果。5 基于 MFC 的应用程序5.1 图形界面设计首

14、先在 VC 中建立 MFC AppWizard(exe)工程，名称为 BFS，并在向导的 Step1 中选择 Dialog based，即建立基于对话框的应用程序，如下图 5 所示。 沈阳理工大学课程设计专用纸 9 图 5 建立 MFC AppWizard(exe)工程打开 MFC AppWizard(exe)工程，根据要求建立基本对话框，如图 6 所示。 图 6 建立基本对话框的应用程序将对话框资源中的默认对话框利用工具箱改造成如下界面，如图 7 所示。 沈阳理工大学课程设计专用纸 10 图 7 对话框图 7 所示的界面中包含了 1 个 Static Text 控件，3 个 Button 控

15、件，和 12 个 Edit Box 控件，控件的基本信息如下表 1 所示。 表 1 控件基本信息控件类别控件 ID控件 Caption说明Static TextIDC_STATIC5 顶点 6 条边无向图IDC_BUTTON_LJ邻接矩阵IDC_BUTTON_SD深度优先遍历BottonIDC_BUTTON_Exit退出IDC_EDIT_12 IDC_EDIT_15IDC_EDIT_23 IDC_EDIT_25IDC_EDIT_34 IDC_EDIT_35Edit BoxIDC_EDIT_45邻接矩阵的权值沈阳理工大学课程设计专用纸 115.2 程序代码设计为了能够将对话框界面上的控件能够与代

16、码联系起来，需要为 12 个 Edit Box 控件建立 Member Variables，按 Ctrl+w 键进入 MFC ClassWizard 界面，选择 Member Variables 选项卡，可显示成员变量设置界面，如图 8 所示。 图 8 成员变量设置界面 通过该界面设置与 24 个 Edit Box 控件对应的成员变量，具体如表 2 所示。表 2 控件基本信息控件 ID成员变量类型成员变量名称IDC_EDIT_12 IDC_EDIT_45intm_e12m_e45IDC_EDIT_LJCStringm_LJIDC_EDIT_SDCStringm_SD 下面是编写代码的重要阶段，

17、可以借鉴在设计基于 DOS 界面的控制台应用程序的代码，并将其作必要的改写，具体改写的步骤与内容如下。 (1)将 BFS.cpp 文件重新命名为 BFS.h，并将其加入MFC工程。(2)修改 BFS.h 文件具体包括：将显示矩阵 printf()函数注释掉，在图形界面的程序上已经不需要个函数承担输出功能了；沈阳理工大学课程设计专用纸 12将主函数注释掉，已经不需要主函数进行操作了； 将深度优先搜索函数 BFS()和 dfs()的 cout 语句去掉，不需要也不能够使用 cout流实现输出；将 graph 类的所有成员改为公共的，方便给 graph 类的成员变量赋值在 graph 类中声明一个

18、CString 型的变量 Dstr，用来保存函数输出结果的字符串；在函数 dfs 内声明一个 CString 型变量 temp，用来临时存储函数输出的结果，并添加以下语句 temp.Format(%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_MF

19、CDlg:OnButtonLj() / TODO: Add your control notification handler code here CString str1010; UpdateData(); g.e01=m_e12;g.e10=m_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_e3

20、4; g.e24=m_e35;g.e42=m_e35;g.e34=m_e45;g.e43=m_e45; m_LJ=; UpdateData(0);沈阳理工大学课程设计专用纸 13for (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 h

21、andler code hereCString str1010;UpdateData();g.e01=m_e12;g.e10=m_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;g.e34=m_e45;g.e43=m_e45; g.Dstr=;g.DFS(

22、);m_SD=; UpdateData(0);m_SD=g.Dstr;UpdateData(0);(7)退出按钮代码如下：void CGuassLineGUIDlg:OnBUTTONExit() / TODO: Add your control notification handler code here沈阳理工大学课程设计专用纸 14OnOK();5.3 运行结果及分析运行程序后，首先出现的界面如图 9 所示。图 9 程序初始运行界面在编辑框输入邻接矩阵的权值后，单击邻接矩阵按钮，可将这个 5 顶点的无向图邻接矩阵在界面上显示出来，如图 10 所示。图 10 程序运行后的界面单击退出按钮后，程序能够正常实现退出。