q15-1.c
/* code: q15-1.c (v1.16.00) */
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
struct code_table
{
int length;
int num;
int first;
};
typedef struct code_table CODE_TABLE_TYPE;
/* -------------------------------------- */
void compute_first (CODE_TABLE_TYPE table[], int array_size)
{
int i, index;
index = array_size - 1;
table[index].first = 0;
for (i = index - 1; i >= 0; i--) {
table[i].first = ceil (((table[i + 1].first + table[i + 1].num) / 2.0));
}
}
/* -------------------------------------- */
void table_print (CODE_TABLE_TYPE table[], int iSize)
{
int i;
printf ("L N F\n");
for (i = 0; i < iSize; i++) {
printf ("%d %d %d", table[i].length, table[i].num, table[i].first);
printf ("\n");
}
}
/* -------------------------------------- */
int table_read (CODE_TABLE_TYPE table[], char *filename)
{
FILE *infile;
int i;
int iLength, iNum;
if (NULL == (infile = fopen (filename, "rt"))) {
printf ("\nERROR: Can not open file [%s]", filename);
exit (-1);
}
i = 0;
while (EOF != fscanf (infile, "%d%d", &iLength, &iNum)) {
table[i].length = iLength;
table[i].num = iNum;
table[i].first = 0;
i++;
}
fclose (infile);
return i;
}
/* -------------------------------------- */
int main ()
{
CODE_TABLE_TYPE table[128];
int i;
i = table_read (table, "table.txt");
table_print (table, i);
compute_first (table, i);
table_print (table, i);
return 0;
}
q15-2.c
/* code: q15-2.c (v1.16.00) */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define TREE_SIZE 2048
struct node
{
char data;
int freq;
struct node *left;
struct node *right;
};
typedef struct node NODE_TYPE;
struct heap
{
NODE_TYPE **array;
int size;
int max_size;
};
typedef struct heap HEAP_TYPE;
/* -------------------------------------- */
NODE_TYPE *heap_new_node (char data, int freq)
{
NODE_TYPE *new_node;
new_node = malloc (sizeof (NODE_TYPE));
if (NULL == new_node) {
printf ("ERROR(heap_new_node): Can not allocate memory.\n");
exit (-1);
}
new_node->data = data;
new_node->freq = freq;
new_node->left = NULL;
new_node->right = NULL;
return new_node;
}
/* -------------------------------------- */
HEAP_TYPE *heap_create (int max_size)
{
HEAP_TYPE *Heap;
Heap = malloc (sizeof (HEAP_TYPE));
if (NULL == Heap) {
printf ("ERROR(heap_create): Can not allocate memory.\n");
exit (-1);
}
Heap->size = 0;
Heap->max_size = max_size;
Heap->array = (NODE_TYPE **) malloc (Heap->max_size * sizeof (NODE_TYPE *));
return Heap;
}
/* -------------------------------------- */
void heap_swap_two_nodes (NODE_TYPE ** src, NODE_TYPE ** tgt)
{
NODE_TYPE *temp;
temp = *src;
*src = *tgt;
*tgt = temp;
}
/* -------------------------------------- */
void heap_heapify_nodes (HEAP_TYPE * Heap, int pos)
{
int left, right, pos_min;
pos_min = pos;
left = 2 * pos + 1;
right = 2 * pos + 2;
if (left < Heap->size &&
Heap->array[left]->freq < Heap->array[pos_min]->freq) {
pos_min = left;
}
if ((right < Heap->size) &&
(Heap->array[right]->freq < Heap->array[pos_min]->freq)) {
pos_min = right;
}
if (pos_min != pos) {
heap_swap_two_nodes (&Heap->array[pos_min], &Heap->array[pos]);
heap_heapify_nodes (Heap, pos_min);
}
}
/* -------------------------------------- */
int heap_check_size (HEAP_TYPE * Heap)
{
if (Heap->size == 1) {
return 1;
}
else {
return 0;
}
}
/* -------------------------------------- */
NODE_TYPE *heap_find_min_node (HEAP_TYPE * Heap)
{
NODE_TYPE *temp;
temp = Heap->array[0];
Heap->array[0] = Heap->array[Heap->size - 1];
Heap->size = Heap->size - 1;
heap_heapify_nodes (Heap, 0);
return temp;
}
/* -------------------------------------- */
void heap_insert_node (HEAP_TYPE * Heap, NODE_TYPE * HeapNode)
{
int i;
Heap->size = Heap->size + 1;
i = Heap->size - 1;
while (i && (HeapNode->freq < Heap->array[(i - 1) / 2]->freq)) {
Heap->array[i] = Heap->array[(i - 1) / 2];
i = (i - 1) / 2;
}
Heap->array[i] = HeapNode;
}
/* -------------------------------------- */
void heap_tree (HEAP_TYPE * Heap)
{
int i, n;
n = Heap->size - 1;
for (i = (n - 1) / 2; i >= 0; --i) {
heap_heapify_nodes (Heap, i);
}
}
/* -------------------------------------- */
int heap_check_leaf_node (NODE_TYPE * tree)
{
return !(tree->left) && !(tree->right);
}
/* -------------------------------------- */
HEAP_TYPE *heap_tree_build (char data[], int freq[], int size)
{
int i;
HEAP_TYPE *Heap;
Heap = heap_create (size);
for (i = 0; i < size; ++i) {
Heap->array[i] = heap_new_node (data[i], freq[i]);
}
Heap->size = size;
heap_tree (Heap);
return Heap;
}
/* -------------------------------------- */
NODE_TYPE *Huffman_tree (char data[], int freq[], int size)
{
NODE_TYPE *left, *right, *node;
HEAP_TYPE *Heap;
int freq_sum;
Heap = heap_tree_build (data, freq, size);
while (!heap_check_size (Heap)) {
left = heap_find_min_node (Heap);
right = heap_find_min_node (Heap);
freq_sum = left->freq + right->freq;
node = heap_new_node ('-', freq_sum);
node->left = left;
node->right = right;
heap_insert_node (Heap, node);
}
return heap_find_min_node (Heap);
}
/* -------------------------------------- */
void Huffman_code_print (NODE_TYPE * tree, int code[], int n)
{
int i;
if (tree->left) {
code[n] = 0;
Huffman_code_print (tree->left, code, n + 1);
}
if (tree->right) {
code[n] = 1;
Huffman_code_print (tree->right, code, n + 1);
}
if (heap_check_leaf_node (tree)) {
printf ("%2c (%d): ", tree->data, tree->freq);
for (i = 0; i < n; ++i) {
printf ("%d", code[i]);
}
printf ("\n");
}
}
/* -------------------------------------- */
int main ()
{
NODE_TYPE *tree;
int buffer[TREE_SIZE];
int array_size;
char array[] = { 'a', 'b', 'd', 'e', 'c' };
int freq[] = { 4, 3, 2, 2, 1 };
array_size = sizeof (array) / sizeof (array[0]);
tree = Huffman_tree (array, freq, array_size);
Huffman_code_print (tree, buffer, 0);
return 0;
}
EOF