Avec sauvegarde de l'arbre binaire à l'écran (ou dans un fichier en faisant dico.exe > dico.txt).
Quelques fonctions de "compactage" du dictionnaire...
Source / Exemple :
#include <stdio.h>
#include <string.h>
static char calu[2]="\0";
static FILE*fichier;
class arbre
{// il reste à étudier le compactage de l'arbre (les fin de mots identiques...)
public:
char data;
arbre*gauche,*droite;
inline arbre(char c=0,arbre*g=NULL,arbre*d=NULL):data(c),gauche(g),droite(d){}
inline arbre(char*mot):data(*mot),droite(NULL){gauche=*mot?new arbre(mot+1):NULL;}
~arbre(){if(gauche)delete gauche;if(droite)delete droite;}
};
static int taille(arbre*a){return a?1+taille(a->gauche)+taille(a->droite):0;}
/*
un 0 est toujours suivi d'un # donc on peut coder 0# par 1
un seul # reste inchangé
un $ reste un $
puis changer ## par '2' puis ### par '3'
####->'4' #####->'5' ... #########->'9' ##########->':' 11#->';' 12# -> '<', 13#->'=', 14 -> '>' 15 -> '?' et 16 par '@' (ce qui n'arrive pas)
donc implémenter un "putchar" et un "getchar" avec un buffer d'entrées sorties
static void sauve(arbre*p)
{
fprintf(fichier,"%c",p->data?p->data:'0');
for(p=p->gauche;p;p=p->droite)sauve(p);
fputc('#',fichier);
}
static void sauvegarde(arbre*p)
{
if(p==NULL)return;
if(fichier=fopen("dico.dat","w"))
{
sauve(p);
while(p->droite)
{
p=p->droite;
fputc('$',fichier);
sauve(p);
}
}
fclose(fichier);
}
static arbre*restaure()
{
arbre*f,*p=new arbre(*calu,NULL,NULL);
fscanf(fichier,"%c",calu,1);
if(*calu=='0')*calu=0;
if((*calu!='#')&&(*calu!='$'))
{
f=p->gauche=restaure();
while((*calu!='#')&&(*calu!='$'))
{
f->droite=restaure();
f=f->droite;
}
}
fscanf(fichier,"%c",calu,1);
if(*calu=='0')*calu=0;
if(*calu=='$')
{
fscanf(fichier,"%c",calu,1);
if(*calu=='0')*calu=0;
f=p;
while(f->droite)f=f->droite;
f->droite=restaure();
}
return p;
}
static arbre*restauration()
{
arbre*dico=NULL;
if(fichier=fopen("dico.dat","r"))
{
fscanf(fichier,"%c",calu,1);
if(*calu=='0')*calu=0;
dico=restaure();
}
fclose(fichier);
return dico;
}
static void affiche(arbre*dummy,char*tmp=NULL,int n=0)
{
if(dummy==NULL)return;
if(n>=80)return;
bool tmpnull=false;
if(tmp==NULL){tmpnull=true;tmp=new char[80];for(int m=0;m<80;m++)tmp[m]=0;}
tmp[n]=dummy->data;
if(*tmp && dummy->data==0)printf("%s\n",tmp);
affiche(dummy->gauche,tmp,++n);
affiche(dummy->droite,tmp,--n);
if(tmpnull)delete tmp;
}
static arbre*add(char*mot,arbre*dico=NULL)
{//création du dictionnaire si besoin
if(dico==NULL)return new arbre(mot);
if(*mot==0)return dico->data?new arbre(0,NULL,dico):dico;
if(*mot<dico->data)return new arbre(*mot,new arbre(mot+1),dico);
if(*mot==dico->data)dico->gauche=add(mot+1,dico->gauche);
else dico->droite=add(mot,dico->droite);
return dico;
}
inline static void Delete(arbre*&dico){if(dico)delete dico;dico=NULL;}
static bool dansdico(char*mot,arbre*dico)
{//savoir si mot se trouve dans le dictionnaire
if((dico==NULL)||(dico->data>*mot))return false;
if(*mot==dico->data)return *mot?dansdico(mot+1,dico->gauche):true;
return dansdico(mot,dico->droite);
}
static void print(char*p,char*d)
{//pour codage du dictionnaire de la fonction code
static char k[16];
for(int n=0;n<16;n++)
{
if(p[n]!=d[n])
{
printf("%c%s",(char)(n+48),&d[n]);
break;
}
}
}
static void code(arbre*dummy,char*tmp=NULL,int n=0)
{//codage "minimal" du dictionnaire à l'écran. Pour générer un fichier, faire dico.exe > dico.txt
if(dummy==NULL)return;
if(n>20)return;
static char motPrecedent[20];
bool tmpnull=false;
if(tmp==NULL){tmpnull=true;tmp=new char[20];for(int m=0;m<20;m++)tmp[m]=motPrecedent[m]=0;}
tmp[n]=dummy->data;
if(*tmp && dummy->data==0){print(motPrecedent,tmp);strcpy(motPrecedent,tmp);}
code(dummy->gauche,tmp,++n);
code(dummy->droite,tmp,--n);
if(tmpnull)delete tmp;
}
arbre*decode()
{//pour retrouver l'arbre créé par code
arbre*dico=NULL;
char buffer[20];
FILE*file=fopen("dico.txt","r");
char c;
int k=0;
while((c=fgetc(file))!=EOF)
{
if(c<'A')
{
buffer[k]=0;
if(*buffer)
{
if(dico)add(buffer,dico);
else dico=add(buffer,dico);
}
k=c-48;
}
else buffer[k++]=c;
}
add(buffer,dico);
fclose(file);
return dico;
}
//#define Add(s) ((char*)s,dico);
int main()
{
arbre*dico=new arbre();
add((char*)"un",dico);
add((char*)"deux",dico);
add((char*)"trois",dico);
add((char*)"quatre",dico);
add((char*)"cinq",dico);
affiche(dico);
sauvegarde(dico);
Delete(dico);
dico=restauration();
affiche(dico);
return 0;
}
Vous n'êtes pas encore membre ?
inscrivez-vous, c'est gratuit et ça prend moins d'une minute !
Les membres obtiennent plus de réponses que les utilisateurs anonymes.
Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.
Le fait d'être membre vous permet d'avoir des options supplémentaires.