Free Allocated Memory in a Tree

[Italbro]

Hi guys
here is my program. I create a dictionnary. I get words from a file .doc or .txt and i build a dictionnary. The thing is i need a function that clears all the memory from the end ( FLAGENDWORD, says when the words is final ) and i go up to the top.

really need help me. My function is Erase() ( that can be a function ) should call it self inside. Anything that can help would be gratefull. THX




#include "stdafx.h"
#include <iostream>
#include <stdlib.h>
#include <string>
#include <fstream>
#include <stdio.h>
using namespace std ;

class Dictio {
private:
Dictio * a[26];
bool FlagEndWord;
public:
Dictio();
~Dictio();

/*
Cette fonction suit le noeud courrant
les lettre donnée le mots. Le mot est LEN caractères
Lors du OutPut, plen va avoir la longeur de cacatères
qui suit le mot qu on retourne.

Cette fonction cherche sur le noeud donnée
en utilisant la première lettre du mot and
continue jusqua temps jusqua temps
qu il trouve plen == len, cela veut dire
que le mot a été lit au complet, sinon
la recherche arrête à un certain noeud
car il n'y a pas de continuation.

len=plen et retourne le noeud a FlagEndWord
ca veut dire que le mot entrer est dans le dictionnaire
et est un mot complet

si len=plen mais le noeud ne retourne pas FlagEndWord, ca veut
dire que le mot contient un prefix valide mais il n'est pas
complet sur lui meme.

si plen<len alors pas toute les caractères dans le mot
peuvent être poursuivit parceque le mot n'est pas dans
le dictionnaire. le plen indique le nombre de lettre qui fait
le prefix qui est dans le dictionnaire
*/
Dictio * follow(const char * word, // le mot
int len, // longeur du mot
int & plen); // OUT: longeur du prefix.

bool IsFullWord() const { return FlagEndWord; }


static void InsertDictionary(const char * word, int len);
void print_words_r(ostream & os, char buf[], int n, char base);

};

Dictio * root = new Dictio;

//fait par moi
bool VerifyWord(const char * word, int len)
{
int plen;
Dictio * n = root -> follow(word,len,plen);
return (plen == len && n -> IsFullWord());
}

//aidé par qqun
void Dictio::InsertDictionary(const char * word, int len)
{
int plen;
Dictio * n = root -> follow(word,len,plen);


//Follow est une fonctio qui essais de trouver qui représente la plus long
//préfix trouver dans l'arbre
//Si &quot;pre&quot; est dans l'arbre et tu fais :
//Dictio * n = follow(&quot;prefix&quot;,6,plen);
//n va représenter le &quot;e&quot; de pre&quot;. plen va avoir la valeur 3,
//ce qui signifie que la longeur du préfix est = 3
//la fonction Follow n'ajoute j'amais eu noeud dans l'arbre mais essais de
//suivre le noeud temps qu'il a un condition valide
//Ca continue si n != 0 ( ca devrait toujours etre) et plen=len, alors le
//noeud représente le mots au complet
if (plen == len)
{
/*
Ici on c'est que le noeud représente le mots au complet
alors on me FlagEndWord a true
Le mot est complet.
*/
n -> FlagEndWord = true;
return;
}
/*
Ici on c'est que le prefix est incomplete, comme on veut
inserer ce mot alors il faut inserer un noeud pour les lettres
manquante apres le prefix
*/

// besoin d'insèrer d'autre noeud a l'arbre
do {
char c = word[plen++];
/*
Le prochain char est &quot;c&quot; alors on a besoin d'ajouter un noeud pour &quot;c&quot;
*/
if (c >= 'A' && c <= 'Z')
c = c - 'A' + 'a'; /* convertir Majuscule à minuscule */
if (c < 'a' || c > 'z') {
/* Pas un lettre! faudrait mettre une erreur ici, à modifier plus
tard!!!!! */
return;
}

Dictio * & next = n -> a[c - 'a'];
if (next != 0) {
/* Ici ca dit que le prochain mot N,est pas un 0,
mais ca indique que FOLLOW na pas été aussi loin qu'il
devait. Devrait mettre une exception
*/
return;
}

//Ajoute un nouveau noeud et continue
next = n = new Dictio;
}
while (plen < len);
/* Le nouveau mot est complet, alors on ajoute FlagEndWord */
n -> FlagEndWord = true;
}


