《数据结构》上机实验报告—有向图的邻接表的建立与遍历

《《数据结构》上机实验报告—有向图的邻接表的建立与遍历》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、福州大学数计学院《数据结构》上机实验报告专业和班级：信息计算科学与应用数学6班学号姓名成绩实验名称图的有关操作实验内容有向图的邻接表的建立及遍历实【实验目的】验１．掌握图的存储思想及其存储实现。目２．掌握图的深度、广度优先遍历算法思想及其程序实现。的３．掌握图的常见应用算法的思想及其程序实现。和要求【实验内容】1.键盘输入数据，建立一个有向图的邻接表。2．在有向图的邻接表的基础上计算各顶点的度。3．采用邻接表存储实现有向图的深度优先遍历。4．采用邻接表存储实现有向图的广度优先遍历。【主要程序】#include

2、#include#include#defineMAX_VERTEX_NUM20#defineOK1#defineERROR0#defineOVERFLOW0intvisited[MAX_VERTEX_NUM];问typedefstructArcNode//表结点{题intadjvex;//该弧所指向的顶点的位置描structArcNode*nextarc;//指向下一条弧的指针述char*info;//该弧相关信息的指针}ArcNode;和主typede

3、fstructVNode//头结点要{chardata;//顶点信息步ArcNode*firstarc;//第一个表结点的地址，指向第一条依附顶骤点的弧的指针}VNode,AdjList[MAX_VERTEX_NUM];//头结点，头结点的顺序表AdjList[]类型typedefstruct//图结构{AdjListvertices;intvexnum,arcnum;//图的当前顶点数与弧数}ALGraph;typedefstructQNode//用于BFS遍历的附设链队列结点结构{intdata;stru

4、ctQNode*next;}QNode,*QueuePtr;typedefstruct//链队列{QueuePtrfront;QueuePtrrear;}LinkQueue;intInitQueue(LinkQueue&Q)//初始化链队{Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));if(!Q.front)exit(OVERFLOW);Q.front->next=NULL;returnOK;}intEnQueue(LinkQueue&Q,inte)//元素e入

5、队{QueuePtrp;p=(QueuePtr)malloc(sizeof(QNode));if(!p)exit(OVERFLOW);p->next=NULL;p->data=e;Q.rear->next=p;Q.rear=p;returnOK;}intDeQueue(LinkQueue&Q,int&e)//队首元素出队,由e返回其值{QueuePtrp;if(Q.front==Q.rear)exit(OVERFLOW);p=Q.front->next;e=p->data;Q.front->next=p->n

6、ext;if(Q.rear==p)Q.rear=Q.front;free(p);returnOK;}intEmptyQueue(LinkQueueQ)//判断队列Q是否为空{if(Q.front==Q.rear)return1;return0;}intLocateVex(ALGraphG,charv)//查找值为v的顶点在顶点向量G.vexs[]中的位置{inti;for(i=0;i

7、tAdjVex(ALGraphG,charv)//返回v的第一个邻接顶点的序号{inti;ArcNode*p;i=LocateVex(G,v);//i为顶点v在图G中的序号if(i==-1)return-1;p=G.vertices[i].firstarc;if(p)returnp->adjvex;elsereturn-1;}intNextAdjVex(ALGraphG,charv,charw)//返回v的(相对于w)的下一个邻接顶点的序号{inti,j;ArcNode*p,*q;i=LocateVex(G,

8、v);j=LocateVex(G,w);if(i==-1

9、

10、j==-1

11、

12、i==j)return-1;p=G.vertices[i].firstarc;//p指向v的邻接顶点链表中的第一个邻接顶点while(p->nextarc&&p->adjvex!=j)//找到邻接顶点wp=p->nextarc;if(p->nextarc)//找到邻接顶点w，且w非v的最后一个邻接顶点{q=p->nextarc