An edition of Data structures & other objects using C++ (2001)

Data structures & other objects using C++

2nd ed.

by

  • 2 Want to read
  • 1 Have read
Cover of: Data structures & other objects using C++ by M. Main, M. Main
Preview Only

My Reading Lists:

Create a new list
Notes
  • 2 Want to read
  • 1 Have read
Notes

Check nearby libraries

Buy this book

Last edited by MARC Bot
October 13, 2025 | History
Edit
An edition of Data structures & other objects using C++ (2001)

Data structures & other objects using C++

2nd ed.

by

  • 2 Want to read
  • 1 Have read

"The second edition continues to provided students with the fundamentals of data structures. It also teaches how to use the C++ Standard Library container classes through: revised interfaces for the principal example classes, which are compliant with the ANSI/ISO C++ Standard Library classes; optional material on Standard Library iterators; thorough coverage of the role of the const keyword in the C++ Standard Library; coverage of new C++ features such as namespaces, static member constants, and the typename keyword; extended coverage of inheritance; and extensive pedagogical features such as programming tips and pitfalls, exercises, and new programming projects."--Jacket.

Publish Date
Publisher
Addison Wesley Longman
Language
English
Pages
783

Check nearby libraries

Buy this book

Previews available in: English

Subjects

C++ (Computer program language), Data structures (Computer science), Object-oriented programming (Computer science), C plus plus (computer program language), C++ (Langage de programmation), Structures de données (Informatique), Programmation orientée objet (Informatique)
Edition Availability
Cover of: Data structures & other objects using C++
Data structures & other objects using C++
2001, Addison Wesley Longman
in English - 2nd ed.

Add another edition?

Book Details

Table of Contents

