数据结构：图子系统(共7页).docx
精选优质文档-倾情为你奉上/*题目：编写按键盘输入的数据建立图的邻接矩阵存储* 编写图的深度优先遍历程序* 编写图的广度优先遍历程序* 设计一个选择式菜单形式如下：* 图 子 系 统* * * 1-更新邻接矩阵 * * 2-深度优先遍历 * * 3-广度优先遍历 * * 0- 返 回 * * 请选择菜单号（0-3）：*/#include <stdio.h>#include <stdlib.h>#define GRAPHMAX 30#define QUEUEMAX 30typedef struct /图的邻接表的结构体 char valueGRAPHMAX; /记录图中的点值 int dataGRAPHMAXGRAPHMAX; /记录图中的边的关系 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 queueEmpty(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; i<G.n; i+) for(j = 0; j<G.n; j+) printf("%5d", G.dataij); printf("n"); while (k) printf("n 图 子 系 统n"); printf("*n"); printf("* 1-更新邻接矩阵 *n"); printf("* 2-深度优先遍历 *n"); printf("* 3-广度优先遍历 *n"); printf("* 0- 返 回 *n"); printf("*n"); printf("请选择菜单号（0-3）："); fflush(stdin); scanf("%d", &choice); switch(choice) case 1: createCraph(&G); printf("图的邻接矩阵存储成功nn"); break; case 2: DFSTraverse(&G); break; case 3: BFSTraverse(&G); break; case 0: k = 0; break; default: printf("输入错误，请重新输入。"); getchar(); k = 1; break; void createCraph(pGraph *G) /建立邻接表 int i, j, k; char ch1, ch2; printf("请输入定点数，边数（格式如3,3）:"); scanf("%d,%d",&(G->n), &(G->e); for(i = 0; i < G->n; i+) /输入顶点值 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; k+) getchar(); printf("请输入第%d条边的顶点值（格式4,5）：", k+1); scanf("%c,%c", &ch1, &ch2); /构建邻接表 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 < 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+) 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->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); for (j = 0; j<G->n; 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; /队尾指针移动 专心-专注-专业
