Originally Posted by
atlantis43
but what type of empty variable is needed to hold the bits?
Your problem says: "array, indexed by character (a number between 0 and 127 for a 7 bit ascii character), that contains an entry for the coded bits and the code’s length."
So, I'd use
Code:
typedef struct {
unsigned int path;
unsigned char length;
} huffman_code;
An unsigned int has (CHAR_BIT*sizeof (unsigned int)) bits, and an unsigned char can hold values between 0 and UCHAR_MAX, inclusive.
So, an array of huffman_code entries can describe any Huffman tree whose maximum depth does not exceed (CHAR_BIT*sizeof (unsigned int)) or UCHAR_MAX (whichever is smaller applies). These constants are defined in limits.h header file.
Let's assume you have a table of the above codes, and you initialize it to "no path/no code":
Code:
#include <limits.h>
huffman_code table[UCHAR_MAX + 1];
int i;
for (i = 0; i <= UCHAR_MAX; i++) {
table[i].path = 0U; /* Same as (unsigned int)0 */
table[i].length = 0U; /* The U just means unsigned */
}
and you're working on tree
Consider the leaf specifying x: The path from root to it is right-left-left-right-left, or 10010, five steps long. Since 10010 in binary is 16+2=18 in decimal, you should have
Code:
table['x'].path = 18;
table['x'].length = 5;
Here's the trick: instead of looping over the 128 characters to fill the table, traverse your tree, keeping track of the path (left or right, and how many steps) taken to reach the current node from the root. Whenever you reach a leaf node, you fill in the corresponding table entry. As you traverse the entire tree, you fill the table.
Assuming your tree is correctly built, the entries that do not get defined while traversing the tree, will not be used at all. (Which is why it is a good idea to initialize them as "no path".)
Questions?