数据结构实验5

1云南大学软件学院实验报告课程：数据结构实验学期：2014-2015学年第一学期任课教师：专业：信息安全学号：姓名：成绩：实验5图基础实验一、实验目的1.掌握图的存储结构及其遍历。二、实验软硬件环境（CPU、OS、IDE）：三、实验任务（要求写出核心代码，并对运行结果截图）1）使用邻接矩阵和邻接表储表示分别实现如下给定的图1、图2、图3所示图的物理存储结构。2）在1）所建立的图形存储结构上分别实现深度优先搜索遍历和广度优先搜索遍历，并给出遍历结果（序列）。图1无向图V1V2V4V5V3V7V6V8装订线2实验代码：#includestdio.h#includestdlib.h#defineMAXVEX20#defineOK1#defineERROR0#defineOVERFLOW-1#defineINFINITY65535#defineQueueSize20//队列中最大元素个数图2无向图V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8图3有向图3typedefintQElemType;//队列的元素的类型typedefintVertexType;typedefintEdgeType;typedefenum{False,True}Boolean;//Boolean是布尔类型，其值是ture或falseBooleanvisited[MAXVEX];//访问标志的数组。typedefstruct{VertexTypevexs[MAXVEX];EdgeTypearc[MAXVEX][MAXVEX];intnumVertexes,numEdges;}MGraph;//邻接矩阵。typedefstructEdgeNode//边表结点。{intadjvex;structEdgeNode*next;}EdgeNode;typedefstructVertexNode//顶点表结点。{intdata;EdgeNode*firstedge;}VertexNode,AdjList[MAXVEX];typedefstruct{AdjListadjlist;intnumVertexes,numEdges;//图中当前顶点数边数。}GraphAdjList;typedefstructNode//队列结点。{QElemTypedata;structNode*next;}Node,*QNode;typedefstruct//队列的顺序存储结构。{QNodefront;QNoderear;intcount;}SqQueue;intInitqueue(SqQueue*Q)//初始化一个空队列。{Q-front=Q-rear=(QNode)malloc(sizeof(Node));if(!Q-front)returnERROR;elseQ-front-next=NULL;4Q-count=0;returnOK;}intEnQueue(SqQueue*Q,QElemTypee)//若队列未满，则插入新的元素在队尾。{if(Q-count==QueueSize)returnERROR;elseQ-count++;QNodep=(QNode)malloc(sizeof(Node));if(!p)exit(OVERFLOW);p-data=e;p-next=NULL;Q-rear-next=p;Q-rear=p;returnOK;}intDeQueue(SqQueue*Q,int*e)//取队列队头的元素{QNodep;if(Q-count==0)returnERROR;elsep=Q-front-next;Q-front-next=p-next;if(Q-rear==p)Q-rear=Q-front;*e=p-data;Q-count--;free(p);returnOK;}intQueueEmpty(SqQueue*Q)//队列是否为空的判断。{if(Q-front==Q-rear)return1;elsereturn0;}intCreateMGraph(MGraph*G)//创建邻接矩阵。{inti,j,k,w,n;VertexTypea,b;printf(输入顶点数和边数（空格隔开、回车结束）：\n);fflush(stdin);scanf(%d%d,&G-numVertexes,&G-numEdges);printf(输入各个顶点的值（空格隔开、回车结束）：\n);5for(i=0;iG-numVertexes;i++){getchar();scanf(%d,&G-vexs[i]);}for(i=0;iG-numVertexes;i++){for(j=0;jG-numVertexes;j++){G-arc[i][j]=0;}}printf(请选择创建有向图（输入1）还是无向图（输入0）（回车结束）：);scanf(%d,&n);if(n==0){for(k=0;kG-numEdges;k++){printf(请输入第%d条边的顶点序号（空格隔开、回车结束）：,k+1);fflush(stdin);scanf(%d%d,&a,&b);for(i=0;a!=G-vexs[i];i++);for(j=0;b!=G-vexs[j];j++);G-arc[i][j]=1;G-arc[j][i]=1;}printf(\n输出创建的无向图邻接矩阵：\n\n);printf();for(i=0;iG-numVertexes;i++){printf(%d,i+1);}printf(\n\n);for(i=0;iG-numVertexes;i++){printf(%d,i+1);for(j=0;jG-numVertexes;j++){if(G-arc[i][j]==1)printf(1);elseprintf(0);}printf(\n);}6printf(\n);}if(n==1){for(k=0;kG-numEdges;k++){printf(请输入第%d条边的顶点序号（空格隔开、回车结束）：,k+1);fflush(stdin);scanf(%d%d,&a,&b);for(i=0;a!=G-vexs[i];i++);for(j=0;b!=G-vexs[j];j++);G-arc[i][j]=1;}printf(\n输出创建的有向图邻接矩阵：\n\n);printf();for(i=0;iG-numVertexes;i++){printf(%d,i+1);}printf(\n\n);for(i=0;iG-numVertexes;i++){printf(%d,i+1);for(j=0;jG-numVertexes;j++){if(G-arc[i][j]==1)printf(1);elseprintf(0);}printf(\n);}printf(\n);}if(n!=0&&n!=1){printf(\n输入错误！！将得到错误结果\n);return0;}}voidDFS(MGraph*G,inti)//邻接矩阵的深度优先遍历算法。{intj;visited[i]=True;printf(v%d,G-vexs[i]);//打印顶点。7for(j=0;jG-numVertexes;j++){if(G-arc[i][j]==1&&!visited[j])DFS(G,j);//对于未访问的邻接顶点使用递归调用。}}voidDFSTraverse(MGraph*G)//邻接矩阵的深度遍历操作。{inti;for(i=0;iG-numVertexes;i++)visited[i]=False;for(i=0;iG-numVertexes;i++){if(!visited[i])DFS(G,i);}}voidBFSTraverse(MGraph*G)//邻接矩阵的广度优先遍历。{inti,j;SqQueueQ;for(i=0;iG-numVertexes;i++)visited[i]=False;Initqueue(&Q);for(i=0;iG-numVertexes;i++){if(!visited[i]){visited[i]=True;printf(v%d,G-vexs[i]);EnQueue(&Q,i);while(!QueueEmpty(&Q)){DeQueue(&Q,&i);for(j=0;jG-numVertexes;j++){if(G-arc[i][j]==1&&!visited[j]){visited[j]=True;printf(v%d,G-vexs[j]);EnQueue(&Q,j);}}}8}}}intLocateVex(GraphAdjList*G1,intv)//返回节点v在图中的位置{inti;for(i=1;i=G1-numVertexes;i++){if(G1-adjlist[i].data==v)break;elsecontinue;}if(i=G1-numVertexes)returni;elsereturn-1;}intFirstAdjvex(GraphAdjListG1,intv)//返回G中第v个顶点的第1个邻接点的序号。如果v无邻接点，返回0。{if(G1.adjlist[v].firstedge)returnG1.adjlist[v].firstedge-adjvex;elsereturn0;}intNextAdjvex(GraphAdjListG1,intv,intw)//返回G中第v个顶点的相对于顶点w的下一个邻接点的序号。//如果v无相对于顶点w的下一个邻接点，返回0。{EdgeNode*p;intflag=0;p=G1.adjlist[v].firstedge;while(p){if(p-adjvex==w){flag=1;break;}p=p-next;}if(flag&&p-next)returnp-next-adjvex;else9return0;}intCreateALGraph(GraphAdjList*G1)//创建邻接表。{inti,j,k,n,x,y;EdgeNode*e,*p,*q;p=(EdgeNode*)malloc(sizeof(EdgeNode));printf(输入顶点数和边数（空格隔开、回车结束）：\n);scanf(%d%d,&G1-numVertexes,&G1-numEdges);printf(输入顶点（空格隔开、回车结束）：\n);for(i=1;i=G1-numVertexes;i++){getchar();scanf(%d,&G1-adjlist[i].data);G1-adjlist[i].firstedge=NULL;}printf(请选择创建有向图（输入1）还是无向图（输入0）：);scanf(%d,&n);if(n==0){for(k=1;k=G1-numEdges;k++){printf(请输入第%d条边的顶点序号（空格隔开、回车结束）：,k);fflush(stdin);scanf(%d%d,&x,&y);i=LocateVex(G1,x);j=LocateVex(G1,y);e=(EdgeNode*)malloc(sizeof(EdgeNode));e-adjvex=j;e-next=NULL;if(!G1-adjlist[i].firstedge){G1-adjlist[i].firstedge=e-next;;G1-adjlist[i].firstedge=e;}else{for(p=G1-adjlist[i].firstedge;p-next;p=p-next){p-next=p-next;}p-next=e-next;