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

福州大学数计学院数据结构上机实验报告专业和班级：信息计算科学与应用数学6班学号姓名成绩实验名称图的有关操作实验内容有向图的邻接表的建立及遍历实验目的和要求【实验目的】 掌握图的存储思想及其存储实现。 掌握图的深度、广度优先遍历算法思想及其程序实现。掌握图的常见应用算法的思想及其程序实现。问题描述和主要步骤【实验内容】1. 键盘输入数据，建立一个有向图的邻接表。2在有向图的邻接表的基础上计算各顶点的度。3采用邻接表存储实现有向图的深度优先遍历。4采用邻接表存储实现有向图的广度优先遍历。【主要程序】#include#include#include#define MAX_VERTEX_NUM 20#define OK 1#define ERROR 0#define OVERFLOW 0int visitedMAX_VERTEX_NUM;typedef struct ArcNode/表结点int adjvex;/该弧所指向的顶点的位置struct ArcNode *nextarc;/指向下一条弧的指针char *info;/该弧相关信息的指针ArcNode;typedef struct VNode/头结点char data;/顶点信息ArcNode *firstarc;/第一个表结点的地址，指向第一条依附顶点的弧的指针VNode,AdjListMAX_VERTEX_NUM; /头结点，头结点的顺序表AdjList类型typedef struct /图结构AdjList vertices;int vexnum,arcnum;/图的当前顶点数与弧数ALGraph;typedef struct QNode/用于BFS遍历的附设链队列结点结构int data;struct QNode *next;QNode,*QueuePtr;typedef struct/链队列QueuePtr front;QueuePtr rear;LinkQueue;int InitQueue(LinkQueue &Q)/初始化链队Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode);if(!Q.front) exit(OVERFLOW);Q.front-next=NULL;return OK;int EnQueue(LinkQueue &Q,int e)/元素e入队QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode);if(!p) exit(OVERFLOW);p-next=NULL;p-data=e;Q.rear-next=p;Q.rear=p;return OK;int DeQueue(LinkQueue &Q,int &e)/队首元素出队,由e返回其值QueuePtr p;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;int EmptyQueue(LinkQueue Q)/判断队列Q是否为空if(Q.front=Q.rear)return 1;return 0;int LocateVex(ALGraph G,char v)/查找值为v的顶点在顶点向量G.vexs中的位置int i;for(i=0;iadjvex;elsereturn -1;int NextAdjVex(ALGraph G,char v,char w)/返回v的(相对于w)的下一个邻接顶点的序号int i,j;ArcNode *p,*q;i=LocateVex(G,v);j=LocateVex(G,w);if(i=-1|j=-1|i=j)return -1;p=G.verticesi.firstarc; /p指向v的邻接顶点链表中的第一个邻接顶点while(p-nextarc&p-adjvex!=j)/找到邻接顶点wp=p-nextarc;if(p-nextarc)/找到邻接顶点w，且w非v的最后一个邻接顶点q=p-nextarc;return q-adjvex;/返回v的(相对于w)的下一个邻接顶点的序号else return -1;/没有找到w或w是v的最后一个邻接顶点int Visit(char v)printf(%c ,v);return OK;int CreateDG(ALGraph &G)/采用邻接表表示，构造有向图Gint v,e,i,j,t;ArcNode *p,*q;char tail,head;printf(输入顶点个数:);scanf(%d,&v);if(v0)return ERROR;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.verticest.data);G.verticest.firstarc=NULL;/初始化该头结点指针域for(t=0;tadjvex=j;p-info=NULL;p-nextarc=NULL;if(!G.verticesi.firstarc)G.verticesi.firstarc=p;else/找尾结点for(q=G.verticesi.firstarc;q-nextarc;q=q-nextarc);q-nextarc=p;/插入到链表尾int DFS(ALGraph G,int v)/从第v个顶点出发，递归的深度优先遍历有向图Gint w;visitedv=-1;printf(%c ,G.verticesv.data);w=FirstAdjVex(G,G.verticesv.data);for(;w=0;w=NextAdjVex(G,G.verticesv.data,G.verticesw.data)if(!visitedw)DFS(G,w);/对v的尚未访问的邻接顶点w递归调用DFS()return OK;int DFSTraverse(ALGraph G) /深度优先搜索遍历图Gint i;for(i=0;iG.vexnum;i+)visitedi=0;for(i=0;iG.vexnum;i+)if(!visitedi)DFS(G,i);return OK;int BFSTraverse(ALGraph G,int(*visit)(char v)LinkQueue Q;int v,w,u;for(v=0;vG.vexnum;v+)visitedv=0;InitQueue(Q);for(v=0;v0;w=NextAdjVex(G,G.verticesu.data,G.verticesw.data)if(!visitedw)visitedw=1;Visit(G.verticesw.data);EnQueue(Q,w);retur