Newsgroup: it.comp.lang.c
Titolo: Codifica di Huffman

Buonasera a tutti,
è da un pò che stò provando a sviluppare un programma che utilizzi la
codifica di huffman, ma con scarsi risultati.
Quello che fino ad oggi ho fatto è molto banale.
Per prima cosa leggo da un file ogni singolo carattere che lo compone e
calcolo le frequenze grazie ad un'array di interi.
Una volta finito scorro l'array e creo lista per ogni carattere presente nel
mio file.
Questa lista è così composta:
struct nodo{
        int num;                //frequenze
        char el;                //carattere
        struct nodo *des;       //ramo destro
        struct nodo *sin;       //ramo sinistro
        struct nodo *pun;//puntatore alla struttura successiva nella lista
};
typedef struct nodo NODO;
Il problema nasce nello sviluppare l'albero in base al peso delle frequenze
di ogno nodo.
Quello che ho provato a fare io è questo:
NODO *crea_albero(NODO *a, NODO *b) {
        NODO *c, *paux;
        if(a==NULL){
        return b;
        }
        else{
        c=crea_nodo_a(a,b);
        paux=crea_albero(a->pun,c);
        }
}
Chiaramente questo mi "dovrebbe" creare una sorta di albero sbilanciato
verso destra.
Mi serve un'aiuto perchè non riesco a capire come possa sviluppare in C
un'albero ben bilanciato.
Vi prego datemi qualche suggerimento.
Grazie a tutti
Ciao
Paolo

 Paolo
Se gli elementi vengono 'sparati' nell'albero in ordine
(alfabetico/numerico) casuale puoi bilanciare l'albero con delle opportune
rotazioni. Se no se prima riesci ad avere gli elementi in ordine crescente
puoi creare un albero bilanciato mandando gli elementi con una sorta di
mergesort (invii l'elemento di mezzo, poi quello di mezzo della meta
sinistra, poi quello di mezzo della meta sinistra della meta sinistra e cosi
via...)

Guarda, ho fatto un programmino per la codifica di huffman poco tempo fa!
Secondo me devi usare un approccio diverso, magari meno compatto, ma +
facile:
a) fai un array di puntatori a delle strutture nodo (il campo num a 0
ovviamnete)...quindi un int *array[256]
b) scorri il file e aggiorna tutte le frequenze (tabto il carattere che
prendi è anche l'indice del vettore...)
c) a questo punto crei l'albero in questo modo:
    - prendi gli indici che puntano ai 2 nodi con minore frequenza
    - crei un nuovo nodo con la frequenza uguale alla somma delle frequenze
dei due nodi con minore frequenza
    - nel nuovo nodo i puntatori "destra" e "sinistra" devono puntare ai 2
nodi presi in considerazione prima.
    - attacchi il nuovo nodo (che in realtà ora è la radice di un albero) ad
uno dei due indici del vettore che hai preso in considerazione prima, e
nell'altro ci metti NULL.
    - iteri il procedimento"c" fino a quando nell'array hai un solo
puntatore attivo (ad ogni iterazione infatti aumentano i puntatori a NULL)
d) a questo punto ti ritrovi un array di puntatori di cui uno solo punta ad
un nodo (tutti gli altri a NULL), che in realtà è la radice dell'albero di
huffman che hai creato.
Cmq l'albero di huffman viene sbilanciato quando c'è una grande differenza
di frequenza tra caratteri, e questo non è un male!
Ciao ciao
Bizio

> ovviamnete)...quindi un int *array[256]
Ho toppato!! è struct nodo *array[256]

 codifica di huffman, ma con scarsi risultati.
Se ti interessa dare un'occhiata a del codice qui c'e' un programmino
scritto da me ( poco commentato ):
nosf.altervista.org/programmi/huffman.cpp
E' c++ ma senza classi  quindi è quasi tutto c.
Stampa anche l'albero in ascii.