C++ PLUS DATA STRUCTURES
1 SOFTWARE ENGINEERING PRINCIPLES 1 1 1 THE SOFTWARE PROCESS 2 1 2 PROGRAM DESIGN 9 1 3 VERIFICATION OF SOFTWARE CORRECTNESS 19 CASE STUDY FRACTION CLASS 50 SUMMARY 58 EXERCISES 60 2 DATA DESIGN AND IMPLEMENTATION 63 2 1 DIFFERENT VIEWS OF DATA 64 2 2 ABSTRACTION AND BUILT IN TYPES 72 2 3 HIGHER LEVEL ABSTRACTION AND THE C CLASS TYPE 85 2 4 OBJECT ORIENTED PROGRAMMING 91 2 5 CONSTRUCTS FOR PROGRAM VERIFICATION 95 CASE STUDY USER DEFINED STRING I O CLASS 100 SUMMARY 116 EXERCISES 117 CONTENTS 3 ADTS UNSORTED LIST AND SORTED LIST 123 3 1 LISTS 124 3 2 ABSTRACT DATA TYPE UNSORTED LIST 125 3 3 ABSTRACT DATA TYPE SORTED LIST 146 3 4 COMPARISON OF ALGORITHMS 157 3 5 COMPARISON OF UNSORTED AND SORTED LIST ADT ALGORITHMS 164 3 6 OVERLOADING OPERATORS 167 3 7 OBJECT ORIENTED DESIGN METHODOLOGY 170 CASE STUDY REAL ESTATE LISTINGS AN OBJECT ORIENTED DESIGN 173 SUMMARY 188 EXERCISES 189 4 ADTS STACK AND QUEUE 195 4 1 STACKS 196 4 2 MORE ABOUT GENERICS C TEMPLATES 210 4 3 POINTER TYPES 214 4 4 DYNAMICALLY ALLOCATED ARRAYS 222 CASE STUDY SIMULATION 245 SUMMARY 261 EXERCISES 262 5 LINKED STRUCTURES 279 5 1 IMPLEMENTING A STACK AS A LINKED STRUCTURE 280 5 2 IMPLEMENTING A QUEUE AS A LINKED STRUCTURE 296 5 3 IMPLEMENTING THE UNSORTED LIST AS A LINKED STRUCTURE 307 5 4 IMPLEMENTING THE SORTED LIST AS A LINKED STRUCTURE 318 SUMMARY 327 EXERCISES 327 6 LISTS PLUS 333 6 1 CIRCULAR LINKED LISTS 334 6 2 DOUBLY LINKED LISTS 344 6 3 LINKED LISTS WITH HEADERS AND TRAILERS 348 6 4 COPY STRUCTURES 350 6 5 A LINKED LIST AS AN ARRAY OF RECORDS 358 6 6 POLYMORPHISM WITH VIRTUAL FUNCTIONS 368 6 7 A SPECIALIZED LIST ADT 373 CASE STUDY IMPLEMENTING A LARGE INTEGER ADT 379 SUMMARY 392 EXERCISES 392 7 PROGRAMMING WITH RECURSION 399 7 1 WHAT IS RECURSION 400 7 2 THE CLASSIC EXAMPLE OF RECURSION 401 7 3 PROGRAMMING RECURSIVELY 404 7 4 VERIFYING RECURSIVE FUNCTIONS 407 7 5 WRITING RECURSIVE FUNCTIONS 408 7 6 USING RECURSION TO SIMPLIFY SOLUTIONS 411 7 7 RECURSIVE LINKED LIST PROCESSING 412 7 8 A RECURSIVE VERSION OF BINARY SEARCH 416 7 9 RECURSIVE VERSIONS OF INSERTITEM AND DELETEITEM 418 7 10 HOW RECURSION WORKS 420 7 11 TRACING THE EXECUTION OF RECURSIVE FUNCTION INSERT 429 7 12 DEBUGGING RECURSIVE ROUTINES 432 7 13 REMOVING RECURSION 432 7 14 DECIDING WHETHER TO USE A RECURSIVE SOLUTION 436 CASE STUDY QUICKSORT 438 SUMMARY 446 EXERCISES 447 AFTER STUDYING THIS CHAPTER YOU SHOULD BE ABLE TO DESCRIBE THE GENERAL ACTIVITIES IN THE SOFTWARE LIFE CYCLE DESCRIBE THE GOALS FOR QUALITY SOFTWARE EXPLAIN THE FOLLOWING TERMS SOFTWARE REQUIREMENTS SOFTWARE SPECIFICA TIONS ALGORITHM INFORMATION HIDING ABSTRACTION STEPWISE REFINEMENT EXPLAIN AND APPLY THE FUNDAMENTAL IDEAS OF TOP DOWN DESIGN EXPLAIN AND APPLY THE FUNDAMENTAL IDEAS OF OBJECT ORIENTED DESIGN IDENTIFY SEVERAL SOURCES OF PROGRAM ERRORS DESCRIBE STRATEGIES TO AVOID SOFTWARE ERRORS SPECIFY THE PRECONDITIONS AND POSTCONDITIONS OF A PROGRAM SEGMENT OR FUNCTION SHOW HOW DESKCHECKING CODE WALK THROUGHS AND DESIGN AND CODE INSPECTIONS CAN IMPROVE SOFTWARE QUALITY AND REDUCE THE SOFTWARE DEVELOPMENT EFFORT EXPLAIN THE FOLLOWING TERMS ACCEPTANCE TESTS REGRESSION TESTING VERIFICATION VALIDATION FUNCTIONAL DOMAIN BLACK BOX TESTING WHITE BOX TESTING STATE SEVERAL TESTING GOALS AND INDICATE WHEN EACH WOULD BE APPROPRIATE DESCRIBE SEVERAL INTEGRATION TESTING STRATEGIES AND INDICATE WHEN EACH WOULD BE APPROPRIATE EXPLAIN HOW PROGRAM VERIFICATION TECHNIQUES CAN BE APPLIED THROUGHOUT THE SOFTWARE DEVELOPMENT PROCESS CREATE A C TEST DRIVER PROGRAM TO TEST A SIMPLE CLASS GOALS SOFTWARE ENGINEERING PRINCIPLES 1