Codage huffman [Résolu]

Signaler
Messages postés
6
Date d'inscription
jeudi 27 mai 2004
Statut
Membre
Dernière intervention
22 mars 2007
-
Messages postés
43
Date d'inscription
jeudi 16 décembre 2004
Statut
Membre
Dernière intervention
14 mars 2007
-
bonjour
je doit rendre un projet de simulation de codage huffman en c.
il y a plusieur etapes:
le comptage des accurences des caracteres dans le texte:
le teste se trouve dans source.txt le fichier est parcouru caractere par caractere et pour chaque caractere rencontré,on procede comme suit:
soit c la premiere occurrence du caractere dans ce cas on ajoute dans un arbre binaire (ordonné suivant l ordre lexicographique) un nouveau noeud.comprenant le caractere et 1(premiere occurence).
soit on a deja rencontré le caractere et il existe deja un noeud de l arbre concernant le caractere et il suffit de mettre a jour l'etiquette "nombre d' occurence" de ce noeud a nbocc++.

on genere ainsi un arbre des occurences.a partir de cet arbre on doit construire une foret ordonnée d arbres :c est a dire une liste d arbres binaires ordonée selon le nombre des ocuurences de chaque caractere.
puis jusqu a que la liste soit reduite a un unique arbre ,on fusionne les deux premiers arbres de la liste en creant un arbre dont la racine est etiquetée avec la somme des etiquettes des racines des deux arbres que l on fusionne et tel que le sous arbre de gauche soit le premier arbreet le sous arbre droit le second arbre.puis on supprime ces deux arbres et on insere le nouvel arbre de facon a ce que la liste obtenue reste ordonnée.

tout cela pour generer l arbre des codes ou le code sera obtenu en parcourant de la racine a la feuille :si on descend vers un fils gauche cela genere un zero, si on descend vers un fils droit on genere un 1.

aidez moi je suis au bout du rouleau s il vous plait!

typedef struct SNoeud
{
int lettre;
int nbocc;
struct SNoeud *fg;
struct SNoeud *fd;
}TNoeud, *TArbre;

TArbre ConsArbreVide(){
return NULL;
}


TArbre ConsArbre (int l,int n,TArbre fg,TArbre fd){
TArbre ArbreTmp;
ArbreTmp = (TArbre)malloc(sizeof(TNoeud));
ArbreTmp->lettre = l;
ArbreTmp->nbocc = n;
ArbreTmp->fg = fg;
ArbreTmp->fd = fd;
return ArbreTmp;
}


bool EstArbreVide (TArbre arbre){
return (arbre==NULL);
}





TArbre Getfg (TArbre arbre){
if (EstArbreVide(arbre->fg))
{
printf("Erreur dans Gauche : arbre vide");
abort();
}
else
{return arbre->fg;}
}


TArbre Getfd (TArbre arbre){
if (EstArbreVide(arbre->fd))
{
printf("Erreur dans Gauche : arbre vide");
abort();
}
else
{return arbre->fd;}
}
on pourra s aider de cette structure et de ces quelques primitives !!

merci d avance!

4 réponses

Messages postés
6
Date d'inscription
jeudi 27 mai 2004
Statut
Membre
Dernière intervention
22 mars 2007

merci virtual dust de tes reponses...mais je ne demande pas tout le projet!
en fait ca c etait pour vous exposer le sujet.(et si des fois quelqu un l avait deja fait ca m arrangeait bien...)
maintenant ca c est ma premiere esquisse de code mais il ne marche pas bien et je ne comprend pas ce qui ne va pas...ou est l erreur?

#pragma hdrstop
#include
#pragma argsused
#include
#include
typedef struct noeud
{
int info;
int nbocc;
struct noeud *fg;
struct noeud *fd;
}NOEUD;


/****************************************************************/
/* Nom de la fonction:creer_noeud */
/* But:creer et initialise un noeud */
/* Entrees: */
/* Sorties:pointeur sur le noeud creé */
/****************************************************************/
NOEUD *creer_noeud(int nInfo,int nbocc)
{
/*declaration des variables*/
NOEUD *a;
/*allocation dynamique du noeud*/
a = (NOEUD*)malloc(sizeof(NOEUD));
a->info = nInfo;
a->nbocc = nbocc;
a->fg = NULL;
a->fd = NULL;
return a;
}


