9
Tôi phải thực hiện một Trie tự chế và tôi bị mắc kẹt trên phần Iterator. Tôi dường như không thể tìm ra phương pháp tăng cho trie.Bị kẹt trên một Iterator Thực hiện của một Trie
Tôi hy vọng ai đó có thể giúp tôi làm rõ mọi thứ.
Dưới đây là các mã cho 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;
};
Và đây là Trie tôi:
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);
};
Câu trả lời hay. Là một sang một bên, đôi khi nó là tốt hơn để lưu trữ các mục công cụ theo thứ tự ngược lại, giống như tên miền. – Josh