坚持迭代器的迭代器实现

Question

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

我希望有人能帮助我解决问题.

这是Iterator的代码:

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);
};

Answer 1

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

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

从您的问题来看,您遇到问题并不清楚:确定订单或计算实际代码？

从迭代器的名称来看,它听起来像是必须以前缀顺序工作.由于您的trie存储单词及其子节点是按字母组织的,因此基本上可以按字母顺序查看所有单词.每个增量都会带你到下一个单词.

关于迭代器的不变量是在任何时候(只要它是有效的),它应该指向一个有效字的"终止符"的节点.确定该单词仅涉及向上扫描父链,直到找到整个字符串.转到下一个单词意味着进行DFS搜索:上一次,扫描后面的"兄弟"中的链接,查看是否找到了单词,如果没有递归上去等等.