10

我必须实现一个自制的 Trie 并且我被困在 Iterator 部分。我似乎无法弄清楚 trie 的增量方法。

我希望有人能帮我把事情弄清楚。

这是迭代器的代码：

template <typename T> class Trie<T>::IteratorPrefixe{
friend class Trie<T>;
public:
    IteratorPrefixe() : tree(NULL), currentNode(NULL), currentKey("") {};
    pair<string, T*> operator*() {return make_pair(currentKey, currentNode -> element);} ;
    IteratorPrefixe operator++()throw(runtime_error);
    void operator=(IteratorPrefixe iter) {tree = iter.tree; currentNode = iter.currentNode; currentKey = iter.currentKey;};
    bool operator==(IteratorPrefixe iter) {return tree == iter.tree && currentNode == iter.currentNode;};
    bool operator!=(IteratorPrefixe iter) {return tree != iter.tree || currentNode != iter.currentNode;};
private:
    Trie<T> * tree;
    Trie<T> * currentNode;
    string currentKey;
};

这是我的特里：

template <typename T> class Trie {
friend class IteratorPrefixe;
public:
    // Create a Trie<T> from the alphabet of nbletters, where nbletters must be
    // between 1 and NBLETTERSMAX inclusively
    Trie(unsigned nbletters) throw(runtime_error);

    // Add a key element of which is given in the first argument and content second argument
    // The content must be defined (different from NULL pointer)
    // The key is to be composed of valid letters (the letters between A + inclusive and exclusive nbletters
    //      Eg  if nblettres is 3, a, b and c are the only characters permitted;
    //          If nblettres is 15, only the letters between a and o inclusive are allowed.
    // Returns true if the insertion was achieved, returns false otherwise.
    bool addElement(string, T*) throw(runtime_error);
    // Deletes a key element of which is given as an argument and returns the contents of the node removed
    // The key is to be composed of letters valid (see above)
    // Can also delete at the same time the reference of the ancestors, if these ancestors are no longer used.
    // Returns NULL if the item has no delete
    T* removeElement(string cle) throw(runtime_error);
    // Find a key element of which is given as an argument and returns the associated content
    // The key is to be composed of letters valid (see above)
    // Returns NULL if the key does not exist
    T* searchElement(string cle) throw();
    // Iterator class to browse the Trie <T> in preorder mode
    class IteratorPrefixe;
    // Returns an iterator pointing to the first element
    IteratorPrefixe pbegin() throw(runtime_error);
    // Returns an iterator pointing beyond the last item
    IteratorPrefixe pend() throw();

private:
    unsigned nbLetters;
    T* element;
    vector<Trie<T> *> childs;
    Trie<T> * parent;

    // This function removes a node and its ancestors if became unnecessary. It is essentially the same work
    // as deleteElement that is how to designate remove a node that is changing. Moreover, unlike
    // deleteElement, it does not return any information on the node removed.
    void remove(Trie<T> * node) throw();

    // This function is seeking a node based on a given key. It is essentially the same work
    // searchElement but that returns a reference to the node found (or null if the node does not exist)
    // The key is to be composed of letters valid (see above)
    Trie<T>* search(string key) throw(runtime_error);
};
4

3 回答 3

7

我很高兴看到 Tries 仍然被教授，它们是一个经常被忽视的重要数据结构。

您的代码中可能存在设计问题，因为您可能应该有一个 Trie 类和一个 Node 类。你写它的方式看起来你的 Trie 中的每个节点都是它自己的 trie，它可以工作，但会使一些事情变得复杂。

从您的问题中并不清楚您遇到的问题是什么：计算顺序还是计算实际代码？

从迭代器的名称来看，听起来它必须按前缀顺序工作。由于您的 trie 存储单词并且它的子节点是按字母组织的，因此您基本上应该按字母顺序遍历所有单词。每个增量都会带您进入下一个单词。

您的迭代器的不变性在于，在任何时候（只要它是有效的），它都应该指向一个带有“终止符”的节点来表示一个有效的单词。计算这个词只涉及向上扫描父链，直到找到整个字符串。移动到下一个单词意味着进行 DFS 搜索：向上一次，扫描后面的“兄弟”中的链接，看看是否找到了一个单词，如果没有递归向上等。

于 2008-12-08T23:39:54.097 回答
2

您可能希望在以下位置查看我修改后的 trie 实现：

具体来说，您可能会发现我在 comp.lang.c++.moderated 上关于以符合 STL 的方式为 trie 实现迭代器的讨论，这是一个问题，因为不幸的是，所有 stl 容器都被迫使用 std::pair<>，并且因此迭代器必须包含该值，而不仅仅是对 trie 中单个节点的引用。

于 2008-12-14T04:36:34.950 回答
0

一方面，显示的代码实际上并没有描述 trie。相反，它似乎是一棵树，在每个节点 (T*和unsigned) 中包含一对元素。您可以按照规则使用元组树作为 trie，但这只是按照惯例，而不是强制执行。这就是为什么你很难实施的部分原因operator++。

您需要做的是让每个都Trie包含一个左右不相交的 ADT，而不仅仅是原始元素。它是一种抽象层，在函数式语言中更常见（例如 Scala 的Either）。不幸的是，C++ 的类型系统还不够强大，无法做那么优雅的事情。但是，没有什么可以阻止您这样做：

template <class L, class R>
class Either
{
public:

    Either(L *l) : left(l), right(0)
    {}

    Either(R *r) : left(0), right(r)
    {}

    L *get_left() const
    {
        return left;
    }

    R *get_right() const
    {
        return right;
    }

    bool is_left() const
    {
        return left != 0;
    }

    bool is_right() const
    {
        return right != 0;
    }

private:
    L *left;
    R *right;
};

然后您Trie的数据成员将定义如下：

private:
    Either<unsigned, T*> disjoint;

    vector<Trie<T> *> children;    // english pluralization
    Trie<T> * parent;

我对你的指点玩得又快又松，但你明白我在说什么。重要的是没有给定的节点可以同时包含an和unsigneda T*。

试试这个，看看是否有帮助。我想你会发现能够轻松地确定你是在叶子上还是在树枝上，这将极大地帮助你尝试迭代。

于 2008-12-14T05:30:53.233 回答