//lit le fichier et ajoute des mots au dictionnaire
// fait par moi
void OuvreFichier(const char * file)
{
ifstream f(file);
char buf[100];
// chaque ligne est un mots

while (f.getline(buf,sizeof(buf),'\n'))
{
Dictio::InsertDictionary(buf,strlen(buf));
}
}

//aider par qqun !!
Dictio * Dictio::follow(const char * word, int len, int & plen)
{
int x = 0;
Dictio * n = this;


/* pour commencer, il faut mettre n à THIS, comme ca on commence avec le
noeud courant*/
while (x < len) {
char c = word[x];
/* prend le prochain caractère */
if (c >= 'A' && c <= 'Z')
c = c - 'A' + 'a';
if (c < 'a' || c > 'z') {
// encore pas une lettre ....
break;
}
Dictio * & next = n -> a[c - 'a'];
if (next == 0) {
// continue pas dans le dictionnaire.
/* on n'a plus de noeud pour continuer alors on retourne le dernier
noeud qu'on a vue ( n). Ca c'est le noeud ou on va mettre nouveaux noeud
si on veut inserer le mot.*/
break;
}
n = next;
++x;
}
/*
plen est le préfix qu'on a continuer jusqu'ici. Ca valeur
est ; 0 <= plen <= x et si plen == x alors le mot est déja dans
le dictionnaire - probablement pas un mot différent.
par exemple si le mot &quot;prefix&quot; est dans le dictionnaire
et on veux ajouter &quot;pre&quot;, alors follow(&quot;pre&quot;,3,plen) va retourner
avec le noeud pour &quot;pre&quot; et plen à la valeur de 3 */

plen = x;
return n;
}

//fait par moi
Dictio:ictio() // constructeur
{
for (int i = 0; i < 26; ++i)
a = 0;
FlagEndWord = false;
}

//fait par moi
Dictio::~Dictio() // desctructeur // je devrais tu mettre les valeur a
//&quot;NULL&quot; avant de les effacer
{

}


// trouver un example sur le net mais pas pareil.
//fait par moi et aider un peu
void Dictio:rint_words_r(ostream & os, char buf[], int n, char base)
{

//os c'est ostream pour imprimer les mots
//buf[0..n-1] retient le 1er caractère du mots
//n est la longeur initial du préfix
//base is 'a' ou 'A' dépendant de majusucle ou minuscule.
if (FlagEndWord) {
buf[n] = '\0'; // termine null.
os << buf << endl;
}
for (int i = 0; i < 26; ++i)
{
if (a != 0)
{
buf[n] = base + i;
a -> print_words_r(os,buf,n+1,'a');
}
}

}


void print_words(ostream & os )
{
char buf[256] ;
root ->print_words_r(os,buf,0,'A');
}




//fait par moi
int main()
{
string prefix;
Dictio D;
string TypeWord ;

bool fin;
fin = false;
int choix ;
OuvreFichier(&quot;dict.txt&quot; // ouvre le fichier et met dans mémoire

do
{
cout<< &quot; Faire un choix \n&quot;;
cout<< &quot; 1 : Imprimer les Mots \n&quot; ;
cout<< &quot; 2 : Trouver un Mots \n&quot; ;
cout<< &quot; 3: Quitter \n&quot;;
cin >> choix;

if (choix == 1)
{
print_words(cout); //imprime
choix=0;
}

if (choix == 2)
{
int longeur ;
cout << &quot; Taper un mot \n&quot; ;
cin >> TypeWord;
longeur = TypeWord.length();

if(VerifyWord(TypeWord.c_str(), longeur))
{
cout << TypeWord << &quot; is in tree &quot;;
}

else
{
cout << TypeWord << &quot; is not in tree.&quot; ;
}
choix=0;
}

if (choix == 3)
{
fin = true;

}
}

while (fin!=true);
return 0;
}

 

[apatterno]

Although it is unclear to me what you are asking, it appears that you have a Dictio class that contains 26 pointers to Dictio, and that you're wondering how to deallocate the memory used by all the Dictio objects.

The destructor would be the place to put such destruction code.

Dictio::~Dictio()
{
   for (int i=0; i<25; i++) {
      if (a[i] != NULL) {
         delete a[i];
      }
   }
}

Of course then, you have to make sure that those pointer values are initialized to NULL in the constructor.

I think that's what you're asking.

Your program is hard to understand without source comments--few people on this forum can read them. In the future, would you post the source comments en anglais, please?

Thanks
I hope to help.

Will