430 Intermediate C Programming
}111
// if endec is 0: encode , if it is 1: decode112
// encoded and decode must flip the order of the two113
// subtree s114
s t a t i c ListNode * M ergeLis tNode ( Lis t Node * head , in t endec )115
{116
ListNode * second = head -> next ;117
// second must not be NULL , otherwise , will not enter118
ListNode * third = second -> next ;119
// third may be NULL120
// get the tree nodes of the first two list nodes121
TreeNode * tn1 = head -> tnptr ;122
TreeNode * tn2 = second -> tnptr ;123
// remove the first two nodes124
free ( head );125
free ( second );126
head = third ;127
TreeNode * mrg ;128
i f ( endec == E NCODEMODE )129
{130
mrg = T ree_merge ( tn1 , tn2 ) ;131
}132
e l s e133
{134
mrg = T ree_merge ( tn2 , tn1 ) ;135
}136
ListNode * ln = L istNod e_crea te ( mrg );137
i f ( endec == E NCODEMODE )138
{139
head = List_i nsert ( head , ln , SORTED ) ;140
}141
e l s e142
{143
head = List_i nsert ( head , ln , STACK );144
}145
return head ;146
}147
// merge the top two list nodes until only one list node148
s t a t i c TreeNode * lis t2Tree ( ListNode * head )149
{150
// merge the top two list nodes until only one list node151
while (( head -> next ) != NULL )152
{153
List_pr i nt ( head ); printf (" - --- --- --- - n") ;154
head = Merg e ListNo d e ( head , ENC O DEMODE );155
}156
List_pr i nt ( head );157
// the linked list is no longer needed158
TreeNode * root = head -> tnptr ;159
// the linked list is no longer needed160
free ( head );161
Huffman Compression 431
return root ;162
}163
int encode ( char * infile , char * outfile )164
{165
CharFreq frequen cies [ NUMLET T ER ];166
// set the array elements to zero167
bzero ( frequencies , s i z e o f ( CharFreq ) * NUM LETTER ) ;168
unsigned int numChar =169
coun t Freque ncy ( infile , f requenci es ) ;170
i f ( numChar == 0)171
{172
return 0;173
}174
// p r intFre quency ( frequ encies );175
sortF requen c y ( frequ e ncies );176
// p r intFre quency ( frequ encies );177
ListNode * head = L ist_build ( freque ncies ) ;178
i f ( head == NULL )179
{180
// the article is empty181
return 0;182
}183
TreeNode * root = l ist2Tree ( head ) ;184
// build the code book185
// get the number of leaf nodes186
int numRow = Tree_l e af ( root );187
// get the tree ’s height188
int numCol = Tree _height ( root );189
// numCol should add 1 to a ccommoda t e the ending -1190
numCol ++;191
// create a 2D array and initializ e the codes to -1192
int * * c o debook = malloc ( s i z e o f ( i nt *) * numRow ) ;193
int row ;194
for ( row = 0; row < numRow ; row ++)195
{196
codebook [ row ] = malloc ( s i z e o f ( i nt ) * numCol ) ;197
int col ;198
// ini tialize to -1199
for ( col = 0; col < numCol ; col ++)200
{201
codebook [ row ][ col ] = -1;202
}203
}204
build CodeBo o k ( root , codebook );205
print CodeBo o k ( codebook , numRow );206
// mapping from ASCII to the in d exes of the code book207
int mapping [ N UMLETTER ];208
int ind ;209
for ( ind = 0; ind < NUMLETTER ; ind ++)210
{211
mapping [ ind ] = -1; // initial ized to invalid index212
432 Intermediate C Programming
int ind2 ;213
for ( ind2 = 0; ind2 < numRow ; ind2 ++)214
{215
i f ( codeboo k [ ind2 ][0] == ind )216
{217
mapping [ ind ] = ind2 ;218
}219
}220
}221
for ( ind = 0; ind < NUMLETTER ; ind ++)222
{223
i f ( mapping [ ind ] != -1)224
{225
printf (" %c :% d n" , ind , ma p ping [ ind ]);226
}227
}228
Tree_h eader ( root , numChar , outfile );229
compress ( infile , outfile , codebook , mapping );230
// release memory231
for ( ind = 0; ind < numRow ; ind ++)232
{233
free ( codebook [ ind ]) ;234
}235
free ( codebook );236
237
Tree_ destroy ( root );238
return 1;239
}240
s t a t i c TreeNode * re adHeader ( FILE * infptr )241
{242
int done = 0;243
unsigned char whichbit = 0;244
unsigned char curbyte = 0;245
unsigned char onebit = 0;246
ListNode * head = NULL ;247
// dec reasing to ensure the list is a stack248
while ( done == 0)249
{250
readBit ( infptr , & onebit , & whichbit , & curbyte );251
i f ( onebit == 1)252
{253
// a leaf node , get 7 move bits254
int bitcount ;255
unsigned char value = 0;256
for ( bitcount = 0; b i tcount < 7; bitcount ++)257
{258
value <<= 1; // shift left by one259
readBit ( infptr , & onebit , & whichbit , &260
curbyte ) ;261
value |= onebit ;262
}263
Huffman Compression 433
// push a tree node into the list264
TreeNode * tn = T reeNod e_crea te ( value , 0) ;265
ListNode * ln = L istNod e_crea te ( tn) ;266
head = List_i nsert ( head , ln , STACK );267
}268
e l s e269
{270
i f ( head == NULL )271
{272
printf (" ERROR , head should not be NULL n") ;273
}274
i f (( head -> next ) == NULL )275
{276
// the tree has been comp l etely built277
done = 1;278
}279
e l s e280
{281
head = Merg e ListNo d e ( head , DEC O DEMODE );282
}283
}284
}285
// un n ecessary to read the rema i ning unused bits286
TreeNode * root = head -> tnptr ;287
// the linked list is no longer needed288
free ( head );289
return root ;290
}291
int decode ( char * infile , char * outfile )292
{293
FILE * infptr = fopen ( infile , "r ") ;294
i f ( infptr == NULL )295
{296
return 0;297
}298
TreeNode * root = r eadHeader ( infptr ) ;299
Tree_pr i nt ( root , 0);300
// read the number of c h aracters301
unsigned int numChar = 0;302
fread (& numChar , s i z e o f ( unsigned in t ), 1 , infptr );303
printf (" numChar = % dn " , numChar ) ;304
// read ’ n ’305
unsigned char newline ;306
fread (& newline , s i z e o f ( unsigned char ) , 1, infptr ) ;307
i f ( newline != ’n ’)308
{309
printf (" ERROR ! n") ;310
}311
unsigned char whichbit = 0;312
unsigned char onebit = 0;313
unsigned char curbyte = 0;314
434 Intermediate C Programming
FILE * outfptr = fopen ( outfile , "w ");315
while ( numChar != 0)316
{317
TreeNode * tn = root ;318
while (( tn -> left ) != NULL )319
{320
// tn is not a leaf node321
readBit ( infptr , & onebit , & whichbit , & curbyte );322
i f ( onebit == 0)323
{324
tn = tn -> left ;325
}326
e l s e327
{328
tn = tn -> right ;329
}330
}331
// tn is a leaf node332
printf (" %c" , tn -> value ) ;333
fprintf ( outfptr , "% c" , tn -> value );334
numChar --;335
}336
Tree_ destroy ( root );337
fclose ( infptr ) ;338
fclose ( outfptr );339
return 1;340
}341
// 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
char value ; // cha r acter8
int freq ; // frequen c y9
} TreeNode ;10
TreeNode * Tre eNode_ creat e ( char val , int freq );11
TreeNode * Tree_m erge ( TreeNode * tn1 , TreeNode * tn2 );12
void Tree_pri n t ( T r eeNode * tn , i nt level );13
// find the maximum height of the leaf nodes14
int Tree_he ight ( TreeNode * tn) ;15
// find the number of leaf nodes16
int Tree_leaf ( Tr e eN ode * tn );17
// save the header of a co m pressed file18
void Tree_he ader ( TreeNode * tn , unsigned int numChar , char *19
outfile ) ;20
void Tree_d estroy ( T r e eNode * tn );21
#e ndif22
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.