Intermediate C Programming. 2 Ed

Cover Page....1 Half-Title Page....2 Title Page....4 Copyright Page....5 Contents....9 List of Figures....64 List of Tables....68 Foreword for the First Edition....72 Recommendations for the First Edition....76 Preface....79 Acknowledgments....86 Source Code....87 Author and Artist....88 I Storage: Memory and File....90 1 Program Execution....91 1.1 Compile....91 1.2 Redirect Output....97 1.3 Problems....98 1.3.1 Replace String....99 1.3.2 Keep Third Column....99 1.3.3 Find String in a File....99 1.3.4 Sort by a Column....99 1.3.5 gcc Warnings....99 1.3.6 du command....100 1.3.7 Show End of a File....100 2 Stack Memory....101 2.1 Values and Addresses....101 2.2 Stack....105 2.3 The Call Stack....106 2.3.1 The Return Location....106 2.3.2 Function Arguments....113 2.3.3 Local Variables....117 2.3.4 Value Address....118 2.3.5 Arrays....122 2.3.6 Retrieving Addresses....124 2.4 Visibility....125 2.5 Examine the Call Stack with DDD....131 2.6 Problems....138 2.6.1 Draw Call Stack I....138 2.6.2 Draw Call Stack II....139 2.6.3 Addresses....141 3 Prevent, Detect, and Remove Bugs....142 3.1 Rules in Software Development....143 3.2 Developing Software ≠ Coding....146 3.2.1 Before Coding....147 3.2.2 During Coding....148 3.2.3 After Coding....151 3.3 Post-Execution and Interactive Debugging....152 3.4 Separate Testing Code from Production Code....154 3.5 Use assert Correctly....156 3.6 How to Comment Code....158 4 Pointers....162 4.1 Scope....162 4.2 The Swap Function....166 4.3 Pointers....170 4.4 Self Test: Pointers....178 4.5 The Swap Function Revisited....179 4.6 Type Errors....185 4.7 Arrays and Pointers....188 4.8 Type Rules....196 4.9 Pointer Arithmetic....197 4.10 Sizes of Data Types....201 4.11 Problems....208 4.11.1 Swap Function 1....208 4.11.2 Swap Function 2....209 4.11.3 Swap Function 3....211 4.11.4 Swap Function 4....212 4.11.5 Swap Function 5....213 4.11.6 15,552 Variations....215 4.11.7 Pointer and Array....217 5 Writing and Testing Programs....221 5.1 Distinct Array Elements....221 5.1.1 main Function....222 5.1.2 areDistinct Function....226 5.1.3 Compiling and Linking....228 5.2 Build and Test Program with Multiple Files....231 5.2.1 make and Makefile....232 5.2.2 Test using make....239 5.2.3 Generate Test Cases....241 5.3 Detect Invalid Memory Access....244 5.4 Test Coverage....249 5.5 Limit Core Size....255 5.6 Remove Large Files....257 5.7 Problems....258 5.7.1 Array Index....258 5.7.2 gcov....258 5.7.3 Test Coverage....258 6 Strings....259 6.1 Array of Characters....259 6.2 String Functions in C....264 6.2.1 Copy: strcpy....265 6.2.2 Copy: strdup....266 6.2.3 Compare: strcmp....267 6.2.4 Find Substrings: strstr....269 6.2.5 Find Characters: strchr....270 6.3 Understand argv....270 6.4 Count Substrings....275 6.5 Problems....278 6.5.1 Compare Strings....278 6.5.2 Count Substring-1....279 6.5.3 Count Substring-2....279 7 Heap Memory....280 7.1 Allocate Memory using malloc....280 7.2 Stack and Heap Memory....285 7.3 Functions that Return a Heap Address....291 7.4 Two-Dimensional Arrays in C....295 7.5 Pointers and Function Arguments....304 7.6 Problems....308 7.6.1 free....308 7.6.2 malloc....308 7.6.3 Address of Stack Memory....308 8 Programming Problems Using Heap Memory....310 8.1 Sort an Array....310 8.1.1 Generate Test Input and Expected Output....310 8.1.2 Sort Integers....311 8.1.3 Makefile....319 8.1.4 Use valgrind to Detect Memory Leaks....322 8.1.5 Use gcc -fsanitize to Detect Memory Leaks....324 8.2 Sort Using qsort....325 8.2.1 qsort....326 8.2.2 The Comparison Function....328 8.2.3 Execution Examples....333 8.2.4 Sort Strings....335 8.3 Problems....339 8.3.1 Bubble Sort....339 8.3.2 Selection Sort....342 8.3.3 Comparison in qsort....342 9 Reading and Writing Files....343 9.1 Read from Files....343 9.2 Write to Files....352 9.3 Read and Write Strings....357 10 Programming Problems Using File....365 10.1 Sort a File of Integers....365 10.2 Count the Occurrences of Characters....370 10.3 Count the Occurrences of a Word....376 10.4 Problems....379 10.4.1 Determine Palindrome....379 10.4.2 Compare Two Files....380 10.4.3 fscanf and ftell....380 11 Array Index, Security, and Trends....383 11.1 Array Index....384 11.2 Modify Program Behavior....390 11.3 Trends in Programming Languages....393 12 Version Control....396 12.1 Version Control Overview....396 12.2 git and github.com....397 12.3 Create a Repository on github....400 12.4 Sample Repository....408 12.5 Use git and github.com....418 12.6 Problems....428 12.6.1 git commit and git push....428 12.6.2 Revert to an earlier version....428 12.6.3 When to commit?....428 12.6.4 When to clone?....428 12.6.5 Recover deleted file....428 II Recursion....430 13 Concept....431 13.1 Select Balls with Restrictions....432 13.1.1 Balls of Two Colors....432 13.1.2 Balls of Three Colors....434 13.2 One-Way Streets....436 13.3 The Tower of Hanoi....438 13.4 Calculate Integer Partitions....441 13.4.1 Count the Number of “1”s....443 13.4.2 Odd Numbers Only....447 13.4.3 Increasing Values....448 13.4.4 Alternating Odd and Even Numbers....450 13.5 Problems....454 13.5.1 Parentheses....454 13.5.2 Ball Selection....456 13.5.3 Partition using Odd and Even Numbers....456 14 Recursive C Functions....458 14.1 Select Balls with Restrictions....459 14.2 One-Way Streets....461 14.3 The Tower of Hanoi....464 14.4 Integer Partition....468 14.5 Factorial....470 14.6 Fibonacci Numbers....475 14.7 Performance Profiling with gprof....486 14.8 Problems....489 14.8.1 Count Number of Calls: Original Definition....489 14.8.2 Count Number of Calls: Efficient Recursion....490 14.8.3 Parentheses....492 14.8.4 Fibonacci Numbers....495 15 Integer Partition....496 15.1 Print Partitions....496 15.2 Stack and Heap Memory....500 15.3 Trace Recursive Function Calls....508 15.4 Generate Partitions with Restrictions....513 15.4.1 Using Odd Numbers Only....515 15.4.2 Using Sequences of Increasing Numbers....517 15.4.3 Using Alternating Odd and Even Numbers....518 15.5 Problems....520 15.5.1 Even Numbers Only....520 15.5.2 Decreasing Values....520 15.5.3 Error in partition....520 15.5.4 Error in partition....521 15.5.5 Error in partition....521 16 Programming Problems Using Recursion....523 16.1 Binary Search....523 16.2 Quick Sort....529 16.3 Permutations and Combinations....542 16.4 Stack Sort....551 16.5 An Incorrect Recursive Function....560 16.6 Problems....564 16.6.1 Shuffle Cards - 1....564 16.6.2 Shuffle Cards - 2....567 16.6.3 Shuffle Cards - 3....567 III Structure....568 17 Programmer-Defined Data Types....569 17.1 Struct and Object....569 17.2 Objects as Arguments....579 17.3 Objects and Pointers....583 17.4 Constructors and Destructors....593 17.5 Structures within Structures....611 17.6 Binary Files and Objects....617 17.7 Problems....625 17.7.1 Structure and Pointer....625 17.7.2 Structure and Attributes' Sizes....628 17.7.3 Alternative Ways to Assign Attributes....632 18 Programming Problems Using Structure....635 18.1 Sort a Person Database....635 18.2 Packing Decimal Digits....651 18.3 Binary File and Pointer....674 18.4 Problems....679 18.4.1 Number Systems....679 18.4.2 Structure with Pointer-1....680 18.4.3 Structure with Pointer-2....680 19 Linked Lists....681 19.1 Dynamic Data Structure....681 19.2 Linked Lists....683 19.3 Insert Data....685 19.4 Search a Linked List....690 19.5 Delete a Node from a Linked List....691 19.6 Print a Linked List....695 19.7 Destroy a Linked List....697 20 Programming Problems Using Linked List....703 20.1 Queues....703 20.2 Sort Numbers....705 20.3 Sparse Arrays....708 20.4 Reversing a Linked List....720 20.5 Doubly Linked List....722 21 Binary Search Trees....725 21.1 Binary Tree....725 21.2 Binary Search Tree....729 21.3 Insert Data into a Binary Search Tree....732 21.4 Search a Binary Search Tree....736 21.5 Print a Binary Tree....738 21.6 Delete from a Binary Search Tree....743 21.7 Destroy a Binary Tree....747 21.8 Count the Different Shapes of a Binary Tree....748 21.9 Problems....753 21.9.1 Count Nodes....753 21.9.2 Tree Height....753 21.9.3 Check Binary Search Tree....753 21.9.4 Ancestor-Offspring....753 21.9.5 Build Binary Tree....753 22 Parallel Programming Using Threads....755 22.1 Parallel Programming....755 22.2 POSIX Threads....757 22.3 Subset Sum....762 22.3.1 Sequential Solution....765 22.3.2 Multiple-Threads Solution....773 22.4 Interleave the Execution of Threads....785 22.5 Thread Synchronization....796 22.6 Amdahl's Law....803 22.6.1 Speedup vs. Efficiency....805 22.6.2 Understanding Amdahl's Law....808 22.6.3 The Limit's of Amdahl's Law....810 22.7 Problems....812 22.7.1 Interleaving of Threads....812 22.7.2 Interleaving of Threads....812 23 Unit Test....813 23.1 Google Test Framework....813 23.2 Rational Numbers....820 23.3 Rational Numbers and Operations....828 23.3.1 Create Ratoinal Object....828 23.3.2 Arithmetic Operations....835 23.4 Use and Test Rational Numbers....844 23.4.1 Use Rational Numbers....844 23.4.2 Test Rational Numbers....852 23.5 Testing Strategies....865 IV Applications....868 24 Find the Exit of a Maze....869 24.1 Maze File Format....869 24.2 Strategy to Find Exit....873 24.3 Implement the Strategy....876 24.4 Problems....890 24.4.1 Mark of Bricks....890 24.4.2 Multiple Exits....890 24.4.3 Order of Directions....890 24.4.4 Change if Conditions....890 25 Sudoku....892 25.1 Sudoku Game....892 25.2 Recursive Solution....895 25.3 Implement the Solution....899 25.4 Design Decisions....922 25.5 Network Communication....925 25.5.1 Server....928 25.5.2 Client....936 25.6 Problems....942 25.6.1 Check Sudoku....942 25.6.2 Transfer Large File....943 26 Image Processing....944 26.1 Structure for Image....944 26.2 Image Pixels and Colors....957 26.3 Color Filter....961 26.4 Invert Colors....963 26.5 Detect Edges....964 26.6 Equalize Colors....969 26.7 main Function....974 26.8 Problems....977 26.8.1 Color Histogram....977 26.8.2 Color Space....978 26.8.3 Gradient....978 26.8.4 Vertical Mirror....978 27 Huffman Compression....979 27.1 Variable-Length Coding....979 27.2 Compress....981 27.2.1 Count and Sort Occurrences....981 27.2.2 Build the Code Tree....983 27.2.3 Create Code Book and Compress Data....986 27.2.4 Describe the Coding Tree....987 27.2.5 Use Bits....988 27.3 Decompress....992 27.4 Implementation....993 27.4.1 Test Case Generator....993 27.4.2 main Function....996 27.4.3 Makefile....998 27.4.4 Compression....1000 27.4.5 Decompression....1011 27.4.6 Compression Ratios....1017 27.5 Problems....1018 27.5.1 Compression Tree....1018 27.5.2 Compressed File....1018 27.5.3 Compressed File....1018 27.5.4 One-Letter Input....1018 27.5.5 Compressed File....1018 27.5.6 Number of Leaf Nodes....1018 27.5.7 Compression Ratio....1018 27.5.8 Tree Description....1018 27.5.9 Highest Possible Compression Ratio....1019 27.5.10 Lowest Possible Compression Ratio....1019 Index....1020 Epilogue: The Computer Engineer as Tool-User....1067