/****************************************************************/
/* Nom de la fonction:EstArbreVide */
/* But:indique si l arbre est vide */
/* Entrees:un pointeur sur un noeud */
/* Sorties:booleen:true si l arbre est vide */
/****************************************************************/
bool EstArbreVide (NOEUD *a){
return (a==NULL);
}
/****************************************************************/
/* Nom de la fonction:Recherche */
/* But:recherche un element dans l'arbre */
/* Entrees:un pointeur sur un noeud et l'info */
/* Sorties:un pointeur sur le noeud recherché */
/****************************************************************/
NOEUD* Recherche(NOEUD *a, int nInfo)
{
/*Si arbre vide: renvoie NULL*/
/*if(a == NULL) return NULL; */


/*Sinon recherche iterative de l'info*/
while(a->info != nInfo)
{
if(a->info > nInfo)
a = a->fg;
else a = a->fd;
if(a == NULL) return NULL;
}
return a;
}
/****************************************************************/
/* Nom de la fonction:Appartient */
/* But:recherche un element dans l'arbre */
/* Entrees:un pointeur sur un noeud et l'info */
/* Sorties:un boolean indiquant si l element est dans l arbre */
/****************************************************************/
bool Appartient(NOEUD *a, int nInfo)
{
/*printf("on est dans appartient\n"); */
/*Si arbre vide: renvoie NULL*/
/*if(a == NULL) return false; */


/*Sinon recherche iterative de l'info*/
while(a->info != nInfo)
{
if(a->info > nInfo)
a = a->fg;
else a = a->fd;
if(a == NULL) return false;
}
return true;
}


/****************************************************************/
/* Nom de la fonction:Copier */
/* But:copie le contenu des valeurs du noeud a vers le noeud b */
/* Entrees:un pointeur sur le noeud a copier et un pointeur */
/* sur le noeud de destination. */
/* Sorties:un pointeur vers la copie du noeud */
/****************************************************************/
NOEUD* Copier(NOEUD *a,NOEUD *b)
{
int inf = a->info;
int nocc = a->nbocc;
b=creer_noeud(inf,nocc);
return b;
}



/****************************************************************/
/* Nom de la fonction:Ajouter */
/* But:Ajoute un element dans l'arbre */
/* Entrees:un pointeur sur un noeud et l'info du */
/* nouveau noeud */
/* Sorties: */
/****************************************************************/
void Ajouter(NOEUD *a, int nInfo)
{
printf("on va ajouter le noeud\n");
NOEUD *pRech;

/*pRech = a; */
printf("l arbre que recoit ajouter contient %c\n",(char)a->info);
pRech = Copier(a,pRech);
/*printf("et sa copie contient %c\n",(char)pRech->info); */
/*Tant que l'on a pas atteint la feuille*/
/*voulue , on parcoure l'arbre*/
while(a != NULL)
{
/*Permet de mémoriser le pere*/
/*pRech = a; */
pRech = Copier(a,pRech);
/*Parcour de l'arbre*/
if(a->info > nInfo)
a = a->fg;
else a = a->fd;
}


/*Creation du noeud*/
a = creer_noeud(nInfo,1);
printf("noeud cree!:'%c'\n",(char)a->info);


/*Insertion dans l'arbre*/
/* int y=pRech->info ; */
printf("insertion dans l arbre\n");
/*printf("ce noeud est le fils de :'%c'\n",(char)y); */


if(pRech->info > nInfo)
pRech->fg = a;
else pRech->fd = a;
printf("noeud insere dans l arbre!\n");
/* printf("ce noeud est le fils de :'%c'\n",(char)pRech->info);
printf("et il a pour valeur '%c' \n",(char)a->info);
if (pRech->fg!= NULL) printf(" fg de pRech:%c \n",(char)pRech->fg->info);
if (pRech->fd!= NULL)printf(" fd de pRech:%c \n",(char)pRech->fd->info);*/
}
/****************************************************************/
/* Nom de la fonction:CreerArbOcc */
/* But:cree l arbre des occurences */
/* Entrees: */
/* Sorties:un pointeur sur l arbre des occurences crée */
/****************************************************************/
NOEUD *CreerArbOcc ()
{
int car;
NOEUD *ArbOcc;


FILE * fic;
fic = fopen("source.txt","r");
/* Se positionner au début du fichier */
fseek(fic, 0, SEEK_SET);
while( !feof(fic) ) {
car= fgetc(fic); /* Lire un entier dans le fichier */


printf("on est dans creer arbocc on a lu le car '%c' ----------------------\n",(char)car);
/*si l arbre est vide on cree la racine*/
if (EstArbreVide(ArbOcc))
{
ArbOcc = creer_noeud(car,1);
printf("valeur de l info de arbocc :'%c'.\n",(char)ArbOcc->info);
printf("on a cree la racine (%c,1)\n",(char)car);
}
else {
/*on cherche si il n existe pas deja un noeud portant l info*/
if (Appartient(ArbOcc,car))
{ /*si oui...*/
ArbOcc=Recherche(ArbOcc,car);/*on se place sur le bon noeud*/
ArbOcc->nbocc=ArbOcc->nbocc+1;/*et on incremente le compteur d occ*/
printf("l occurence '%c' existait deja on a incremente nbocc\n",(char)ArbOcc->info);
}
/*si il n y en a pas:*/
else
{
printf("il n y a pas de noeud portant l info!\n");
Ajouter(ArbOcc,car);/*on l ajoute*/
}
}


}
return ArbOcc;
}
/****************************************************************/
/* Nom de la fonction:nbre_noeud */
/* But:compte le nombre de noeud dans les */
/* sous-arbres ainsi que le noeud lui-meme */
/* Entrees:un pointeur sur le noeud */
/* Sorties:le nombre de noeud */
/****************************************************************/
int nbre_noeud(NOEUD *a)
{
if(a == NULL) return 0;
return( 1+ nbre_noeud(a->fg) + nbre_noeud(a->fd));
}
/****************************************************************/
/* Nom de la fonction:visite */
/* But:affiche le contenu d'un noeud */
/* Entrees:le pointeur sur le noeud */
/* Sorties: */
/****************************************************************/
void visite(NOEUD *a)
{
/* Affiche l'info du noeud visité ainsi que le nombre */
/* de noeuds sous lui en se comptant */
printf("%c(%d) ",(char)a->info,nbre_noeud(a));
}



