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)
Contents
List of Figures xiii
List of Tables xix
Foreword xxi
Preface xxiii
Author, Reviewers, and Artist xxvii
Rules in Software Development xxix
Source Code xxxi
I Computer Storage: Memory and File 1
1 Program Execution 3
1.1 Compile ...................................... 3
1.2 RedirectOutput ................................. 7
2StackMemory 9
2.1 ValuesandAddresses .............................. 9
2.2 Stack ....................................... 11
2.3 TheCallStack .................................. 11
2.3.1 TheReturnLocation........................... 11
2.3.2 FunctionArguments ........................... 15
2.3.3 LocalVariables.............................. 18
2.3.4 ValueAddress .............................. 19
2.3.5 Arrays................................... 20
2.3.6 RetrievingAddresses........................... 21
2.4 Visibility . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.5 Exercises ..................................... 24
2.5.1 DrawCallStackI ............................ 24
2.5.2 DrawCallStackII............................ 25
2.5.3 Addresses................................. 25
2.6 Answers...................................... 26
2.6.1 DrawCallStackI ............................ 26
2.6.2 DrawCallStackII............................ 26
2.6.3 Addresses................................. 27
2.7 ExaminetheCallStackwithDDD ....................... 27
v
vi Contents
3 Prevent, Detect, and Remove Bugs 33
3.1 Developing Software =Coding ......................... 33
3.1.1 Beforecoding............................... 34
3.1.2 Duringcoding .............................. 34
3.1.3 Aftercoding ............................... 35
3.2 CommonMistakes ................................ 35
3.2.1 UninitializedVariables.......................... 36
3.2.2 WrongArrayIndexes .......................... 36
3.2.3 WrongTypes............................... 36
3.3 Post-ExecutionandInteractiveDebugging .................. 36
3.4 SeparateTestingCodefromProductionCode ................ 37
4Pointers 39
4.1 Scope ....................................... 39
4.2 TheSwapFunction ............................... 41
4.3 Pointers ...................................... 43
4.4 TheSwapFunctionRevisited .......................... 47
4.5 TypeErrors ................................... 50
4.6 ArraysandPointers ............................... 51
4.7 TypeRules .................................... 54
4.8 PointerArithmetic ................................ 55
4.9 Exercises ..................................... 59
4.9.1 SwapFunction1 ............................. 59
4.9.2 SwapFunction2 ............................. 59
4.9.3 SwapFunction3 ............................. 60
4.9.4 SwapFunction4 ............................. 60
4.9.5 SwapFunction5 ............................. 61
4.9.6 15,552Variations............................. 61
4.10Answers...................................... 62
4.10.1 SwapFunction1 ............................. 62
4.10.2 SwapFunction2 ............................. 63
4.10.3 SwapFunction3 ............................. 63
4.10.4 SwapFunction4 ............................. 63
4.10.5 SwapFunction5 ............................. 63
5 Writing and Testing Programs 65
5.1 DistinctArrayElements ............................ 65
5.1.1 main Function .............................. 66
5.1.2 areDistinct Function.......................... 67
5.1.3 Compiling and Linking . . . . . . . . . . . . . . . . . . . . . . . . . . 68
5.1.4 make .................................... 69
5.2 Test Using Makefile .............................. 71
5.2.1 GeneratingTestCases.......................... 72
5.2.2 RedirectingOutput ........................... 72
5.2.3 Use diff toCompareOutput...................... 73
5.2.4 Adding Tests to Makefile ........................ 73
5.3 Invalid Memory Access . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
5.4 Using valgrind to Check Memory Access Errors . . . . . . . . . . . . . . . 77
5.5 TestCoverage .................................. 79
5.6 LimitCoreSize ................................. 82
5.7 Programs with Infinite Loops . . . . . . . . . . . . . . . . . . . . . . . . . . 83
Contents vii
6Strings 85
6.1 ArrayofCharacters ............................... 85
6.2 StringFunctionsinC .............................. 88
6.2.1 Copy: strcpy ............................... 88
6.2.2 Compare: strcmp ............................. 89
6.2.3 Finding Substrings: strstr ....................... 90
6.2.4 Finding Characters: strchr ....................... 90
6.3 Understanding argv ............................... 91
6.4 Counting Substrings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
7 Programming Problems and Debugging 97
7.1 ImplementingStringFunctions ......................... 97
7.1.1 TheCLibrary .............................. 97
7.1.2 HeaderFile ................................ 98
7.1.3 mystring.h ................................ 99
7.1.4 Creating Inputs and Correct Outputs . . . . . . . . . . . . . . . . . 100
7.1.5 Makefile ................................. 104
7.1.6 mystring.c ................................ 105
7.1.7 Using const ................................ 106
7.2 Debugging .................................... 108
7.2.1 Find Infinite Loops . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
7.2.2 FindInvalidMemoryAccesses ..................... 109
7.2.3 DetectInvalidMemoryAccesses .................... 111
8 Heap Memory 113
8.1 Creating Array with malloc .......................... 113
8.2 TheStackandtheHeap ............................ 115
8.3 FunctionsthatReturnaHeapAddress .................... 118
8.4 Two-DimensionalArraysinC ......................... 119
8.5 PointersandArguments............................. 122
9 Programming Problems Using Heap Memory 125
9.1 SortinganArray ................................. 125
9.1.1 Generating Test Input and Expected Output . . . . . . . . . . . . . 125
9.1.2 Redirecting Input . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
9.1.3 SortingIntegers.............................. 129
9.1.4 Using valgrind toDetectMemoryLeaks ............... 132
9.2 Sort Using qsort ................................ 133
9.2.1 qsort ................................... 133
9.2.2 TheComparisonFunction........................ 135
9.2.3 ExecutionExamples ........................... 137
9.2.4 SortingStrings .............................. 138
10 Reading and Writing Files 141
10.1 Passing a File Name via argv ......................... 141
10.2ReadingfromFiles ............................... 142
10.2.1 Reading Characters: fgetc ....................... 142
10.2.2 Reading Integers: fscanf(... %d...) ................. 145
10.3WritingtoFiles ................................. 147
10.4ReadingandWritingStrings .......................... 150
viii Contents
11 Programming Problems Using File 153
11.1SortingaFileofIntegers ............................ 153
11.2CountingtheOccurrencesofCharacters .................... 155
11.3CountingtheOccurrencesofaWord...................... 158
11.4HowtoCommentCode ............................. 160
II Recursion 163
12 Recursion 165
12.1SelectingBallswithRestrictions ........................ 166
12.1.1 BallsofTwoColors ........................... 166
12.1.2 BallsofThreeColors........................... 167
12.1.3 AFurtherRestriction .......................... 168
12.2One-WayStreets ................................. 170
12.3TheTowerofHanoi ............................... 171
12.4CalculatingIntegerPartitions ......................... 174
12.4.1 Count the Number of “1”s . . . . . . . . . . . . . . . . . . . . . . . . 175
12.4.2 OddNumbersOnly ........................... 177
12.4.3 IncreasingValues............................. 178
12.4.4 AlternatingOddandEvenNumbers.................. 179
12.4.5 Generalizing the Integer Partition Problem . . . . . . . . . . . . . . 180
12.4.6 HowNottoSolvetheIntegerPartitionProblem ........... 181
13 Recursive C Functions 183
13.1SelectBallswithRestrictions .......................... 184
13.2One-WayStreets ................................. 187
13.3TheTowerofHanoi ............................... 188
13.4IntegerPartition ................................. 190
13.5Factorial ..................................... 191
13.6FibonacciNumbers ............................... 193
13.7 Performance Profiling with gprof ....................... 199
14 Integer Partition 201
14.1StackandHeapMemory ............................ 202
14.2TraceRecursiveFunctionCalls ......................... 210
14.3GeneratingPartitionswithRestrictions .................... 213
14.3.1 UsingOddNumbersOnly........................ 214
14.3.2 Using Sequences of IncreasingNumbers ................ 215
14.3.3 UsingAlternatingOddandEvenNumbers .............. 215
14.3.4 Using gprof and gcov to Identify Performance Bottlenecks . . . . . 216
15 Programming Problems Using Recursion 223
15.1BinarySearch .................................. 223
15.2QuickSort .................................... 226
15.3PermutationsandCombinations ........................ 232
15.4StackSort .................................... 236
15.4.1 Example1................................. 236
15.4.2 Example2................................. 237
15.4.3 Example3................................. 237
15.4.4 Example4................................. 238
15.4.5 StackSortable .............................. 238
Contents ix
15.5TracingaRecursiveFunction .......................... 242
15.6ARecursiveFunctionwithaMistake ..................... 244
III Structure 247
16 Programmer-Defined Data Types 249
16.1 Struct andObject ............................... 250
16.2PassingObjectsasArguments ......................... 253
16.3ObjectsandPointers .............................. 256
16.3.1 ReturninganObject........................... 258
16.3.2 Objects and malloc ........................... 258
16.4ConstructorsandDestructors.......................... 261
16.5StructureswithinStructures .......................... 268
16.6BinaryFilesandObjects ............................ 270
17 Programming Problems Using Structure 275
17.1SortingaPersonDatabase ........................... 275
17.2PackingDecimalDigits ............................. 281
17.2.1 NumberSystems ............................. 281
17.2.2 PackingTwoDecimalDigitsintoOneByte .............. 282
17.2.3 BitOperations .............................. 283
17.2.4 InsertingandRetrievingDecimalDigits ................ 285
17.2.5 DecPackProgram ............................ 286
17.3BinaryFileandPointer ............................. 290
18 Linked Lists 293
18.1ExpandableTypes ................................ 293
18.2LinkedLists ................................... 294
18.3InsertingData .................................. 295
18.4SearchingaLinkedList ............................. 297
18.5DeletingfromaLinkedList ........................... 298
18.6PrintingaLinkedList .............................. 302
18.7DestroyingaLinkedList ............................ 303
19 Programming Problems Using Linked List 307
19.1Queues ...................................... 307
19.2SortingNumbers ................................. 308
19.3SparseArrays .................................. 308
19.4ReversingaLinkedList ............................. 314
20 Binary Search Trees 317
20.1BinarySearchTree ............................... 318
20.2InsertingDataintoaBinarySearchTree ................... 319
20.3SearchingaBinarySearchTree ........................ 323
20.4PrintingaBinaryTree ............................. 325
20.5DeletingfromaBinarySearchTree ...................... 327
20.6DestroyingaBinarySearchTree ........................ 330
20.7 main ....................................... 331
20.8 Makefile ..................................... 332
20.9CountingtheDifferentShapesofaBinaryTree ............... 332