Intermediate C Programming

Huﬀman 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

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

Huﬀman 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

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

Huﬀman 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.

Previous Chapter

24. Huffman Compression (2/10)

Next Chapter

24. Huffman Compression (4/10)

Table of Contents for Intermediate C Programming

Table of Contents for
Intermediate C Programming