08梁伟华实验四

《08梁伟华实验四》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实验VSBB的的操乍及应用实验课程名：数据结构专业班级：计算机科学与技术（2）班学号：201140410208_姓名：梁伟华实验时间：—12.13实验地点：K4-209指导教师：祁文青一、实验目的1、理解图的基木概念及术语；2、掌握图的两种存储结构（邻接矩阵和邻接表）的表示方法:3、熟练掌握图的两种遍历（深度优先搜索遍历和广度优先搜索遍历）的算法思想、步骤，并能列出在两种存储结构上按上述两种遍历算法得到的序列；4、理解最小生成树的概念，能按Prim算法构造最小生成树；领会并学握拓扑排序、关键路径、最範路径的算法思想。二、实验

2、内容任务1:构造图的邻接矩阵存储结构或邻接表存储结构图的邻接表#includeCiostreamh>#include#define(K^FHH#define20structedgenode{intadjvex,edgenode*next;}；/定义邻接表的边结点类型typedefedgenode好adjlist;/定义邻接表类型voidInitGAdjoin^dj1istintrj);/初始化图的邻接表voidCreateAdjoin@dj1istintn,intn);#includeCiostreamh>

3、#includevoidCheck(intn,int&i,int&j);voidInitGdjoinfedj1isint®/初始化图的邻接表{Gj=mewedgenode*[n];for(inti=l;i5i;i~H)GL[i]吕LU;voidCreateAdjoin^djlist8G^intn,intn)/建立图的邻接表{inti,j,k,cout«输入图的总边数："；ciri»e;iffn=O{/建立无向图fork

4、);edgenode*p^newedgenode;pH>adjve^j;pH>next=GL[订；GL[i]=p；/向序号为i的单链表的表头插入一个边结点p^newedgenod^pH>adjvex=i;pH>next=GL[j];GLUE；力向序号为j的单链表的表头插入一个边结点}coutnext)

5、cout«"

6、—1->

7、"«pH>adjvex;cout«"「

8、cout«encll;}力输出邻接表}elseif(n=l)0建立有向图for(k=l;leH){coutv^输入第条边的起点和终点序号！"Wfendl;cin»i»j;Check(h,i,j);/向序号为i的表头插入一个边结点edgenode*p=newedgenode;p^>adjve^j;pH>next=GL[i]；GL[i]=p；cout«'图的邻接表为：

9、匕fend1;for(i=l;i<^n;i-H){edgenode*p

10、«卄11W«i;for(p=G^[i];p!=^NLLL;p=^p-^iext)cout«"

11、一

12、—>

13、"WfH>adjve骂cout«"

14、八

15、cout«fendl;}/输出邻接表}}voidCheck(intn,int&i,int&j)力t查输入的边序号是否越界，若越界则重输{Mile(1){if(i^O

16、

17、i>n

18、

19、j^O

20、

21、j>n)cout«'输入有误,请重新输入！"；elsereturn;cin»i»j;}}voidmainJ{inti,n,rrjZ^cout«'ii'

22、in>>n;cout«'输入是否有向(0为无,1为有)："；cirt^frjboo1*visitecHiewbool冋；adjlistgl;InitGXdjoin(gl,rj);CreateAdjoin(gl,n,n);cout«endl;cout«"08梁伟华"

23、的邻接矩阵#includcSinclude#defineM20ttdefineMAX20typedefstruct{intbegin;intend;intweight;ledge;typedefstruct{intadj;intweight;}AdjM