Data Structures and Other Objects Using C++ (4th Edition)

Cover......Page 1
CONTENTS......Page 16
CHAPTER 1 THE PHASES OF SOFTWARE DEVELOPMENT......Page 32
 1.1 Specification, Design, Implementation......Page 34
  Design Concept: Decomposing the Problem......Page 35
  Preconditions and Postconditions......Page 37
  Implementation Issues for the ANSI/ISO C++ Standard......Page 39
  C++ Feature: The Standard Library and the Standard Namespace......Page 40
  Programming Tip: Use Declared Constants......Page 42
  Programming Tip: Use Assert to Check a Precondition......Page 43
  Self-Test Exercises for Section 1.1......Page 45
  The Stair-Counting Problem......Page 46
  Big-O Notation......Page 52
  Time Analysis of C++ Functions......Page 54
  Self-Test Exercises for Section 1.2......Page 56
  Choosing Test Data......Page 57
  Boundary Values......Page 58
  Programming Tip: How to Debug......Page 59
  Self-Test Exercises for Section 1.3......Page 60
 Chapter Summary......Page 61
 Solutions to Self-Test Exercises......Page 62
CHAPTER 2 ABSTRACT DATA TYPES AND C++ CLASSES......Page 64
  Programming Example: The Throttle Class......Page 65
  Clarifying the Const Keyword Part 2: Constant Member Functions......Page 69
  Using a Class......Page 70
  A Small Demonstration Program for the Throttle Class......Page 71
  Implementing Member Functions......Page 73
  Programming Tip: Style for Boolean Variables......Page 75
 2.2 Constructors......Page 76
  The Throttle’s Constructor......Page 77
  Inline Member Functions......Page 80
  Programming Tip: When to Use an Inline Member Function......Page 81
  Creating a Namespace......Page 82
  The Header File......Page 83
  Describing the Value Semantics of a Class Within the Header File......Page 87
  The Implementation File......Page 88
  Using the Items in a Namespace......Page 90
  Pitfall: Never Put a Using Statement Actually in a Header File......Page 91
  Self-Test Exercises for Section 2.3......Page 93
  Programming Example: The Point Class......Page 94
  Default Arguments......Page 96
  Programming Tip: A Default Constructor Can Be Provided by Using Default Arguments......Page 97
  Parameters......Page 98
  Pitfall: Using a Wrong Argument Type for a Reference Parameter......Page 101
  Clarifying the Const Keyword Part 3: Const Reference Parameters......Page 103
  When the Type of a Function’s Return Value Is a Class......Page 104
 2.5 Operator Overloading......Page 105
  Overloading Binary Comparison Operators......Page 106
  Overloading Binary Arithmetic Operators......Page 107
  Overloading Output and Input Operators......Page 108
  Friend Functions......Page 111
  Programming Tip: When to Use a Friend Function......Page 112
  The Point Class—Putting Things Together......Page 113
  Self-Test Exercises for Section 2.5......Page 116
 2.6 The Standard Template Libary and the Pair Class......Page 117
 Chapter Summary......Page 118
 Solutions to Self-Test Exercises......Page 119
 Programming Projects......Page 121
