Structure de données Arbre de Huffman

Question

Bonjour, j'ai un projet en programmation c qui consiste &#224; coder un programme qui compresse selon l'algorithme de Huffman.

J'ai bien compris le principe mais je n'ai pas beaucoup d'exp&#233;rience en
prog c et le prof nous oblige &#224; utiliser une structure qu'il nous a
donn&#233; pour l'arbre.

Et le probl&#232;me est que je ne comprend pas cette structure et donc je ne sais pas comment l'utiliser.

Si quelqu'un pouvait m'expliquer cette structure, cela m'aiderai beaucoup...

Merci d'avance,



typedef unsigned char uchar;

/* Attention : ulong d&#233;j&#224; d&#233;fini dans "/usr/include/sys/types.h" */

typedef unsigned long ulong;

struct huffman {

  enum { EXTERNE, INTERNE} type; /* Donn&#233;e dans champ u */

  union {

    struct {

      struct huffman *fg; /* Code 0 */

      struct huffman *fd; /* Code 1 */

    } interne; /* Un noeud interne */

    uchar feuille; /* La valeur de l'octet */

  } u;

  ulong proba; /* Le nombre d'occurence (cumul&#233; pour un noeud interne) */

};

typedef struct huffman *huffman;

vecchio56 · Answer

La structure, c'est un arbre. Un arbre, c'est soit une feuille, soit une noued, avec sous sous arbre gauche et un sous arbre droit. Union exprime ce choix entre feuille et noeud, c'est un peu moche c'est vrai

nicloss · Answer

Merci beaucoup de ta r&#233;ponse.



Donc avec cette structure je peux coder Huffman ?

Tu pourrais m'expliquer comment utiliser feuille et noeud pour la suite de mon programme?

Car si je n'arrive pas &#224; acc&#233;der &#224; ces champs, je suis mal barr&#233; !!!

La structure est un peu complexe et je ne vois pas trop comment acc&#233;der aux diff&#233;rents champs.

J'ai vu pas mal de sources sur l'algo d'Huffman et aucun n'utilise de structure similaire.

vecchio56 · Answer

Pour ce type de structures, le langage C n'est pas terrible. Le langages à objets sont bien plus adaptés.
Pour utiliser ta structure, tu aura des codes du genre:
struct huffman* h; // que tu obtiens de je ne sais pas où
pour savoir si c'est une feuille, tu as h->type
if(h->type == EXTERNE)
{
  h->feuille contient la valeur de la feuille
}
else
{
  h->interne.fg et h->interne.fd désignent les sou-arbres
}

Bonne chance

nicloss · Answer

Merci beaucoup !!!

Je pense que je vais pouvoir avancer...

Et si je bloque encore pour l'utilisation de la structure, je reviendrais faire un tour...

nicloss · Answer

Bon j'ai encore des petits probl&#232;mes pour utiliser la structure...

Le programme me met des "Segmentation Fault" lorsque que je veux affecter des valeurs &#224; mes champs.

Je m'y prend surement mal !!!

Par exemple, pour affecter 10 au champ "proba", je fais &#231;a :



h->proba = 10;



Et &#231;a ne marche pas.

Tu peux m'aider ?



je crois que je n'ai pas encore parfaitement compris comment utiliser ces put*** de champs !!!

vecchio56 · Answer

Bien sur, dans l'exemple que je t'ai donné, h n'est pas initialisé. Du as sans doute un algo a suivre ou quelque chose, non? Si ce n'est pas le cas, bon courage car l'algo n'est pas particulièrement simple a coder. Tu as un exemple dans mes sources si tu veux

Structure de données Arbre de Huffman

6 réponses

Votre réponse

Discussions similaires