#include <stdio.h> #include <stdlib.h> #define MaxSize 10 int visited[MaxSize]={0}; typedef char DataType; typedef struct { DataType vertex[MaxSize]; int edge[MaxSize][MaxSize]; int vertexNum, edgeNum; } MGraph; void func1(MGraph *G, DataType a[ ], int n, int e) { int i, j, k; G->vertexNum = n; G->edgeNum = e; for (i = 0; i < G->vertexNum; i++) G->vertex[i] = a[i]; for (i = 0; i < G->vertexNum; i++) for (j = 0; j < G->vertexNum; j++) G->edge\[i\]\[j\] = 0; for (k = 0; k < G->edgeNum; k++) { printf("输入边依附的顶点编号:"); scanf("%d%d", &i, &j); G->edge[i][j] = 1; G->edge[j][i] = 1; } } void func2(MGraph *G, int v) { int j; printf("%c ", G->vertex[v]); visited[v] = 1; for (j = 0; j < G->vertexNum; j++) if (G->edge[v][j] == 1 && visited[j] == 0) func2(G, j); } 1、解释结构体struct的内容和含义(4分) 2、解释func1的函数的作用,包含整个函数的输入输出函数,代码段的作用(8分) 解释func2的函数的作用,包含整个函数的输入输出函数,代码段的作用(8分)
时间: 2024-04-26 15:25:36 浏览: 180
1、结构体struct定义了一个名为MGraph的结构体类型,其中包含了一个顶点数组vertex,一个边数组edge,一个顶点数vertexNum和一条边数edgeNum。这个结构体用来描述一个图的基本信息。
2、函数func1的作用是根据输入的顶点信息和边信息构建一个图,并将其存储在MGraph结构体中。其中,函数的输入参数包括一个指向MGraph结构体的指针G,一个字符类型的顶点数组a,一个整型变量n表示顶点数,一个整型变量e表示边数。函数的输出参数为构建好的图信息存储在MGraph结构体中。
函数的代码段首先将输入的顶点信息存储在MGraph结构体中,然后将边数组中的所有元素初始化为0。接着,循环读入边信息,并将对应的边在边数组中标记为1,表示两个顶点之间有边。
函数func2的作用是进行深度优先遍历,并输出遍历结果。其中,函数的输入参数包括一个指向MGraph结构体的指针G,一个整型变量v表示遍历起始点。函数的输出参数为遍历结果。
函数的代码段首先输出遍历起始点的顶点信息,并将其标记为已访问过。然后循环遍历起始点的所有相邻顶点,并递归调用函数func2来遍历这些相邻顶点。在遍历相邻顶点之前,需要先判断该顶点是否已经被访问过,以避免重复访问。
相关问题
优化这段代码#include<stdio.h> #include<stdlib.h> #define Maxsize 10 int visited[Maxsize]={0}; typedef char DataType; typedef struct { DataType vertex[Maxsize]; int edge[Maxsize][Maxsize]; int vertexNum,edgeNum; }MGraph; void CreatGraph(MGraph*G,DataType a[],int n,int e) { int i,j,k; G->vertexNum=n; G->edgeNum=e; for(i=0;i<G->vertexNum;i++) { G->vertex[i]=a[i]; } for(i=0;i<G->vertexNum;i++) { for(j=0;j<G->vertexNum;j++) { G->edge[i][j]=0; } } printf("输入边的位置:"); for(k=0;k<=G->edgeNum;k++) { scanf("%d%d",&i,&j); getchar(); G->edge[i][j]=1; G->edge[j][i]=1; } } void DFSTraverse(MGraph*G,int v) { printf("%c",G->vertex[v]); visited[v]=1; for(int j=0;j<=G->vertexNum;j++) { if(G->edge[v][j]==1&&visited[j]==0) DFSTraverse(G,j); } } void BFSTraverse(MGraph*G,int v) { printf("%c",G->vertex[v]); visited[v]=1; for(int j=0;j<=G->vertexNum;j++) { if(G->edge[j][v]==1&&visited[v]==0) DFSTraverse(G,j); } } void BFSTraverseclear(MGraph*G) { int i; for(i=1; i<G->vertexNum; i++) { visited[i]=0; } } int main() { MGraph MG; int i,t,h; printf("输入顶点数"); scanf("%d",&t); printf("输入边数"); scanf("%d",&h); char ch[t]; printf("输入顶点值"); for(i=0;i<t;i++) { scanf("%c",&ch[i]); } CreatGraph(&MG,ch,t,h); for(i=0;i<t;i++) visited[i]=0; printf("深度遍历"); DFSTraverse(&MG,0); printf("\n广度遍历"); BFSTraverseclear(&MG); BFSTraverse(&MG,0); return 0; }
首先,可以将一些重复的代码进行封装,例如将深度优先遍历和广度优先遍历中的 visited 数组清零的操作封装成一个函数。同时,在输入边的位置时,可以使用循环而非递归,避免重复代码。
下面是优化后的代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define Maxsize 10
typedef char DataType;
typedef struct {
DataType vertex[Maxsize];
int edge[Maxsize][Maxsize];
int vertexNum, edgeNum;
} MGraph;
int visited[Maxsize] = {0};
void CreatGraph(MGraph *G, DataType a[], int n, int e) {
int i, j, k;
G->vertexNum = n;
G->edgeNum = e;
for (i = 0; i < G->vertexNum; i++) {
G->vertex[i] = a[i];
}
for (i = 0; i < G->vertexNum; i++) {
for (j = 0; j < G->vertexNum; j++) {
G->edge[i][j] = 0;
}
}
printf("输入边的位置:");
for (k = 0; k < G->edgeNum; k++) {
scanf("%d%d", &i, &j);
getchar();
G->edge[i][j] = 1;
G->edge[j][i] = 1;
}
}
void TraverseClear(MGraph *G) {
int i;
for (i = 0; i < G->vertexNum; i++) {
visited[i] = 0;
}
}
void DFS(MGraph *G, int v) {
printf("%c", G->vertex[v]);
visited[v] = 1;
for (int j = 0; j < G->vertexNum; j++) {
if (G->edge[v][j] == 1 && visited[j] == 0) {
DFS(G, j);
}
}
}
void DFSTraverse(MGraph *G, int v) {
TraverseClear(G);
DFS(G, v);
}
void BFS(MGraph *G, int v) {
int queue[Maxsize], front = 0, rear = 0;
printf("%c", G->vertex[v]);
visited[v] = 1;
queue[rear++] = v;
while (front != rear) {
int w = queue[front++];
for (int j = 0; j < G->vertexNum; j++) {
if (G->edge[w][j] == 1 && visited[j] == 0) {
printf("%c", G->vertex[j]);
visited[j] = 1;
queue[rear++] = j;
}
}
}
}
void BFSTraverse(MGraph *G, int v) {
TraverseClear(G);
BFS(G, v);
}
int main() {
MGraph MG;
int t, h;
printf("输入顶点数:");
scanf("%d", &t);
printf("输入边数:");
scanf("%d", &h);
char ch[t];
printf("输入顶点值:");
for (int i = 0; i < t; i++) {
scanf(" %c", &ch[i]);
}
CreatGraph(&MG, ch, t, h);
printf("深度遍历:");
DFSTraverse(&MG, 0);
printf("\n广度遍历:");
BFSTraverse(&MG, 0);
return 0;
}
```
#include <stdio.h> #include <stdlib.h> #define maxsize 10 int visited[maxsize]={0}; typedef char datatype; typedef struct { datatype vertex[maxsize]; int edge[maxsize][maxsize]; int vertexnum,edgenum; }mgraph; void creatgraph(mgraph *G,datatype a[],int n,int e) { int i,j,k; G->vertexnum=n; G->edgenum=e; for(i=0;i<G->vertexnum;i++) G->vertex[i]=a[i]; for(i=0;i<G->vertexnum;i++) { for(j=0;j<G->vertexnum;j++) G->edge[i][j]=0; } for(k=0;k<G->edgenum;k++) { scanf("%d%d",&i,&j); G->edge[i][j]=1; G->edge[j][i]=1; } } void dfraverse(mgraph *G,int v) { printf("%c",G->vertex[v]); visited[v]=1; int j=0; for(j=0;j<G->vertexnum;j++) { if(G->edge[v][j]==1&&visited[j]==0) dfraverse(G,j); } } void bftraverse(mgraph *G,int v) { int i,j,Q[maxsize]; int front=-1; int rear=-1; printf("%c",G->vertex[v]); visited[v]=1; Q[++rear]=v; while(front!=rear) { i=Q[++front]; for(j=0;j<G->vertexnum;j++) { if(G->edge[i][j]==1&&visited[j]==0) { printf("%c",G->vertex[j]); visited[j]=1; Q[++rear]=j; } } } } int main () { int i; char ch[]={'A','B','C','D','E'}; mgraph MG; creatgraph(&MG,ch,5,6); for(i=0;i<maxsize;i++) visited[i]=0; dfraverse(&MG,0); for(i=0;i<maxsize;i++) visited[i]=0; bftraverse(&MG,0); return 0; }
这段代码的问题不大,可能是由于代码格式问题导致看起来不太清晰。如果需要改进,可以尝试对代码进行一些注释,以便更好地理解代码的功能和实现方式。以下是一些注释的示例:
```c
#include <stdio.h>
#include <stdlib.h>
#define maxsize 10
int visited[maxsize]={0}; //定义一个全局数组,表示节点是否被访问过
typedef char datatype;
typedef struct {
datatype vertex[maxsize]; //存储节点名称的数组
int edge[maxsize][maxsize]; //邻接矩阵
int vertexnum,edgenum; //节点数目和边数目
}mgraph;
void creatgraph(mgraph *G,datatype a[],int n,int e) {
int i,j,k;
G->vertexnum=n;
G->edgenum=e;
for(i=0;i<G->vertexnum;i++)
G->vertex[i]=a[i]; //初始化节点名称
for(i=0;i<G->vertexnum;i++)
{
for(j=0;j<G->vertexnum;j++)
G->edge[i][j]=0; //初始化邻接矩阵
}
for(k=0;k<G->edgenum;k++)
{
int i,j;
scanf("%d%d",&i,&j);
G->edge[i][j]=1;
G->edge[j][i]=1; //读入节点之间的关系,构建邻接矩阵
}
}
void dfraverse(mgraph *G,int v) {
printf("%c",G->vertex[v]); //输出当前遍历的节点名称
visited[v]=1; //标记该节点已被访问
int j=0;
for(j=0;j<G->vertexnum;j++)
{
if(G->edge[v][j]==1&&visited[j]==0)
dfraverse(G,j); //递归遍历与当前节点相邻的未被访问的节点
}
}
void bftraverse(mgraph *G,int v) {
int i,j,Q[maxsize];
int front=-1;
int rear=-1;
printf("%c",G->vertex[v]); //输出当前遍历的节点名称
visited[v]=1; //标记该节点已被访问
Q[++rear]=v;
while(front!=rear)
{
i=Q[++front];
for(j=0;j<G->vertexnum;j++)
{
if(G->edge[i][j]==1&&visited[j]==0)
{
printf("%c",G->vertex[j]); //输出当前遍历的节点名称
visited[j]=1; //标记该节点已被访问
Q[++rear]=j;
}
}
}
}
int main () {
int i;
char ch[]={'A','B','C','D','E'};
mgraph MG;
creatgraph(&MG,ch,5,6); //创建图
for(i=0;i<maxsize;i++)
visited[i]=0; //初始化visited数组
dfraverse(&MG,0); //深度优先遍历
for(i=0;i<maxsize;i++)
visited[i]=0; //初始化visited数组
bftraverse(&MG,0); //广度优先遍历
return 0;
}
```
阅读全文