编程实现有向图图的邻接表存储，并计算给定结点的入度和初度。 如有向图： 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; } };

以下是 C++ 代码实现：

#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;
    }
};

//返回结点在邻接表中的下标
int GetIndex(ALGraph& G, string s)
{
    for (int i = 0; i < G.n; i++)
    {
        if (G.hnode[i].hnode.data == s)
            return i;
    }
    return -1;
}

//插入边结点
void InsertEdgeNode(ALGraph& G, string s1, string s2)
{
    int i = GetIndex(G, s1);
    int j = GetIndex(G, s2);
    if (i == -1 || j == -1)
        return;
    EdgeNode* p = new EdgeNode(s2);
    p->nextedge = G.hnode[i].firstedge;
    G.hnode[i].firstedge = p;
}

//创建邻接表
void CreateALGraph(ALGraph& G)
{
    cin >> G.n >> G.e;
    for (int i = 0; i < G.n; i++)
    {
        string s;
        cin >> s;
        G.hnode[i].hnode.data = s;
        G.hnode[i].hnode.no = i;
    }
    for (int i = 0; i < G.e; i++)
    {
        string s1, s2;
        cin >> s1 >> s2;
        InsertEdgeNode(G, s1, s2);
    }
}

//计算结点的入度和出度
void CalculateDegree(ALGraph& G, string s)
{
    int i = GetIndex(G, s);
    if (i == -1)
        return;
    int in_degree = 0;
    int out_degree = 0;
    EdgeNode* p = G.hnode[i].firstedge;
    while (p != NULL)
    {
        out_degree++;
        int j = GetIndex(G, p->nextnode.data);
        if (j != -1)
        {
            EdgeNode* q = G.hnode[j].firstedge;
            while (q != NULL)
            {
                if (q->nextnode.data == s)
                    in_degree++;
                q = q->nextedge;
            }
        }
        p = p->nextedge;
    }
    cout << "The in-degree of " << s << " is " << in_degree << endl;
    cout << "The out-degree of " << s << " is " << out_degree << endl;
}

//输出邻接表
void PrintALGraph(ALGraph& G)
{
    cout << "This graph has " << G.n << " vertexs, and " << G.e << " edges." << endl;
    cout << "The information of vertexs are: " << endl;
    for (int i = 0; i < G.n; i++)
    {
        cout << G.hnode[i].hnode.data << " " << i << " ";
    }
    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 << " ";
    }
    cout << endl;
}

int main()
{
    ALGraph G;
    CreateALGraph(G);
    PrintALGraph(G);
    string s;
    cin >> s;
    CalculateDegree(G, s);
    return 0;
}

输入样例：

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

代码实现了有向图的邻接表存储，并可以计算给定结点的入度和出度。