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

福州大学数计学院《数据结构》上机实验报告专业和班级：信息计算科学与应用数学6班学号姓名成绩实验名称图的有关操作实验内容有向图的邻接表的建立及遍历实验目的和要求【实验目的】１．掌握图的存储思想及其存储实现。２．掌握图的深度、广度优先遍历算法思想及其程序实现。３．掌握图的常见应用算法的思想及其程序实现。问题描述和主要步骤【实验内容】1.键盘输入数据，建立一个有向图的邻接表。2．在有向图的邻接表的基础上计算各顶点的度。3．采用邻接表存储实现有向图的深度优先遍历。4．采用邻接表存储实现有向图的广度优先遍历。【主要程序】#includestdio.h#includestdlib.h#includeconio.h#defineMAX_VERTEX_NUM20#defineOK1#defineERROR0#defineOVERFLOW0intvisited[MAX_VERTEX_NUM];typedefstructArcNode//表结点{intadjvex;//该弧所指向的顶点的位置structArcNode*nextarc;//指向下一条弧的指针char*info;//该弧相关信息的指针}ArcNode;typedefstructVNode//头结点{chardata;//顶点信息ArcNode*firstarc;//第一个表结点的地址，指向第一条依附顶点的弧的指针}VNode,AdjList[MAX_VERTEX_NUM];//头结点，头结点的顺序表AdjList[]类型typedefstruct//图结构{AdjListvertices;intvexnum,arcnum;//图的当前顶点数与弧数}ALGraph;typedefstructQNode//用于BFS遍历的附设链队列结点结构{intdata;structQNode*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入队{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-next;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;iG.vexnum;i++)if(v==G.vertices[i].data)returni;return-1;}intFirstAdjVex(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,v);j=LocateVex(G,w);if(i==-1||j==-1||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;returnq-adjvex;//返回v的(相对于w)的下一个邻接顶点的序号}elsereturn-1;//没有找到w或w是v的最后一个邻接顶点}intVisit(charv){printf(%c,v);returnOK;}intCreateDG(ALGraph&G)//采用邻接表表示，构造有向图G{intv,e,i,j,t;ArcNode*p,*q;chartail,head;printf(输入顶点个数:);scanf(%d,&v);if(v0)returnERROR;G.vexnum=v;printf(输入弧的条数:);scanf(%d,&e);if(e0)returnERROR;G.arcnum=e;printf(建立DG:\n);for(t=0;tG.vexnum;t++)//建立头结点顺序表{fflush(stdin);printf(输入%d的信息:,t+1);scanf(%c,&G.vertices[t].data);G.vertices[t].firstarc=NULL;//初始化该头结点指针域}for(t=0;tG.arcnum;t++)//建立表结点链表(每个顶点的邻接顶点链表){fflush(stdin);printf(输入弧的信息(弧尾-弧头));scanf(%c%*c%c,&tail,&head);i=LocateVex(G,tail);j=LocateVex(G,head);if(i==-1||j==-1||i==j)returnERROR;p=(ArcNode*)malloc(sizeof(ArcNode));p-adjvex=j;p-info=NULL;p-nextarc=NULL;if(!G.vertices[i].firstarc)G.vertices[i].firstarc=p;else{//找尾结点for(q=G.vertices[i].firstarc;q-nextarc;q=q-nextarc);q-nextarc=p;//插入到链表尾}}}intDFS(ALGraphG,intv)//从第v个顶点出发，递归的深度优先遍历有向图G{intw;visited[v]=-1;printf(%c,G.vertices[v].data);w=FirstAdjVex(G,G.vertices[v].data);for(;w=0;w=NextAdjVex(G,G.vertices[v].data,G.vertices[w].data))if(!visited[w])DFS(G,w);//对v的尚未访问的邻接顶点w递归调用DFS()returnOK;}intDFSTraverse(ALGraphG)//深度优先搜索遍历图G{inti;for(i=0;iG.vexnum;i++)visited[i]=0;for(i=0;iG.vexnum;i++)if(!visited[i])DFS(G,i);returnOK;}intBFSTraverse(ALGraphG,int(*visit)(charv)){LinkQueueQ;intv,w,u;for(v=0;vG.vexnum;v++)visited[v]=0;InitQueue(Q);for(v=0;vG.vexnum;v++){if(!visited[v]){visited[v]=1;Visit(G.vertices[v].data);}EnQueue(Q,v);while(!EmptyQueue(Q)){DeQueue(Q,u);for(w=FirstAdjVex(G,G.vertices[u].data);w0;w=NextAdjVex(G,G.vertices[u].data,G.vertices[w].data))if(!visited[w]){visited[w]=1;Visit(G.vertices[w].data);EnQueue(Q,w);}}}returnOK;}voidmain(){ALGraphG;printf(建立有向图G\n);if(CreateDG(G)){printf(深度优先搜索的顺序:);DFSTraverse(G);printf(\n);printf(广度优先搜索的顺序:);BFSTraverse(G,Visit);}printf(\n);}【结果截图】