这道题只是套了一个计算机网络的壳子，本质是在考数据结构。

⑴ 题目给了一张网络拓扑图，结点之间可以双向通信，所以可以抽象为无向图。如果没办法区分有向图和无向图，直接写图就行。

⑵ 首先这一问非常考验阅读理解能力，而且是阅读表格的能力，做这种题目必须要耐心。

比如Link1里面包含三个成员变量ID、IP和Metric，很容易想到将Link1抽象为一个结构体，下面观察每个成员变量：

• ID的备注是所连路由器的Router ID，即有向边的终点。
• IP的备注是Link1本地的IP地址，即有向边的起点。
• Metric的备注是Link1的费用，即有向边的边权。

以此类推，表格左边栏每一项都可以抽象成结构体，左边栏有两种结构体，一种是Link，另一种是Net，Link表示路由器的一个端口，Net表示一个网络，无论端口还是网络，都是一个结点。增加Flag区分不同结点，为了把不同结构体封装在一个结构体内，需要运用C语言的union，或者运用C++类和工厂模式。

最后把这些结构体都作为成员变量封装在一个HeadNode结构体中，表示一个路由器在网络传播路径中作为一个网络结点的有效部分，一个路由器可以有多个端口。

整个过程非常像组装高达模型，先分别组装头，躯干，四肢，最后将头和四肢连接到躯干上，模型组装完成。

C代码如下：

struct LinkNode{
    unsigned int ID, IP;
};

struct NetNode{
    unsigned int Prefix, Mask;
};

struct Node{
    int Flag;  // Flag = 1 means LinkNode and Flag = 2 means NetNode
    union LinkOrNet{
        struct LinkNode LNode;
        struct NetNode NNode;
    };
    unsigned int Metric;
    struct Node *next;
};

struct HeadNode{
    unsigned int RouterID;
    struct Node *link;
    struct HeadNode *next;
};

C++代码如下：

typedef enum nodetype{
    LNode,
    NNode,
}NodeType;

class Node {
public:
    unsigned int Metric;
    Node *next;
    virtual void foo() = 0;
    virtual ~Node(){};
};

class NetNode: public Node {
public:
    unsigned int Prefix, Mask;
    void foo() {
        cout << "net node"<< endl;
    }
};

class LinkNode: public Node {
public:
    unsigned int ID, IP;
    void foo() {
        cout << "link node"<< endl;
    }
};

class NodeFactory {
public:
    Node* createNode(NodeType type) {
        switch (type) {
            case LNode:
                return new LinkNode();
                break;
            case NNode:
                return new NetNode();
                break;
            default:
                return nullptr;
                break;
        }
    }
};

class HeadNode {
public:
    unsigned int RouterID;
    NodeType type;
    Node *link;
    HeadNode *next;
    virtual ~HeadNode(){};
};

对应题42表的链式存储结构示意图如下：

⑶ 题目要求依次给出R1到达题42图中子网192.1.x.x的最短路径及费用。

观察题42图，所有子网都是192.1.x.x的格式，也就是要完整遍历整个图了。

Dijkstra算法使用贪心策略，维护一个点集 S ，开始将起点加入点集 S ，并维护一个距离数组，计算顶点到每一个顶点的距离，每次选择距离起点最近的顶点加入点集 S ，从该顶点继续进行搜索，采用松弛算法更新起点到各个顶点的距离。不断重复上述过程直到所有点都加入点集 S 。

画表格模拟Dijkstra算法过程，然后按照遍历顺序输出子网192.1.x.x的最短路径及费用：

当然，由于本题的网络拓扑图过于简单，为了节省时间，考场上完全不需要模拟Dijkstra算法过程，可以直接找出R1到达题42图中子网192.1.x.x的最短路径，然后按照从小到大排序打表输出。