1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96
|
/* realise un arbre de Huffman a partir d'un tableau de feuilles trie */
huffman_tree make_huffman_tree( huffman_tree * tab_leaves )
{
unsigned int i ;
huffman_tree node ;
unsigned int nb_chars ;
nb_chars = 43 ;
for ( i = NB_CHARS-1 ; i > 0 ; i = i - 1 )
{
/* le tableau suppose trie est range dans l'ordre decroissant :
on commence par les nombres les plus grands (taille du tableau :
256 caracteres, donc 256 cases */
node.right = dump_huffman_node(tab_leaves[i]) ;
node.left = dump_huffman_node(tab_leaves[i-1]) ;
/* on initialise ce noeud avec ses valeurs propres */
node.character = '*' ; /* on met ce caractere generique pour
initialiser la valeur */
node.count = tab_leaves[i].count + tab_leaves[i-1].count ; /* le poids
de ce noeud est la somme du poids de chacun des autres noeuds
raccordes */
node.is_leaf = 0 ; /* ce noeud n'est pas une feuille de l'arbre */
node.bin_word = 0 ; /* mot binaire sur un unsigned int */
node.bit_size = 0 ; /* longueur du mot en bits */
/* on ecrase l'une des deux valeurs jointes dans le tableau */
tab_leaves[i-1] = node ;
/* on maintient la liste triee */
sort_leaf_tab(tab_leaves) ;
}
return node ;
}
/* cette fonction va simplement recopier le noeud passe en argument
a une nouvelle adresse dans la memoire, pour les besoins de l'arbre */
huffman_tree * dump_huffman_node(huffman_tree my_node)
{
huffman_tree * my_tree ;
my_tree = malloc(sizeof(*my_tree)) ;
if(my_tree == NULL)
{
puts("alloc memoire dans dump_huffman_tree") ;
return NULL ;
}
else
{
my_tree->count = my_node.count ;
my_tree->character = my_node.character ;
my_tree->right = my_node.right ;
my_tree->left = my_node.left ;
my_tree->bin_word = my_node.bin_word ;
my_tree->bit_size = my_node.bit_size ;
return my_tree ;
}
}
void print_huffman_tree(huffman_tree my_tree)
{
printf("is_leaf=%u, count=%u, character=%c, bit_size=%u, bin_word=%u\n",
my_tree.is_leaf, my_tree.count , my_tree.character , my_tree.bit_size , my_tree.bin_word) ;
}
void sort_leaf_tab(huffman_tree * leaf_tab )
{
qsort( leaf_tab , NB_CHARS , sizeof(*leaf_tab) , compare_huffman_tree ) ;
}
static int compare_huffman_tree( const void * elem1, const void * elem2 )
{
huffman_tree a, b ;
a = *((huffman_tree*)elem1) ;
b = *((huffman_tree*)elem2) ;
if ( a.count > b.count ) {
return -1 ;
}
else if ( a.count < b.count ) {
return 1 ;
}
else {
return 0 ;
}
}
unsigned int dtobin(unsigned char h){
double n;
unsigned int b=0;
for(n=0;n<=7;n++) {
b+=(pow(10,n)*(h%2)); h/=2;
}
return b;
} |
Partager