5

我将数据存储在描述链表的 XML 文档中；除了一个之外的所有节点都跟随另一个，所以数据看起来像这样：

<cars>
    <car id="9" follows="34" />
    <car id="12" follows="20" />
    <car id="20" follows="9" />
    <car id="29" follows="30" />
    <car id="30" />
    <car id="34" follows="29" />
</cars>

...给出30、29、34、9、20、12的顺序。我正在使用.NET的LinkedList类来构造一个链表来反映这些数据，但是构造起来很尴尬，因为这些值是乱序的。我真正想要做的是假设数据是有效的——只有一个第一个值，而所有其他值都有“跟随”列表中另一个节点之后的值。像这样的代码会很好（这FindFirstForwards是我编写的自定义扩展方法，用于查找给定 lambda 返回 true 的第一个链表条目）：

LinkedList<CarInstance> orderedCars = new LinkedList<CarInstance>();
XPathNodeIterator xmlIterator = _nav.Select("/dflt:cars/dflt:car", _namespaceResolver);
while (xmlIterator.MoveNext()) {
    if (!(xmlIterator.Current.Select("@follows").Count > 0)) {
        orderedCars.AddFirst(new CarInstance {
            CarId = int.Parse(xmlIterator.Current.GetAttribute("id", _defaultNamespace))
        });
    }
    else {
        orderedCars.AddAfter(orderedCars.FindFirstForwards(car => car.CarId == int.Parse(xmlIterator.Current.GetAttribute("follows", _defaultNamespace))), new CarInstance {
            CarId = int.Parse(xmlIterator.Current.GetAttribute("id", _defaultNamespace))
        });
    }
}

麻烦的是，如果这个跟随的车还没有被添加到orderedCars，则会抛出异常，因为FindFirstForwards没有找到具有“跟随”ID 的车。我真正想做的是说“将其添加到链接列表中，假设它会跟随某个具有特定 ID 的未来条目，即使该条目尚未添加，并继续。” 最后，检查链表的完整性，确保每个节点都指向另一个节点，并且有一个头节点。

有没有一种简洁的方法来做到这一点？如果不是，那么将此 XML 转换为内存中链表的最有效（最好是代码简洁）的方法是什么？

4

1 回答 1

4

我会以两步的方式做到这一点：

  1. 将所有汽车加载到字典中，由汽车的 id 键入，而不考虑它们的顺序
  2. 通过循环遍历所有汽车（按字典顺序，无关紧要）来链接所有汽车，并通过字典找到下面的汽车，此时应该是一个O(1)操作。

如果您不能在没有将下一辆车链接到该点的情况下构造汽车对象，即。汽车对象的“跟随”部分（或全部）是不可变的，我会创建一个临时类，甚至将 XML 节点存储在字典中，然后在您获得它们的顺序后构造汽车对象。

此外，即使您只有一个从一个对象到另一个对象的链接，您也可以为此考虑拓扑排序，但请注意，该算法的快速实现通常也使用字典。

于 2013-01-08T11:15:16.117 回答