CHAPTER 3 CONTAINER CLASSES......Page 127
 3.1 The Bag Class......Page 128
  The Bag Class—Specification......Page 129
  C++ Feature: Typedef Statements Within a Class Definition......Page 130
  C++ Feature: The std::size_t Data Type......Page 131
  Clarifying the Const Keyword Part 4: Static Member Constants......Page 135
  The Bag Class—Documentation......Page 136
  The Bag Class—Demonstration Program......Page 138
  The Bag Class—Design......Page 140
  The Invariant of a Class......Page 141
  The Bag Class—Implementation......Page 142
  Programming Tip: Make Assertions Meaningful......Page 143
  C++ Feature: The Copy Function from the C++ Standard Library......Page 147
  Programming Tip: Document the Class Invariant in the Implementation File......Page 148
  Pitfall: An Object Can Be an Argument to Its Own Member Function......Page 152
  The Bag Class—Analysis......Page 153
  Self-Test Exercises for Section 3.1......Page 154
  The Sequence Class—Specification......Page 155
  The Sequence Class—Design......Page 158
  The Sequence Class—Pseudocode for the Implementation......Page 161
  Self-Test Exercises for Section 3.2......Page 163
 3.3 Interactive Test Programs......Page 164
  C++ Feature: Converting Input to Uppercase Letters......Page 165
  Self-Test Exercises for Section 3.3......Page 169
  The Multiset Template Class......Page 170
  Iterators and the [...) Pattern......Page 171
  Pitfall: Do Not Access an Iterator’s Item After Reaching end( )......Page 173
  Other Multiset Operations......Page 174
  Pitfall: Changing a Container Object Can Invalidate Its Iterators......Page 175
  Self-Test Exercises for Section 3.4......Page 176
 Solutions to Self-Test Exercises......Page 177
 Programming Projects......Page 180
CHAPTER 4 POINTERS AND DYNAMIC ARRAYS......Page 185
 4.1 Pointers and Dynamic Memory......Page 186
  Pointer Variables......Page 187
  Using the Assignment Operator with Pointers......Page 189
  Dynamic Variables and the new Operator......Page 190
  Using new to Allocate Dynamic Arrays......Page 191
  The delete Operator......Page 194
  Programming Tip: Define Pointer Types......Page 195
  Self-Test Exercises for Section 4.1......Page 196
 4.2 Pointers and Arrays as Parameters......Page 197
  Clarifying the Const Keyword Part 6: Const Parameters That Are Pointers or Arrays......Page 202
  Self-Test Exercises for Section 4.2......Page 204
  Pointer Member Variables......Page 207
  Member Functions Allocate Dynamic Memory as Needed......Page 208
  Value Semantics......Page 212
  The Destructor......Page 215
  The Revised Bag Class—Class Definition......Page 216
  The Revised Bag Class—Implementation......Page 218
  Programming Tip: How to Check for Self-Assignment......Page 219
  Programming Tip: How to Allocate Memory in a Member Function......Page 222
  The Revised Bag Class—Putting the Pieces Together......Page 223
  Self-Test Exercises for Section 4.3......Page 225
  Special Importance of the Copy Constructor......Page 226
  Pitfall: Using Dynamic Memory Requires a Destructor, a Copy Constructor, and an Overloaded Assignment Operator......Page 227
  Null-Terminated Strings......Page 228
  The Empty String......Page 229
  The strcpy Function......Page 230
  Pitfall: Dangers of strcpy, strcat, and Reading Strings......Page 231
  The String Class—Specification......Page 232
  Constructor for the String Class......Page 234
  Some Further Overloading......Page 235
  The String Class—Design......Page 236
  The String Class—Implementation......Page 237
  Demonstration Program for the String Class......Page 239
  Constructor-Generated Conversions......Page 241
  Self-Test Exercises for Section 4.5......Page 242
 4.6 Programming Project: The Polynomial......Page 243
 Solutions to Self-Test Exercises......Page 247
 Programming Projects......Page 249
