400 Intermediate C Programming
#in clude < strings .h >6
int count Freque ncy ( char * filename , CharFreq * freq )7
{8
FILE * fptr = fopen ( filename , "r ");9
int count = 0;10
i f ( fptr == NULL )11
{12
return 0;13
}14
while (! feof ( fptr ) )15
{16
int onechar = fgetc ( fptr );17
i f ( onechar != EOF )18
{19
count ++;20
freq [ onechar ]. value = ( char ) onechar ;21
freq [ onechar ]. freq ++;22
}23
}24
fclose ( fptr );25
return count ;26
}27
void print Freque ncy ( CharFreq * freq )28
{29
int ind ;30
for ( ind = 0; ind < NUMLETTER ; ind ++)31
{32
printf (" %d %d n" , freq [ ind ]. value ,33
freq [ ind ]. freq );34
}35
printf (" - --- --- --- --- --- -- - -- --- n ") ;36
}37
s t a t i c i n t comp areFreq ( const void * p1 , const void * p2 )38
{39
const CharFreq * ip1 = ( const CharFreq *) p1 ;40
const CharFreq * ip2 = ( const CharFreq *) p2 ;41
const i n t iv1 = ip1 -> freq ;42
const i n t iv2 = ip2 -> freq ;43
return ( iv1 - iv2 );44
}45
void sortF requenc y ( C harFreq * freq )46
{47
qsort ( freq , NUMLETTER , s i z e o f ( Char F req ) , c ompareFr e q );48
}49
24.2.3 Build a Code Tree
Let’s revisit the small example from the first section of this chapter. Fig. 24.2 to Fig. 24.7
illustrate the procedure for building the tree. First, the characters (C) are sorted by the
frequencies (F). Then, a linked list is created and the nodes are sorted by the character
Huffman Compression 401
(a)
(b)
FIGURE 24.2: (a) The characters are sorted by the frequencies. (b) A linked list is created.
List nodes are expressed by rectangles. Tree nodes are expressed by ovals.
frequencies. Each list node points to a tree node. At the beginning of the algorithm, none
of the tree nodes have children.
Fig. 24.3 shows how to merge the first two list nodes. The first two list nodes, L and R,
are taken. A new tree node N is created and its left and right children are L and R. The
frequency of the newly created tree node is the sum of the frequencies of the two children.
The newly created tree node is not a leaf node so its character is irrelevant. A new list node
is created and points to the newly created tree node. The list nodes must remain sorted in
the ascending order by the tree nodes’ frequencies. These three steps have removed the two
trees from the list with the smallest frequencies, combined them into a single tree, and then
placed the new tree back onto the list, keeping the list sorted by the frequencies.
Fig. 24.4 to Fig. 24.6 repeat the same steps: (i) taking the first two tree nodes, (ii)
creating a parent node (the node’s frequency is the sum of the frequencies of the two
children), (iii) creating a list node, and (iv) inserting the list node and keeping the list
sorted. As a result, two nodes are moved from the list, and one is added, giving a net
change of removing one list node. The linked list becomes shorter.
It is important to understand the concept that is described in the figures. The first part
of the program is described below.
1. A tree structure is created. Each tree node stores a character and the character’s
frequency.
// tree . h1
#i f n d e f TREE_H2
#d ef in e TREE_H3
typedef s t ru ct treenode4
{5
st ruc t treenode * left ;6
st ruc t treenode * right ;7
402 Intermediate C Programming
(a)
(b)
(c)
FIGURE 24.3: (a) Take the tree nodes, L and R, from the first two list nodes. (b) Create
a tree node N whose left and right children are L and R. (c) Create a new list node pointing
to the newly created tree node. The list nodes are sorted in the ascending order by the tree
nodes’ frequencies.
char value ; // cha r acter8
int freq ; // fr equency9
} TreeNode ;10
#e ndif11
2. A list structure is created. Each list node has a pointer to the tree node and a link to
the next list node.
// list . h1
#i f n d e f LIST_H2
#d ef in e LIST_H3
typedef s t ru ct listnode4
{5
st ruc t listnode * next ;6
TreeNode * tnptr ;7
} ListNode ;8
#e ndif9
3. A linked list is created. Each list node points to a tree node. The linked list is sorted
by the frequencies. If two characters have the same frequency, then they are sorted
alphabetically.
4. Repeat the following steps until the linked list has only one node left.
Huffman Compression 403
(a)
(b)
(c)
FIGURE 24.4: Continue the procedure.
5. Take the first two nodes from the linked list (the head and the node after the head).
Take the two tree nodes pointed to by these two list nodes. Call these two tree nodes
L and R. Create a new tree node N whose left and right children are L and R. N’s
frequency is the sum of L’s and R’s frequencies. The character stored in this non-leaf
node is irrelevant.
6. Remove the first two list nodes and discard them. They are no longer needed.
7. Create a new list node pointing to N. Insert this list node so that the list nodes remain
sorted by the tree nodes’ frequencies.
Below is the program for building the tree.
// constan t . h1
#i f n d e f CONSTATN T_H2
#d ef in e CONS T ATNT_H3
#d ef in e NUMLETTE R 1284
#d ef in e TEXT 15
#d ef in e BINARY 26
#e ndif7
404 Intermediate C Programming
(a)
(b)
FIGURE 24.5: At every step, two tree nodes are removed, combined into a single tree,
and then the new tree is added into the list.
// extend the p r e vious tree .h1
TreeNode * Tre eNode_ creat e ( char val , int freq );2
TreeNode * Tree_m erge ( TreeNode * tn1 , TreeNode * tn2 );3
void Tree_pri n t ( T r eeNode * tn , i nt level );4
// extend the p r e vious list .h1
#in clude " tree .h "2
#in clude " constant .h "3
#in clude " freq .h "4
#in clude < stdio .h >5
ListNode * List_b uild ( CharFreq * fre q uencies );6
ListNode * Lis tNode_ creat e ( TreeNode * tn) ;7
ListNode * List _ insert ( List N ode * head , L i stNode * ln );8
void List_pri n t ( L i stNode * head );9
// encode . h1
#i f n d e f ENCODE_H2
#d ef in e ENCODE_H3
..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset