(15分)某网络中的路由器运行OSPF路由协议，题42表是路由器R1维护的主要链路状态信息(LSI), 题42图是根据题42表的接口名构造出来的网络拓扑。
请回答下列问题。
(1)本题中的网络可抽象为数据结构中的哪种结构?
(2)针对题42表中的内容，设计合理的链式存储结构，以保存题42表中的链路状态信息( LSI) 。 要求给 出链式存储结构的数据定义，并画出对应题42表的链式存储结构示意图(示意图中仅以ID 标识结点)。
(3)按照迪杰斯特拉( Dijkstra) 算法的策略，依次给出R1 到达题42图中子网192.1.x.x的最短路径及费 用。
题42表R1所维护的LSI
| R1的LSI | R2的LSI | R3的LSI | R4的LSI | 备注 | |
|---|---|---|---|---|---|
| Router ID | 10.1.1.1 | 10.1.1.2 | 10.1.1.5 | 10.1.1.6 | 标识路由器的IP地址 |
| Link1 | |||||
| ID | 10.1.1.2 | 10.1.1.1 | 10.1.1.6 | 10.1.1.5 | 所连路由器的Router ID |
| IP | 10.1.1.1 | 10.1.1.2 | 10.1.1.5 | 10.1.1.6 | Link1的本地IP地址 |
| Metric | 3 | 3 | 6 | 6 | Link1的费用 |
| Link2 | |||||
| ID | 10.1.1.5 | 10.1.1.6 | 10.1.1.1 | 10.1.1.2 | 所连路由器的Router ID |
| IP | 10.1.1.9 | 10.1.1.13 | 10.1.1.10 | 10.1.1.14 | Link2的本地IP地址 |
| Metric | 2 | 4 | 2 | 4 | Link2的费用 |
| Link3 | |||||
| Prefix | 192.1.1.0/24 | 192.1.6.0/24 | 192.1.5.0/24 | 192.1.7.0/24 | 直连网络Net1的网络前缀 |
| Metric | 1 | 1 | 1 | 1 | 到达直连网络Net1的费用 |
[tag_link]
很多考生乍看之下以为是网络的题目，其实该题本身并没有涉及太多的网络知识点，只是 应用了网络的模型，实际上考查的还是数据结构的内容。 1）图（1 分） 题中给出的是一个简单的网络拓扑图，可以抽象为无向图。 【评分说明】只要考生的答案中给出与图含义相似的描述，例如，“网状结构”“非线性结构”等，同样 给分。 2）链式存储结构的如下图所示。
struct Arc {
uint32_t id;
uint32_t ip;
int metric;
};
struct Net {
uint32_t prefix;
uint32_t mask;
int metric;
};
struct LNode {
LNode *next; // flag == 1：链路连接到路由器
// flag == 2：链路连接到子网
int flag;
union NetOrArc {
Net net;
Arc arc;
};
};
struct HNode {
uint32_t router_id;
LNode *next;
HNode *next_hnode;
};
【评分说明】① 若考生给出的答案是将链表中的表头结点保存在一个一维数组中（即采用邻接表形式），同样给分。② 若考生给出的答案中，弧结点没有使用 union 定义，而是采用两种不同的结构分别表示 Link 和 Net，同时在表头结点中定义了两个指针，分别指向由这两种类型的结点构成的两个链表，同样给分。③ 考生所给答案的弧结点中，可以在单独定义的域中保存各直连网络 IP 地址的前缀长度，也可以与网络地址保存在同一个域中。④ ③的标准给分。⑤ 若考生给出的答案中，图示部分与其数据类型定义部分一致，图示只要能够体现链式存储结构和网络连接关系（可以不给出结点内细节信息），即可给分。⑥ ①