PTA（图）1-2 采用邻接表创建无向图

1-2 采用邻接表创建无向图

分数 4

作者 王东

单位 贵州师范学院

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

函数接口定义：

1
void CreateUDG(ALGraph &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
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <stdio.h>
#include <stdlib.h>
#define MVNum 100 
typedef struct ArcNode{
    int adjvex; 
    struct ArcNode *nextarc; 
    int info; 
}ArcNode; 

typedef struct VNode{ 
    char data; 
    ArcNode *firstarc; 
}VNode, AdjList[MVNum]; 

typedef struct{ 
    VNode vertices[MVNum]; 
    int vexnum, arcnum; 
}ALGraph;

void CreateUDG(ALGraph &G);

int main(){
    ALGraph G;     
    int i , j,sum=0;
    CreateUDG(G);
    ArcNode * p; 
    for(i = 0 ; i < G.vexnum ; ++i){
        sum=0;
        p=G.vertices[i].firstarc;
        for(; p!=NULL; p=p->nextarc){
                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

我的正确代码

  • 才知道可以在函数题里面加上头文件和另一个函数
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
#include<iostream>
using namespace std;
int LocateVexIndex(ALGraph G, char v) {
    for (int i = 0; i < G.vexnum; ++i) {
        if (v == G.vertices[i].data) {
            return i;
        }
    }
    return -1;
}

void CreateUDG(ALGraph &G) {
    cin >> G.vexnum >> G.arcnum;
    // 读取顶点信息
    for (int i = 0; i < G.vexnum; ++i) {
        cin >> G.vertices[i].data;
        G.vertices[i].firstarc = NULL;
    }
    for (int k = 0; k < G.arcnum; ++k) {
        char v1, v2;
        cin >> v1 >> v2;

        int i = LocateVexIndex(G, v1);
        int j = LocateVexIndex(G, v2);

        // 将邻接边头插入链表
        ArcNode *p1 = new ArcNode();
        p1->nextarc = G.vertices[i].firstarc;
        p1->adjvex = j;
        G.vertices[i].firstarc = p1;

        // 双向
        ArcNode *p2 = new ArcNode();
        p2->nextarc = G.vertices[j].firstarc;
        p2->adjvex = i;
        G.vertices[j].firstarc = p2;
    }
}