Huffman Compression 405
(a) (b)
FIGURE 24.6: Continue the procedure shortening the linked list.
// encode the text in the input file4
// save the result in the output file5
// mode : TEXT or BINARY6
// return 0 if cannot read from file or write to file7
// return 1 if success8
int encode ( char * infile , char * outfile , i n t mode ) ;9
#e ndif10
// tree . c1
#in clude " tree .h "2
#in clude < stdio .h >3
#in clude < stdlib .h >4
TreeNode * Tre eNode_ creat e ( char val , int freq )5
{6
TreeNode * tn = malloc ( s i z e o f ( TreeNode )) ;7
tn -> left = NULL ;8
tn -> right = NULL ;9
tn -> value = val ;10
tn -> freq = freq ;11
return tn;12
}13
TreeNode * Tree_m erge ( TreeNode * tn1 , TreeNode * tn2 )14
{15
TreeNode * tn = malloc ( s i z e o f ( TreeNode )) ;16
tn -> left = tn1 ;17
tn -> right = tn2 ;18
tn -> value = 0; // do not care19
tn -> freq = tn1 -> freq + tn2 -> freq ;20
406 Intermediate C Programming
FIGURE 24.7: Now the linked list has only one node. The tree has been built, and it is
in the only remaining list node.
return tn;21
}22
// post - order23
void Tree_pri n t ( T r eeNode * tn , i nt level )24
{25
i f ( tn == NULL )26
{27
return ;28
}29
TreeNode * lc = tn -> left ; // left child30
TreeNode * rc = tn -> right ; // right child31
Tree_pr i nt ( lc , level + 1) ;32
Tree_pr i nt ( rc , level + 1) ;33
int depth ;34
for ( depth = 0; depth < level ; depth ++)35
{36
printf (" ") ;37
}38
printf (" freq = %d " , tn -> freq );39
i f (( lc == NULL ) && ( rc == NULL ) )40
{41
// a leaf node42
printf (" value = %d , ’%c ’" , tn -> value , tn -> value ) ;43
}44
printf (" n" );45
}46
Huffman Compression 407
// list . c1
#in clude " list .h "2
#in clude " freq .h "3
#in clude < stdlib .h >4
ListNode * Lis tNode_ creat e ( TreeNode * tn)5
{6
ListNode * ln = malloc ( s i z e o f ( ListNode )) ;7
ln -> next = NULL ;8
ln -> tnptr = tn ;9
return ln;10
}11
// head may be NULL12
// ln must not be NULL13
// ln -> next must be NULL14
ListNode * List _ insert ( List N ode * head , L i stNode * ln )15
{16
i f ( head == NULL )17
{18
return ln;19
}20
i f ( ln == NULL )21
{22
printf (" ERROR ! ln is NULL n ");23
}24
i f (( ln -> next ) != NULL )25
{26
printf (" ERROR ! ln -> next is not NULL n ");27
}28
int freq1 = ( head -> tnptr ) -> freq ;29
int freq2 = ( ln -> tnptr ) -> freq ;30
i f ( freq1 > freq2 )31
{32
// ln should be the first node33
ln -> next = head ;34
return ln;35
}36
// ln should be after head37
head -> next = List_i nsert ( head -> next , ln );38
return head ;39
}40
// fr e quencies must be sorted41
ListNode * List_b uild ( CharFreq * fre q uencies )42
{43
// find the first index whose freque n cy is nonzero44
int ind = 0;45
while ( freq uencies [ ind ]. freq == 0)46
{47
ind ++;48
}49
i f ( ind == NUMLETTER )50
{51
408 Intermediate C Programming
// no letter appears52
return NULL ;53
}54
// create a linked list , each node points to a tree node55
ListNode * head = NULL ;56
while ( ind < NUMLETTER )57
{58
TreeNode * tn =59
Tree Node_c reate ( freque ncies [ ind ]. value ,60
freque ncies [ ind ]. freq );61
ListNode * ln = L istNod e_crea te ( tn) ;62
head = List_i nsert ( head , ln );63
ind ++;64
}65
return head ;66
}67
void List_pri n t ( L i stNode * head )68
{69
i f ( head == NULL )70
{71
return ;72
}73
Tree_pr i nt ( head -> tnptr , 0) ;74
List_pr i nt ( head -> next );75
}76
The following function implements the concept depicted earlier.
// encode . c1
#in clude " encode .h "2
#in clude " constant .h "3
#in clude " freq . h"4
#in clude " list . h"5
#in clude < stdio .h >6
#in clude < strings .h >7
#in clude < stdlib .h >8
int encode ( char * infile , char * outfile , i n t mode )9
{10
CharFreq frequen cies [ NUMLET T ER ];11
// set the array elements to zero12
bzero ( frequencies , s i z e o f ( CharFreq ) * NUM L ETTER ) ;13
i f ( c o untFre quency ( infile , fr e quencies ) == 0)14
{15
return 0;16
}17
// p r intFre quency ( frequ encies );18
sortF requenc y ( frequ e ncies );19
// p r intFre quency ( frequ encies );20
ListNode * head = L ist_build ( freque n cies ) ;21
i f ( head == NULL )22
{23
// the article is empty24
Huffman Compression 409
return 0;25
}26
// merge the top two list nodes until only one list node27
while (( head -> next ) != NULL )28
{29
List_pr i nt ( head ); printf (" - --- --- --- - n") ;30
ListNode * second = head -> next ;31
// second must not be NULL , otherwise , will not enter32
ListNode * third = second -> next ;33
// third may be NULL34
// get the tree nodes of the first two list nodes35
TreeNode * tn1 = head -> tnptr ;36
TreeNode * tn2 = second -> tnptr ;37
// remove the first two nodes38
free ( head );39
free ( second );40
head = third ;41
TreeNode * mrg = Tree_me r ge ( tn1 , tn2 ) ;42
ListNode * ln = L istNod e_crea te ( mrg );43
head = List_i nsert ( head , ln );44
}45
List_pr i nt ( head );46
return 1;47
}48
Line 46 prints the linked list, and it should have only one list node. Otherwise, the
function should continue inside while. Calling Tree print prints the tree nodes using a
post-order traversal. Below is the output. Note that it matches Fig. 24.7.
freq = 73 value = 104, ’h’
freq = 46 value = 100, ’d’
freq = 23 value = 112, ’p’
freq = 7 value = 84, ’T’
freq = 1 value = 69, ’E’
freq = 2 value = 78, ’N’
freq = 3
freq = 7 value = 71, ’G’
freq = 10
freq = 17
freq = 19 value = 103, ’g’
freq = 36
freq = 59
freq = 105
freq = 178
Fig. 24.8 shows the list of tree nodes as displayed in the debugging program DDD. DDD
can help you visualize how the list nodes and the tree nodes change as the program makes
progress. Fig. 24.9 shows the tree in DDD after the tree has been completely built. It is the
same tree as Fig. 24.7. The visualization function in DDD can help you see the nodes of the
tree.
..................Content has been hidden....................

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