Sujet Précédent Sujet Suivant

Codage huffman

Résolu
morganistic Messages postés 6 Date d'inscription jeudi 27 mai 2004 Statut Membre Dernière intervention 22 mars 2007 - 6 janv. 2005 à 22:57
vdust Messages postés 43 Date d'inscription jeudi 16 décembre 2004 Statut Membre Dernière intervention 14 mars 2007 - 7 janv. 2005 à 19:46
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

Réponse 1 / 4
morganistic Messages postés 6 Date d'inscription jeudi 27 mai 2004 Statut Membre Dernière intervention 22 mars 2007
7 janv. 2005 à 14:50
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.
3

Discussions similaires

Recuperer la taille d'un tableau de string
kobee12 -
kobee12 -

2 réponses
Calcul de moyenne de note en C
tinkiete78 -
boumarsel -

4 réponses
fonction rand() : nombre positifs et négaifs ???
mrdaryx -
coucou747 -

13 réponses
Equivalent du Chr en C++ (Ascii)
bundy318 -
bundy318 -

3 réponses
afficher le reste d'une division
busta74 -
busta74 -

2 réponses
Convertir un const char * en char *
cs_Mike -
Kaid -

12 réponses
Rejoignez-nous