PTA（图）1-1 采用邻接矩阵表示法创建无向图

1-1 采用邻接矩阵表示法创建无向图

分数 4

作者 王东

单位 贵州师范学院

采用邻接矩阵表示法创建无向图G ，依次输出各顶点的度。

函数接口定义：

1
void CreateUDN(AMGraph &G);

其中 G 是采用邻接矩阵表示的无向图。

裁判测试程序样例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <stdio.h>
#define MVNum 100                           
typedef struct{ 
    char vexs[MVNum];          
    int arcs[MVNum][MVNum];   
    int vexnum,arcnum;      
}AMGraph;

void CreateUDN(AMGraph &G);
int main(){
    AMGraph G;     
    int i , j,sum=0;
    CreateUDN(G);
    for(i = 0 ; i < G.vexnum ; ++i){
        sum=0;
        for(j = 0; j < G.vexnum; ++j){
            if(G.arcs[i][j]==1)
                sum+=1;
        }
        if(i==0)
            printf("%d",sum);
        else
            printf(" %d",sum);
    }
    return 0;
}

/* 请在这里填写答案 */

输入格式:

输入第一行中给出2个整数i(0<i≤10)，j(j≥0)，分别为图G的顶点数和边数。
输入第二行为顶点的信息，每个顶点只能用一个字符表示。
依次输入j行，每行输入一条边依附的顶点。

输出格式:

依次输出各顶点的度，行末没有最后的空格。

输入样例:

1
2
3
4
5
6
7
8
9
5 7
ABCDE
AB
AD
BC
BE
CD
CE
DE

输出样例:

1
2 3 3 3 3

一定要注意要getchar（）！！！，因为换行符会被读取字符的读取

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
void CreateUDN(AMGraph &G) {
    scanf("%d %d",&G.vexnum, &G.arcnum);
    // 吸收第一行输入后的换行符
    getchar();
    // 读取顶点信息（连续字符，如"ABCDE"）
    for (int i = 0; i < G.vexnum; ++i) {
        scanf("%c",&G.vexs[i]);
    }
    // 初始化邻接矩阵
    for (int i = 0; i < G.vexnum; ++i) {
        for (int j = 0; j < G.vexnum; j++) {
            G.arcs[i][j] = 0;
        }
    }
    getchar();

    for (int k = 0; k < G.arcnum; k++){
        char v1, v2;
        scanf("%c %c",&v1, &v2);
        getchar();

        int a = -1, b = -1; // 用于存储v1v2下标
        for (int i = 0; i < G.vexnum; ++i) {
            if (v1 == G.vexs[i]) {
                a = i;
                break;
            }
        }
        for (int i = 0; i < G.vexnum; ++i) {
            if (v2 == G.vexs[i]) {
                b = i;
                break;
            }
        }
        if (a == -1 || b == -1) {
            continue;  // 无效顶点则不处理
        }
        G.arcs[a][b] = 1;
        G.arcs[b][a] = 1;

    }

}