【数据结构】图的存储和遍历实验报告.doc

《【数据结构】图的存储和遍历实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《数据结构B》实验报告系计算机与电子专业级01__班姓名学号2010年10月9日1.上机题目：图的存储和遍历2.详细设计#include#defineGRAPHMAX10#defineFALSE0#defineTRUE1#defineerrorprintf#defineQueueSize30typedefstruct{charvexs[GRAPHMAX];intedges[GRAPHMAX][GRAPHMAX];intn,e;}MGraph;intvisited[10];typede

2、fstruct{intfront,rear,count;intdata[QueueSize];}CirQueue;voidInitQueue(CirQueue*Q){Q->front=Q->rear=0;Q->count=0;}intQueueEmpty(CirQueue*Q){returnQ->count=QueueSize;}intQueueFull(CirQueue*Q){returnQ->count==QueueSize;}voidEnQueue(CirQueue*Q,intx){if(Que

3、ueFull(Q))error("Queueoverflow");else{Q->count++;Q->data[Q->rear]=x;Q->rear=(Q->rear+1)%QueueSize;}}intDeQueue(CirQueue*Q){inttemp;if(QueueEmpty(Q)){error("Queueunderflow");returnNULL;}else{temp=Q->data[Q->front];Q->count--;Q->front=(Q->front+1)%QueueSi

4、ze;returntemp;}}voidCreateMGraph(MGraph*G){inti,j,k;charch1,ch2;printf("tt请输入定点数，边数并按回车（格式如：3，4）：");scanf("%d,%d",&(G->n),&(G->e));for(i=0;in;i++){getchar();printf("tt请输入第%d个定点数并按回车：",i+1);scanf("%c",&(G->vexs[i]));}for(i=0;in;i++)for(j=

5、0;jn;j++)G->edges[i][j]=0;for(k=0;ke;k++){getchar();printf("tt请输入第%d条边的顶点序号（格式如：i,j）：",k+1);scanf("%c,%c",&ch1,&ch2);for(i=0;ch1!=G->vexs[i];i++);for(j=0;ch2!=G->vexs[j];j++);G->edges[i][j]=1;}}voidDFSM(MGraph*G,inti){intj;printf("tt深度优先

6、遍历序列：%c",G->vexs[i]);visited[i]=TRUE;for(j=0;jn;j++)if(G->edges[i][j]==1&&visited[j]!=1)////////////////DFSM(G,j);}voidBFSM(MGraph*G,intk){inti,j;CirQueueQ;InitQueue(&Q);printf("tt广度优先遍历序列：%c",G->vexs[k]);visited[k]=TRUE;EnQueue(&Q,k);while(

7、!QueueEmpty(&Q)){i=DeQueue(&Q);for(j=0;jn;j++)if(G->edges[i][j]==1&&visited[j]!=1){visited[j]=TRUE;EnQueue(&Q,j);}}}voidDFSTraverseM(MGraph*G){inti;for(i=0;in;i++)visited[i]=FALSE;for(i=0;in;i++)if(!visited[i])DFSM(G,i);}voidBFSTraverseM(MGr

8、aph*G){inti;for(i=0;in;i++)visited[i]=FALSE;for(i=0;in;i++)if(!visited[i])BFSM(G,i);}voidmain(){MGraph*G,a;charch1;inti,j,ch2;G=&a;printf("tt建立一个有向图的邻接矩阵表示");CreateMGraph(G);printf("tt已建立一个有向图的邻接矩阵存储");for(i=0