Amazon no longer offers textbook rentals. We do!

Data Structures and Other Objects Using C++

by: Main, Michael; Savitch, Walter

Data Structures and Other Objects Using C++

by: Main, Michael; Savitch, Walter

ISBN 13:
9780321197160
ISBN 10:
032119716X
Edition: 4th
Format: Paperback
Copyright: 01/01/2011
Publisher: Addison Wesley
Newer Edition

Rent

Sorry, this item is currently unavailable.

Note: Supplemental materials are not guaranteed with Rental or Used book purchases.

Extend or Purchase Your Rental at Any Time

Need to keep your rental past your due date? At any time before your due date you can extend or purchase your rental through your account.

Summary

This book successfully balances the introduction of object-oriented concepts with data structures in C++. KEN TOPICS:Provides interfaces for the principal example classes, which are compliant with the ANSI/ISO C++ Standard Library classes. Thorough coverage of the role of the const keyword in the C++ Standard Library. Covers C++ features such as namespaces, static member constants, typename keyword, and inheritance. Thorough review of C++ syntax and OOP concepts, making book accessible for programmers at various levels. The book also gives readers a firm grasp of key concepts and allows programmers experienced in another language to adjust easily. A solid foundation in building and using abstract data types is also provided, along with an assortment of advanced topics such as B-trees for project building and graphs. This book is designed for novice programmers who have learned the concepts of objects and classes and want to move on to the data structures topics of recursion and data abstraction.

The Phases of Software Development

(32)

Specification, Design, Implementation

(12)

Design Concept: Decomposing the Problem

(2)

Preconditions and Postconditions

(2)

Using Functions Provided by Other Programmers

(1)

Implementation Issues for the ANSI/ISO C++ Standard

(1)

C++ Feature: The Standard Library and the Standard Namespace

(2)

Programming Tip: Use Declared Constants

(1)

Programming Tip: Use Assert to Check a Precondition

(2)

Programming Tip: Use Exit_Success in a Main Program

(1)

C++ Feature: Exception Handling

(1)

Self-Test Exercises for Section 1.1

(1)

Running Time Analysis

(11)

The Stair-Counting Problem

(6)

Big-O Notation

(2)

Time Analysis of C++ Functions

(2)

Worst-Case, Average-Case, and Best-Case Analyses

(1)

Self-Test Exercises for Section 1.2

(1)

Testing and Debugging

(7)

Choosing Test Data

(1)

Boundary Values

(1)

Fully Exercising Code

(1)

Debugging

(1)

Programming Tip: How to Debug

(1)

Self-Test Exercises for Section 1.3

(1)

Chapter Summary

(1)

Solutions to Self-Test Exercises

(2)

Abstract Data Types and C++ Classes

(62)

Classes and Members

(11)

Programming Example: The Throttle Class

(5)

Using a Class

(1)

A Small Demonstration Program for the Throttle Class

(2)

Implementing Member Functions

(2)

Member Functions May Activate Other Members

(1)

Programming Tip: Style for Boolean Variables

(1)

Self-Test Exercises for Section 2.1

(1)

Constructors

(6)

The Throttle's Constructor

(3)

What Happens If You Write a Class with No Constructors?

(1)

Programming Tip: Always Provide Constructors

(1)

Revising the Throttle's Member Functions

(1)

Inline Member Functions

(1)

Programming Tip: When to Use an Inline Member Function

(1)

Self-Test Exercises for Section 2.2

(1)

Using a Namespace, Header File, and Implementation File

(12)

Creating a Namespace

(1)

The Header File

(4)

Describing the Value Semantics of a Class Within the Header File

(1)

Programming Tip: Document the Value Semantics

(1)

The Implementation File

(2)

Using the Items in a Namespace

(1)

Pitfall: Never Put a Using Statement Actually in a Header File

(2)

Self-Test Exercises for Section 2.3

(1)

Classes and Parameters

(11)

Programming Example: The Point Class

(2)

Default Arguments

(1)

Programming Tip: A Default Constructor Can Be Provided by Using Default Arguments

(1)

Parameters

(3)

Pitfall: Using a Wrong Argument Type for a Reference Parameter

(3)

Programming Tip: Use const Consistently

(1)

When the Type of a Function's Return Value Is a Class

(1)

Self-Test Exercises for Section 2.4

