1

次のような、ネストされた数値のリストを格納できるデータ構造の効率的な C++ 実装が必要です。

0: 
   1: 
      3
      4
      7
   5: 
      10
      13
      15
   7: 
      2
1:
   1: 
       2
       3
   6: 
       7
       9

ネストされたリストに表示される順序で 3 つの数値のセットにアクセスできるように、非常に効率的な方法で最も深い要素をループできるようにしたいと考えています。

(0,1,3)
(0,1,4)
(0,5,10)
...

また、3 つの数値のセットを渡し、適切な数値をツリーの各レベルに追加することで、ツリーに要素を追加したいと考えています。これにはある種のツリーデータ構造を使用する必要があると思いますが、どれが最も効率的かはわかりません。

最後に、各「リーフ」に値を関連付けたいので、各トリプルは何らかの整数値にマップされます。

4

3 に答える 3

3

Trie は、このようなものにとって最も効率的な構造である可能性があります。Trie の概要については、こちらを参照してください。

基本的に、値の早い段階で多くのオーバーラップが発生する可能性のある値 (文字列や一連の数値など) の値を、各位置に 1 回だけ格納することで、Trie の格納値を格納します。あなたが描いた図は、ほぼ正確にトライを描いています。

于 2013-06-06T23:17:52.593 に答える
1

欲しいものを正確に伝えるのは難しいです。

簡単な解決策はstd::map<std::tuple<int, int, int>, ValueType>、あなたの例でValueTypeは だけですint。

または、次のようなこともできます。

class Node
{
    //optional - depends on whether you need it:
    std::weak_ptr<Node> parent;

    //for the children, you might want this (if they are numbered 0, 1, ...)
    std::vector<std::unique_ptr<Node>> children;

    //or instead you might want this for the children
    //(if they are numbered with potential gaps, like in your example):
    std::map<int, std::unique_ptr<Node>> children;
};

class LeafNode : Node
{
    ValueType data; //ValueType is whatever you want
}
于 2013-06-06T23:18:15.870 に答える
0

treesの接尾辞と同じです。しかし、どちらがあなたにとってより便利ですか..あなたを解決します。

于 2013-06-06T23:20:36.103 に答える