数据结构 邻接表有向图

《数据结构 邻接表有向图》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、#include"C:DocumentsandSettings中原桌面GraphLinkList.h"//====================================================================================================================================////邻接表有向图部分////========================================================

2、============================================================================structListNode//定义图的顶点结点每个结点包含结点vex和一个用于存储边的链表lis{charvex;//顶点元素LinkListlis;//边链表ListNode(){};//结点的无参构造函数ListNode(charv){vex=v;}//给定顶点时构造结点voidoperator=(ListNode&n){vex=n.vex;lis=n.

3、lis;}//实现结点的赋值booloperator>(ListNoden){returnvex>n.vex;}//实现结点的比较booloperator==(ListNoden){returnvex==n.vex;}//实现结点的比较};classAdjListDirGraph//定义邻接表有向图{public:intvexNum,edgeNum;//定义vexNum存储图的顶点数、和有向边数edgeNumLinkListvList;//定义以图的顶点结点构成的表AdjListDirGraph()

4、{vexNum=0;edgeNum=0;}//图的构造函数无参数时默认构造0个顶点的图~AdjListDirGraph(){clear();}//析构函数voidinsetVertex(charv);//向图中插入一个顶点vvoiddelVertex(charv);//在图中删除顶点vvoidsetEdge(intv1,intv2);//插入从顶点v1到顶点v2的边v1、v2为顶点对应的位置voiddelEdge(intv1,intv2);//删除从顶点v1到顶点v2的边v1、v2为顶点对应的位置intgetSite(

5、charv);//获取顶点v在顶点表中的位置voidsetEdge(charv1,charv2){setEdge(getSite(v1),getSite(v2));}//插入从顶点v1到顶点v2的边v1、v2为顶点voiddelEdge(charv1,charv2){delEdge(getSite(v1),getSite(v2));}//删除从顶点v1到顶点v2的边v1、v2为顶点voidshowVertex();//输出图的顶点及其对应的位置voidshowEdge();//输出以每个顶点为起点的边intinDegr

6、ee(intv);//求第v个顶点的入度intoutDegree(intv);//求以顶点v为起点的边数求第v个顶点的出度intinDegree(charv){returninDegree(getSite(v));}//求顶点v的入度intoutDegree(charv){returnoutDegree(getSite(v));}//求取顶点v的出度voidclear();//图清空voidoperator=(AdjListDirGraph&G){vexNum=G.vexNum;edgeNum=G.edgeNum;vL

7、ist=G.vList;}//重载运算符”="实现图的复制};voidAdjListDirGraph::insetVertex(charv){intsite=getSite(v);if(site==vexNum+1){ListNodee(v);//生成顶点结点vvList.TailInsert(e);//向顶点表的末位插入一个顶点结点vexNum++;}}voidAdjListDirGraph::delVertex(charv){intsite=getSite(v);if(site>=1&&site<=vexNum)/

8、/当顶点在已存在顶点的表示的范围之内时进行操作{for(inti=1;i<=vList.Length();i++){//i<=vList的顶点数时for(intj=1;j<=vList.GetPosP(i)->data.lis.Length();j++){if(vList.GetPosP(i)->data.lis.GetPosP(