(1)

Operator Overloading

(21)

Overloading Binary Comparison Operators

(1)

Overloading Binary Arithmetic Operators

(1)

Overloading Output and Input Operators

(3)

Friend Functions

(1)

Programming Tip: When to Use a Friend Function

(1)

The Point Class---Putting Things Together

(3)

Summary of Operator Overloading

(1)

Self-Test Exercises for Section 2.5

(1)

Chapter Summary

(1)

Solutions to Self-Test Exercises

(2)

Programming Projects

(6)

Container Classes

(50)

The Bag Class

(27)

The Bag Class---Specification

(1)

C++ Feature: Typedef Statements Within a Class Definition

(1)

C++ Feature: The std::size_t Data Type

(5)

Older Compilers Do Not Support Initialization of Static Member Constants

104

(1)

The Bag Class---Documentation

104

(2)

Documenting the Value Semantics

106

(1)

The Bag Class---Demonstration Program

106

(2)

The Bag Class---Design

108

(1)

Pitfall: The value_type Must Have a Default Constructor

109

(1)

The Invariant of a Class

109

(1)

The Bag Class---Implementation

110

(1)

Pitfall: Needing to Use the Full Type Name bag::size_type

111

(1)

Programming Tip: Make Assertions Meaningful

111

(4)

C++ Feature: The Copy Function from the C++ Standard Library

115

(1)

The Bag Class---Putting the Pieces Together

116

(1)

Programming Tip: Document the Class Invariant in the Implementation File

116

(4)

The Bag Class---Testing

120

(1)

Pitfall: An Object Can Be an Argument to Its Own Member Function

120

(1)

The Bag Class---Analysis

121

(1)

Self-Test Exercises for Section 3.1

122

(1)

Programming Project: The Sequence Class

123

(9)

The Sequence Class---Specification

123

(3)

The Sequence Class---Documentation

126

(1)

The Sequence Class---Design

126

(1)

The Sequence Class---Pseudocode for the Implementation

127

(4)

Self-Test Exercises for Section 3.2

131

(1)

Interactive Test Programs

132

(13)

C++ Feature: Converting Input to Uppercase Letters

133

(4)

C++ Feature: The Switch Statement

137

(1)

Self-Test Exercises for Section 3.3

137

(1)

Chapter Summary

138

(1)

Solutions to Self-Test Exercises

138

(2)

Programming Projects

140

(5)

Pointers and Dynamic Arrays

145

(66)

Pointers and Dynamic Memory

146

(11)

Pointer Variables

147

(2)

Using the Assignment Operator with Pointers

149

(1)

Dynamic Variables and the new Operator

150

(1)

Using new to Allocate Dynamic Arrays

151

(3)

The Heap and the bad_alloc Exception

154

(1)

The delete Operator

154

(1)

Programming Tip: Define Pointer Types

155

(1)

Self-Test Exercises for Section 4.1

156

(1)

Pointers and Arrays as Parameters

157

(10)

Self-Test Exercises for Section 4.2

164

(3)

The Bag Class with a Dynamic Array

167

(19)

Pointer Member Variables

167

(1)

Member Functions Allocate Dynamic Memory as Needed

168

(4)

Programming Tip: Provide Documentation About Possible Dynamic Memory Failure

172

(1)

Value Semantics

172

(3)

The Destructor

175

(1)

The Revised Bag Class---Class Definition

176

(2)

The Revised Bag Class---Implementation

178

(1)

Programming Tip: How to Check for Self-Assignment

179

(3)

Programming Tip: How to Allocate Memory in a Member Function

182

(1)

The Revised Bag Class---Putting the Pieces Together

183

(2)

Self-Test Exercises for Section 4.3

185

(1)

Prescription for a Dynamic Class

186

(2)

Four Rules

186

(1)

Special Importance of the Copy Constructor

186

(1)

Pitfall: Using Dynamic Memory Requires a Destructor, a Copy Constructor, and an Overloaded Assignment Operator

187

(1)

Self-Test Exercises for Section 4.4

188

(1)

Programming Project: The String Class

188

(15)

Null-Terminated Strings

188

(1)

Initializing a String Variable

189

(1)

The Empty String

189

(1)

Reading and Writing String Variables

190

(1)

Pitfall: Using = and == with Strings

190

(1)

The strcpy Function