/****************************************************************/
/* Nom de la fonction:affich_infixe_croissant */
/* But:affichage de l'arbre en infixe croissant */
/* Entrees:la racine de l'arbre */
/* Sorties: */
/****************************************************************/
void affich_infixe_croissant(NOEUD *a)
{
if(a!=NULL)
{
affich_infixe_croissant(a->fg);
/*operation sur le noeud*/
visite(a);
affich_infixe_croissant(a->fd);
}
}








int main (){
int choix;
NOEUD *ArbreDesOccurrences;
printf("creation de l arbre des occurrences\n");
ArbreDesOccurrences = CreerArbOcc();
affich_infixe_croissant(ArbreDesOccurrences);
scanf("%d",choix);
}

donc pour l instant j aimerais deja que la console m affiche mon arbre des occurences
et au lieu de ca elle ne m affiche que la racine de mon arbre
il y a un prob au niveau de l insertion des noeuds dans l arbre.
mais je ne voit pas ou.
si ca vous dit de m aider il suffit de copier coller vers un editeur c et de compiler...
merci d avance.
Messages postés
43
Date d'inscription
jeudi 16 décembre 2004
Statut
Membre
Dernière intervention
14 mars 2007

Te rends tu comptes qu'ici, tu demandes la réalisation de l'intégralité
du projet ? un problème sur un point, passe encore, mais tout le projet
!!! Ca ne se fait pas en trois lignes... et ça dépasse à mon avis le
cadre du forum. Bon, peut-être que d'autres seront plus indulgents,
mais personnellement, je trouve que là, c'est de la faignantite aigüe
(et je mâche mes mots)... Surtout que ce problème est un classique du
genre, et qu'avec un peu de recherche, tu pourras sûrement trouver au
moins des pistes sérieuses (morceaux de codes) ou dans le meilleur des
cas pour toi, l'intégralité du code...

-- Virtual Dust --
Messages postés
43
Date d'inscription
jeudi 16 décembre 2004
Statut
Membre
Dernière intervention
14 mars 2007

Bon, j'avoue, j'ai été un peu virulent dans mon précédent message, et
j'aurais presque des remords (surtout que la politesse de ma part est
passée à la trape :) ; bien que je ne pense pas moins ce que j'ai dit,
voici une adresse où est décrit l'algorithme de construction de l'arbre
de huffman :



http://prografix.games-creators.org/document/109


Voilà... J'espère que ça pourra t'être utile...



bye


-- Virtual Dust --
Messages postés
43
Date d'inscription
jeudi 16 décembre 2004
Statut
Membre
Dernière intervention
14 mars 2007

Salut.

D'abord, je m'excuse encore pour cette nuit. J'étais vraiment naze, et dans ces cas là, un rien énerve.



Je pense avoir résolu ton problème. Tout d'abord, il y avait bien un problème dans ta fonction Ajouter. Il provient de la ligne

