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

1、精選優(yōu)質(zhì)文檔-傾情為你奉上/*題目：編寫按鍵盤輸入的數(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 30typedef struct /圖的鄰接表的結(jié)構(gòu)體 char valueGRAPHMAX; /記錄圖中的

2、點(diǎn)值 int dataGRAPHMAXGRAPHMAX; /記錄圖中的邊的關(guān)系 int n, e; /記錄圖中的點(diǎn)的個(gè)數(shù)及邊的個(gè)數(shù)pGraph;typedef struct /隊(duì)列結(jié)構(gòu)體 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 *G, int i);void

3、 initQueue(grQueue *Q);int queueEmpty(grQueue *Q);int queueFull(grQueue *Q);int outQueue(grQueue *Q);void inQueue(grQueue *Q, int i);int visitedGRAPHMAX; /用于標(biāo)志性的數(shù)組（全局變量）void main() pGraph G; int choice, i, j, k = 1; printf("建立一個(gè)有向圖的鄰接矩陣表示n"); createCraph(&G); printf("已建立一個(gè)圖的鄰接矩陣存儲(chǔ)

4、nn"); 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"); printf("* 1-更新鄰接矩陣 *n"); printf("* 2-深度優(yōu)先遍歷 *n"); printf("* 3-廣度優(yōu)先遍歷 *n"); printf(&q

5、uot;* 0- 返 回 *n"); printf("*n"); printf("請(qǐng)選擇菜單號(hào)（0-3）："); fflush(stdin); scanf("%d", &choice); switch(choice) case 1: createCraph(&G); printf("圖的鄰接矩陣存儲(chǔ)成功nn"); break; case 2: DFSTraverse(&G); break; case 3: BFSTraverse(&G); break; case 0: k

6、= 0; break; default: printf("輸入錯(cuò)誤，請(qǐng)重新輸入。"); getchar(); k = 1; break; void createCraph(pGraph *G) /建立鄰接表 int i, j, k; char ch1, ch2; printf("請(qǐng)輸入定點(diǎn)數(shù)，邊數(shù)（格式如3,3）:"); scanf("%d,%d",&(G->n), &(G->e); for(i = 0; i < G->n; i+) /輸入頂點(diǎn)值 getchar(); printf("

7、請(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; k+) getchar(); printf("請(qǐng)輸入第%d條邊的頂點(diǎn)值（格式4,5）：", k+1); scanf("%c,%c", &ch1, &ch2); /構(gòu)建鄰接表 for

8、 (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 < G->n; i+) visitedi = 0; for (i = 0; i < G->n;i+) if (!visitedi) DFS(G, i); /廣度遍歷void BFSTraverse(pGraph *G) i

9、nt i; for (i = 0; i < G->n; i+) 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->valuei); visitedi = 1; for (j = 0; j<G->n; j+) if (G->dataij = 1&&!visitedj) DFS(G, j); void BFS(pGra

10、ph *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); for (j = 0; j<G->n; j+) if (G->datakj = 1&&!visitedj) visitedj = 1; inQueue(&Q, j); void

11、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 = QUEUEMAX;int outQueue(grQueue *Q) /出隊(duì) int temp; if (queueEmpty(Q) printf("隊(duì)列為空。"); return -1; else temp = Q->queueDataQ->front; /出隊(duì)的元素 Q->count-; Q->front = (Q->front+1)%QUEUEMAX; return temp; void inQueue(grQueue *