190

(1)

The strcat Function

191

(1)

Pitfall: Dangers of strcpy, strcat, and Reading Strings

191

(1)

The strlen Function

192

(1)

The strcmp Function

192

(1)

The String Class---Specification

192

(2)

Constructor for the String Class

194

(1)

Overloading the operator [ ]

195

(1)

Some Further Overloading

195

(1)

Other Operations for the String Class

196

(1)

The String Class---Design

196

(1)

The String Class---Implementation

197

(2)

Demonstration Program for the String Class

199

(2)

Chaining the Output Operator

201

(1)

Declaring Constant Objects

201

(1)

Constructor-Generated Conversions

201

(1)

Using Overloaded Operations in Expressions

202

(1)

Our String Class versus the C++ Library String Class

202

(1)

Self-Test Exercises for Section 4.5

202

(1)

Programming Project: The Polynomial

203

(8)

Chapter Summary

207

(1)

Solutions to Self-Test Exercises

207

(2)

Programming Projects

209

(2)

Linked Lists

211

(67)

A Fundamental Node Class for Linked Lists

212

(10)

Declaring a Class for Nodes

212

(1)

Using a Typedef Statement with Linked-List Nodes

213

(1)

Head Pointers, Tail Pointers

214

(1)

The Null Pointer

215

(1)

The Meaning of a Null Head Pointer or Tail Pointer

215

(1)

The Node Constructor

215

(1)

The Node Member Functions

216

(1)

The Member Selection Operator

217

(2)

Programming Tip: A Rule for a Node's Constant Member Functions

219

(2)

Pitfall: Dereferencing the Null Pointer

221

(1)

Self-Test Exercises for Section 5.1

221

(1)

A Linked-List Toolkit

222

(28)

Linked-List Toolkit---Header File

223

(1)

Computing the Length of a Linked List

223

(3)

Programming Tip: How to Traverse a Linked List

226

(1)

Pitfall: Forgetting to Test the Empty List

227

(1)

Parameters for Linked Lists

227

(2)

Inserting a New Node at the Head of a Linked List

229

(2)

Inserting a New Node That Is Not at the Head

231

(3)

Pitfall: Unintended Calls to delete and new

234

(3)

Finding a Node by Its Position in a Linked List

237

(1)

Copying a Linked List

238

(3)

Removing a Node at the Head of a Linked List

241

(1)

Removing a Node That Is Not at the Head

242

(1)

Clearing a Linked List

243

(1)

Linked-List Toolkit---Putting the Pieces Together

244

(1)

Using the Linked-List Toolkit

245

(4)

Self-Test Exercises for Section 5.2

249

(1)

The Bag Class with a Linked List

250

(16)

Our Third Bag---Specification

250

(1)

Our Third Bag---Class Definition

250

(1)

How to Make the Bag value_type Match the Node value_type

251

(3)

Following the Rules for Dynamic Memory Usage in a Class

254

(1)

The Third Bag Class---Implementation

255

(1)

Pitfall: The Assignment Operator Causes Trouble with Linked Lists

256

(2)

Programming Tip: How to Choose Between Approaches

258

(4)

The Third Bag Class---Putting the Pieces Together

262

(1)

Self-Test Exercises for Section 5.3

263

(3)

Programming Project: The Sequence Class with a Linked List

266

(2)

The Revised Sequence Class---Design Suggestions

266

(1)

The Revised Sequence Class---Value Semantics

267

(1)

Self-Test Exercises for Section 5.4

268

(1)

Dynamic Arrays vs Linked Lists vs Doubly Linked Lists

268

(10)

Making the Decision

270

(1)

Self-Test Exercises for Section 5.5

270

(1)

Chapter Summary

271

(1)

Solutions to Self-Test Exercises

271

(4)

Programming Projects

275

(3)

Software Development with Templates, Iterators, and the STL

278

(70)

Template Functions

279

(10)

Syntax for a Template Function

281

(1)

Programming Tip: Capitalize the Name of a Template Parameter

281

(1)

Using a Template Function

282

(1)

Pitfall: Failed Unification Errors

282

(2)

A Template Function to Swap Two Values

284

(1)

C++ Feature: Swap, Max, and Min Functions

284

(1)

Parameter Matching for Template Functions

284

(1)

A Template Function to Find the Biggest Item in an Array