pRech = Copier(a, pRech);


Il ne faut pas que tu copies le noeud père ! En faisant ça, c'est comme
si tu créais un nouvel arbre dont la racine est la copie du noeud père.
Les noeuds ne sont donc pas insérés dans le bon arbre, et cet arbre est
ensuite perdu (il vient encombrer, avec ses fils, la mémoire
inutilement) lorsque tu retournes à la fonction appelante. Si après, le
code corrigé (et qui fonctionne) de la fonction ajoutée, avec les
commentaires, plus quelques modifications dans les messages printf, qui
permettent de voir où sont insérés exactement les nouveaux noeuds en
montrant le parcours descendant.



void Ajouter(NOEUD *a, int nInfo)

{

// printf("on va ajouter le noeud\n");

NOEUD *pRech;



/*pRech = a; */

//printf("ajout -> %c\n",(char)a->info);



// pRech = Copier(a,pRech);

// pas utile créé cet élément puisqu'il

// est perdu immédiatement dans la boucle while

// sans que la mémoire ne soit libérée.



/*Tant que l'on a pas atteint la feuille*/

/*voulue , on parcoure l'arbre*/

#if _DEBUG //ça, c juste que je trouvais les autres messages

//trop longs, et sans intérêt pour le débogage :)

printf("insertion : ");

#endif

while(a != NULL)

{

/*Permet de mémoriser le pere*/

//pRech = Copier(a,pRech);

// pas utile de copier puisque

// tu ne modifie pas l'élément.

// de plus, c'était la source du problème

pRech = a; //son pointeur suffit

/*Parcour de l'arbre*/

if(a->info > nInfo)

{

#if _DEBUG //
est fils gauche de


printf("g:%c>",a->info);

#endif

a = a->fg;

} else {

#if _DEBUG
// est fils droit de


printf("d:%c>",a->info);

#endif

a = a->fd;

}

}



/*Creation du noeud*/

a = creer_noeud(nInfo,1);

// printf("noeud cree!:'%c'\n",(char)a->info);



/*Insertion dans l'arbre*/

/* int y=pRech->info ; */

// printf("noeud cree - insertion > ");

/*printf("ce noeud est le fils de :'%c'\n",(char)y); */



if(pRech->info > nInfo)

{

pRech->fg = a;

#if _DEBUG

printf("[g:%c(%i)]\n",a->info, a->nbocc);

#endif

} else {

pRech->fd = a;

#if _DEBUG

printf("[d:%c
(%i)]\n",a->info, a->nbocc
);

#endif

}

}



Voilà pour
la fonction Ajouter. A ce moment là, est apparu un nouveau problème,
que j'ai mis un moment à trouver. C'est dans ta fonction CreerArbOcc que ça coinçait. En gros, tu écrasais ton arbre lorsque tu incrémentais le nbocc
d'un noeud. Voici le code corrigé de la fonction :



NOEUD *CreerArbOcc ()

{

int car;

NOEUD *ArbOcc=NULL;



FILE * fic;

fic = fopen("source.txt","r");

/* Se positionner au début du fichier */

fseek(fic, 0, SEEK_SET);

while( !feof(fic) )

{

car= fgetc(fic); /* Lire un entier dans le fichier */



#if _DEBUG

printf("--- LECTURE '%c' ---\n",(char)car);

#endif _DEBUG

/*si l arbre est vide on cree la racine*/

if (EstArbreVide(ArbOcc))

{

ArbOcc = creer_noeud(car,1);

#if _DEBUG

printf("Racine -> '%c'\n",(char)ArbOcc->info);

#endif _DEBUG

} else {

/*on cherche si il n existe pas deja un noeud portant l info*/

if (Appartient(ArbOcc,car))

{ /*si oui...*/

/// ICI : tu perts tout les ascendants de ton noeuds


//
ArbOcc=Recherche(ArbOcc,car);/*on se place sur le bon noeud


//
ArbOcc->nbocc++;/*et on incremente le compteur d occ*/

Recherche(ArbOcc,car)->nbocc++; //incrémentation

///


printf("'%c' existant -> nbocc=%i\n",(char)ArbOcc->info,
ArbOcc->nbocc);

}

/*si il n y en a pas:*/

else

{

printf("'%c' inexistant\n", car);

Ajouter(ArbOcc,car);/*on l ajoute*/

}

}



}

return ArbOcc;

}




Voilà... J'espère que ça fonctionnera aussi chez toi, en tout cas, moi, ça marche



Bonne chance pour la suite


-- Virtual Dust --