数据结构实验3图的遍历

《数据结构实验3图的遍历》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、灌海工含淀针其机工趕孝院实验报告书课程名：《数据结构》题目，实验3图型数据结构实验图的建立和遍历班级：学号：姓名：评语：成绩：指导教师：批阅时间：年月实验3图的建立和遍历实验目的和要求1.熟悉图的两种常用的存储结构，邻接矩阵和邻接表。1.在这两种存储结构上的两种遍历图的方法，即深度优先遍历和广度优先遍历。2.进一步掌握递归算法的设计方法。实验环境TurboC或VC++实验学时4学吋，必做实验实验内容和步骤要求凼图外对所凼的图进行DFS和BFS遍历。如：建立阁的邻接表比较复杂，完成有W难的同学可以参考以卜例

2、程，学有余力的同学可以实现Prim算法求最小生成树。t#defineN10#defineINFINITY32768#defineTrue1#defineFalse0#defineError-1#dcfincOk1#include"stdlib.hninclude"stdio.h'1typedefenum{DG,DN,UDG,UDN}GraphKind;typedefcharVertexData;*/typedefstructArcNode2intadjvex;structArcNode2*nextarc;

3、)ArcNode2;typedefstructVertexNode{VertexDatadata;ArcNode2*firstarc;}VertexNode;typedefstruct{VertexNodevertexfN];intvexnum2，arcnum2;GraphKindkind2;JAdjList;/**/typedefstructNode{intdata;structNode*next;JLinkQueueNode;typedefstruct{LinkQueueNode*front;Link

4、QueueNode*rear;JLinkQueue;intInitQueue(LinkQueue*Q){Q->front=(LinkQueueNode*)malloc(sizeof(LinkQueueNode));if(Q->front!=NULL){Q->rear=Q->front;Q->front->next=NULL;return(True);}elsereturn(False);}intEnterQueue(LinkQueue*Q，intx)LinkQueueNode*NewNode;NewNod

5、e=(LinkQueueNode*)malloc(sizeof(LinkQueueNode));if(NewNode!=NULL){NewNode->data=x;NewNode-〉next=NULL;Q->rear->next=NewNode;Q->rear=NewNode;return(True);}elsereturn(False);}intDeleteQueue(LinkQueue*Q，int*x){LinkQueueNode*p;if(Q-〉front==Q-〉rear)retum(False)

6、;p=Q->front->next;Q-〉front-〉next=p-〉next;if(Q->rear==p)Q->rear=Q->front;*x=p->data;free(p);retum(True);}intIsEmpty(LinkQueue*Q){if(Q->front==Q->rcar)return(True);elseretum(False);typedefstructnode1{chardata;structnode1*next;JNodel,*LinkListl;typedefstruct

7、node2chardatal;chardata2;structnode2*next;}Node2,*LinkList2;inta[2];intvisited[N];intLocateVertex2(AdjList*G2，VertexDatav){intk，j=Error;for(k=0;kvexnum2;k++)if(G2->vertex[kj.data==v){j=k;break;}return(j);}intCreateUDG2(AdjList*G2){inti，j，k;ArcNode2*p

8、,*r;VertexDatavl,v2;printf(’'ninputG-〉vexnum，G-〉arcnumn);scanf("%d,%d",&(G2->vexnum2),&(G2->arcnum2));getchar();printf("inputG->vexsH);for(i=0;ivertex[i].data));G2->vertex[i].f