Dictionnaire dans un arbre binaire

Soyez le premier à donner votre avis sur cette source.

Vue 5 955 fois - Téléchargée 1 061 fois

Description

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; }

Codes Sources

A voir également

Ajouter un commentaire Commentaires
Messages postés
286
Date d'inscription
vendredi 5 décembre 2003
Statut
Membre
Dernière intervention
22 avril 2012
2
1. Utilise des streams
2. As-tu essayé de construire ton arbre à partir du fichier dico.dat ? Si non, fais-le. Que remarques-tu de particulier ? Que faire pour l'éviter ?
Messages postés
27
Date d'inscription
mardi 18 avril 2006
Statut
Membre
Dernière intervention
23 avril 2021

/*
pour réaliser les fichiers ".dat" moins longs
*/
static char buf[20];
void videbuf()
{//fprintf(fichier,"%s",buf);*buf=0;return;
int n=strlen(buf);
if(n)
{
fputc((char)(n+48),fichier);
*buf=0;
}
}
void ecrit(char c)
{
if(c=='#')
{
if(*buf=='0')*buf=0;
else strcat(buf,"#");
return;
}
videbuf();
if(!c){*buf=c='0';}
fputc(c,fichier);
}
void lit()
{// fscanf(fichier,"%c",calu,1);if(*calu=='0')*calu=0;return;
int n=strlen(buf);
if(n)
{
*calu=*buf;
buf[n-1]=0;
return;
}
fscanf(fichier,"%c",calu,1);
if(*calu=='0')
{
*calu=0;
strcat(buf,"#");
}
else if((*calu>'0')&&(*calu<'A'))
{
for(n=0;n<(*calu)-49;n++)strcat(buf,"#");
*calu='#';
}
}

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.