《数据结构》实验指导/实验七:图的存储及操作1 《数据结构》实验指导 实验七:图的存储及操作 、实验目的 1、掌握图的定义和专业术语。 2、掌握图的存储实现。 3、掌握图的操作算法实现, 4、了解图的应用。 二、实验学时 、实验类型 设计性实验 四、实验需求 1、硬件 每位学生配备计算机一台: 2、软件 Windows XP/ Windows7操作系统:开发工具软件: Microsoft visual studio2010。 五、实验理论与预备知识 1、数据结构的基本概念 2、存储结构的特点 3、图的特点和基本运算 4、图在邻接矩阵和邻接表存储结构下的操作算法 六、实验任务 1、图抽象数据类型的代码实现 2、编写应用程序,用相关数据验证运算算法 管理科学与工程学科/共7页第1页
《数据结构》实验指导 / 实验七：图的存储及操作 1 管理科学与工程学科 / 共7页,第1页 《数据结构》实验指导 实验七：图的存储及操作 一、实验目的 1、 掌握图的定义和专业术语。 2、 掌握图的存储实现。 3、 掌握图的操作算法实现。 4、 了解图的应用。 二、实验学时 2 学时 三、实验类型 设计性实验 四、实验需求 1、硬件 每位学生配备计算机一台； 2、软件 Windows XP/ Windows 7 操作系统；开发工具软件：Microsoft Visual Studio 2010。 五、实验理论与预备知识 1、数据结构的基本概念 2、存储结构的特点 3、图的特点和基本运算 4、图在邻接矩阵和邻接表存储结构下的操作算法 六、实验任务 1、图抽象数据类型的代码实现 2、编写应用程序，用相关数据验证运算算法
《数据结构》实验指导/实验七:图的存储及操作 2 七、实验内容及步骤 任务:代码实现图的邻接矩阵和邻接表存储结构:编写应用程序,用相关数据验证运算算法。 实验步骤: (1)启动 sual studio2010,创建窗体应用程序。 (2)创建图的存储结构,包括邻接矩阵、邻接表、创建邻接矩阵方法、邻接矩阵和邻接表 转换方法、输出邻接矩阵方法和输出邻接表方法等,代码参考如下: ∥-图的邻接矩阵 truct VertexType ∥顶点类型 public int no 顶点编号 public string data; 顶点其他信息 struct MGraph 图邻接矩阵类型 public intl, edges ∥接矩阵的边数组 public int n, e; 顶点数,边数 public Vertex Typell vexs; 存放顶点信息 ∥1-图的邻接表 class arcnode ∥边结点类型 public int adjvex ∥该边的终点编号 public areNode nextarc ∥指向下一条边的指针 public int weight; ∥该边的相关信息如边的权值 struct VNode ∥表头结点类型 public string data; 顶点信息 public AreNode firstarc 指向第一条边 struct ALGraph ∥图的邻接表类型 public VNodell adjlist; ∥接表数组 public int n, e; /图中顶点数n和边数e }; class Graph class const int MAXV=100: ∥最大顶点个数 const int INF= 32767; 用INF表示 管理科学与工程学科/共7页第2页
《数据结构》实验指导 / 实验七：图的存储及操作 2 管理科学与工程学科 / 共7页,第2页 七、实验内容及步骤 任务：代码实现图的邻接矩阵和邻接表存储结构；编写应用程序，用相关数据验证运算算法。 实验步骤： （1） 启动 Visual Studio 2010，创建窗体应用程序。 （2） 创建图的存储结构，包括邻接矩阵、邻接表、创建邻接矩阵方法、邻接矩阵和邻接表 转换方法、输出邻接矩阵方法和输出邻接表方法等，代码参考如下： //------图的邻接矩阵------------------------------------------------- struct VertexType //顶点类型 { public int no; //顶点编号 public string data; //顶点其他信息 }; struct MGraph //图邻接矩阵类型 { public int[,] edges; //邻接矩阵的边数组 public int n, e; //顶点数，边数 public VertexType[] vexs; //存放顶点信息 }; //------图的邻接表--------------------------------------------------- class ArcNode //边结点类型 { public int adjvex; //该边的终点编号 public ArcNode nextarc; //指向下一条边的指针 public int weight; //该边的相关信息,如边的权值 }; struct VNode //表头结点类型 { public string data; //顶点信息 public ArcNode firstarc; //指向第一条边 }; struct ALGraph //图的邻接表类型 { public VNode[] adjlist; //邻接表数组 public int n, e; //图中顶点数 n 和边数 e }; //------------------------------------------------------------------- class GraphClass { const int MAXV = 100; //最大顶点个数 const int INF = 32767; //用 INF 表示∞
《数据结构》实验指导/实验七:图的存储及操作 3 public MGraph g= new MGrapho public ALGraph G= new ALGrapho public Graph Class 构造函数 gedges= new int[MAXV, MAXV; g.vexs= new VertexType MAXV; Gadjlist=new VNode maxi; ∥-图的基本运算算法--- public void CreateMGraph(int n,inte,int,la)∥通过相关数据建立邻接矩阵 for G=0; gedges i,j=a|i,Jl: public string DispMGrapho /输出图的邻接矩阵 string mystr="": I,J; r(i=0; i<g =0;j<gn;j++) if (gedges, jI= INF) mystr+=string. Format(10,-4", gedges i,jl-ToString0); mystr+="rIn"; return mystr; public void MatTolisto 将邻接矩阵g转换成邻接表G int i,j; p for (i=0; i<gn; i++) 给邻接表中所有头结点的指针域置初值 G adjlist[i].fi for(i=0; i<g n; i++) ∥检查邻接矩阵中每个元素 if( gedges i, jl!=0&& g edges,j!:=INF)在一条边 p= new AreNodeo ∥创建一个结点p 管理科学与工程学科/共7页第3页
《数据结构》实验指导 / 实验七：图的存储及操作 3 管理科学与工程学科 / 共7页,第3页 public MGraph g = new MGraph(); public ALGraph G = new ALGraph(); public GraphClass() //构造函数 { g.edges = new int[MAXV, MAXV]; g.vexs = new VertexType[MAXV]; G.adjlist = new VNode[MAXV]; } //-------图的基本运算算法----------------- public void CreateMGraph(int n, int e, int[,] a) //通过相关数据建立邻接矩阵 { int i, j; g.n = n; g.e = e; for (i = 0; i < g.n; i++) for (j = 0; j < g.n; j++) g.edges[i, j] = a[i, j]; } public string DispMGraph() //输出图的邻接矩阵 { string mystr = ""; int i, j; for (i = 0; i < g.n; i++) { for (j = 0; j < g.n; j++) if (g.edges[i, j] == INF) mystr += string.Format("{0,-3}", "∞"); else mystr += string.Format("{0,-4}", g.edges[i, j].ToString()); mystr += "\r\n"; } return mystr; } public void MatToList() //将邻接矩阵 g 转换成邻接表 G { int i, j; ArcNode p; for (i = 0; i < g.n; i++) //给邻接表中所有头结点的指针域置初值 G.adjlist[i].firstarc = null; for (i = 0; i < g.n; i++) //检查邻接矩阵中每个元素 for (j = g.n - 1; j >= 0; j--) if (g.edges[i, j] != 0 && g.edges[i, j] != INF) //存在一条边 { p = new ArcNode(); //创建一个结点 p
《数据结构》实验指导/实验七:图的存储及操作 4 djvex=j; p weight=gedges[i,j: 边的权值 p. nextare= G adjlisti. firstarc;/.用头插法插入p Gadjlist[i firstare=p; G n=gn; public string DispALGrapho ∥输出图的邻接表 . adjlisti p指向第一个邻接点 (p while(p!=null) mystr+="+p. adjvex.ToString0+"("+pweight. ToString0+")"; p移向下一个邻接点 (3)通过边数组a、顶点数n和边数e来建立图的邻接矩阵,并实现显示邻接矩阵和邻接表 的功能。设计界面,参考如下: 管理科学与工程学科/共7页第4页
《数据结构》实验指导 / 实验七：图的存储及操作 4 管理科学与工程学科 / 共7页,第4页 p.adjvex = j; p.weight = g.edges[i, j]; //边的权值 p.nextarc = G.adjlist[i].firstarc; //采用头插法插入 p G.adjlist[i].firstarc = p; } G.n = g.n; G.e = g.e; } public string DispALGraph() //输出图的邻接表 { string mystr = ""; int i; ArcNode p; for (i = 0; i < G.n; i++) { mystr += "[" + i.ToString() + "]"; p = G.adjlist[i].firstarc; //p 指向第一个邻接点 if (p != null) mystr += " →"; while (p != null) { mystr += " " + p.adjvex.ToString() + "(" + p.weight.ToString() + ")"; p = p.nextarc; //p 移向下一个邻接点 } mystr += "\r\n"; } return mystr; } （3） 通过边数组 a、顶点数 n 和边数 e 来建立图的邻接矩阵，并实现显示邻接矩阵和邻接表 的功能。设计界面，参考如下：
《数据结构》实验指导/实验七:图的存储及操作 5 Forl 操作步骤1-建立邻接矩阵 操作步骤2转换成邻接表并输出 建立图的邻接矩阵 产生邻接表并输出 [o]→1(1)3(1 一个无向图如下 [1]→01)2(1) →1(1)3(1)4 [3]→0(1)2(1)4(1) [4]→2(1)3(1) 操作步骤3-转换成邻接矩阵并输出 产生邻接矩阵并输出 01010 010 从结点 开始遍历 深度忧先搜索序列:30124 L厂度优先搜索遍历序列 30241 操作提示:无向图的邻接矩阵输出完毕 (4)编写窗体中按钮等控件的代码,调用循环顺序队列类,参考如下: Graph Class gl= new Graph Class ∥图对象g private void button Click(object sender, EventArgs e) int ns=5. en= 6: in,a= new int,{{01,01,0},{1,0,1,0,0},{0,1,0,1,1},{1,0,1,0,1} 0,0,1,1,0}}; infolabel.Iext="操作提示:一个无向图的邻接矩阵生成完毕 private void button2_ Click(object sender, EventArgs e) 管理科学与工程学科/共7页第5页
《数据结构》实验指导 / 实验七：图的存储及操作 5 管理科学与工程学科 / 共7页,第5页 （4） 编写窗体中按钮等控件的代码，调用循环顺序队列类，参考如下： GraphClass gl = new GraphClass(); //图对象 gl private void button1_Click(object sender, EventArgs e) { int ns = 5, en = 6; int[,] a = new int[,] { { 0, 1, 0, 1, 0 }, { 1, 0, 1, 0, 0 }, { 0, 1, 0, 1, 1 }, { 1, 0, 1, 0, 1 }, { 0, 0, 1, 1, 0 } }; gl.CreateMGraph(ns, en, a); infolabel.Text = "操作提示:一个无向图的邻接矩阵生成完毕"; } private void button2_Click(object sender, EventArgs e) {