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

1、/*題目：編寫(xiě)按鍵盤(pán)輸入的數(shù)據(jù)建立圖的鄰接矩陣存儲(chǔ)* 編寫(xiě)圖的深度優(yōu)先遍歷程序* 編寫(xiě)圖的廣度優(yōu)先遍歷程序* 設(shè)計(jì)一個(gè)選擇式菜單形式如下：* 圖 子 系 統(tǒng)* * * 1-更新鄰接矩陣 * * 2-深度優(yōu)先遍歷 * * 3-廣度優(yōu)先遍歷 * * 0- 返 回 * * 請(qǐng)選擇菜單號(hào)（0-3）：*/#include #include #define GRAPHMAX 30#define QUEUEMAX 30typedef struct /圖的鄰接表的結(jié)構(gòu)體 char valueGRAPHMAX; /記錄圖中的點(diǎn)值 int dataGRAPHMAXGRAPHMAX; /記錄圖中的邊的關(guān)系 int

2、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 initQueue(grQueue *Q);int queueEmpty(grQueu

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

4、 i n; i+) /輸入頂點(diǎn)值 getchar(); printf(請(qǐng)輸入第%d頂點(diǎn)的值：, i+1); scanf(%c, &(G-valuei); /初始化鄰接表 for (i = 0; in; i+) for (j = 0; jn; j+) G-dataij = 0; for (k = 0; k e; k+) getchar(); printf(請(qǐng)輸入第%d條邊的頂點(diǎn)值（格式4,5）：, k+1); scanf(%c,%c, &ch1, &ch2); /構(gòu)建鄰接表 for (i = 0; in; i+) if (ch1 = G-valuei) for (j = 0; jn; j+) i

5、f (ch2 = G-valuej) G-dataij = 1; /深度遍歷void DFSTraverse(pGraph *G) int i; for (i = 0; i n; i+) visitedi = 0; for (i = 0; i n;i+) if (!visitedi) DFS(G, i); /廣度遍歷void BFSTraverse(pGraph *G) int i; for (i = 0; i n; i+) visitedi = 0; for (i = 0; i n;i+) if (!visitedi) BFS(G, i); void DFS(pGraph *G, int i

6、) int j; printf(深度優(yōu)先遍歷序列：%cn, G-valuei); visitedi = 1; for (j = 0; jn; 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); for (j = 0; jn;

7、 j+) if (G-datakj = 1&!visitedj) 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 = 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 *Q, int i) /入隊(duì) if (que