数据结构复习笔记图的邻接表存储表示及重要的基本操作

《数据结构复习笔记图的邻接表存储表示及重要的基本操作》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、图的邻接表存储表示及重要的基本操作/*图的邻接表存储表示及重要的基本操作*//*图的邻接表存储表示,真的很重要，要不然后面全是白搭*/#defineMAX_VERTEX_NUM20typedefenum{DG,DN,UDG,UDN}GraphKind;/*{有向图,有向网,无向图,无向网}*/typedefstructArcNode{intadjvex;/*该弧所指向的顶点的位置*/structArcNode*nextarc;/*指向下一条弧的指针*/InfoType*info;/*网的权值指针）*/}ArcNode;/*表结点*/typedefstruct{VertexTyp

2、edata;/*顶点信息*/ArcNode*firstarc;/*第一个表结点的地址,指向第一条依附该顶点的弧的指针*/}VNode,AdjList[MAX_VERTEX_NUM];/*头结点*/typedefstruct{AdjListvertices;intvexnum,arcnum;/*图的当前顶点数和弧数*/GraphKindkind;/*图的种类标志*/}ALGraph;有向图、无向图的邻接表：（注意表结点的域）网邻接表的表示：注意表结点的域中多加一个权值域1//基本操作选择性的看吧StatusLocateVex(ALGraphG,VertexTypeu){/*初始条

3、件：图G存在，u和G中顶点有相同特征*//*操作结果：若G中存在顶点u，则返回该顶点在图中位置；否则返回NULL*/inti;for(i=0;i

4、构造表头向量（顶点信息）G.vertices[i].firstarc=NULL;}//初始化指针，头结点指针为空for(k=0;kInf

5、o);}}StatusFirstAdjVex(ALGraphG,VertexTypev)2{/*初始条件：图G存在，v是G中某个顶点*//*操作结果：返回v的第一个邻接顶点的序号。若顶点在G中没有邻接顶点，则返回NULL*/LinkListp;intv1;v1=LocateVex(G,v);/*v1为顶点v在图G中的序号*/p=G.vertices[v1].firstarc;if(p)returnp->data.adjvex;elsereturnNULL;}Statusequalvex(ElemTypea,ElemTypeb){/*DeleteArc()、DeleteVex()

6、和NextAdjVex()要调用的函数*/if(a.adjvex==b.adjvex)returnOK;elsereturnERROR;}StatusNextAdjVex(ALGraphG,VertexTypev,VertexTypew){/*初始条件：图G存在，v是G中某个顶点，w是v的邻接顶点*//*操作结果：返回v的(相对于w的)下一个邻接顶点的序号。若w是v的最后一个邻接点，则返回NULL*//*用到的函数Point（）为查找表L中满足条件的结点。如找到，返回指向该结点的指针，p指向该结点的前驱(若该结点是*//*首元结点，则p=NULL)。如表L中无满足条件的结点，则

7、返回NULL，p无定义。*/LinkListp,p1;/*p1在Point()中用作辅助指针*/ElemTypee;intv1;v1=LocateVex(G,v);/*v1为顶点v在图G中的序号*/e.adjvex=LocateVex(G,w);/*e.adjvex为顶点w在图G中的序号*/p=Point(G.vertices[v1].firstarc,e,equalvex,&p1);/*p指向顶点v的链表中邻接顶点为w的结点*/if(!p

8、

9、!p->next)/*没找到w或w是最后一个邻接