1

我需要一个可以存储嵌套数字列表的数据结构的高效 C++ 实现，例如：

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

我希望能够以非常有效的方式循环最深的元素，以便我可以按照它们出现在嵌套列表中的顺序访问三个数字的集合：

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

我还希望通过传递一组三个数字并将适当的数字添加到树的每个级别来将元素添加到树中。我相信我应该为此使用某种类型的树数据结构，但不知道哪个最有效。

最后，我想为每个“叶子”关联一个值，因此每个三元组都将映射到某个整数值。

4

3 回答 3

3

对于这种情况，Trie 可能是最有效的结构。您可以在此处找到有关 Trie 的概述。

本质上，Trie 的存储值很可能在值的早期存在许多重叠（如字符串或数字序列），方法是仅在每个位置存储每个值一次。您绘制的图表几乎完全描绘了一个 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

非常喜欢给树加后缀。但是哪个更方便你..解决你。

于 2013-06-06T23:20:36.103 回答