数据结构：图子系统(共7页).docx

《数据结构：图子系统(共7页).docx》由会员分享，可在线阅读，更多相关《数据结构：图子系统(共7页).docx（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上/*题目：编写按键盘输入的数据建立图的邻接矩阵存储* 编写图的深度优先遍历程序* 编写图的广度优先遍历程序* 设计一个选择式菜单形式如下：* 图 子 系 统* * * 1-更新邻接矩阵 * * 2-深度优先遍历 * * 3-广度优先遍历 * * 0- 返 回 * * 请选择菜单号（0-3）：*/#include #include #define GRAPHMAX 30#define QUEUEMAX 30typedef struct /图的邻接表的结构体 char valueGRAPHMAX; /记录图中的点值 int dataGRAPHMAXGRAPHMAX; /记

2、录图中的边的关系 int n, e; /记录图中的点的个数及边的个数pGraph;typedef struct /队列结构体 int queueDataQUEUEMAX; int front, rear, count; /队头，队尾，数目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 queu

3、eEmpty(grQueue *Q);int queueFull(grQueue *Q);int outQueue(grQueue *Q);void inQueue(grQueue *Q, int i);int visitedGRAPHMAX; /用于标志性的数组（全局变量）void main() pGraph G; int choice, i, j, k = 1; printf(建立一个有向图的邻接矩阵表示n); createCraph(&G); printf(已建立一个图的邻接矩阵存储nn); for (i = 0; iG.n; i+) for(j = 0; jn), &(G-e); fo

4、r(i = 0; i n; i+) /输入顶点值 getchar(); printf(请输入第%d顶点的值：, 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(请输入第%d条边的顶点值（格式4,5）：, k+1); scanf(%c,%c, &ch1, &ch2); /构建邻接表 for (i = 0; in; i+) if (ch1 = G-valuei) for (j = 0; j

5、n; j+) if (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 *

6、G, int i) int j; printf(深度优先遍历序列：%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(广度优先遍历序列：%cn, G-valuek); for (j

7、= 0; jn; j+) if (G-datakj = 1&!visitedj) visitedj = 1; inQueue(&Q, j); void initQueue(grQueue *Q) /队列初始化 Q-front = Q-rear = 0; Q-count = 0;int queueEmpty(grQueue *Q) /队列判空 return Q-count = 0;int queueFull(grQueue *Q) /队列判满 return Q-count = QUEUEMAX;int outQueue(grQueue *Q) /出队 int temp; if (queueEmpty(Q) printf(队列为空。); return -1; else temp = Q-queueDataQ-front; /出队的元素 Q-count-; Q-front = (Q-front+1)%QUEUEMAX; return temp; void inQueue(grQueue *Q, int i) /入队 if (queueFull(Q) printf(队列已满。); return; else Q-count+; /数目增加 Q-queueDataQ-rear = i; /入队 Q-rear = (Q-rear+1)%QUEUEMAX; /队尾指针移动 专心-专注-专业