數(shù)據(jù)結(jié)構(gòu)：圖子系統(tǒng)

1、WORD格式/* 題目：編寫按鍵盤輸入的數(shù)據(jù)建立圖的鄰接矩陣存儲(chǔ)* 編寫圖的深度優(yōu)先遍歷程序* 編寫圖的廣度優(yōu)先遍歷程序* 設(shè)計(jì)一個(gè)選擇式菜單形式如下：*圖子系統(tǒng)* *1-更新鄰接矩陣*2-深度優(yōu)先遍歷*3-廣度優(yōu)先遍歷*0-返回* * 請(qǐng)選擇菜單號(hào) 0-3：*/#include <stdio.h>#include <stdlib.h>#define GRAPHMAX 30#define QUEUEMAX 30專業(yè)資料整理WORD格式typedef struct/ 圖的鄰接表的構(gòu)造體專業(yè)資料整理WORD格式char valueGRAPHMAX;/ 記錄圖中的點(diǎn)值int

2、dataGRAPHMAXGRAPHMAX;/ 記錄圖中的邊的關(guān)系int n, e;/ 記錄圖中的點(diǎn)的個(gè)數(shù)及邊的個(gè)數(shù)pGraph;專業(yè)資料整理WORD格式typedef struct/ 隊(duì)列構(gòu)造體專業(yè)資料整理WORD格式int queueDataQUEUEMAX;int front, rear, count;/ 隊(duì)頭，隊(duì)尾，數(shù)目grQueue;void createCraph(pGraph *G);void DFSTraverse(pGraph *G);void BFSTraverse(pGraph *G);void DFS(pGraph *G, int i);void BFS(pGraph *

3、G, int i);void initQueue(grQueue *Q);int queueEmpty(grQueue *Q);int queueFull(grQueue *Q);int outQueue(grQueue *Q);void inQueue(grQueue *Q, int i);專業(yè)資料整理WORD格式int visitedGRAPHMAX;/ 用于標(biāo)志性的數(shù)組全局變量void main()pGraph G;int choice, i, j, k = 1;專業(yè)資料整理WORD格式printf(" 建立一個(gè)有向圖的鄰接矩陣表示 createCraph(&G);n&

4、quot;);專業(yè)資料整理WORD格式printf("已建立一個(gè)圖的鄰接矩陣存儲(chǔ)nn");專業(yè)資料整理WORD格式for (i = 0; i<G.n; i+)for(j = 0; j<G.n; j+)printf("%5d", G.dataij);printf("n");while (k)printf("n圖子系統(tǒng) n");printf("*n");專業(yè)資料整理WORD格式printf("*printf("*printf("*printf("*

5、1- 更新鄰接矩陣2- 深度優(yōu)先遍歷3- 廣度優(yōu)先遍歷0-返回*n");*n");*n");*n");專業(yè)資料整理WORD格式printf("*n");專業(yè)資料整理WORD格式printf(" 請(qǐng)選擇菜單號(hào) fflush(stdin); scanf("%d", &choice);0-3： ");專業(yè)資料整理WORD格式switch(choice)case 1:createCraph(&G);printf(" 圖的鄰接矩陣存儲(chǔ)成功break;case 2:nn"

6、);專業(yè)資料整理WORD格式DFSTraverse(&G);break;case 3:BFSTraverse(&G);專業(yè)資料整理WORD格式break;case 0:k = 0;break;default:printf(" 輸入錯(cuò)誤，請(qǐng)重新輸入。");getchar();k = 1;break;void createCraph(pGraph *G) / 建立鄰接表int i, j, k;char ch1, ch2;專業(yè)資料整理WORD格式printf(" 請(qǐng)輸入定點(diǎn)數(shù)，邊數(shù)格式如 scanf("%d,%d",&(G-&

7、gt;n), &(G->e);3,3 :");專業(yè)資料整理WORD格式for(i = 0; i < G->n; i+)/ 輸入頂點(diǎn)值專業(yè)資料整理WORD格式getchar();printf(" 請(qǐng)輸入第 %d 頂點(diǎn)的值： ", i+1);scanf("%c", &(G->valuei);/ 初始化鄰接表for (i = 0; i<G->n; i+)for (j = 0; j<G->n; j+)G->dataij = 0;for (k = 0; k < G->e;

8、k+)getchar();printf(" 請(qǐng)輸入第 %d 條邊的頂點(diǎn)值格式4,5： ", k+1);scanf("%c,%c", &ch1, &ch2);專業(yè)資料整理WORD格式/ 構(gòu)建鄰接表for (i = 0; i<G->n; i+)if (ch1 = G->valuei)for (j = 0; j<G->n; j+)if (ch2 = G->valuej)G->dataij = 1;/ 深度遍歷void DFSTraverse(pGraph *G)int i;for (i = 0; i &

9、lt; G->n; i+)visitedi = 0;for (i = 0; i < G->n;i+)if (!visitedi)DFS(G, i);/ 廣度遍歷void BFSTraverse(pGraph *G)int i;for (i = 0; i < G->n; i+)專業(yè)資料整理WORD格式visitedi = 0;for (i = 0; i < G->n;i+)if (!visitedi)BFS(G, i);void DFS(pGraph *G, int i)int j;printf(" 深度優(yōu)先遍歷序列：%cn", G-

10、>valuei);visitedi = 1;for (j = 0; j<G->n; j+)if (G->dataij = 1&&!visitedj)DFS(G, j);void BFS(pGraph *G, int i)int k, j;grQueue Q;initQueue(&Q);/ 初始化visitedi = 1;inQueue(&Q, i);while (!queueEmpty(&Q)k = outQueue(&Q);printf(" 廣度優(yōu)先遍歷序列：%cn", G->valuek);f

11、or (j = 0; j<G->n; j+)if (G->datakj = 1&&!visitedj)專業(yè)資料整理WORD格式visitedj = 1;inQueue(&Q, j);void initQueue(grQueue *Q)/ 隊(duì)列初始化Q->front = Q->rear = 0;Q->count = 0;int queueEmpty(grQueue *Q)/ 隊(duì)列判空return Q->count = 0;int queueFull(grQueue *Q)/ 隊(duì)列判滿return Q->count = QUE

12、UEMAX;專業(yè)資料整理WORD格式int outQueue(grQueue *Q)/ 出隊(duì)專業(yè)資料整理WORD格式int temp;專業(yè)資料整理WORD格式if (queueEmpty(Q)專業(yè)資料整理WORD格式printf(" 隊(duì)列為空。return -1;");專業(yè)資料整理WORD格式else專業(yè)資料整理WORD格式temp = Q->queueDataQ->front;Q->count-;Q->front = (Q->front+1)%QUEUEMAX;return temp;/ 出隊(duì)的元素專業(yè)資料整理WORD格式專業(yè)資料整理WORD格式void inQueue(grQueue *Q, in