CHAPTER 5 LINKED LISTS......Page 251
  Declaring a Class for Nodes......Page 252
  Using a Typedef Statement with Linked-List Nodes......Page 253
  Head Pointers, Tail Pointers......Page 254
  The Node Constructor......Page 255
  The Node Member Functions......Page 256
  The Member Selection Operator......Page 257
  Clarifying the Const Keyword Part 7: The Const Keyword with a Pointer to a Node, and the Need for Two Versions of Some Member Functions......Page 258
  Programming Tip: A Rule for a Node’s Constant Member Functions......Page 259
  Self-Test Exercises for Section 5.1......Page 261
 5.2 A Linked-List Toolkit......Page 262
  Computing the Length of a Linked List......Page 263
  Programming Tip: How to Traverse a Linked List......Page 266
  Parameters for Linked Lists......Page 267
  Inserting a New Node at the Head of a Linked List......Page 269
  Inserting a New Node That Is Not at the Head......Page 271
  Pitfall: Unintended Calls to delete and new......Page 274
  Searching for an Item in a Linked List......Page 276
  Finding a Node by Its Position in a Linked List......Page 277
  Copying a Linked List......Page 278
  Removing a Node at the Head of a Linked List......Page 281
  Removing a Node That Is Not at the Head......Page 282
  Clearing a Linked List......Page 283
  Linked-List Toolkit—Putting the Pieces Together......Page 284
  Using the Linked-List Toolkit......Page 285
  Self-Test Exercises for Section 5.2......Page 289
  Our Third Bag—Class Definition......Page 290
  How to Make the Bag value_type Match the Node value_type......Page 291
  Following the Rules for Dynamic Memory Usage in a Class......Page 294
  The Third Bag Class—Implementation......Page 295
  Pitfall: The Assignment Operator Causes Trouble with Linked Lists......Page 296
  Programming Tip: How to Choose Between Approaches......Page 298
  The Third Bag Class—Putting the Pieces Together......Page 302
  Self-Test Exercises for Section 5.3......Page 303
  The Revised Sequence Class—Design Suggestions......Page 306
  The Revised Sequence Class—Value Semantics......Page 307
 5.5 Dynamic Arrays vs. Linked Lists vs. Doubly Linked Lists......Page 308
  Self-Test Exercises for Section 5.5......Page 310
 5.6 STL Vectors vs. STL Lists vs. STL Deques......Page 311
  Self-Test Exercises for Section 5.6......Page 313
 Solutions to Self-Test Exercises......Page 314
 Programming Projects......Page 318
CHAPTER 6 SOFTWARE DEVELOPMENT WITH TEMPLATES, ITERATORS, AND THE STL......Page 321
 6.1 Template Functions......Page 322
  Programming Tip: Capitalize the Name of a Template Parameter......Page 324
  Pitfall: Failed Unification Errors......Page 325
  Parameter Matching for Template Functions......Page 327
  A Template Function to Find the Biggest Item in an Array......Page 328
  A Template Function to Insert an Item into a Sorted Array......Page 330
  Syntax for a Template Class......Page 332
  Programming Tip: Use the Name Item and the typename Keyword......Page 334
  More About the Template Implementation File......Page 335
  Using the Template Class......Page 340
  Self-Test Exercises for Section 6.2......Page 343
  STL Algorithms......Page 344
  Standard Categories of Iterators......Page 345
  Iterators for Arrays......Page 347
 6.4 The Node Template Class......Page 348
  Functions That Return a Reference Type......Page 349
  The Data Member Function Now Requires Two Versions......Page 351
  Self-Test Exercises for Section 6.4......Page 352
  The Node Iterator......Page 359
  The Node Iterator Is Derived from std::iterator......Page 361
  Node Iterator—the * Operator......Page 362
  Node Iterator—Two Versions of the ++ Operator......Page 363
  Iterators for Constant Collections......Page 365
  Self-Test Exercises for Section 6.5......Page 367
  How to Provide an Iterator for a Container Class That You Write......Page 368
  The Bag Iterator......Page 369
  Self-Test Exercises for Section 6.6......Page 370
 Chapter Summary and Summary of the Five Bags......Page 378
 Solutions to Self-Test Exercises......Page 379
 Programming Projects......Page 381
