0
votes

Comment gérer "l'utilisation non valide d'un membre de données non statique" dans l'implémentation de classe en C ++?

J'ai essayé de résoudre une question Word Search II sur LeetCode qui nécessite l'utilisation de Trie pour aider à rendre les appels de retour plus efficaces et essaie essentiellement d'être utilisé, j'ai essayé d'implémenter ma propre classe de trie mais Je rencontre un barrage routier dans ma fonction remove , cela nécessite une copie de root, mais je ne sais pas comment lui en donner un. Voici la partie avec laquelle j'ai des problèmes:

TrieNode * crawl = root dans la fonction remove (string word, TrieNode * crawl = root, int depth = 0)

L'erreur: utilisation incorrecte du membre de données non statique 'Trie :: root'

Je ne connais pas la bonne façon de procéder.

struct TrieNode {
    bool isLeaf;
    vector<TrieNode*> arr;
    TrieNode() : isLeaf(false), arr(26, nullptr) {};
};

Voici à quoi ressemble ma classe Trie:

class Trie {
    private:
        TrieNode* root;

    public:            
        Trie() : root(new TrieNode()) {};
    
        void insert(const string &word) {
            auto crawl = root;
            // does it's thing
        }

        bool search(const string &word) {
            auto crawl = root;
            // does it's thing
        }
    
        bool isPrefix(const string &word) {
            auto crawl = root;
            // does it's thing
        }
    

        bool isEmpty(TrieNode* root) { 
            for(int i = 0; i < 26; i++) if(root->arr[i]) return false; 
            return true; 
        } 
        
        TrieNode* remove(string word, TrieNode* crawl = root, int depth = 0) {

Avec ceci comme TrieNode:

XXX

Edit: Un merci spécial à @SPD pour avoir suggéré une amélioration de la fonction de suppression

pointers c++ oop class trie

5 commentaires

Vous ne pouvez pas faire référence à la variable membre non statique root dans le paramètre de la fonction comme TrieNode * crawl = root .

delete n'est pas une fonction, ne mettez pas de parenthèses autour de son argument (comme pour return !).

Vous n'avez pas besoin de passer le pointeur parent (c'est-à-dire l'exploration) dans remove (), cela peut être fait lorsque vous déroulerez la pile d'appels récursifs

@SPD Je ne suis pas sûr de comprendre, pouvez-vous élaborer un peu plus?

@ gh05t, j'ai élaboré mes commentaires comme réponse ci-dessous. J'espère que cela aide.

3 Réponses :

1
votes

Vous ne pouvez pas utiliser de variables membres comme arguments par défaut.

Cependant au lieu de:

TrieNode* remove(string word, TrieNode* crawl = nullptr, int depth = 0) { 
  if (!crawl) {
    crawl = root;
  }
  //...

Vous pouvez faire

TrieNode* remove(string word, TrieNode* crawl = root, int depth = 0) { 
//...

3 commentaires

Mais la fonction est de nature récursive avec null étant un cas de base, je n'étais pas sûr que cela gâcherait les appels de fonction, c'est pourquoi je ne l'ai pas fait de cette façon. Je pense que ça ira dans une boucle infinie si je le fais comme ça.

@ gh05t Je viens de vous montrer pour éviter l'erreur. Pourquoi pensez-vous cela ? (ça ne ressemble pas à ça)

OK oui vous avez raison, la profondeur == word.size () l'empêche de passer à l'étape suivante qui l'aurait rendue infinie sinon, est-ce la bonne façon de traiter ce problème ou aurais-je pu structurer ma structure et la classe mieux en quelque sorte? J'attends que quelqu'un réponde dans ce sens.

2
votes

Une alternative à la réponse de @ darune serait d'avoir une surcharge:

TrieNode* remove(const string& word)
{
    return remove(word, root);
}
TrieNode* remove(string word, TrieNode* crawl, int depth = 0) { 
//...

0 commentaires

1
votes

Quelques suggestions:

vous n'avez pas vraiment besoin d'une classe Trie, TrieNode est suffisant. Toutes les opérations d'insertion / suppression peuvent être déplacées vers TrieNode, vous trouverez probablement plus «naturel» d'écrire des fonctions membres de TrieNode
Si vous vous en tenez à votre conception existante et supprimez l'exploration elle-même suivie de crawl = nullptr , je pense que vous devez passer l'exploration par référence de pointeur plutôt que par simple pointeur.
Une alternative à # 2 consiste à supprimer l'exploration dans la pile appelante. remove () renvoie maintenant un booléen indiquant si l'appelant peut supprimer ce nœud en toute sécurité. Exemple de code ci-dessous.
Enfin, pensez à utiliser des ptr gérés plutôt que des ptr bruts. (Cela n'a probablement pas d'importance pour un exercice de leetcode)

bool remove(string word, TrieNode* crawl, int depth = 0) { 
    if(!crawl) return true; 

    if(depth == word.size()) { 
        if(crawl->isLeaf) crawl->isLeaf = false; 
        return isEmpty(crawl);
    }

    int index = word[depth] - 'a';
    if (remove(word, crawl->arr[index], depth + 1)) {
        // it's empty or nullptr, safe to remove
        delete crawl->arr[index];
        crawl->arr[index] = nullptr; 
    }
    return !crawl->isLeaf && isEmpty(crawl);
}

3 commentaires

Merci pour la réponse, une petite chose, j'ai essayé d'utiliser cette version et si j'ajoute les mots "babaa" et "baci", après avoir enlevé "baci", il y a toujours le mot "bac" (pas comme un mot mais un préfixe au moins) dedans, donc il a juste enlevé le «i» pas «c» et «i» comme il devrait idéalement.

@ gh05t Je pense que la condition de retour devrait être return! crawl-> isLeaf () && isEmpty (crawl); . J'ai raté le "!". Je l'ai essayé;)

Oui, c'était le problème!