【问题描述】编程实现有向图图的邻接表存储，并计算给定结点的入度和初度。 如有向图： 51097d4665434b54a8ff4c6ff2ff9a43.jpg 【输入形式】 【输出形式】 【样例输入】(所有数据从键盘输入） 4 4 A B C D A B A D B C C A A 【样例输出】 This graph has 4 vertexs, and 4 edges. The information of vertexs are: A 0 B 1 C 2 D 3 The adjacent table of graph is: A:D->B B:C C:A D: The in-degree of A is 1 The out-degree of A is 2 【样例说明】 【评分标准】 #include<iostream> #include<string> #include<fstream> using namespace std; const int MAXL = 20; //结点信息 struct Node { string data;//结点值 int no;//结点编号 Node(string data):data(data),no(0){} Node() { data = ""; no = 0; } }; //边结点 struct EdgeNode { Node nextnode;//终止结点信息 EdgeNode* nextedge;//下一条邻接边 EdgeNode(string s) { this->nextnode.data = s; this->nextnode.no = 0; this->nextedge = NULL; } EdgeNode() { this->nextnode.data = ""; this->nextnode.no = 0; this->nextedge = NULL; } }; //表头结点 struct HNode { Node hnode;//起始结点信息 EdgeNode* firstedge;//第一条邻接边 HNode(string s) { hnode.data = s; hnode.no = 0; firstedge = NULL; } HNode() { hnode.data = ""; hnode.no = 0; firstedge = NULL; } }; //邻接表 struct ALGraph { int n, e;//分别表示顶点数和边数 HNode hnode[MAXL];//头结点数组 ALGraph() { n = e = 0; for (int i = 0; i < MAXL; i++) hnode[i].firstedge = NULL; } };

以下是实现有向图邻接表存储并计算给定节点入度和出度的代码（注释已说明每个函数的作用）：

#include<iostream>
#include<string>
#include<fstream>

using namespace std;

const int MAXL = 20;

//结点信息
struct Node {
    string data; //结点值
    int no; //结点编号
    Node(string data) : data(data), no(0) {}
    Node() { data = ""; no = 0; }
};

//边结点
struct EdgeNode {
    Node nextnode; //终止结点信息
    EdgeNode* nextedge; //下一条邻接边
    EdgeNode(string s) {
        this->nextnode.data = s;
        this->nextnode.no = 0;
        this->nextedge = NULL;
    }
    EdgeNode() {
        this->nextnode.data = "";
        this->nextnode.no = 0;
        this->nextedge = NULL;
    }
};

//表头结点
struct HNode {
    Node hnode; //起始结点信息
    EdgeNode* firstedge; //第一条邻接边
    HNode(string s) {
        hnode.data = s;
        hnode.no = 0;
        firstedge = NULL;
    }
    HNode() {
        hnode.data = "";
        hnode.no = 0;
        firstedge = NULL;
    }
};

//邻接表
struct ALGraph {
    int n, e; //分别表示顶点数和边数
    HNode hnode[MAXL]; //头结点数组
    ALGraph() {
        n = e = 0;
        for (int i = 0; i < MAXL; i++)
            hnode[i].firstedge = NULL;
    }
};

//计算节点入度和出度
void calculateDegree(ALGraph& g, Node n) {
    int in_degree = 0, out_degree = 0;
    //遍历每个头结点
    for (int i = 0; i < g.n; i++) {
        //如果头结点的起始结点信息和给定结点信息相同，则遍历该头结点的邻接边
        if (g.hnode[i].hnode.data == n.data) {
            EdgeNode* p = g.hnode[i].firstedge;
            while (p != NULL) {
                //如果邻接边的终止结点信息和给定结点信息相同，则出度加1
                if (p->nextnode.data == n.data)
                    out_degree++;
                p = p->nextedge;
            }
        }
        //遍历整个邻接表，计算给定结点的入度
        EdgeNode* p = g.hnode[i].firstedge;
        while (p != NULL) {
            if (p->nextnode.data == n.data)
                in_degree++;
            p = p->nextedge;
        }
    }
    //输出结果
    cout << "The in-degree of " << n.data << " is " << in_degree << endl;
    cout << "The out-degree of " << n.data << " is " << out_degree << endl;
}

//建立邻接表
void createALGraph(ALGraph& g, string* vertexs, int n, string* edges, int e) {
    g.n = n;
    g.e = e;
    //设置每个结点的编号
    for (int i = 0; i < n; i++) {
        g.hnode[i].hnode.data = vertexs[i];
        g.hnode[i].hnode.no = i;
    }
    //遍历每条边，添加到邻接表中
    for (int i = 0; i < e; i++) {
        string start = edges[2 * i];
        string end = edges[2 * i + 1];
        int start_no = 0, end_no = 0;
        //查找起始结点和终止结点的编号
        for (int j = 0; j < n; j++) {
            if (g.hnode[j].hnode.data == start)
                start_no = j;
            if (g.hnode[j].hnode.data == end)
                end_no = j;
        }
        //将边添加到邻接表中
        EdgeNode* p = new EdgeNode(end);
        p->nextnode.no = end_no;
        p->nextedge = g.hnode[start_no].firstedge;
        g.hnode[start_no].firstedge = p;
    }
}

//打印邻接表
void printALGraph(ALGraph& g) {
    //输出顶点数和边数
    cout << "This graph has " << g.n << " vertexs, and " << g.e << " edges." << endl;
    //输出每个结点的信息
    cout << "The information of vertexs are:";
    for (int i = 0; i < g.n; i++) {
        cout << " " << g.hnode[i].hnode.data << " " << g.hnode[i].hnode.no;
    }
    cout << endl;
    //输出邻接表
    cout << "The adjacent table of graph is:" << endl;
    for (int i = 0; i < g.n; i++) {
        cout << g.hnode[i].hnode.data << ":";
        EdgeNode* p = g.hnode[i].firstedge;
        while (p != NULL) {
            cout << "->" << p->nextnode.data;
            p = p->nextedge;
        }
        cout << endl;
    }
}

int main() {
    int n, e;
    string vertexs[MAXL], edges[MAXL * 2];
    string node;
    cin >> n >> e;
    for (int i = 0; i < n; i++)
        cin >> vertexs[i];
    for (int i = 0; i < 2 * e; i++)
        cin >> edges[i];
    cin >> node;

    //建立邻接表
    ALGraph g;
    createALGraph(g, vertexs, n, edges, e);

    //打印邻接表
    printALGraph(g);

    //计算给定节点的入度和出度
    Node n_node(node);
    calculateDegree(g, n_node);

    return 0;
}