数据结构
2014-42
某网络中的路由器运行OSPF路由协议，题42表是路由器R1维护的主要链路状态信息（LSI），题42图是根据题42表及R1的接口名构造出来的网络拓扑。
请回答下列问题。
1）本题中的网络可抽象为数据结构中的哪种逻辑结构？
2）针对题42表中的内容，设计合理的链式存储结构，以保存题42表中的链路状态信息（LSI）。要求给出链式存储结构的数据类型定义，并画出对应题42表的链式存储结构示意图（示意图中可仅以ID标识结点）。
3）按照迪杰斯特拉（Dijkstra）算法的策略，依次给出R1到达题42图中子网192.1.x.x的最短路径及费用。
答案
（1）本题中的网络可抽象为数据结构中的图（具体为无向图）。
（2）采用带表头结点的链式存储。每个表头结点保存路由器 ID，并指向该路由器的链路/网络信息链；弧结点用 Flag 区分 Link 和 Net 两种记录。数据类型可定义为：
typedef struct {
unsigned int ID, IP;
} LinkNode; // Link的结构
typedef struct {
unsigned int Prefix, Mask;
} NetNode; // Net的结构
typedef struct Node {
int Flag; // Flag=1为Link，Flag=2为Net
union {
LinkNode Lnode;
NetNode Nnode;
} LinkORNet;
unsigned int Metric;
struct Node *next;
} ArcNode; // 弧结点
typedef struct HNode {
unsigned int RouterID;
ArcNode *LN_link;
struct HNode *next;
} HNODE; // 表头结点例如，R1 的表头结点保存 Router ID 10.1.1.1，其信息链依次记录到 R2 的 Link、到 R3 的 Link 以及直连网络 192.1.1.0/24 的 Net；其他路由器按同样方式组织。这样既能表示题表中的全部 LSI，也与题图中的无向图相对应。
（3）从R1到各目的网络的最短路径及代价如下表所示：
| 目的网络 | 路径 | 代价（费用） |
|---|---|---|
| 192.1.1.0/24 | 直接到达 | 1 |
| 192.1.5.0/24 | R1-R3-192.1.5.0/24 | 3 |
| 192.1.6.0/24 | R1-R2-192.1.6.0/24 | 4 |
| 192.1.7.0/24 | R1-R2-R4-192.1.7.0/24 | 8 |