1. Accueil
  2. Forum Codes-Sources
  3. C / C++ / C++.NET
  4. C

Creation récursive de l'arbre de codage de la compression Huffman

Signaler
Messages postés
7
Date d'inscription
lundi 27 septembre 2004
Statut
Membre
Dernière intervention
22 décembre 2010
 -
Messages postés
10
Date d'inscription
mercredi 23 janvier 2008
Statut
Membre
Dernière intervention
3 juillet 2009
 -
Bonjour,


Voila mon probleme : ayant un projet sur la compression de Huffman,
j'ai décider de changer le format de l entete de mon fichier suite à un
conseil donnée sur ce forum : http://www.developpez.net/forums/sho...d.php?t=312519

Donc pour résumer je coder le bit '0' pour un nouveau noeud, '1' pour
une feuille et je met le caractere ascii correspondant a la feuille
apres les '1' donc.


Ceux qui donne sur cette arbre par exemple:


le code "001D01B01F1A01C1E" . Bien sur les 0 et les 1 sont des bits et
les code ascii des caracteres seront codé sur un octet. Mais pour
simplifier pour l'instant les 0 et les 1 sont codée en tant que
caractere (cela évite de s'encombrer de l'utilisation d'une file
d'attente pour écrire octet par octet dans le fichier).


J'ai donc dévelloper la fonction pour ecrire l'entete de cette fonction
(qui est fonctionnelle) mais ma fonction pour la recréation de l'arbre
ne marche pas! C'est en quelques sorte une fonction doublement
récursive (avec adresse du noeud actuelle dans l'arbre en construction
et la position du pointeur sur fichier (FILE*) qui avance à chaque
lecture (fread).


Cette fonction marche pour les arbre à 3 niveau de profondeur (soit 2
noeuds) mais ne marche pour plus grand. Car dépassé cette limite, la
lecture des valeurs de l'arbre me ferme mon programme. Pourtant lorsque
je lit un emplacement mémoire interdit, windows me retourne un message
d'erreur avant. Je précise que je développe sous "Dev C++". Bon sans
plus attendre je met les code source donc vous aurez besoin et souhaite
bonne chance au plus courageux (lol)


SOURCE:


DEFINITION DU TYPE ARBRE ET DE SON POINTEUR

<!-- BEGIN TEMPLATE: bbcode_code -->

Code :

typedefstruct arbre_ arbre;
typedef feuille *ptr_arbre;
 
struct arbre_
{
unsignedchar code_ascii;
ptr_feuille fils_gauche;
ptr_feuille fils_droite;
};
 

<!-- END TEMPLATE: bbcode_code -->


FONCTION DEVANT RECREER L ARBRE AVEC EN ARGUMENT LE POINTEUR SUR
FICHIER POINTANT AU DEBUT SUR LE DEBUT DE L ENTETE ET L ADRESSE DU
NOEUD ACTUELLE EN DEUXIEME ARGUMENT

<!-- BEGIN TEMPLATE: bbcode_code -->

Code :

void creer_arbre(FILE *fichier_entree,ptr_arbre noeud)
{
unsignedchar caract;
if(!fread(&caract,sizeof(unsignedchar),1,fichier_entree))
{ printf("\n\nerreur entete fichier compresse"); while(1); }
printf("caractere lu %c\n",caract);
if(caract=='1')
{
if(!fread(&caract,sizeof(unsignedchar),1,fichier_entree))
{ printf("\n\nerreur entete fichier compresse"); while(1); }
noeud->code_ascii=caract;
printf("lettre a placer %c\n",caract);
}
else//creation des deux fils
{
if(((noeud->fils_gauche)=(ptr_arbre)malloc(sizeof(arbre)))==NULL)
{ printf("\n\nErreur allocation memoire"); while(1); }
printf("noeud gauche creer\n");
if(((noeud->fils_droite)=(ptr_arbre)malloc(sizeof(arbre)))==NULL)
{ printf("\n\nErreur allocation memoire"); while(1); }
printf("noeud droite creer\n");
noeud->fils_gauche->code_ascii='H';
noeud->fils_droite->code_ascii='H';
noeud->fils_gauche->fils_gauche=NULL;
noeud->fils_gauche->fils_droite=NULL;
noeud->fils_droite->fils_gauche=NULL;
noeud->fils_droite->fils_droite=NULL;
printf("depart fils gauche\n");
creer_arbre(fichier_entree,noeud->fils_gauche);
printf("depart fils droite\n");
creer_arbre(fichier_entree,noeud->fils_droite);
}
}
 

<!-- END TEMPLATE: bbcode_code -->


AUPARAVANT J'AI INITIALISER UNE FEUILLE POUR L'ARBRE A CONSTRUIRE AVEC LA FONCTION :
<!-- BEGIN TEMPLATE: bbcode_code -->

Code :

ptr_arbre creer_feuille()
{
ptr_arbre inter;
if((inter=(ptr_arbre)malloc(sizeof(arbre)))==NULL)
{ printf("\n\nErreur allocation memoire"); while(1); }
inter->code_ascii='H';
inter->fils_gauche=NULL;
inter->fils_droite=NULL;
return inter;
}
 

<!-- END TEMPLATE: bbcode_code -->


J'AI DONC DANS LA FONCTION PRINCIPALE:
<!-- BEGIN TEMPLATE: bbcode_code -->

Code :

ptr_arbre arbre_huffman=creer_feuille();
 
//creation de l arbre simplifier avec entete
creer_arbre(fichier_in,arbre_huffman);
 

<!-- END TEMPLATE: bbcode_code -->


VOILA, si vous avez besoin de la fonction qui écrit l'entete a partir
de l'arbre de la partie "compression de fichier" faite moi signe!


Encore bonne chance et merci d'avance...

<!-- / message -->
<!-- BEGIN TEMPLATE: postbit_onlinestatus -->
Afficher la suite
A voir également:

3 réponses

Réponse 1 / 3
Messages postés
21042
Date d'inscription
jeudi 23 janvier 2003
Statut
Modérateur
Dernière intervention
21 août 2019
 25
http://www.cppfrance.com/codes/HUFFMAN-CPPFRANCE_38961.aspx

C'est ici qu'il faut regarder, une très bonne analyse des différentes méthodes y est faite.

ciao...
BruNews, MVP VC++
Réponse 2 / 3
Messages postés
7
Date d'inscription
lundi 27 septembre 2004
Statut
Membre
Dernière intervention
22 décembre 2010
Merci, aprés recherche, j'ai trouvé exactement ce que je cherchait!!!
Réponse 3 / 3
Messages postés
10
Date d'inscription
mercredi 23 janvier 2008
Statut
Membre
Dernière intervention
3 juillet 2009
bonjour,
je suis nouvelle sur le site et maitrise à peine le c
pourriez-vous m'aider à élaborer un code qui construit graphiquement l'arbre de huffman c'est-à-dire un arbre binaire ordonné.
moi je comprend cette construction comme suit:
-creer de n feuilles qui sont des pointeurs sur des structures avec pour champ:
                 char lettre
                 float freq
                 pointeur de même type filsG;
                 pointeur de même type filsD;

-ranger les feuilles en ordre décroissant
-creer de (n-1) noeuds dont lun sera la somme de deux feuilles et les ranger en ordre décroissant ainsi de suite jusqu'a n'avoir plus qu'un noeud=1
-retracer le parcours de chaque feuille jusqu'à la source pour pouvoir trouver le code de chaque lettre.
bref c'est un peu ça
merci d'avance
Répondre Posez votre question