【题目】
42.(10分)某网络中的路由器运行OSPF路由协议，题42表是路由器R1维护的主要链路状态信息(LSI)，题42图是根据题42表及R1的接口名构造出来的网络拓扑。
请回答下问题。
(1)本题中的网络可抽象为数据结构中的哪种逻辑结构?
(2)针对题42表中的内容，设计合理的链式存储结构，以保存题42表中的链路状态信息(LSI)。要求给出链式存储结构的数据类型定义，并画出对应题42表的链式存储结构示意图(示意图中可仅以ID标识结点)。
(3)按照迪杰斯特拉(Dijkstra)算法的策略，依次给出R1到达题42图中子网192.1.x.x的最短路径及费用。
【答案】：
(1)本题中的网络可抽象为图结构。
(2)链式存储结构的数据类型定义如下：
typedef struct
{ unsigned int ID：
unsigned int IP：
}Link Node; //Link的结构
typedef struct
{ unsigned int Prefix：
unsigned int Mask：
}Net Node; //Net的结构
typedef struct Node
} int Flag; //F1ag=1：Link;Flag=2：Net
union
} Link Node Lnode;
Net Node Nnode：
}Link OR Net;
unsigned int Metric：
struct N0de * Next：
} Are Node; //弧结点
typedef struct H Node
{ unsigned int Router ID：
弧结点的两种基本形态
Arc Node * LN_link;
struct H Node * Next：
} HNODE; //表头结点
表头结点结构示意
对应题42表的链式存储结构示意图如下。
(3)计算结果如下表所示。
