数据结构：图子系统

1、WORD格式/* 题目：编写按键盘输入的数据建立图的邻接矩阵存储* 编写图的深度优先遍历程序* 编写图的广度优先遍历程序* 设计一个选择式菜单形式如下：*图子系统* *1-更新邻接矩阵*2-深度优先遍历*3-广度优先遍历*0-返回* * 请选择菜单号 0-3：*/#include <stdio.h>#include <stdlib.h>#define GRAPHMAX 30#define QUEUEMAX 30专业资料整理WORD格式typedef struct/ 图的邻接表的构造体专业资料整理WORD格式char valueGRAPHMAX;/ 记录图中的点值int

2、dataGRAPHMAXGRAPHMAX;/ 记录图中的边的关系int n, e;/ 记录图中的点的个数及边的个数pGraph;专业资料整理WORD格式typedef struct/ 队列构造体专业资料整理WORD格式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 *

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);专业资料整理WORD格式int visitedGRAPHMAX;/ 用于标志性的数组全局变量void main()pGraph G;int choice, i, j, k = 1;专业资料整理WORD格式printf(" 建立一个有向图的邻接矩阵表示 createCraph(&G);n&

4、quot;);专业资料整理WORD格式printf("已建立一个图的邻接矩阵存储nn");专业资料整理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图子系统 n");printf("*n");专业资料整理WORD格式printf("*printf("*printf("*printf("*

5、1- 更新邻接矩阵2- 深度优先遍历3- 广度优先遍历0-返回*n");*n");*n");*n");专业资料整理WORD格式printf("*n");专业资料整理WORD格式printf(" 请选择菜单号 fflush(stdin); scanf("%d", &choice);0-3： ");专业资料整理WORD格式switch(choice)case 1:createCraph(&G);printf(" 图的邻接矩阵存储成功break;case 2:nn"

6、);专业资料整理WORD格式DFSTraverse(&G);break;case 3:BFSTraverse(&G);专业资料整理WORD格式break;case 0:k = 0;break;default:printf(" 输入错误，请重新输入。");getchar();k = 1;break;void createCraph(pGraph *G) / 建立邻接表int i, j, k;char ch1, ch2;专业资料整理WORD格式printf(" 请输入定点数，边数格式如 scanf("%d,%d",&(G-&

7、gt;n), &(G->e);3,3 :");专业资料整理WORD格式for(i = 0; i < G->n; i+)/ 输入顶点值专业资料整理WORD格式getchar();printf(" 请输入第 %d 顶点的值： ", 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(" 请输入第 %d 条边的顶点值格式4,5： ", k+1);scanf("%c,%c", &ch1, &ch2);专业资料整理WORD格式/ 构建邻接表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+)专业资料整理WORD格式visitedi = 0;for (i = 0; i < G->n;i+)if (!visitedi)BFS(G, i);void DFS(pGraph *G, int i)int j;printf(" 深度优先遍历序列：%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(" 广度优先遍历序列：%cn", G->valuek);f

11、or (j = 0; j<G->n; j+)if (G->datakj = 1&&!visitedj)专业资料整理WORD格式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 = QUE

12、UEMAX;专业资料整理WORD格式int outQueue(grQueue *Q)/ 出队专业资料整理WORD格式int temp;专业资料整理WORD格式if (queueEmpty(Q)专业资料整理WORD格式printf(" 队列为空。return -1;");专业资料整理WORD格式else专业资料整理WORD格式temp = Q->queueDataQ->front;Q->count-;Q->front = (Q->front+1)%QUEUEMAX;return temp;/ 出队的元素专业资料整理WORD格式专业资料整理WORD格式void inQueue(grQueue *Q, in