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

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

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

2、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(QueueFull(Q))error("Queueoverflow");e

3、lse{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)%QueueSize;returntemp;}}voidCreateMGraph(MGraph*G){inti,j,k

4、;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=0;jn;j++)G->edges[i][j]=0;for(k=0;ke;k++){getchar();printf("

5、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深度优先遍历序列：%c",G->vexs[i]);visited[i]=TRUE;for(j=0;jn;j++)if(G->edges[i][j]==1&&visit

6、ed[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(!QueueEmpty(&Q)){i=DeQueue(&Q);for(j=0;jn;j++)if(G->edges[i][j]==1&&visited[j]!=1){visited[j]=TRUE

7、;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(MGraph*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;char

8、ch1;inti,j,ch2;G=&a;printf("tt建立一个有向图的邻接矩阵表示");CreateMGraph(G);printf("tt已建立一个有向图的邻接矩阵存储");for(i=0