285

(2)

Pitfall: Mismatches for Template Function Arguments

287

(1)

A Template Function to Insert an Item into a Sorted Array

287

(2)

Self-Test Exercises for Section 6.1

289

(1)

Template Classes

289

(12)

Syntax for a Template Class

289

(2)

Programming Tip: Use the Name Item and the typename Keyword

291

(1)

Pitfall: Do Not Place Using Directives in a Template Implementation

292

(1)

More About the Template Implementation File

292

(5)

Parameter Matching for Member Functions of Template Classes

297

(1)

Using the Template Class

297

(3)

Details of the Story-Writing Program

300

(1)

Self-Test Exercises for Section 6.2

300

(1)

Standard Template Classes and Their Iterators

301

(12)

The Multiset Template Class

301

(1)

Some Multiset Members

302

(1)

Iterators and the [...) Pattern

302

(2)

Pitfall: Do Not Access an Iterator's Item after Reaching end( )

304

(1)

Testing Iterators for Equality

305

(1)

Other Multiset Operations

306

(1)

Set Algorithms

306

(1)

Invalid Iterators

307

(1)

Pitfall: Changing a Container Object Can Invalidate Its Iterators

308

(1)

Standard Categories of Iterators

309

(1)

Iterators for Arrays

310

(1)

The Standard Template Library List Class

311

(1)

Self-Test Exercises for Section 6.3

312

(1)

The Node Template Class

313

(11)

Functions That Return a Reference Type

314

(1)

What Happens When a Reference Return Value Is Copied Elsewhere

315

(1)

The Data Member Function Now Requires Two Versions

316

(1)

Header and Implementation Files for the New Node

316

(1)

Self-Test Exercises for Section 6.4

316

(8)

An Iterator for Linked Lists

324

(9)

The Node Iterator

324

(2)

The Node Iterator Is Derived from std::iterator

326

(1)

Pitfall: std::iterator Might Not Exist

327

(1)

The Node Iterator's Private Member Variable

327

(1)

Node Iterator---Constructor

327

(1)

Node Iterator---The * Operator

327

(1)

Node Iterator---Two Versions of the ++ Operator

328

(2)

Programming Tip: ++p Is More Efficient Than p++

330

(1)

Iterators for Constant Collections

330

(2)

Programming Tip: When to Use a Const Iterator

332

(1)

Self-Test Exercises for Section 6.5

332

(1)

Linked-List Version of the Bag Template Class with an Iterator

333

(15)

How to Provide an Iterator for a Container Class That You Write

333

(1)

The Bag Iterator

334

(1)

Why the Iterator Is Defined Inside the Bag

335

(1)

Self-Test Exercises for Section 6.6

335

(8)

Chapter Summary and Summary of the Five Bags

343

(1)

Solutions to Self-Test Exercises

344

(2)

Programming Projects

346

(2)

Stacks

348

(41)

Introduction to Stacks and the STL Stack

349

(4)

The Standard Library Stack Class

350

(1)

Programming Example: Reversing a Word

351

(1)

Self-Test Exercises for Section 7.1

352

(1)

Stack Applications

353

(12)

Programming Example: Balanced Parentheses

353

(2)

Programming Example: Evaluating Arithmetic Expressions

355

(1)

Evaluating Arithmetic Expressions---Specification

355

(1)

Evaluating Arithmetic Expressions---Design

356

(6)

Evaluating Arithmetic Expressions---Implementation

362

(1)

Functions Used in the Calculator Program

363

(1)

Evaluating Arithmetic Expressions---Testing and Analysis

363

(1)

Evaluating Arithmetic Expressions---Enhancements

364

(1)

Self-Test Exercises for Section 7.2

364

(1)

Implementations of the Stack Class

365

(8)

Array Implementation of a Stack

365

(4)

Linked-List Implementation of a Stack

369

(1)

The Koenig Lookup

370

(1)

Self-Test Exercises for Section 7.3

370

(3)

More Complex Stack Applications

373

(16)

Evaluating Postfix Expressions

373

(2)

Translating Infix to Postfix Notation

375

(2)

Using Precedence Rules in the Infix Expression

377

(2)

Correctness of the Conversion from Infix to Postfix

379

(4)

Self-Test Exercises for Section 7.4

383

(1)

Chapter Summary

383

