Visual_C++_6.0调试功能_图解教程(4)--实例.doc

Visual C+ 6.0调试功能 图解教程(4)-实例三图 1. 实验目的 熟悉图的两种常用的存储结构，以及在这两种存储结构上的两种遍历图的方法，即深 度优先遍历和广度优先遍历。进一步掌握递归算法的设计方法。 关于各种典型著名的复杂算法，在上机实习方面不做基本要求。更适合于安排大型课 程设计。 二.需求分析 本程序演示用C+编写,完成有向图的创建,用Prim算法实现最小生成树,实现边的插入和删除. 输入值的范围:创建图时要求输入的结点个数不大于MaxVertices的值.在插入边时要求原图不存在起点和终点之间边,并且插入的边不是矩阵对角线上的边.输入的数据类型为整形. 输出形式:以邻接矩阵的形式输出图的数据项.如果操作非法则给出错误信息. 测试数据 A创建5个顶点4条边的图:输入顶点分别为1,2,3,4,5;1和2之间,2和3之间,3和4 之间,4和5之间的权值分别为10,20,30,40.得到图: 输出顶点的信息（整型）： 1 2 3 4 5 输出邻接矩阵 ： 1: 0 10 1000 1000 1000 2: 1000 0 20 1000 1000 3: 1000 1000 0 30 1000 4: 1000 1000 1000 0 40 5: 1000 1000 1000 1000 0 B顶点4和3之间插入一条权值为50边得 输出顶点的信息（整型）： 1 2 3 4 5 输出邻接矩阵 ： 1: 0 10 1000 1000 1000 2: 1000 0 20 1000 1000 3: 1000 1000 0 30 1000 4: 1000 1000 50 0 40 5: 1000 1000 1000 1000 0 C删除顶点4和3之间的边得 输出顶点的信息（整型）： 1 2 3 4 5 输出邻接矩阵 ： 1: 0 10 1000 1000 1000 2: 1000 0 20 1000 1000 3: 1000 1000 0 30 1000 4: 1000 1000 1000 0 40 5: 1000 1000 1000 1000 0 三.设计概要 (1)为了实现上述程序的功能,需要定义图的抽象数据类型: ADT Graph is 数据对象：D=ai|aiIntegerSet,i=0,1,2,n,n0 基本操作: CreatG() 操作结果:创建有向图 InsertE() 初始条件:有向图已经存在 操作结果:插入一条边 DeleteE () 初始条件: 有向图已经存在 操作结果:删除一条边 END ADT BiTree (2) 本程序包含一个类和一个结构体类型 A无向图类AdjMWGraph有7个函数 1主函数main() 2.构造函数AdjMWGraph() 3. 创建图函数CreatG(int n,int e) 4. 插入边函数InsertE() 5. 删除边函数DeleteE() 6. 求最小生成树Prim算法函数Prim() B结构体类型MinSpanTree (3)本程序的两个文件 1.头文件Graph.h 2.源文件 Graph.cpp (4)函数之间的关系 四.详细设计 1/Graph.h2#includeiostream3#include4#include5usingnamespacestd;6constintMaxVertices=10;7constintMaxWeight=1000;8structMinSpanTree/带权边的三个参数910intbegin,end;/边的起点与终点11intlength;/边的权值12;1314classAdjMWGraph1516private:17intVertices20;/顶点信息的数组18intEdgeMaxVerticesMaxVertices;/边的权信息的矩阵19intnumE;/当前的边数20intnumV;/当前的顶点数21public:22AdjMWGraph();/构造函数23voidCreatG(intn,inte);/创建图函数24voidPrintOut();/打印图中数据项函数25voidPrim();/求最小生成树方法(Prim算法)26voidInsertE();/插入边函数27voidDeleteE();/删除边函数28;29/Graph.cpp30#includeGraph.h3132/初始化矩阵33AdjMWGraph:AdjMWGraph()/构造函数3435/初始化矩阵为36for(inti=0;iMaxVertices;i+)/行37for(intj=0;jMaxVertices;j+)/列3839if(i=j)40Edgeij=0;/对角线置零41else42Edgeij=MaxWeight;/无边时权值置这无穷大4344numE=0;/当前边个数初始为45numV=0;/当前的顶点个数为464748/创建图49voidAdjMWGraph:CreatG(intn,inte)5051intvi,vj,w;52numE=e;53numV=n;54coutn输入顶点的信息（整型）：;5556/顶点赋值57for(inti=0;inumV;i+)5859coutni+1Verticesi;61626364/边赋权值65for(inti=0;inumE;)6667coutvivjw;6970/判断起点和终点是否存在,是否是对角线上的点并且边是否存在71if(vi!=vj)72&(vi0&vi0&vj=numV)74&(Edgevi-1vj-1=MaxWeight)7576Edgevi-1vj-1=w;/更改对应的行和列的权值77i+;7879else8081coutt插入位置错误或边已经存在!nt请正确输入.endl;8283848586/打印图中数据项87voidAdjMWGraph:PrintOut()8889coutn输出顶点的信息（整型）：n;90for(inti=0;inumV;i+)91couttVerticesi;92coutn输出邻接矩阵：endl;93for(inti=0;inumV;i+)9495coutni+1:;96for(intj=0;jnumV;j+)97couttEdgeij;98coutendl;99100101102/Prim普里姆算法求最小生成树103voidAdjMWGraph:Prim()104105intn=numV,m,v;/顶点总数106MinSpanTreee,mintreeMaxVertices;/mintree生成树数组107108for(intj=1;jn;j+)/初始化treen-1109110mintreej-1.begin=1;/顶点并入U111mintreej-1.end=j+1;112mintreej-1.length=Edge0j;/G.Edge是连通网的带权邻接矩阵113114115for(intk=0;kn-1;k+)/求第k+1条边116117intmin=MaxWeight;118119for(intj=k;jn-1;j+)120if(mintreej.lengthmin)/求邻接的最小的边121122min=mintreej.length;123m=j;124/forj125126/交换方法置下个邻接点为终点127e=mintreem;128mintreem=mintreek;129mintreek=e;130v=mintreek.end;/VU131132for(intj=k+1;jn-1;j+)/在新的顶点v并入U之后更新treen-1133134intd=Edgev-1mintreej.end-1;135if(dmintreej.length)/循环找到与当前点相邻的最小权值的边136137mintreej.length=d;138mintreej.begin=v;/置当前点为起点139140/fork141142for(intj=0;jn-1;j+)143coutn起点：mintreej.begin终点：144mintreej.end权值：mintreej.length;145coutendl;146147148/插入一条的算法149voidAdjMWGraph:InsertE()150151inti,j,w;152coutijw;154/判断起点各终点是否存在并且不是对角线上的点155if(i!=j)&(i0&i0&j=numV)156157if(Edgei-1j-1!=0)&(Edgei-1j-1=MaxWeight)158159Edgei-1j-1=w;/更改对应的行和列的权值160161else162163coutt边已经存在!endl;164/exit(0);165166167else168169coutt插入位置错误!endl;170/exit(0);171172173174175/删除一条边的算法176voidAdjMWGraph:DeleteE()177178inti,j;179coutij;181if(i0&i0&j=numV)/判断起点各终点是否存在182183/判断是否是对角线上的点,判断是否是边已经存在184if(i!=j)&(Edgei-1j-1!=MaxWeight)185186Edgei-1j-1=MaxWeight;/对应的行和列权值置零187188189else190191coutt删除的边不存在!endl;192/exit(0);193194195196else197198coutt删除位置错误!endl;199/exit(0);200201202203204intmain(intargc,char*argv)205206AdjMWGraphG;207intn,e;208intk;209210do211212coutnt1.创建图endl;213coutnt2.插入一条边endl;214coutnt3.删除一条边endl;215coutnt4.退出endl;216coutnt=endl;217coutk;219220switch(k)221222223case1:224225coutne;227G.CreatG(n,e);228G.PrintOut();229cout最小生成树如下;230cout共有n-10&k i j w;语句.然后在DOS窗口输入4,3,55回车. 这时Debugger仍停留在if ( ( i != j ) & (i0 & i0 & j=numV)处.可以在监视1窗口中看到 i != j的值为true,即可以步入if()语句. 2. 在监视窗口1中输入: (Edgei-1j-1 = MaxWeight), (Edgei-1j-1 != 0)进行