【數(shù)據(jù)結(jié)構(gòu)】圖的存儲(chǔ)和遍歷實(shí)驗(yàn)報(bào)告.doc

《【數(shù)據(jù)結(jié)構(gòu)】圖的存儲(chǔ)和遍歷實(shí)驗(yàn)報(bào)告.doc》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、《數(shù)據(jù)結(jié)構(gòu)B》實(shí)驗(yàn)報(bào)告系計(jì)算機(jī)與電子專業(yè)級(jí)01__班姓名學(xué)號(hào)2010年10月9日1.上機(jī)題目：圖的存儲(chǔ)和遍歷2.詳細(xì)設(shè)計(jì)#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請(qǐng)輸入定點(diǎn)數(shù)，邊數(shù)并按回車（格式如：3，4）：");scanf("%d,%d",&(G->n),&(G->e));for(i=0;in;i++){getchar();printf("tt請(qǐng)輸入第%d個(gè)定點(diǎn)數(shù)并按回車：",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請(qǐng)輸入第%d條邊的頂點(diǎn)序號(hào)（格式如：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深度優(yōu)先

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廣度優(yōu)先遍歷序列：%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建立一個(gè)有向圖的鄰接矩陣表示");CreateMGraph(G);printf("tt已建立一個(gè)有向圖的鄰接矩陣存儲(chǔ)");for(i=0