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)
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