[邻接矩阵表示的带权有向图网”演示程序.docVIP

班级:信息1102 姓名：贾孟涛 ========实习报告十四“邻接矩阵表示的带权有向图（网）”演示程序 ========== 、程序的功能和特点 该程序可以建立有向图的带权邻接矩阵，能够对建立的邻接矩阵进行添加顶点，添加边和删除顶点，删除边的操作，并能显示输出邻接矩阵。该程序的特点是采用java面向对象语言，对边，顶点和邻接矩阵用类进行封装。采用链式存储结构。 （二）、程序的算法设计 算法一：“插入一个顶点”算法： 1.【逻辑结构与存储结构设计】???? 逻辑结构：线性结构。 存储结构：顺序存储与链式存储结合。 【基本操作设计】 文字说明： 创建新结点，找到结点L位置，在?L后插入新结点。 【算法设计】 文字说明：? ???（1）.首先判断顶点表是否满。? ???（2）.若满则插入失败，放回false。? ???（3）.顶点表若不满，创建新顶点，将新顶点加入顶点表。? ???（4）.插入顶点成功，返回true。 4.【高级语言代码】 //插入一个顶点 public int InsertVertex ( char vertex ){ if(IsGraphFull()) return -1; //插入失败 //顶点表增加一个元素 VerticesList[CurrentVertices]=vertex; //邻接矩阵增加一行一列 for ( int j = 0;j =CurrentVertices;j++ ) { Edge[CurrentEdges][j]=MaxValue; Edge[j][CurrentEdges]=MaxValue; } Edge[CurrentEdges][CurrentEdges]=0; CurrentVertices++; return CurrentVertices; //插入位置 } 算法二：“插入一条边”算法： 1.【逻辑结构与存储结构设计】???? 逻辑结构：线性结构。 存储结构：链式存储结构。 【基本操作设计】 文字说明： 创建新边结点，再将新创建的边结点插入图中。 【算法设计】 文字说明：? ??（1）.首先判断插入边上的两个顶点编号是否越界。????? if (v1 0 || v1 CurrentVertices - 1) ?????return?false;? ? if (v2 0 || v2 CurrentVertices - 1)?????return?false;? ??（2）.如果越界则插入失败，返回false。? ? （3）.否则创建新边结点? ??（4）.再将新创建的边结点插入图中???? （5) .插入成功返回true。 4.【高级语言代码】 //插入一个边 public boolean InsertEdge( int v1, int v2, double weight){ if (v1 0 || v1 CurrentVertices - 1) return false; //出错 if (v2 0 || v2 CurrentVertices - 1) return false; Edge[v1][v2]=weight; //网,有向边 return true; } （三）、程序中类的设计 “Graph”类： 【逻辑结构与存储结构】 逻辑结构：网状结构。 存储结构：顺序存储与链式存储结合。 【主要成员变量说明】 static int MaxEdges = 50; static int MaxVertices = 10; static double MaxValue=9999.9; //无穷大 //存放顶点的数组 private char VerticesList[]=new char[MaxVertices]; //邻接矩阵（存放两个顶点权值） private double Edge[][]=new double[MaxVertices][MaxVertices]; private int CurrentEdges; //现有边数 private int CurrentVertices; //现有顶点数 //构造函数：建立空的邻接矩阵 【主要成员方法说明】 public Graph ( )：为定义的构造函数，建立空的邻接矩阵。