Huffman : arbre et chaine de binaire

Commenter

Contenu du snippet 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct huffarbre {
    char l;
    int n;
    struct huffarbre *g, *d;
};
struct hal {
    struct huffarbre *ha;
    struct hal *next;
};
void sort_chaine(char * liste, int l){
    int i, j; char a;
    for (i=0;i<l;i++)
        for (j=i+1;j<l;j++)
            if (liste[i] > liste[j]){
                a=liste[i]; liste[i]=liste[j]; liste[j]=a;
            }
}
void ajouter(struct huffarbre * ha, struct hal * li, struct hal **pred){
    if (li->ha == NULL){
        li->ha = ha;
    }else{
        if (ha->n < li->ha->n){
            struct hal *li2 = malloc(sizeof(struct hal));
            li2->ha=ha;
            li2->next = li;
            if (*pred) (*pred)->next=li2;
            else *pred = li2;
        }else if (li->next == NULL){
            li->next = malloc(sizeof(struct hal));
            li->next->next=NULL;
            li->next->ha=ha;
        }else{
            ajouter(ha, li->next, &li);
        }
    }
}
void arbreliste ( char * chaine, int l, struct hal ** li){
    struct hal *first=NULL;
    int i, j;
    struct huffarbre *ha;
    for (i=0;i<l;i++){
        j=i;
        while (chaine[i]==chaine[j] && j<l) j++;
        ha = malloc(sizeof (struct huffarbre));
        ha->l=chaine[i]; ha->n=j-i; ha->g=NULL; ha->d=NULL;
        ajouter(ha, *li, &first);
        if (first) (*li)=first;
        i=j-1;
    }
}
void reduire_arbre(struct hal *first, struct huffarbre **arbre){
    struct hal *a, *b, *of;
    struct huffarbre *ha;
    of = first; // original first
    while (1){
        a=first;
        b=first->next; first=b->next;
        ha = malloc(sizeof (struct huffarbre));
        ha->l=0;
        ha->n=a->ha->n + b->ha->n;
        ha->g = a->ha; ha->d = b->ha;
        if (first==NULL) break;
        ajouter(ha, first, &first);
    }
    while (of){
        a=of;
        of=of->next;
        free(a);
    }
    *arbre = ha;
}
// affichage de la liste
void affliste(struct hal *li){
    struct hal *it_li;
    for (it_li = li; it_li!=NULL; it_li=it_li->next){
        printf("%c, %d\n", it_li->ha->l, it_li->ha->n);
    }
}
// affichage de l'arbre
void affarbre(struct huffarbre *ha, int t){
    int i;
    for (i=0;i<t-1;i++) printf("  |");
    if (t!=0) printf("---");
    if (ha->l){
        printf("%c, %d\n", ha->l, ha->n);
    }else{
        printf("\n");
        t++;
        affarbre(ha->d, t);
        affarbre(ha->g, t);
    }
}
// liberation de la memoire
void freearbre(struct huffarbre *ha){
    if (!ha->l){
        freearbre(ha->g);
        freearbre(ha->d);
    }
    free(ha);
}
// on recupere le code du caractere c, dans *chaine a partir du bit b, au format binaire. renvoie le nombre de bits utilises
int getbinarychainefor(struct huffarbre *ha, char c, char * chaine, int b){
    int l;
    if (ha->l){
        if (c==ha->l){
            return b;
        }else{
            return 0;
        }
    }else{
        if (b%8==0) *(chaine + b/8) = 0;
        if (l=getbinarychainefor(ha->g, c, chaine, b+1)){
            *(chaine + b/8)|=1 << (b%8);
            return l;
        }else if (l=getbinarychainefor(ha->d, c, chaine, b+1)){
            return l;
        }else{
            return 0;
        }
    }
}
// on recupere le code de la chaine *chaine, dans *out, au format binaire. renvoie le nombre de bits utilises
int getbinarychainefromString(struct huffarbre *ha, char * chaine, char *out){
    int l=strlen(chaine);
    int i, j=0;
    for (i=0;i<l;i++){
        j=getbinarychainefor(ha, chaine[i], out, j);
    }
    return j;
}
int main(){
    char chaine[]="test ok arbre test";
    int l=strlen(chaine);
    struct hal *li=malloc(sizeof(struct hal));
    struct huffarbre *ha;
    li->next=NULL; li->ha=NULL;
    sort_chaine(chaine, l);
    arbreliste(chaine, l, &li);
    //affliste(li);
    reduire_arbre(li, &ha);
    //affarbre(ha, 0);
// l'affichage des resultats du test
    l=getbinarychainefromString(ha, "ttb", chaine);
    printf("taille : %d\n", l);
    for (;l>0;l-=8){
        printf("%hhx", *(chaine+(l-1)/8));
    }
    printf("\n");
    freearbre(ha);
    return 0;
}

Compatibilité : C

Disponible dans d'autres langages :

A voir également

S'inscrire maintenant

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.

Du même auteur (coucou747)