(1)

Solutions to Self-Test Exercises

383

(2)

Programming Projects

385

(4)

Queues

389

(42)

Introduction to Queues and the STL Queue

390

(4)

The Standard Library Queue Class

391

(1)

Uses for Queues

391

(2)

Self-Test Exercises for Section 8.1

393

(1)

Queue Applications

394

(15)

Programming Example: Recognizing Palindromes

394

(2)

Self-Test Exercises for Middle of Section 8.2

396

(1)

Programming Example: Car Wash Simulation

397

(1)

Car Wash Simulation---Specification

397

(1)

Car Wash Simulation---Design

398

(3)

Car Wash Simulation---Implementing the Car Wash Classes

401

(5)

Car Wash Simulation---Implementing the Simulation Function

406

(1)

Self-Test Exercises for Section 8.2

407

(2)

Implementations of the Queue Class

409

(13)

Array Implementation of a Queue

409

(3)

Programming Tip: Use Small Helper Functions to Improve Clarity

412

(2)

Discussion of the Circular Array Implementation of a Queue

414

(2)

Linked-List Implementation of a Queue

416

(3)

Programming Tip: Make Note of ``Don't Care'' Situations

419

(1)

Pitfall: Which End Is Which

419

(3)

Self-Test Exercises for Section 8.3

422

(1)

Priority Queues

422

(2)

How the Priorities Are Specified

423

(1)

The Standard Library Priority Queue Class

423

(1)

Priority Queue Class---Implementation Ideas

423

(1)

Self-Test Exercises for Section 8.4

424

(1)

Reference Return Values for the Stack, Queue, and Priority Queue Classes

424

(7)

Chapter Summary

426

(1)

Solutions to Self-Test Exercises

426

(1)

Programming Projects

427

(4)

Recursive Thinking

431

(38)

Recursive Functions

432

(10)

A First Example of Recursive Thinking

432

(2)

Tracing Recursive Calls

434

(2)

Programming Example: An Extension of write_vertical

436

(1)

A Closer Look at Recursion

437

(3)

General Form of a Successful Recursive Function

440

(1)

Self-Test Exercises for Section 9.1

441

(1)

Studies of Recursion: Fractals and Mazes

442

(14)

Programming Example: Generating Random Fractals

442

(1)

A Function for Generating Random Fractals---Specification

443

(2)

Design and Implementation of the Fractal Function

445

(1)

How the Random Fractals Are Displayed

446

(2)

Programming Example: Traversing a Maze

448

(1)

Traversing a Maze---Specification

448

(2)

Traversing a Maze---Design

450

(1)

Traversing a Maze---Implementation

451

(2)

The Recursive Pattern of Exhaustive Search with Backtracking

453

(1)

Programming Example: The Teddy Bear Game

454

(1)

Pitfall: Forgetting to Use the Return Value from a Recursive Call

454

(1)

Self-Test Exercises for Section 9.2

455

(1)

Reasoning About Recursion

456

(13)

How to Ensure That There Is No Infinite Recursion

458

(3)

Inductive Reasoning About the Correctness of a Recursive Function

461

(1)

Self-Test Exercises for Section 9.3

462

(1)

Chapter Summary

463

(1)

Solutions to Self-Test Exercises

463

(2)

Programming Projects

465

(4)

Trees

469

(65)

Introduction to Trees

470

(5)

Binary Trees

470

(3)

Binary Taxonomy Trees

473

(1)

General Trees

474

(1)

Self-Test Exercises for Section 10.1

475

(1)

Tree Representations

475

(5)

Array Representation of Complete Binary Trees

475

(3)

Representing a Binary Tree with a Class for Nodes

478

(2)

Self-Test Exercises for Section 10.2

480

(1)

Binary Tree Nodes

480

(15)

Pitfall: Not Connecting All the Links

483

(1)

Programming Example: Animal Guessing

484

(2)

Animal Guessing Program---Design and Implementation

486

(5)

Animal Guessing Program---Improvements

491

(4)

Self-Test Exercises for Section 10.3

495

(1)

Tree Traversals

495

(18)

Traversals of Binary Trees

495

(5)

Printing the Data from a Tree's Node

500

(1)

The Problem with Our Traversals

501

(1)

A Parameter Can Be a Function

502

(2)

A Template Version of the Apply Function

