数据结构实验报告(6)

《数据结构实验报告(6)》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数据就结构实验报告姓名：班级：学号：日期：2015年11月12日上机环境：win7系统，mircosoftvisual++1.实验题目编写一个程序，实现带权图的邻接矩阵与邻接表的相互转换算法，输出邻接矩阵与邻接表的运算，并在此基础上设计一个主程序完成如下功能：(1)建立有向图G的邻接矩阵，并输出；(2)由有向图G的邻接矩阵产生邻接表，并输出；(3)再由(2〉的邻接表产生对应的邻接矩阵，并输出；(4)输出有向图G从顶点0开始的深度优先遍历序列；(5)输出有向图G从顶点0开始的广度优先遍历序列；2.实验程序#include#include#de

2、fineMAXV100#defineINF32767typedefintInfoType;typedefintVertex;typedefstruct{intno;InfoTypeinfo;JVertexType;typedefstruct{intedges[MAXV][MAXV];intn,e;VertexTypevexs[MAXV];}MGraph;typedefstructANode{intadjvex;structANode*nextarc;InfoTypeinfo;}ArcNode;typedefstructVnode{Vertexdate;ArcNode*first

3、arc;}VNode;typedefVNodeAdjList[MAXV];typedefstructAdjListadjlist;intn,e;JALGraph;voidMatToList(MGraphg?ALGraph*&G){inti,j；ArcNode*p;G=(ALGraph*)malloc(sizeof(ALGraph));for(i=0;iadjlist[i].firstarc=NULL;for(i=0;i=0;j-)if(g.edges[i][j]!=O&&g.edges[i][j]!=INF)

4、{p=(ArcNode*)malloc(sizeof(ArcNode));p->adjvex=j;p->info=g.edges[i][j];p->nextarc=G->adjIist[i].firstarc;G->adjlist[i].firstarc=p;}G・>n二g.n;G・>e=g.e;}voidListToMat(ALGraph*GzMGraph&g){inti,j；ArcNode*p;for(i=0;in;i++)for(j=0;jn;j++)if(i==j)g.edges[i][j]=O;elseg.edges[i][j]=INF;for(i=0

5、;in;i++){p=G->adjlist[i].firstarc;while(p!=NULL){g.edges[i][p->adjvex]=p->info;p=p->nextarc;}}g.n二G・>n;g.e=G->e;}voidDispMat(MGraphg){intij;for(i=0;i

6、nti;ArcNode*p;for(i=0;in;i++){p=G->adjlist[i].firstarc;printf(吆3d:”,i);while(p!=NULL){printff'%3d(%d)",p->adjvexzp->info);p=p->nextarc;}printf("");}}intvisited[MAXV];voidDFS(ALGraph*G,intv){ArcNode*p;visited[v]=l;printf("%2d,,/v);p=G->adjlist[v].firstarc;while(p!=NULL){if(visited[p->ad

7、jvex]==O)DFS(G,p->adjvex);p=p->nextarc;}voidBFS(ALGraph*G,intv){ArcNode*p;intqueue[MAXV]/front=0/rear=0;intvisited[MAXV];intw,i;for(i=0;in;i++)visited[i]=O;printf(,,%2d"/v);visited[v]=l;rear=(rear+l)%MAXV;queue[rear]=v;while(front!=rear){front=