Застрял в реализации итератора Trie

Question

Я должен реализовать самодельный 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

Я рад видеть, что попытки все еще преподаются, они являются важной структурой данных, которой часто пренебрегают.

В вашем коде может быть проблема разработки, поскольку у вас, вероятно, должны быть класс Trie и класс Node. То, как вы это написали, похоже, что каждый узел в вашем Trie - это свой собственный trie, который может работать, но усложнит некоторые вещи.

Из вашего вопроса не совсем понятно, с чем связана ваша проблема: вычисление порядка или фактический код?

Судя по названию итератора, он должен работать в порядке префикса. Так как в вашем дереве хранятся слова, а его дочерние узлы организованы буквами, то, по сути, ожидается, что вы пройдете все слова в алфавитном порядке. Каждое увеличение приведет вас к следующему слову.

Инвариант вашего итератора заключается в том, что в любой точке (если он действителен) он должен указывать на узел с "символом-терминатором" для правильного слова. Чтобы понять это слово, нужно просто просмотреть родительскую цепочку вверх, пока вы не найдете всю строку. Переход к следующему слову означает выполнение поиска в DFS: поднимитесь один раз, просмотрите ссылки в последующих «братьях», посмотрите, не найдете ли вы слово, если не рекурсивно поднимитесь, и т. Д.

Answer 2

Возможно, вы захотите увидеть мои модифицированные реализации Trie по адресу:

• Трико Дж.Дкофтинова

В частности, вы можете найти обсуждение , которое я проводил на comp.lang.c ++. Модерируемый по поводу реализации итераторов для trie в соответствии с STL, что является проблемой, поскольку, к сожалению, все контейнеры stl вынуждены использовать std :: pair <>, и итератор для этого должен содержать значение, а не просто ссылку на один узел в дереве.

Answer 3

Во-первых, приведенный код на самом деле не описывает три. Скорее, это дерево, содержащее пару элементов в каждом узле (T* и unsigned). Вы можете по дисциплине использовать дерево кортежей в качестве дерева, но это только по соглашению, а не по принуждению. Это одна из причин того, почему вам так трудно реализовать operator++.

Вам нужно, чтобы каждый Trie содержал разделенную слева направо ADT, а не только необработанные элементы. Это слой абстракции, который чаще встречается в функциональных языках (например, Scala's 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;

Я играю быстро и свободно с вашими указателями, но вы понимаете суть того, что я говорю. Важным битом является то, что ни один данный узел не может содержать и , unsigned и T*.

.

Попробуйте и посмотрите, поможет ли это. Я думаю, вы обнаружите, что возможность легко определить, находитесь ли вы на листе или на ветке, чрезвычайно поможет вам в вашей попытке выполнить итерацию.