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
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.