1. The Phases of Software Development
Page 1
1.1. Specification, Design, Implementation
Page 3
Design Technique: Decomposing the Problem
Page 4
Preconditions and Postconditions
Page 5
Using Functions Provided by Other Programmers
Page 8
Implementation Issues for the ANSI/ISO C++ Standard
Page 10
C++ Feature: The Standard Library and the Standard Namespace
Page 10
Programming Tip: Use Declared Constants
Page 11
Programming Tip: Use Assert to Check a Precondition
Page 12
Programming Tip: Use EXIT_SUCCESS in a Main Program
Page 13
Self-Test Exercises
Page 13
1.2. Running Time Analysis
Page 14
The Stair-Counting Problem
Page 14
Big-O Notation
Page 19
Time Analysis of C++ Functions
Page 22
Worst-Case, Average-Case, and Best-Case Analyses
Page 24
Self-Test Exercises
Page 24
1.3. Testing and Debugging
Page 24
Choosing Test Data
Page 25
Boundary Values
Page 25
Fully Exercising Code
Page 26
Debugging
Page 26
Programming Tip: How to Debug
Page 27
Self-Test Exercises
Page 27
Chapter Summary
Page 28
Solutions to Self-Test Exercises
Page 29
2. Abstract Data Types and C++ Classes
Page 30
2.1. Classes and Members
Page 31
The Throttle Class
Page 31
Using a Class
Page 36
A Small Demonstration Program for the Throttle Class
Page 37
Implementing Member Functions
Page 39
Member Functions May Activate Other Members
Page 41
Programming Tip: Style for Boolean Values
Page 42
Self-Test Exercises
Page 42
2.2. Constructors
Page 42
The Throttle's Constructor
Page 43
What Happens If You Write a Class with No Constructors?
Page 46
Programming Tip: Always Provide Constructors
Page 46
Revising the Throttle's Member Functions
Page 46
Inline Member Functions
Page 47
Programming Tip: When to Use an Inline Member Function
Page 48
Self-Test Exercises
Page 48
2.3. Using a Namespace, Header File, and Implementation File
Page 48
Creating a Namespace
Page 48
The Header File
Page 49
Describing the Value Semantics of a Class within the Header File
Page 53
Programming Tip: Document the Value Semantics
Page 54
The Implementation File
Page 54
Using the Items in a Namespace
Page 56
Pitfall: Never Put a Using Statement Actually in a Header File
Page 57
Self-Test Exercises
Page 59
2.4. Classes and Parameters
Page 60
The Point Class
Page 60
Default Arguments
Page 62
Programming Tip: A Default Constructor Can Be Provided by Using Default Arguments
Page 63
Parameters
Page 64
Pitfall: Using a Wrong Argument Type for a Reference Parameter
Page 67
Programming Tip: Use const Consistently
Page 70
When the Type of a Function's Return Value is a Class
Page 70
Self-Test Exercises
Page 71
2.5. Operator Overloading
Page 71
Overloading Binary Comparison Operators
Page 72
Overloading Binary Arithmetic Operators
Page 73
Overloading Output and Input Operators
Page 74
Friend Functions
Page 77
Programming Tip: When to Use a Friend Function
Page 78
The Point Class—Putting Things Together
Page 79
Summary of Operator Overloading
Page 82
Self-Test Exercises
Page 82
Chapter Summary
Page 83
Solutions to Self-Test Exercises
Page 84
Programming Projects
Page 85
3. Container Classes
Page 91
3.1. The Bag Class
Page 92
The Bag Class—Specification
Page 92
C++ Feature: Typedef Statements within a Class Definition
Page 94
C++ Feature: The std::size_t Data Type
Page 94
Older Compilers Do Not Support Initialization of Static Member Constants
Page 99
The Bag Class—Documentation
Page 100
Documenting the Value Semantics
Page 100
The Bag Class—Demonstration Program
Page 102
The Bag Class—Design
Page 104
Pitfall: The value_type Type Must Have a Default Constructor
Page 105
The Invariant of a Class
Page 105
The Bag Class—Implementation
Page 106
Pitfall: When to Use the Full Type Name bag::size_type
Page 107
Programming Tip: Make Assertions Meaningful
Page 107
C++ Feature: The copy Function from the C++ Standard Library
Page 111
The Bag Class—Putting the Pieces Together
Page 112
Programming Tip: Document the Class Invariant in the Implementation File
Page 112
The Bag Class—Testing
Page 112
Pitfall: An Object Can Be an Argument to Its Own Member Function
Page 116
The Bag Class—Analysis
Page 117
Self-Test Exercises
Page 118
3.2. Programming Project: The Sequence Class
Page 119
The Sequence Class—Specification
Page 119
The Sequence Class—Documentation
Page 122
The Sequence Class—Design
Page 122
The Sequence Class—Pseudocode for the Implementation
Page 123
Self-Test Exercises
Page 128
3.3. Interactive Test Programs
Page 128
C++ Feature: Converting Input to Uppercase Letters
Page 129
C++ Feature: The Switch Statement
Page 133
Self-Test Exercises
Page 133
Chapter Summary
Page 134
Solutions to Self-Test Exercises
Page 134
Programming Projects
Page 136
4. Pointers and Dynamic Arrays
Page 140
4.1. Pointers and Dynamic Memory
Page 141
Pointer Variables
Page 141
Using the Assignment Operator with Pointers
Page 144
Dynamic Variables and the new Operator
Page 145
Using new to Allocate Dynamic Arrays
Page 146
The Heap and the bad_alloc Exception
Page 149
The delete Operator
Page 149
Programming Tip: Define Pointer Types
Page 150
Self-Test Exercises
Page 151
4.2. Pointers and Arrays as Parameters
Page 152
Programming Example: Using a Dynamic Array
Page 159
Self-Test Exercises
Page 159
4.3. The Bag Class with a Dynamic Array
Page 162
Pointer Member Variables
Page 162
Member Functions Allocate Dynamic Memory as Needed
Page 163
Programming Tip: Provide Documentation about Possible Dynamic Memory Failure
Page 167
Value Semantics
Page 167
The Destructor
Page 170
The Revised Bag Class—Class Definition
Page 171
The Revised Bag Class—Implementation
Page 173
Programming Tip: How to Check for Self-Assignment
Page 174
Programming Tip: How to Allocate Memory in a Member Function
Page 177
The Revised Bag Class—Putting the Pieces Together
Page 178
Self-Test Exercises
Page 180
4.4. Prescription for a Dynamic Class
Page 181
Four Rules
Page 181
Special Importance of the Copy Constructor
Page 181
Pitfall: Using Dynamic Memory Requires a Destructor, a Copy Constructor, and an Overloaded Assignment Operator
Page 182
Self-Test Exercises
Page 182
4.5. Programming Project: The String Class
Page 183
Null-Terminated Strings
Page 183
Initializing a String Variable
Page 184
The Empty String
Page 184
Reading and Writing String Variables
Page 184
Pitfall: Using = and == with Strings
Page 185
The strcpy Function
Page 185
The strcat Function
Page 186
Pitfall: Dangers of strcpy, strcat, and Reading Strings
Page 186
The strlen Function
Page 186
The strcmp Function
Page 187
The String Class—Specification
Page 187
Constructor for the String Class
Page 189
Overloading the Operator ()
Page 190
Some Further Overloading
Page 190
Other Operations for the String Class
Page 191
The String Class—Design
Page 191
The String Class—Implementation
Page 192
Demonstration Program for the String Class
Page 194
Chaining the Output Operator
Page 196
Declaring Constant Objects
Page 196
Constructor-Generated Conversions
Page 196
Using Overloaded Operations in Expressions
Page 197
Our String Class versus the C++ Library String Class
Page 197
Self-Test Exercises
Page 198
4.6. Programming Project: The Polynomial
Page 198
Chapter Summary
Page 202
Solutions to Self-Test Exercises
Page 202
Programming Projects
Page 204
5. Linked Lists
Page 205
5.1. A Fundamental Node Class for Linked Lists
Page 206
Declaring a Class for Nodes
Page 206
Using a Typedef Statement with Linked List Nodes
Page 207
Head Pointers, Tail Pointers
Page 207
The Null Pointer
Page 208
The Meaning of a Null Head Pointer or Tail Pointer
Page 209
The Node Constructor
Page 209
The Node Member Functions
Page 211
The Member Selection Operator
Page 211
The const Keyword with a Pointer to a Node, and the Need for Two Versions of Some Member Functions
Page 212
Programming Tip: A Rule for a Node's Constant Member Functions
Page 213
Pitfall: Dereferencing the Null Pointer
Page 214
Self-Test Exercises
Page 215
5.2. A Linked List Toolkit
Page 215
Linked List Toolkit—Header File
Page 216
Computing the Length of a Linked List
Page 217
Programming Tip: How to Traverse a Linked List
Page 220
Pitfall: Forgetting to Test the Empty List
Page 220
Parameters for Linked Lists
Page 221
Inserting a New Node at the Head of a Linked List
Page 222
Inserting a New Node That Is Not at the Head
Page 225
Pitfall: Unintended Calls to delete and new
Page 227
Finding a Node by Its Position in a Linked List
Page 230
Copying a Linked List
Page 231
Removing a Node at the Head of a Linked List
Page 235
Removing a Node That Is Not at the Head
Page 235
Clearing a Linked List
Page 237
Linked List Toolkit—Putting the Pieces Together
Page 238
Using the Linked List Toolkit
Page 238
Self-Test Exercises
Page 238
5.3. The Bag Class with a Linked List
Page 243
Our Third Bag—Specification
Page 243
Our Third Bag—Class Definition
Page 243
How to Make the Bag value_type Match the Node value_type
Page 244
Following the Rules for Dynamic Memory Usage in a Class
Page 247
The Third Bag Class—Implementation
Page 248
Pitfall: The Assignment Operator Causes Trouble with Linked Lists
Page 249
Programming Tip: How to Choose Between Different Approaches
Page 251
The Third Bag Class—Putting the Pieces Together
Page 255
Self-Test Exercises
Page 256
5.4. Programming Project: The Sequence Class with a Linked List
Page 259
The Revised Sequence Class—Design Suggestions
Page 259
The Revised Sequence Class—Value Semantics
Page 260
Self-Test Exercises
Page 261
5.5. Dynamic Arrays vs Linked Lists vs Doubly Linked Lists
Page 261
Making the Decision
Page 263
Self-Test Exercises
Page 263
Chapter Summary
Page 264
Solutions to Self-Test Exercises
Page 264
Programming Projects
Page 267
6. Software Development with Templates, Iterators, and the Standard Library
Page 270
6.1. Template Functions
Page 271
Syntax for a Template Function
Page 272
Programming Tip: Capitalize the Name of a Template Parameter
Page 273
Using a Template Function
Page 273
Pitfall: Failed Unification Errors
Page 274
A Template Function to Swap Two Values
Page 274
C++ Feature: swap, max and min Functions
Page 276
Parameter Matching for Template Functions
Page 276
A Template Function to Find the Biggest Item in an Array
Page 277
Pitfall: Mismatches for Template Function Arguments
Page 278
A Template Function to Insert an Item into a Sorted Array
Page 279
Self-Test Exercises
Page 280
6.2. Template Classes
Page 281
Syntax for a Template Class
Page 281
Programming Tip: Use the name Item and the typename Keyword
Page 282
Pitfall: Do Not Place Using Directives in a Template Implementation
Page 283
More about the Template Implementation File
Page 283
Parameter Matching for Member Functions of Template Classes
Page 288
Using the Template Class
Page 288
Details of the Story-Writing Program
Page 289
Self-Test Exercises
Page 292
6.3. Standard Template Classes and Their Iterators
Page 292
The Multiset Template Class
Page 292
Some Multiset Members
Page 293
Iterators and the ( ... ) Pattern
Page 293
Pitfall: Do Not Access an Iterator's Item after Reaching end()
Page 295
Testing Iterators for Equality
Page 296
Other Multiset Operations
Page 297
Invalid Iterators
Page 297
Pitfall: Changing a Container Object Can Invalidate Its Iterators
Page 297
Const Iterators
Page 298
Standard Categories of Iterators
Page 299
Iterators for Arrays
Page 300
Self-Test Exercises
Page 300
6.4. The Node Template Class
Page 301
Functions That Return a Reference Type
Page 302
What Happens When a Reference Return Value Is Copied Elsewhere
Page 304
The Data Member Function Now Requires Two Versions
Page 304
Header and Implementation Files for the New Node
Page 305
Self-Test Exercises
Page 305
6.5. An Iterator for Linked Lists
Page 313
The Node Iterator
Page 313
The Node Iterator Is Derived from std::iterator
Page 315
Pitfall: std::iterator Might Not Exist
Page 316
The Node Iterator's Private Member Variable
Page 316
Node Iterator—Constructor
Page 316
Node Iterator—The * Operator
Page 316
Node Iterator—Two Versions of the ++ Operator
Page 317
Programming Tip: "++p" Is More Efficient Than "p++"
Page 319
Iterators for Constant Collections
Page 319
Programming Tip: When to Use a Const Iterator
Page 321
Self-Test Exercises
Page 321
6.6. Linked List Version of the Bag Template Class with an Iterator
Page 322
How to Provide an Iterator for a Container Class That You Write
Page 322
The Bag Iterator
Page 323
Why the Iterator Is Defined Inside the Bag
Page 324
Self-Test Exercises
Page 324
Chapter Summary and Summary of the Five Bags
Page 332
Solutions to Self-Test Exercises
Page 333
Programming Projects
Page 335
7. Stacks
Page 337
7.1. Introduction to Stacks and the STL stack
Page 337
The Standard Library stack Class
Page 339
Programming Example: Reversing a Word
Page 340
Self-Test Exercises
Page 341
7.2. Stack Applications
Page 342
Programming Example: Balanced Parentheses
Page 342
Programming Example: Evaluating Arithmetic Expressions
Page 344
Evaluating Arithmetic Expressions—Specification
Page 344
Evaluating Arithmetic Expressions—Design
Page 345
Evaluating Arithmetic Expressions—Implementation
Page 351
Functions Used in the Calculator Program
Page 352
Evaluating Arithmetic Expressions—Testing and Analysis
Page 352
Evaluating Arithmetic Expressions—Enhancements
Page 353
Self-Test Exercises
Page 354
7.3. Implementations of the stack Class
Page 354
Array Implementation of a Stack
Page 354
Linked List Implementation of a Stack
Page 358
The Koenig Lookup
Page 359
Self-Test Exercises
Page 359
7.4. More Complex Stack Applications
Page 362
Evaluating Postfix Expressions
Page 362
Translating Infix to Postfix Notation
Page 364
Using Precedence Rules in the Infix Expression
Page 366
Correctness of the Conversion from Infix to Postfix
Page 368
Self-Test Exercises
Page 372
Chapter Summary
Page 372
Solutions to Self-Test Exercises
Page 372
Programming Projects
Page 374
8. Queues
Page 377
8.1. Introduction to Queues and the STL queue
Page 377
The Standard Library queue Class
Page 379
Uses for Queues
Page 380
Self-Test Exercises
Page 381
8.2. Queue Applications
Page 381
Programming Example: Recognizing Palindromes
Page 381
Self-Test Exercises
Page 384
Programming Example: Car Wash Simulation
Page 384
Car Wash Simulation—Specification
Page 385
Car Wash Simulation—Design
Page 385
Car Wash Simulation—Implementing the Car Wash Classes
Page 389
Car Wash Simulation—Implementing the Simulation Function
Page 394
Self-Test Exercises
Page 395
8.3. Implementations of the Queue Class
Page 397
Array Implementation of a Queue
Page 397
Programming Tip: Use Small Helper Functions to Improve Clarity
Page 400
Discussion of the Circular Array Implementation of a Queue
Page 402
Linked List Implementation of a Queue
Page 404
Programming Tip: Make Note of "Don't Care" Situations
Page 407
Pitfall: Forgetting Which End Is Which
Page 407
Self-Test Exercises
Page 410
8.4. Priority Queues
Page 410
How the Priorities Are Specified
Page 411
The Standard Library priority_queue Class
Page 411
Priority Queue Class—Implementation Ideas
Page 411
Self-Test Exercises
Page 412
8.5. Reference Return Values for the Stack, Queue, and Priority Queue Classes
Page 412
Chapter Summary
Page 414
Solutions to Self-Test Exercises
Page 414
Programming Projects
Page 415
9. Recursive Thinking
Page 418
9.1. Recursive Functions
Page 419
A First Example of Recursive Thinking
Page 419
Tracing Recursive Calls
Page 421
Programming Example: An Extension of write_vertical
Page 422
A Closer Look at Recursion
Page 423
General Form of a Successful Recursive Function
Page 427
Self-Test Exercises
Page 428
9.2. Studies of Recursion: Fractals and Mazes
Page 429
Programming Example: Generating Random Fractals
Page 429
A Function for Generating Random Fractals—Specification
Page 430
Design and Implementation of the Fractal Function
Page 432
How the Random Fractals Are Displayed
Page 433
Programming Example: Traversing a Maze
Page 435
Traversing a Maze—Specification
Page 435
Traversing a Maze—Design
Page 437
Traversing a Maze—Implementation
Page 438
Self-Test Exercises
Page 439
9.3. Reasoning about Recursion
Page 441
How to Ensure That There is No Infinite Recursion
Page 443
Inductive Reasoning about the Correctness of a Recursive Function
Page 446
Self-Test Exercises
Page 448
Chapter Summary
Page 448
Solutions to Self-Test Exercises
Page 448
Programming Projects
Page 450
10. Trees
Page 453
10.1. Introduction to Trees
Page 454
Binary Trees
Page 454
Binary Taxonomy Trees
Page 457
General Trees
Page 458
Self-Test Exercises
Page 459
10.2. Tree Representations
Page 459
Array Representation of Complete Binary Trees
Page 459
Representing a Binary Tree with a Class for Nodes
Page 462
Self-Test Exercises
Page 464
10.3. Binary Tree Nodes
Page 464
Pitfall: Not Connecting All the Links
Page 467
Programming Example: Animal Guessing
Page 468
Animal Guessing Program—Design and Implementation
Page 470
Animal Guessing Program—Improvements
Page 479
Self-Test Exercises
Page 479
10.4. Tree Traversals
Page 479
Traversals of Binary Trees
Page 479
A Useful Backward In-Order Traversal
Page 484
Programming Tip: Quick and Easy Printing of a Tree
Page 485
The Problem with Our Traversals
Page 486
A Parameter Can Be a Function
Page 486
A Template Version of the apply Function
Page 488
More Generality for the apply Template Function
Page 489
Template Functions for Tree Traversals
Page 490
Self-Test Exercises
Page 491
10.5. Binary Search Trees
Page 497
The Binary Search Tree Storage Rules
Page 497
Our Sixth Bag—Class Definition
Page 501
Our Sixth Bag—Implementation of Some Simple Functions
Page 501
Counting the Occurrences of an Item in a Binary Search Tree
Page 502
Inserting a New Item into a Binary Search Tree
Page 503
Removing an Item from a Binary Search Tree
Page 504
The Union Operators for Binary Search Trees
Page 508
Time Analysis and an Iterator
Page 510
Self-Test Exercises
Page 510
Chapter Summary
Page 510
Solutions to Self-Test Exercises
Page 511
Programming Projects
Page 513
11. Tree Projects
Page 517
11.1. Heaps
Page 518
The Heap Storage Rules
Page 518
The Priority Queue ADT with Heaps
Page 519
Adding an Entry to a Heap
Page 519
Removing an Entry from a Heap
Page 521
Self-Test Exercises
Page 524
11.2. B-Trees
Page 524
The Problem of Unbalanced Trees
Page 524
The B-Tree Rules
Page 525
An Example B-Tree
Page 526
The Set ADT with B-Trees
Page 527
Searching for an Item in a B-Tree
Page 532
Inserting an Item into a B-Tree
Page 534
The Loose Insertion into a B-Tree
Page 534
A Private Member Function to Fix an Excess in a Child
Page 537
Back to the Insert Member Function
Page 538
Employing Top-Down Design
Page 540
Removing an Item from a B-Tree
Page 540
The Loose Erase from a B-Tree
Page 541
A Private Member Function to Fix a Shortage in a Child
Page 543
Removing the Biggest Item from a B-Tree
Page 546
Programming Tip: Write and Test Small Pieces
Page 546
External B-Trees
Page 547
Self-Test Exercises
Page 548
11.3. Trees, Logs, and Time Analysis
Page 549
Time Analysis for Binary Search Trees
Page 549
Time Analysis for Heaps
Page 550
Logarithms
Page 553
Logarithmic Algorithms
Page 554
Self-Test Exercises
Page 554
Chapter Summary
Page 554
Solutions to Self-Test Exercises
Page 555
Programming Projects
Page 557
12. Searching
Page 558
12.1. Serial Search and Binary Search
Page 559
Serial Search
Page 559
Serial Search—Analysis
Page 559
Binary Search
Page 561
Binary Search—Design
Page 562
Pitfall: Common Indexing Errors in Binary Search Implementations
Page 563
Binary Search—Analysis
Page 565
Self-Test Exercises
Page 569
12.2. Open-Address Hashing
Page 569
Introduction to Hashing
Page 570
The Table Class—Specification
Page 572
The Table Class—Design
Page 574
Programming Tip: Using size_t Can Indicate a Value's Purpose
Page 577
The Table ADT—Implementation
Page 578
C++ Feature: Inline Functions in the Implementation File
Page 583
Choosing a Hash Function to Reduce Collisions
Page 583
Double Hashing to Reduce Clustering
Page 584
Self-Test Exercises
Page 585
12.3. Chained Hashing
Page 586
Self-Test Exercises
Page 588
12.4. Time Analysis of Hashing
Page 588
The Load Factor of a Hash Table
Page 588
Self-Test Exercises
Page 591
Chapter Summary
Page 591
Solutions to Self-Test Exercises
Page 592
Programming Projects
Page 594
13. Sorting
Page 595
13.1. Quadratic Sorting Algorithms
Page 596
Selectionsort—Specification
Page 596
Selectionsort—Design
Page 596
Selectionsort—Implementation
Page 598
Selectionsort—Analysis
Page 600
Programming Tip: Rough Estimates Suffice for Big-O
Page 602
Insertionsort
Page 602
Insertionsort—Analysis
Page 606
Self-Test Exercises
Page 608
13.2. Recursive Sorting Algorithms
Page 608
Divide-and-Conquer Using Recursion
Page 608
C++ Feature: Specifying a Subarray with Pointer Arithmetic
Page 609
Mergesort
Page 611
The Merge Function
Page 613
Dynamic Memory Usage in Mergesort
Page 618
Mergesort—Analysis
Page 618
Mergesort for Files
Page 620
Quicksort
Page 620
The Partition Function
Page 623
Quicksort—Analysis
Page 626
Quicksort—Choosing a Good Pivot Element
Page 628
Self-Test Exercises
Page 628
13.3. An O(n log n) Algorithm Using a Heap
Page 629
Heapsort
Page 629
Making the Heap
Page 636
Reheapification Downward
Page 637
Heapsort—Analysis
Page 638
Self-Test Exercises
Page 640
13.4. Standard Library Sorting Functions
Page 640
The C++ sort Function
Page 640
The Original C Version of qsort
Page 640
Chapter Summary
Page 642
Solutions to Self-Test Exercises
Page 642
Programming Projects
Page 643
14. Derived Classes and Inheritance
Page 646
14.1. Derived Classes
Page 646
How to Declare a Derived Class
Page 649
The Automatic Constructors of a Derived Class
Page 650
Using a Derived Class
Page 651
The Automatic Assignment Operator for a Derived Class
Page 652
The Automatic Destructor of a Derived Class
Page 653
Overriding Inherited Member Functions
Page 653
Programming Tip: Make the Overriding Function Call the Original
Page 654
Self-Test Exercises
Page 655
14.2. Simulation of an Ecosystem
Page 655
Implementing Part of the Organism Object Hierarchy
Page 656
The Organism Class
Page 656
The Animal Class: A Derived Class with New Private Member Variables
Page 659
How to Provide a New Constructor for a Derived Class
Page 659
The Other Animal Member Functions
Page 661
Self-Test Exercises
Page 665
The Herbivore Class
Page 666
The Pond Life Simulation Program
Page 668
Pondlife—Implementation Details
Page 673
Using the Pond Model
Page 673
Dynamic Memory Usage
Page 674
Self-Test Exercises
Page 675
14.3. Virtual Member Functions and a Game Class
Page 675
Introduction to the Game Class
Page 675
Protected Members
Page 679
Virtual Member Functions
Page 679
Virtual Destructors
Page 681
The Protected Virtual Member Functions of the Game Class
Page 681
A Derived Class to Play Connect Four
Page 682
The Private Member Variables of the Connect Four Class
Page 682
The Connect Four Constructor and Restart Function
Page 684
Three Connect Four Functions That Deal with the Game's Status
Page 684
Three Connect Four Functions That Deal with Moves
Page 686
The Clone Function
Page 686
Writing Your Own Derived Games from the Game Class
Page 687
The Game Class's Play Algorithm with Minimax
Page 688
Self-Test Exercises
Page 691
Chapter Summary
Page 691
Further Reading
Page 691
Solutions to Self-Test Exercises
Page 692
Programming Projects
Page 694
15. Graphs
Page 695
15.1. Graph Definitions
Page 695
Undirected Graphs
Page 696
Programming Example: Undirected State Graphs
Page 697
Directed Graphs
Page 700
More Graph Terminology
Page 701
Airline Routes Example
Page 702
Self-Test Exercises
Page 702
15.2. Graph Implementations
Page 703
Representing Graphs with an Adjacency Matrix
Page 703
Using a Two-Dimensional Array to Store an Adjacency Matrix
Page 704
Representing Graphs with Edge Lists
Page 704
Representing Graphs with Edge Sets
Page 705
Which Representation Is Best?
Page 706
Programming Example: Labeled Graph Class
Page 706
Member Functions to Add Vertices and Edges
Page 707
Labeled Graph Class—Overloading the Subscript Operator
Page 708
A Const Version of the Subscript Operator
Page 709
Labeled Graph Class—neighbors Function
Page 710
Labeled Graph Class—Implementation
Page 710
Self-Test Exercises
Page 711
15.3. Graph Traversals
Page 716
Depth-First Search
Page 717
Breadth-First Search
Page 720
Depth-First Search—Implementation
Page 722
Breadth-First Search—Implementation
Page 724
Self-Test Exercises
Page 724
15.4. Path Algorithms
Page 726
Determining Whether a Path Exists
Page 726
Graphs with Weighted Edges
Page 727
Shortest Distance Algorithm
Page 728
Shortest Path Algorithm
Page 738
Self-Test Exercises
Page 739
Chapter Summary
Page 740
Solutions to Self-Test Exercises
Page 740
Programming Projects
Page 741
Appendix A. ASCII Character Set
Page 745
Appendix B. Further Big-O Notation
Page 746
Appendix C. Precedence of Operators
Page 748
Appendix D. Compiling, Linking, and Running Programs
Page 749
Appendix E. Dealing with Older Compilers
Page 752
Appendix F. Input and Output in C++
Page 754
Appendix G. Selected Library Functions
Page 762
Appendix H. Brief Reference for the Standard Template Classes
Page 765
Appendix I. A Toolkit of Useful Functions
Page 772
Appendix J. Fundamental Style Guide
Page 775
Appendix K. Downloading the GNU Compiler and Software
Page 776
Index
Page 777

Edition Notes

Includes bibliographical references and index.

Published in
Boston, MA
Other Titles
Data structures and other objects using C++

Classifications

Dewey Decimal Class
005.7/3
Library of Congress
QA76.73.C153 M25 2001, QA76.73.C153M25 2001

The Physical Object

Pagination
xxxi, 783 p. :
Number of pages
783

Edition Identifiers

Open Library
OL24875564M
ISBN 10
0201702975
LCCN
00026255
OCLC/WorldCat
43561820

Work Identifiers

Work ID
OL15969766W

Source records

Community Reviews (0)

No community reviews have been submitted for this work.

Lists

Loading indicator
Loading carousel

History

Download catalog record: RDF / JSON / OPDS | Wikipedia citation
October 13, 2025 Edited by MARC Bot import existing book
September 23, 2025 Edited by Drini Add TOC from Tocky
January 8, 2023 Edited by MARC Bot import existing book
November 17, 2022 Edited by ImportBot import existing book
July 28, 2011 Created by ImportBot Imported from Harvard University record