我将数据存储在描述链表的 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
类来构造一个链表来反射(reflect)这些数据,但它是构造起来很尴尬,因为值是乱序的。我真正想做的是假设数据是有效的——只有一个第一个值,而所有其他值都在列表中的另一个节点之后有“跟随”值。像这样的代码会很好(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 的 future 条目,即使该条目尚未添加,然后继续。”然后在最后检查链表的完整性,确保每个节点都指向另一个节点,并且有一个头节点。
有没有一种简洁的方法可以做到这一点?如果不是,将此 XML 转换为内存中链表的最有效(最好是代码简洁)的方法是什么?
最佳答案
我会分两步进行:
- 将所有汽车加载到字典中,以汽车 ID 为键,不考虑它们的顺序
- 通过循环遍历所有汽车(按字典顺序,无关紧要)将所有汽车链接起来,并通过字典找到后面的汽车,这应该是一个
O(1)
操作点。
如果你不能在没有将下一辆车链接到它的情况下构建一个汽车对象,即。 car 对象的“follows”部分(或全部)是不可变的,我会创建一个临时类,甚至将 XML 节点存储在字典中,然后在您对它们进行排序后构造 car 对象。
此外,即使您只有一个从一个对象到另一个对象的链接,您也可以为此考虑拓扑排序,但请注意,此算法的快速实现通常也会使用字典。
关于c# - 从存储的数据构造链表的最有效方法?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/14213437/