CHAPTER 7 STACKS......Page 383
 7.1 The STL Stack Class......Page 384
  The Standard Library Stack Class......Page 385
  Programming Example: Reversing a Word......Page 386
  Self-Test Exercises for Section 7.1......Page 387
  Programming Example: Balanced Parentheses......Page 388
  Evaluating Arithmetic Expressions—Specification......Page 390
  Evaluating Arithmetic Expressions—Design......Page 391
  Evaluating Arithmetic Expressions—Implementation......Page 397
  Evaluating Arithmetic Expressions—Testing and Analysis......Page 398
  Self-Test Exercises for Section 7.2......Page 399
  Array Implementation of a Stack......Page 400
  Linked-List Implementation of a Stack......Page 404
  Self-Test Exercises for Section 7.3......Page 405
  Evaluating Postfix Expressions......Page 408
  Translating Infix to Postfix Notation......Page 410
  Using Precedence Rules in the Infix Expression......Page 412
  Correctness of the Conversion from Infix to Postfix......Page 414
 Solutions to Self-Test Exercises......Page 418
 Programming Projects......Page 420
CHAPTER 8 QUEUES......Page 424
 8.1 The STL Queue......Page 425
  Uses for Queues......Page 426
  Self-Test Exercises for Section 8.1......Page 428
  Programming Example: Recognizing Palindromes......Page 429
  Self-Test Exercises for Middle of Section 8.2......Page 431
  Car Wash Simulation—Specification......Page 432
  Car Wash Simulation—Design......Page 433
  Car Wash Simulation—Implementing the Car Wash Classes......Page 436
  Car Wash Simulation—Implementing the Simulation Function......Page 441
  Self-Test Exercises for End of Section 8.2......Page 442
  Array Implementation of a Queue......Page 444
  Programming Tip: Use Small Helper Functions to Improve Clarity......Page 447
  Discussion of the Circular Array Implementation of a Queue......Page 449
  Linked-List Implementation of a Queue......Page 451
  Implementation Details......Page 452
  Pitfall: Which End Is Which......Page 454
 8.4 Implementing the STL Deque Class......Page 457
  Calling the Destructor and Constructor for the Deque’s value_type Items......Page 460
 Chapter Summary......Page 461
 Solutions to Self-Test Exercises......Page 463
 Programming Projects......Page 464
CHAPTER 9 RECURSIVE THINKING......Page 467
  A First Example of Recursive Thinking......Page 468
  Tracing Recursive Calls......Page 470
  Programming Example: An Extension of write_vertical......Page 472
  A Closer Look at Recursion......Page 473
  General Form of a Successful Recursive Function......Page 476
  Self-Test Exercises for Section 9.1......Page 477
  Programming Example: Generating Random Fractals......Page 478
  A Function for Generating Random Fractals—Specification......Page 479
  Design and Implementation of the Fractal Function......Page 481
  How the Random Fractals Are Displayed......Page 482
  Traversing a Maze—Specification......Page 484
  Traversing a Maze—Design......Page 486
  Traversing a Maze—Implementation......Page 487
  The Recursive Pattern of Exhaustive Search with Backtracking......Page 489
  Pitfall: Forgetting to Use the Return Value from a Recursive Call......Page 490
  Self-Test Exercises for Section 9.2......Page 491
 9.3 Reasoning About Recursion......Page 492
  How to Ensure That There Is No Infinite Recursion......Page 494
  Inductive Reasoning About the Correctness of a Recursive Function......Page 497
  Self-Test Exercises for Section 9.3......Page 498
 Solutions to Self-Test Exercises......Page 499
 Programming Projects......Page 501
CHAPTER 10 TREES......Page 505
  Binary Trees......Page 506
  Binary Taxonomy Trees......Page 509
  General Trees......Page 510
  Array Representation of Complete Binary Trees......Page 511
  Representing a Binary Tree with a Class for Nodes......Page 514
 10.3 Binary Tree Nodes......Page 516
  Pitfall: Not Connecting All the Links......Page 519
  Programming Example: Animal Guessing......Page 520
  Animal Guessing Program—Design and Implementation......Page 522
  Animal Guessing Program—Improvements......Page 527
  Traversals of Binary Trees......Page 531
  Printing the Data from a Tree’s Node......Page 536
  The Problem with Our Traversals......Page 537
  A Parameter Can Be a Function......Page 538
  A Template Version of the Apply Function......Page 540
  More Generality for the Apply Template Function......Page 541
  Template Functions for Tree Traversals......Page 542
  Self-Test Exercises for Section 10.4......Page 543
  The Binary Search Tree Storage Rules......Page 549
  Our Sixth Bag—Implementation of Some Simple Functions......Page 553
  Counting the Occurrences of an Item in a Binary Search Tree......Page 554
  Inserting a New Item into a Binary Search Tree......Page 555
  Removing an Item from a Binary Search Tree......Page 556
  The Union Operators for Binary Search Trees......Page 560
 Chapter Summary......Page 562
 Solutions to Self-Test Exercises......Page 563
 Programming Projects......Page 565