504

(1)

More Generality for the Apply Template Function

505

(1)

Template Functions for Tree Traversals

506

(1)

Self-Test Exercises for Section 10.4

507

(6)

Binary Search Trees

513

(21)

The Binary Search Tree Storage Rules

513

(4)

Our Sixth Bag---Class Definition

517

(1)

Our Sixth Bag---Implementation of Some Simple Functions

517

(1)

Counting the Occurrences of an Item in a Binary Search Tree

518

(1)

Inserting a New Item into a Binary Search Tree

519

(1)

Removing an Item from a Binary Search Tree

520

(4)

The Union Operators for Binary Search Trees

524

(2)

Time Analysis and an Iterator

526

(1)

Self-Test Exercises for Section 10.5

526

(1)

Chapter Summary

526

(1)

Solutions to Self-Test Exercises

527

(2)

Programming Projects

529

(5)

Tree Projects

534

(41)

Heaps

535

(6)

The Heap Storage Rules

535

(1)

The Priority Queue ADT with Heaps

536

(1)

Adding an Entry to a Heap

537

(1)

Removing an Entry from a Heap

538

(3)

Self-Test Exercises for Section 11.1

541

(1)

B-Trees

541

(25)

The Problem of Unbalanced Trees

541

(1)

The B-Tree Rules

542

(1)

An Example B-Tree

543

(1)

The Set ADT with B-Trees

544

(5)

Searching for an Item in a B-Tree

549

(2)

Inserting an Item into a B-Tree

551

(1)

The Loose Insertion into a B-Tree

551

(3)

A Private Member Function to Fix an Excess in a Child

554

(1)

Back to the Insert Member Function

555

(2)

Employing Top-Down Design

557

(1)

Removing an Item from a B-Tree

557

(1)

The Loose Erase from a B-Tree

558

(2)

A Private Member Function to Fix a Shortage in a Child

560

(3)

Removing the Biggest Item from a B-Tree

563

(1)

Programming Tip: Write and Test Small Pieces

563

(1)

Programming Tip: Consider Using the STL Vector

564

(1)

External B-Trees

564

(1)

Self-Test Exercises for Section 11.2

565

(1)

Trees, Logs, and Time Analysis

566

(9)

Time Analysis for Binary Search Trees

567

(1)

Time Analysis for Heaps

567

(2)

Logarithms

569

(1)

Logarithmic Algorithms

570

(1)

Self-Test Exercises for Section 11.3

571

(1)

Chapter Summary

571

(1)

Solutions to Self-Test Exercises

572

(2)

Programming Projects

574

(1)

Searching

575

(47)

Serial Search and Binary Search

576

(14)

Serial Search

576

(1)

Serial Search---Analysis

576

(2)

Binary Search

578

(1)

Binary Search---Design

579

(2)

Pitfall: Common Indexing Errors in Binary Search Implementations

581

(1)

Binary Search---Analysis

582

(4)

Standard Library Search Functions

586

(1)

Functions for Sorted Ranges

586

(2)

Functions for Unsorted Ranges

588

(1)

The STL search Function

588

(2)

Self-Test Exercises for Section 12.1

590

(1)

Open-Address Hashing

590

(17)

Introduction to Hashing

590

(3)

The Table Class---Specification

593

(2)

The Table Class---Design

595

(3)

Programming Tip: Using size_t Can Indicate a Value's Purpose

598

(1)

The Table ADT---Implementation

598

(6)

C++ Feature: Inline Functions in the Implementation File

604

(1)

Choosing a Hash Function to Reduce Collisions

604

(1)

Double Hashing to Reduce Clustering

605

(1)

Self-Test Exercises for Section 12.2

606

(1)

Chained Hashing

607

(2)

Self-Test Exercises for Section 12.3

609

(1)

Time Analysis of Hashing

609

(3)

The Load Factor of a Hash Table

609

(3)

Self-Test Exercises for Section 12.4

612

(1)

Programming Project: A Table Class with STL Vectors

612

(4)

A New Table Class

612

(1)

Using Vectors in the New Table

613

(1)

Template Parameters That Are Constants

613

(1)

Template Parameters That Are Functions

613

(1)

Implementing the New Table Class

614

(1)

Self-Test Exercises for Section 12.5

615

(1)

Maps and Multimaps from the STL

616

