Impression trie lexicographiquement dans c

Question

Donc je suis en train d'implémenter un trie pour stocker des mots dans un fichier dictionnaire. J'ai implémenté l'opération d'insertion; Maintenant, j'essaie d'imprimer lexicographiquement. Je suis proche de l'obtenir, mais j'ai un petit problème que je ne suis pas sûr de savoir comment résoudre. J'essaie également de garder à l'esprit la rapidité de mon programme, c'est pourquoi j'ai opté pour un trie sur un tableau ou une liste chaînée. Voici ce qu'un seul nœud ressemble:

struct node { 
    int end; 
    int occurrences; 
    int superwords; 
    struct node* child[26]; 
}; 

« fin » indique l'achèvement d'un mot (par exemple, à la fin == 1 à la lettre « k » dans le livre de mot, ce qui évite la confusion à vérifier si ou pas un mot a été réellement inséré dans l'arbre).

est ici la méthode:

void preorder(struct node *follow, char hold[200], int s){ 
    int i = 0; 
    if(follow == NULL){ 
    return; 
    } 

    for(i = 0; i < 26; i++){ 
    if(follow->child[i] == NULL){ 
     continue; 
    } 
    else{ 
     printf("%c",'a'+i); 
     hold[s] = 'a'+i; 
     s++; 
     if(follow->child[i]->end == 1){ 
     printf("\n"); 
     hold[s] = '\0'; 
     printf("%s", hold); 
     } 
     preorder(follow->child[i], hold, s); 
    } 
    } 
    return; 
} 

Les mots que j'ai inséré sont: boo, livre, réservation, john, tex, texte. Ils devraient être imprimés dans cet ordre et séparés par une ligne. Ma sortie ressemble:

boo 
book 
booking 
bookingjohn 
bjohntex 
bjtext 
bjtext 

Je sais que cela a probablement quelque chose à voir avec mon tableau « hold », qui stocke les préfixes de mots afin qu'ils ne se perdent pas. J'ai besoin de remettre l'index à zéro quelque part pour indiquer l'achèvement d'un préfixe et tous ses mots associés (boo, book, booking étant un bon exemple) mais n'ont pas été couronnés de succès. Toute aide serait très appréciée et je serais heureux de clarifier davantage mon processus de pensée.

Answer 1

Vous êtes très proche.

Il y a deux problèmes, à la fois dans la boucle for qui traverse les branches TRIE:

else{ 
    printf("%c",'a'+i); 
    hold[s] = 'a'+i; 
    s++; 

Le premier problème est que vous imprimez (presque) deux fois. Dans l'extrait ci-dessus, vous imprimez le préfixe lorsque vous tracez l'arborescence. Puis plus tard, lorsque vous atteignez la fin du mot, vous imprimez le mot entier:

if(follow->child[i]->end == 1){ 
    printf("\n"); 
    hold[s] = '\0'; 
    printf("%s", hold); 
    } 

Il n'y avait pas besoin d'imprimer le préfixe du tout, et la double impression est source de confusion. Deuxièmement, l'argument s représente la profondeur dans l'arbre, qui est la longueur du préfixe courant. Il devrait donc être constant pendant l'exploration d'un nœud trie. Mais chaque fois que vous trouvez une nouvelle branche, vous l'incrémentez (s++ dans le premier extrait ci-dessus). Au lieu de cela, vous avez besoin de l'appel récursif pour utiliser s + 1 comme argument, afin qu'il soit appelé avec la longueur de préfixe correcte.

Vous pouvez également simplifier vos structures de contrôle.

Voici un exemple:

void preorder(struct node *follow, char hold[200], int s){ 
    int i = 0; 
    if(follow == NULL){ 
    return; 
    } 
    /* Print the word at the beginning instead of the end */ 
    if (follow->end) { 
    hold[s] = 0; 
    printf("%s\n", hold); 
    } 

    for(i = 0; i < 26; i++){ 
    /* preorder returns immediately if its argument is NULL, so 
    * there's no need to check twice. Perhaps even better would be 
    * to do the check here, and not do it at the beginning. 
    */ 
    hold[s] = 'a'+i; 
    preorder(follow->child[i], hold, s + 1); 
    } 
}