CHAPTER 11 BALANCED TREES......Page 570
  The Heap Storage Rules......Page 571
  The Priority Queue ADT with Heaps......Page 572
  Adding an Entry to a Heap......Page 573
  Removing an Entry from a Heap......Page 574
 11.2 The STL Priority Queue and Heap Algorithms......Page 577
  The Problem of Unbalanced Trees......Page 578
  The B-Tree Rules......Page 579
  An Example B-Tree......Page 580
  The Set ADT with B-Trees......Page 581
  Searching for an Item in a B-Tree......Page 586
  The Loose Insertion into a B-Tree......Page 588
  A Private Member Function to Fix an Excess in a Child......Page 591
  Back to the Insert Member Function......Page 592
  Removing an Item from a B-Tree......Page 594
  The Loose Erase from a B-Tree......Page 595
  A Private Member Function to Fix a Shortage in a Child......Page 597
  Programming Tip: Write and Test Small Pieces......Page 600
  External B-Trees......Page 601
  Self-Test Exercises for Section 11.2......Page 602
 11.4 Trees, Logs, and Time Analysis......Page 603
  Time Analysis for Heaps......Page 604
  Logarithms......Page 606
  Logarithmic Algorithms......Page 607
 11.5 The STL Map and Multimap Classes......Page 608
  Map and Multimap Implementations......Page 609
 Solutions to Self-Test Exercises......Page 610
 Programming Projects......Page 613
CHAPTER 12 SEARCHING......Page 614
  Serial Search—Analysis......Page 615
  Binary Search......Page 617
  Binary Search—Design......Page 618
  Pitfall: Common Indexing Errors in Binary Search Implementations......Page 620
  Binary Search—Analysis......Page 621
  Functions for Sorted Ranges......Page 625
  The STL search Function......Page 627
  Introduction to Hashing......Page 629
  The Table Class—Specification......Page 632
  The Table Class—Design......Page 634
  The Table ADT—Implementation......Page 637
  Choosing a Hash Function to Reduce Collisions......Page 643
  Double Hashing to Reduce Clustering......Page 644
  Self-Test Exercises for Section 12.2......Page 645
 12.3 Chained Hashing......Page 646
  The Load Factor of a Hash Table......Page 648
  A New Table Class......Page 651
  Template Parameters That Are Functions......Page 652
  Implementing the New Table Class......Page 653
  Self-Test Exercises for Section 12.5......Page 654
 Chapter Summary......Page 655
 Solutions to Self-Test Exercises......Page 656
 Programming Projects......Page 659
CHAPTER 13 SORTING......Page 660
  Selectionsort—Design......Page 661
  Selectionsort—Implementation......Page 663
  Selectionsort—Analysis......Page 665
  Insertionsort......Page 667
  Insertionsort—Analysis......Page 671
  Divide-and-Conquer Using Recursion......Page 673
  C++ Feature: Specifying a Subarray with Pointer Arithmetic......Page 674
  Mergesort......Page 676
  The merge Function......Page 677
  Mergesort—Analysis......Page 682
  Quicksort......Page 684
  The partition Function......Page 686
  Quicksort—Analysis......Page 690
  Self-Test Exercises for Section 13.2......Page 692
  Heapsort......Page 693
  Making the Heap......Page 698
  Reheapification Downward......Page 701
  Heapsort—Analysis......Page 702
  The Original C qsort Function......Page 703
  The STL sort Function......Page 704
  Binary Search Functions in the STL......Page 705
  The Comparison Parameter for STL Sorting Functions......Page 706
  Writing Your Own sort Function That Uses Iterators......Page 707
 Chapter Summary......Page 708
 Solutions to Self-Test Exercises......Page 709
 Programming Projects......Page 710
