Sujet Précédent Sujet Suivant

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

kuja2053 Messages postés 7 Date d'inscription lundi 27 septembre 2004 Statut Membre Dernière intervention 22 décembre 2010 - 6 mai 2007 à 22:56
josekym Messages postés 10 Date d'inscription mercredi 23 janvier 2008 Statut Membre Dernière intervention 3 juillet 2009 - 24 janv. 2008 à 11:10
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 -->
A voir également:

3 réponses

Réponse 1 / 3
BruNews Messages postés 21040 Date d'inscription jeudi 23 janvier 2003 Statut Modérateur Dernière intervention 21 août 2019
7 mai 2007 à 00:54
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++
0
Réponse 2 / 3
kuja2053 Messages postés 7 Date d'inscription lundi 27 septembre 2004 Statut Membre Dernière intervention 22 décembre 2010
7 mai 2007 à 12:51
Merci, aprés recherche, j'ai trouvé exactement ce que je cherchait!!!
0
Réponse 3 / 3
josekym Messages postés 10 Date d'inscription mercredi 23 janvier 2008 Statut Membre Dernière intervention 3 juillet 2009
24 janv. 2008 à 11:10
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
0

Discussions similaires

Codage de l'arbre de Huffman
cs_janette -
jakor -

3 réponses
codage huffman
morganistic -
vdust -

4 réponses
Structure de données Arbre de Huffman
nicloss -
vecchio56 -

6 réponses
chronometre en milliseconde
sarici -
sarici -

3 réponses
Calcul de dérivée
darkjedi1024 -
lamri11111 -

19 réponses
Rejoignez-nous