Huffman Compression 435
// tree . c1
#in clude " tree .h "2
#in clude " utility . h"3
#in clude < stdio .h >4
#in clude < stdlib .h >5
TreeNode * Tre eNode_ creat e ( char val , int freq )6
{7
TreeNode * tn = malloc ( s i z e o f ( TreeNode )) ;8
tn -> left = NULL ;9
tn -> right = NULL ;10
tn -> value = val ;11
tn -> freq = freq ;12
return tn;13
}14
TreeNode * Tree_m erge ( TreeNode * tn1 , TreeNode * tn2 )15
{16
TreeNode * tn = malloc ( s i z e o f ( TreeNode )) ;17
tn -> left = tn1 ;18
tn -> right = tn2 ;19
tn -> value = 0; // do not care20
tn -> freq = tn1 -> freq + tn2 -> freq ;21
return tn;22
}23
// post - order24
void Tree_pri n t ( T r eeNode * tn , i nt level )25
{26
i f ( tn == NULL )27
{28
return ;29
}30
TreeNode * lc = tn -> left ; // left child31
TreeNode * rc = tn -> right ; // right child32
Tree_pr i nt ( lc , level + 1) ;33
Tree_pr i nt ( rc , level + 1) ;34
int depth ;35
for ( depth = 0; depth < level ; depth ++)36
{37
printf (" ") ;38
}39
printf (" freq = %d " , tn -> freq );40
i f (( lc == NULL ) && ( rc == NULL ) )41
{42
// a leaf node43
printf (" value = %d , ’%c ’" , tn -> value , tn -> value ) ;44
}45
printf (" n" );46
}47
s t a t i c i n t Tr e e_he i ghtHe lper ( T re eNode * tn , i nt height )48
{49
i f ( tn == 0)50
{51
436 Intermediate C Programming
return height ;52
}53
int lh = Tree _heig h tHelp er ( tn -> left , height + 1) ;54
int rh = Tree _heig h tHelp er ( tn -> right , height + 1);55
i f ( lh < rh )56
{57
return rh;58
}59
i f ( lh > rh )60
{61
return lh;62
}63
return lh;64
}65
int Tree_he ight ( TreeNode * tn)66
{67
return Tre e_hei ghtHe lper (tn , 0) ;68
}69
s t a t i c void Tree_l eafHe l per ( TreeNo d e * tn , in t * num )70
{71
i f ( tn == 0)72
{73
return ;74
}75
// if it is a leaf node , add one76
TreeNode * lc = tn -> left ;77
TreeNode * rc = tn -> right ;78
i f (( lc == NULL ) && ( rc == NULL ) )79
{80
(* num ) ++;81
return ;82
}83
Tree _leafH elper (lc , num );84
Tree _leafH elper (rc , num );85
}86
int Tree_leaf ( Tre eN ode * tn )87
{88
int num = 0;89
Tree _leafH elper (tn , & num ) ;90
return num ;91
}92
// print the 7 bits of an ASCII charac ter93
s t a t i c void char2bits ( FILE * outfptr , i n t ch ,94
unsigned char * whichbit ,95
unsigned char * curbyte )96
{97
unsigned char mask = 0 x40 ; // only 7 bits98
while ( mask > 0)99
{100
writeBit ( outfptr , ( ch & mask ) == mask ,101
whichbit , curbyte );102
Huffman Compression 437
mask >>= 1;103
}104
}105
s t a t i c void Tree_ heade rHelp er ( TreeNode * tn ,106
FILE * outfptr ,107
unsigned char * whichbit ,108
unsigned char * curbyte )109
{110
i f ( tn == NULL )111
{112
return ; // should not get here113
}114
TreeNode * lc = tn -> left ;115
TreeNode * rc = tn -> right ;116
i f (( lc == NULL ) && ( rc == NULL ) )117
{118
// leaf node119
writeBit ( outfptr , 1 , whichbit , curbyte ) ;120
char2bits ( outfptr , tn -> value , whichbit , c u r b y t e ) ;121
return ;122
}123
Tree _head erHel per ( lc , outfptr , whichbit , curbyte );124
Tree _head erHel per ( rc , outfptr , whichbit , curbyte );125
writeBit ( outfptr , 0 , whichbit , curbyte ) ;126
}127
void Tree_he ader ( TreeNode * tn , unsigned int numChar ,128
char * outfile )129
{130
FILE * outfptr = fopen ( outfile , "w ");131
i f ( outfptr == NULL )132
{133
return ;134
}135
unsigned char whichbit = 0;136
unsigned char curbyte = 0;137
Tree _head erHel per ( tn , outfptr , & whichbit , & curbyte );138
// add one more 0 to end the header139
writeBit ( outfptr , 0 , & whichbit , & c urby t e );140
padZero ( outfptr , & whichbit , & curbyte );141
// write the number of characte r s142
fwrite (& numChar , s i z e o f ( unsigned in t ), 1 , outfptr ) ;143
// add ’ n ’ at the end of the header144
unsigned char newline = ’n ’;145
fwrite (& newline , s i z e o f ( unsigned char ) , 1, outfptr );146
fclose ( outfptr );147
}148
void Tree_d estroy ( T r e eNode * tn )149
{150
i f ( tn == NULL )151
{152
return ;153
438 Intermediate C Programming
}154
Tree_ destroy ( tn -> left );155
Tree_ destroy ( tn -> right ) ;156
free ( tn ) ;157
}158
// list . h1
#i f n d e f LIST_H2
#d ef in e LIST_H3
#in clude " tree .h "4
#in clude " constant .h "5
#in clude " freq .h "6
#in clude < stdio .h >7
#d ef in e QUEUE 08
#d ef in e STACK 19
#d ef in e SORTED 210
typedef s t ru ct listnode11
{12
st ruc t listnode * next ;13
TreeNode * tnptr ;14
} ListNode ;15
ListNode * List_b uild ( CharFreq * fre q uencies );16
ListNode * Lis tNode_ creat e ( TreeNode * tn) ;17
// The mode is QUEUE , STACK , or SORTED18
ListNode * List _ insert ( List N ode * head , L i stNode * ln , i nt19
mode ) ;20
void List_pri n t ( L i stNode * head );21
#e ndif22
// 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
int mode )16
{17
i f ( ln == NULL )18
{19
printf (" ERROR ! ln is NULL n ");20
return NULL ;21
}22
Huffman Compression 439
i f (( ln -> next ) != NULL )23
{24
printf (" ERROR ! ln -> next is not NULL n ");25
}26
i f ( head == NULL )27
{28
return ln;29
}30
i f ( mode == STACK )31
{32
ln -> next = head ;33
return ln;34
}35
i f ( mode == QUEUE )36
{37
head -> next = List_i nsert ( head -> next , ln , mode );38
return head ;39
}40
// insert in incr e asing order41
int freq1 = ( head -> tnptr ) -> freq ;42
int freq2 = ( ln -> tnptr ) -> freq ;43
i f ( freq1 > freq2 )44
{45
// ln should be the first node46
ln -> next = head ;47
return ln;48
}49
// ln should be after head50
head -> next = List_i nsert ( head -> next , ln , mode );51
return head ;52
}53
// fr e quencies must be sorted54
ListNode * List_b uild ( CharFreq * fre q uencies )55
{56
// find the first index whose freque n cy is nonzero57
int ind = 0;58
while ( freq uencies [ ind ]. freq == 0)59
{60
ind ++;61
}62
i f ( ind == NUMLETTER )63
{64
// no letter appears65
return NULL ;66
}67
// create a linked list , each node points to a tree node68
ListNode * head = NULL ;69
while ( ind < NUMLETTER )70
{71
TreeNode * tn =72
Tree Node_c reate ( freque ncies [ ind ]. value ,73
..................Content has been hidden....................

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