CHAPTER 14 DERIVED CLASSES AND INHERITANCE......Page 714
 14.1 Derived Classes......Page 715
  How to Declare a Derived Class......Page 717
  The Automatic Constructors of a Derived Class......Page 718
  Using a Derived Class......Page 719
  The Automatic Destructor of a Derived Class......Page 721
  Overriding Inherited Member Functions......Page 722
 14.2 Simulation of an Ecosystem......Page 723
  The organism Class......Page 724
  How to Provide a New Constructor for a Derived Class......Page 727
  The Other Animal Member Functions......Page 729
  Self-Test Exercises for Middle of Section 14.2......Page 733
  The herbivore Class......Page 734
  The Pond Life Simulation Program......Page 736
  Using the Pond Model......Page 741
  Dynamic Memory Usage......Page 742
  Introduction to the Game Class......Page 743
  Virtual Member Functions......Page 747
  The Protected Virtual Member Functions of the Game Class......Page 749
  The Private Member Variables of the Connect Four Class......Page 750
  Three Connect Four Functions That Deal with the Game’s Status......Page 752
  Three Connect Four Functions That Deal with Moves......Page 753
  The clone Function......Page 754
  The Game Class’s Play Algorithm with Minimax......Page 755
  Self-Test Exercises for Section 14.3......Page 757
 Solutions to Self-Test Exercises......Page 759
 Programming Projects......Page 761
CHAPTER 15 GRAPHS......Page 763
  Undirected Graphs......Page 764
  Programming Example: Undirected State Graphs......Page 765
  Directed Graphs......Page 768
  More Graph Terminology......Page 769
  Self-Test Exercises for Section 15.1......Page 770
  Representing Graphs with an Adjacency Matrix......Page 771
  Representing Graphs with Edge Lists......Page 772
  Representing Graphs with Edge Sets......Page 773
  Programming Example: Labeled Graph Class......Page 774
  Member Functions to Add Vertices and Edges......Page 775
  Labeled Graph Class—Overloading the Subscript Operator......Page 776
  A Const Version of the Subscript Operator......Page 777
  Labeled Graph Class—Implementation......Page 778
  Self-Test Exercises for Section 15.2......Page 779
 15.3 Graph Traversals......Page 784
  Depth-First Search......Page 785
  Breadth-First Search......Page 788
  Depth-First Search—Implementation......Page 790
  Self-Test Exercises for Section 15.3......Page 792
  Determining Whether a Path Exists......Page 794
  Graphs with Weighted Edges......Page 795
  Shortest-Distance Algorithm......Page 796
  Shortest-Path Algorithm......Page 806
  Self-Test Exercises for Section 15.4......Page 807
 Solutions to Self-Test Exercises......Page 808
 Programming Projects......Page 809
 A. ASCII CHARACTER SET......Page 812
 B. FURTHER BIG-O NOTATION......Page 813
 C. PRECEDENCE OF OPERATORS......Page 815
 F. INPUT AND OUTPUT IN C++......Page 816
 G. SELECTED LIBRARY FUNCTIONS......Page 824
 H. BRIEF REFERENCE FOR THE STANDARD TEMPLATE CLASSES......Page 826
 I. A TOOLKIT OF USEFUL FUNCTIONS......Page 834
 J. FUNDAMENTAL STYLE GUIDE......Page 837
 L. EXCEPTION HANDLING......Page 838
 B......Page 842
 D......Page 843
 G......Page 844
 L......Page 845
 P......Page 846
 S......Page 847
 U......Page 848
 W......Page 849