(6)

Chapter Summary

617

(1)

Solutions to Self-Test Exercises

617

(3)

Programming Projects

620

(2)

Sorting

622

(51)

Quadratic Sorting Algorithms

623

(12)

Selectionsort---Specification

623

(1)

Selectionsort---Design

623

(2)

Selectionsort---Implementation

625

(2)

Selectionsort---Analysis

627

(2)

Programming Tip: Rough Estimates Suffice for Big-O

629

(1)

Insertionsort

629

(4)

Insertionsort---Analysis

633

(2)

Self-Test Exercises for Section 13.1

635

(1)

Recursive Sorting Algorithms

635

(20)

Divide-and-Conquer Using Recursion

635

(1)

C++ Feature: Specifying a Subarray with Pointer Arithmetic

636

(2)

Mergesort

638

(1)

The Merge Function

639

(5)

Dynamic Memory Usage in Mergesort

644

(1)

Mergesort---Analysis

644

(2)

Mergesort for Files

646

(1)

Quicksort

646

(2)

The Partition Function

648

(4)

Quicksort---Analysis

652

(2)

Quicksort---Choosing a Good Pivot Element

654

(1)

Self-Test Exercises for Section 13.2

654

(1)

An O(n log n) Algorithm Using a Heap

655

(10)

Heapsort

655

(5)

Making the Heap

660

(3)

Reheapification Downward

663

(1)

Heapsort---Analysis

664

(1)

Self-Test Exercises for Section 13.3

665

(1)

Sorting with Library Functions and Random Acesss Iterators

665

(8)

The Original C qsort Function

665

(1)

The STL Sort Function

666

(1)

Writing a Sort Function That Uses Iterators

667

(1)

Chapter Summary

668

(1)

Solutions to Self-Test Exercises

669

(1)

Programming Projects

670

(3)

Derived Classes and Inheritance

673

(49)

Derived Classes

674

(8)

How to Declare a Derived Class

676

(1)

The Automatic Constructors of a Derived Class

677

(1)

Using a Derived Class

678

(2)

The Automatic Assignment Operator for a Derived Class

680

(1)

The Automatic Destructor of a Derived Class

680

(1)

Overriding Inherited Member Functions

681

(1)

Programming Tip: Make the Overriding Function Call the Original

682

(1)

Self-Test Exercises for Section 14.1

682

(1)

Simulation of an Ecosystem

682

(20)

Implementing Part of the Organism Object Hierarchy

683

(1)

The Organism Class

683

(3)

The Animal Class: A Derived Class with New Private Member Variables

686

(1)

How to Provide a New Constructor for a Derived Class

686

(2)

The Other Animal Member Functions

688

(4)

Self-Test Exercises for Middle of Section 14.2

692

(1)

The Herbivore Class

693

(2)

The Pond Life Simulation Program

695

(5)

Pondlife---Implementation Details

700

(1)

Using the Pond Model

700

(1)

Dynamic Memory Usage

701

(1)

Self-Test Exercises for Section 14.2

702

(1)

Virtual Member Functions and a Game Class

702

(20)

Introduction to the Game Class

702

(4)

Protected Members

706

(1)

Virtual Member Functions

706

(2)

Virtual Destructors

708

(1)

The Protected Virtual Member Functions of the Game Class

708

(1)

A Derived Class to Play Connect Four

709

(1)

The Private Member Variables of the Connect Four Class

709

(2)

The Connect Four Constructor and Restart Function

711

(1)

Three Connect Four Functions That Deal with the Game's Status

711

(1)

Three Connect Four Functions That Deal with Moves

712

(1)

The Clone Function

713

(1)

Writing Your Own Derived Games from the Game Class

714

(1)

The Game Class's Play Algorithm with Minimax

714

(2)

Self-Test Exercises for Section 14.3

716

(2)

Chapter Summary

718

(1)

Amazon no longer offers textbook rentals. We do!

Data Structures and Other Objects Using C++

Data Structures and Other Objects Using C++

9780321197160

032119716X

Summary

Table of Contents

Supplemental Materials

Write a Review

Amazon no longer offers textbook rentals. We do!

Data Structures and Other Objects Using C++

Data Structures and Other Objects Using C++

9780321197160

032119716X

Summary

Table of Contents

Supplemental Materials

Write a Review

Related Products