资源描述:
《Visual C++ 60调试功能 图解教程(4)--实例》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、VisualC++6.0调试功能图解教程(4)--实例三图 1.实验目的熟悉图的两种常用的存储结构,以及在这两种存储结构上的两种遍历图的方法,即深度优先遍历和广度优先遍历。进一步掌握递归算法的设计方法。关于各种典型著名的复杂算法,在上机实习方面不做基本要求。更适合于安排大型课程设计。二.需求分析 本程序演示用C++编写,完成有向图的创建,用Prim算法实现最小生成树,实现边的插入和删除.输入值的范围:创建图时要求输入的结点个数不大于MaxVertices的值.在插入边时要求原图不存在起点和终点之间边,并且插入的边不是矩阵对角线上的边.输入的数据类型为整形.输出形式:以邻接矩阵的
2、形式输出图的数据项.如果操作非法则给出错误信息.测试数据A创建5个顶点4条边的图:输入顶点分别为1,2,3,4,5;1和2之间,2和3之间,3和4之间,4和5之间的权值分别为10,20,30,40.得到图:输出顶点的信息(整型):12345输出邻接矩阵: 1:010100010001000 2:100002010001000 3:100010000301000 4:100010001000040 5:10001000100010000B顶点4和3之间插入一条权值为50边得输出顶点的信息(整型):12345输出邻接矩阵: 1:010100010001000 2:100002010001
3、000 3:100010000301000 4:1000100050040 5:10001000100010000 C删除顶点4和3之间的边得 输出顶点的信息(整型):12345输出邻接矩阵: 1:010100010001000 2:100002010001000 3:100010000301000 4:100010001000040 5:10001000100010000三.设计概要(1)为了实现上述程序的功能,需要定义图的抽象数据类型:ADTGraphis{数据对象:D={ai
4、ai∈IntegerSet,i=0,1,2,…,n,n≥0}基本操作:CreatG()操作结果:创建有
5、向图InsertE()初始条件:有向图已经存在操作结果:插入一条边DeleteE()初始条件:有向图已经存在操作结果:删除一条边}ENDADTBiTree(2)本程序包含一个类和一个结构体类型A无向图类AdjMWGraph有7个函数 1主函数 main() 2.构造函数 AdjMWGraph() 3.创建图函数 CreatG(intn,inte) 4.插入边函数
6、 InsertE() 5.删除边函数 DeleteE() 6.求最小生成树Prim算法函数 Prim()B结构体类型MinSpanTree(3)本程序的两个文件1.头文件 Graph.h2.源文件 Graph.cpp(4)函数之间的关系 四.详细设计 1//Graph.h 2#include "iostream" 3#include 4#include 5using namespace std; 6c
7、onst int MaxVertices=10; 7const int MaxWeight=1000; 8struct MinSpanTree //带权边的三个参数 9{ 10 int begin,end; //边的起点与终点 11 int length; //边的权值 12}; 13 14class AdjMWGraph 15{ 16private: 17 int Vertice
8、s[20]; //顶点信息的数组 18 int Edge[MaxVertices][MaxVertices]; //边的权信息的矩阵 19 int numE; //当前的边数 20 int numV; //当前的顶点数 21public: 22 A