5

リンク リストを記述する XML ドキュメントにデータを格納しています。1 つを除くすべてのノードが別のノードに従うため、データは次のようになります。

<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クラスを使用して、このデータを反映するリンク リストを作成していますが、値が順不同であるため、作成するのが面倒です。私が本当にやりたいことは、データが有効であると仮定することです.最初の値は1つだけで、他のすべての値はリスト内の他のノードに続く「フォロー」値を持っています. 次のようなコードが適しています (FindFirstForwardsこれは、特定のラムダが 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))
        });
    }
}

問題は、この車がフォローしている車がまだ に追加されていない場合、「フォロー」ID を持つ車が見つからないorderedCarsため、例外がスローされることです。FindFirstForwards私が本当にやりたいことは、「これをリンクされたリストに追加し、そのエントリがまだ追加されていなくても、特定の ID を持つ将来のエントリに続くと仮定して、続行する」と言うことです。最後に、リンクされたリストの整合性をチェックして、各ノードが別のノードを指していること、およびヘッド ノードが 1 つあることを確認します。

これを行う簡潔な方法はありますか？そうでない場合、この XML をメモリ内リンク リストに変換する最も効率的な (そしてできればコードが簡潔な) 方法は何でしょうか?

4

1 に答える 1

4

私はこれを2段階の方法で行います：

  1. 順序を考慮せずに、すべての車を車の ID でキー付けされたディクショナリに読み込みます
  2. すべての車をループしてリンクし (辞書の順序は関係ありません)、辞書を介して次の車を見つけますO(1)。これは、この時点で操作する必要があります。

その時点で次の車をそれにリンクせずに車のオブジェクトを構築できない場合、つまり. car オブジェクトの "follows" 部分 (またはすべて) は不変です。一時的なクラスを作成するか、XML ノードをディクショナリに格納し、順序付けが完了したら car オブジェクトを構築します。

また、あるオブジェクトから別のオブジェクトへのリンクが 1 つしかない場合でも、これにトポロジカル ソートを検討することもできますが、このアルゴリズムの高速な実装では通常、辞書も使用されることに注意してください。

于 2013-01-08T11:15:16.117 に答える