Table of Contents for
Intermediate C Programming

Version ebook / Retour

Cover image for bash Cookbook, 2nd Edition Intermediate C Programming by Yung-Hsiang Lu Published by CRC Press, 2015
  1. Front Cover
  2. Contents (1/2)
  3. Contents (2/2)
  4. List of Figures (1/2)
  5. List of Figures (2/2)
  6. List of Tables
  7. Foreword
  8. Preface
  9. Author, Reviewers, and Artist
  10. Rules in Software Development
  11. Source Code
  12. I. Computer Storage: Memory and File
  13. 1. Program Execution (1/2)
  14. 1. Program Execution (2/2)
  15. 2. Stack Memory (1/5)
  16. 2. Stack Memory (2/5)
  17. 2. Stack Memory (3/5)
  18. 2. Stack Memory (4/5)
  19. 2. Stack Memory (5/5)
  20. 3. Prevent, Detect, and Remove Bugs (1/2)
  21. 3. Prevent, Detect, and Remove Bugs (2/2)
  22. 4. Pointers (1/6)
  23. 4. Pointers (2/6)
  24. 4. Pointers (3/6)
  25. 4. Pointers (4/6)
  26. 4. Pointers (5/6)
  27. 4. Pointers (6/6)
  28. 5. Writing and Testing Programs (1/4)
  29. 5. Writing and Testing Programs (2/4)
  30. 5. Writing and Testing Programs (3/4)
  31. 5. Writing and Testing Programs (4/4)
  32. 6. Strings (1/3)
  33. 6. Strings (2/3)
  34. 6. Strings (3/3)
  35. 7. Programming Problems and Debugging (1/4)
  36. 7. Programming Problems and Debugging (2/4)
  37. 7. Programming Problems and Debugging (3/4)
  38. 7. Programming Problems and Debugging (4/4)
  39. 8. Heap Memory (1/3)
  40. 8. Heap Memory (2/3)
  41. 8. Heap Memory (3/3)
  42. 9. Programming Problems Using Heap Memory (1/4)
  43. 9. Programming Problems Using Heap Memory (2/4)
  44. 9. Programming Problems Using Heap Memory (3/4)
  45. 9. Programming Problems Using Heap Memory (4/4)
  46. 10. Reading and Writing Files (1/3)
  47. 10. Reading and Writing Files (2/3)
  48. 10. Reading and Writing Files (3/3)
  49. 11. Programming Problems Using File (1/2)
  50. 11. Programming Problems Using File (2/2)
  51. II. Recursion
  52. 12. Recursion (1/4)
  53. 12. Recursion (2/4)
  54. 12. Recursion (3/4)
  55. 12. Recursion (4/4)
  56. 13. Recursive C Functions (1/4)
  57. 13. Recursive C Functions (2/4)
  58. 13. Recursive C Functions (3/4)
  59. 13. Recursive C Functions (4/4)
  60. 14. Integer Partition (1/5)
  61. 14. Integer Partition (2/5)
  62. 14. Integer Partition (3/5)
  63. 14. Integer Partition (4/5)
  64. 14. Integer Partition (5/5)
  65. 15. Programming Problems Using Recursion (1/5)
  66. 15. Programming Problems Using Recursion (2/5)
  67. 15. Programming Problems Using Recursion (3/5)
  68. 15. Programming Problems Using Recursion (4/5)
  69. 15. Programming Problems Using Recursion (5/5)
  70. III. Structure
  71. 16. Programmer-Defined Data Types (1/6)
  72. 16. Programmer-Defined Data Types (2/6)
  73. 16. Programmer-Defined Data Types (3/6)
  74. 16. Programmer-Defined Data Types (4/6)
  75. 16. Programmer-Defined Data Types (5/6)
  76. 16. Programmer-Defined Data Types (6/6)
  77. 17. Programming Problems Using Structure (1/4)
  78. 17. Programming Problems Using Structure (2/4)
  79. 17. Programming Problems Using Structure (3/4)
  80. 17. Programming Problems Using Structure (4/4)
  81. 18. Linked Lists (1/3)
  82. 18. Linked Lists (2/3)
  83. 18. Linked Lists (3/3)
  84. 19. Programming Problems Using Linked List (1/2)
  85. 19. Programming Problems Using Linked List (2/2)
  86. 20. Binary Search Trees (1/4)
  87. 20. Binary Search Trees (2/4)
  88. 20. Binary Search Trees (3/4)
  89. 20. Binary Search Trees (4/4)
  90. 21. Parallel Programming Using Threads (1/5)
  91. 21. Parallel Programming Using Threads (2/5)
  92. 21. Parallel Programming Using Threads (3/5)
  93. 21. Parallel Programming Using Threads (4/5)
  94. 21. Parallel Programming Using Threads (5/5)
  95. IV. Applications
  96. 22. Finding the Exit of a Maze (1/5)
  97. 22. Finding the Exit of a Maze (2/5)
  98. 22. Finding the Exit of a Maze (3/5)
  99. 22. Finding the Exit of a Maze (4/5)
  100. 22. Finding the Exit of a Maze (5/5)
  101. 23. Image Processing (1/3)
  102. 23. Image Processing (2/3)
  103. 23. Image Processing (3/3)
  104. 24. Huffman Compression (1/10)
  105. 24. Huffman Compression (2/10)
  106. 24. Huffman Compression (3/10)
  107. 24. Huffman Compression (4/10)
  108. 24. Huffman Compression (5/10)
  109. 24. Huffman Compression (6/10)
  110. 24. Huffman Compression (7/10)
  111. 24. Huffman Compression (8/10)
  112. 24. Huffman Compression (9/10)
  113. 24. Huffman Compression (10/10)
  114. A. Linux
  115. B. Version Control
  116. C. Integrated Development Environments (IDE) (1/3)
  117. C. Integrated Development Environments (IDE) (2/3)
  118. C. Integrated Development Environments (IDE) (3/3)
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 = % d\n " , 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