Amazon no longer offers textbook rentals. We do!

Data Abstraction and Problem Solving with C++

by: Carrano, Frank

Data Abstraction and Problem Solving with C++

by: Carrano, Frank

ISBN 13:
9780321247254
ISBN 10:
0321247256
Edition: 4th
Format: Paperback
Copyright: 01/01/2007
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 classic book has been revised to further enhance its focus on data abstraction and data structures using C++. In this new edition, the clarity of the C++ language is enhanced, along with coverage of the latest C++ features, including stronger use of the Standard Template Library. This edition continues with Frank Carrano's lucid writing style, widespread use of examples, and flexible coverage of important topics.

Preface

Chapter Dependency Chart

vii

PART I Problem-Solving Techniques

(278)

CHAPTER 1 Principles of Programming and Software Engineering

(51)

1.1 Problem Solving and Software Engineering

(12)

What Is Problem Solving?

(1)

The Life Cycle of Software

(9)

What Is a Good Solution?

(2)

1.2 Achieving a Modular Design

(11)

Abstraction and Information Hiding

(2)

Object-Oriented Design

(3)

Top-Down Design

(1)

General Design Guidelines

(1)

Modeling Object-Oriented Designs Using UML

(4)

Advantages of an Object-Oriented Approach

(1)

1.3 A Summary of Key Issues in Programming

(20)

Modularity

(1)

Modifiability

(2)

Ease of Use

(1)

Fail-Safe Programming

(6)

Style

(7)

Debugging

(2)

Summary

(1)

Cautions

(1)

Self-Test Exercises

(1)

Exercises

(2)

Programming Problems

(3)

CHAPTER 2 Recursion: The Mirrors

(60)

2.1 Recursive Solutions

(21)

A Recursive Valued Function: The Factorial of n

(6)

A Recursive void Function: Writing a String Backward

(12)

2.2 Counting Things

(8)

Multiplying Rabbits (The Fibonacci Sequence)

(3)

Organizing a Parade

(2)

Mr. Spock's Dilemma (Choosing k Out of n Things)

(3)

2.3 Searching an Array

(9)

Finding the Largest Item in an Array

(1)

Binary Search

(4)

Finding the k th Smallest Item of an Array

(4)

2.4 Organizing Data

(5)

The Towers of Hanoi

(5)

2.5 Recursion and Efficiency

(5)

Summary

102

(1)

Cautions

103

(1)

Self-Test Exercises

104

(1)

Exercises

104

(8)

Programming Problems

112

(1)

CHAPTER 3 Data Abstraction: The Walls

113

(51)

3.1 Abstract Data Types

114

(5)

3.2 Specifying ADTs

119

(14)

The ADT List

119

(5)

The ADT Sorted List

124

(2)

Designing an ADT

126

(5)

Axioms (Optional)

131

(2)

3.3 Implementing ADTs

133

(23)

C++ Classes

135

(9)

C++ Namespaces

144

(2)

An Array-Based Implementation of the ADT List

146

(6)

C++ Exceptions

152

(2)

An Implementation of the ADT List Using Exceptions

154

(2)

Summary

156

(1)

Cautions

157

(1)

Self-Test Exercises

158

(1)

Exercises

159

(3)

Programming Problems

162

(2)

CHAPTER 4 Linked Lists

164

(78)

4.1 Preliminaries

165

(12)

Pointers

166

(6)

Dynamic Allocation of Arrays

172

(3)

Pointer-Based Linked Lists

175

(2)

4.2 Programming with Linked Lists

177

(32)

Displaying the Contents of a Linked List

178

(1)

Deleting a Specified Node from a Linked List

179

(3)

Inserting a Node into a Specified Position of a Linked List

182

(6)

A Pointer-Based Implementation of the ADT List

188

(8)

Comparing Array-Based and Pointer-Based Implementations

196

(2)

Saving and Restoring a Linked List by Using a File

198

(4)

Passing a Linked List to a Function

202

(1)

Processing Linked Lists Recursively

203

(5)

Objects as Linked List Data

208

(1)

4.3 Variations of the Linked List

209

(6)

Circular Linked Lists

209

(2)

Dummy Head Nodes

211

(1)

Doubly Linked Lists

211

(4)

4.4 Application: Maintaining an Inventory

215

(6)

4.5 The C++ Standard Template Library

221

(7)

Containers

221

(1)

Iterators

222

(2)

The Standard Template Library Class list

224

(4)

Summary

228

(2)

Cautions

230

(2)

Self-Test Exercises

232

(3)

Exercises

235

(3)

Programming Problems

238

(4)

CHAPTER 5 Recursion as a Problem-Solving Technique

242

(37)

5.1 Backtracking

243

(7)

The Eight Queens Problem

243

(2)

Implementing Eight Queens Using the STL Class vector

245

(5)

5.2 Defining Languages

250

(15)

The Basics of Grammars

251

(1)

Two Simple Languages

252

(3)

Algebraic Expressions

255

(10)

5.3 The Relationship Between Recursion and Mathematical Induction

265

(3)

The Correctness of the Recursive Factorial Function

265

(1)

The Cost of Towers of Hanoi

266

(2)

Summary

268

(1)

Cautions

269

(1)

Self-Test Exercises

269

(1)

Exercises

269

(4)

Programming Problems

273

(6)

PART II Problem Solving with Abstract Data Types

279

(534)

CHAPTER 6 Stacks

280

(58)

6.1 The Abstract Data Type Stack

281

(6)

Developing an ADT During the Design of a Solution

281

(6)

6.2 Simple Applications of the ADT Stack

287

(4)

Checking for Balanced Braces

287

(3)

Recognizing Strings in a Language

290

(1)

6.3 Implementations of the ADT Stack

291

(14)

An Array-Based Implementation of the ADT Stack

292

(4)

A Pointer-Based Implementation of the ADT Stack

296

(3)

An Implementation That Uses the ADT List

299

(4)

Comparing Implementations

303

(1)

The STL Class stack

303

(2)

6.4 Application: Algebraic Expressions

305

(6)

Evaluating Postfix Expressions

306

(1)

Converting Infix Expressions to Equivalent Postfix Expressions

307

(4)

6.5 Application: A Search Problem

311

(12)

A Nonrecursive Solution That Uses a Stack

312

(8)

A Recursive Solution

320

(3)

6.6 The Relationship Between Stacks and Recursion

323

(2)

Summary

325

(1)

Cautions

326

(1)

Self-Test Exercises

326

(1)

Exercises

327

(4)

Programming Problems

331

(7)

CHAPTER 7 Queues

338

(46)

7.1 The Abstract Data Type Queue

339

(2)

7.2 Simple Applications of the ADT Queue

341

(3)

Reading a String of Characters

342

(1)

Recognizing Palindromes

343

(1)

7.3 Implementations of the ADT Queue

344

(19)

A Pointer-Based Implementation

344

(6)

An Array-Based Implementation

350

(6)

An Implementation That Uses the ADT List

356

(3)

The STL Class queue

359

(3)

Comparing Implementations

362

(1)

7.4 A Summary of Position-Oriented ADTs

363

(1)

7.5 Application: Simulation

364

(10)

Summary

374

(1)

Cautions

375

(1)

Self-Test Exercises

375

(1)

Exercises

376

(4)

Programming Problems

380

(4)

CHAPTER 8 Advanced C++ Topics

384

(59)

8.1 Inheritance Revisited

385

(11)

Public, Private, and Protected Inheritance

391

(2)

Is-a , Has-a , and As-a Relationships

393

(3)

8.2 Virtual Functions and Late Binding

396

(10)

Abstract Base Classes

401

(5)

8.3 Friends

406

(2)

8.4 The ADTs List and Sorted List Revisited

408

(8)

Implementations of the ADT Sorted List That Use the ADT List

411

(5)

8.5 Class Templates

416

(6)

8.6 Overloaded Operators

422

(5)

8.7 Iterators

427

(6)

Implementing the ADT List Using Iterators

429

(4)

Summary

433

(1)

Cautions

434

(1)

Self-Test Exercises

435

(1)

Exercises

436

(4)

Programming Problems

440

(3)

CHAPTER 9 Algorithm Efficiency and Sorting

443

(56)

9.1 Measuring the Efficiency of Algorithms

444

(12)

The Execution Time of Algorithms

445

(2)

Algorithm Growth Rates

447

(1)

Order-of-Magnitude Analysis and Big O Notation

448

(5)

Keeping Your Perspective

453

(2)

The Efficiency of Searching Algorithms

455

(1)

9.2 Sorting Algorithms and Their Efficiency

456

(34)

Selection Sort

457

(4)

Bubble Sort

461

(2)

Insertion Sort

463

(2)

Mergesort

465

(6)

Quicksort

471

(11)

Radix Sort

482

(3)

A Comparison of Sorting Algorithms

485

(1)

The STL Sorting Algorithms

485

(5)

Summary

490

(1)

Cautions

491

(1)

Self-Test Exercises

492

(1)

Exercises

493

(3)

Programming Problems

496

(3)

CHAPTER 10 Trees

499

(90)

10.1 Terminology

501

(6)

10.2 The ADT Binary Tree

507

(28)

Traversals of a Binary Tree

512

(4)

Possible Representations of a Binary Tree

516

(4)

A Pointer-Based Implementation of the ADT Binary Tree

520

(15)

10.3 The ADT Binary Search Tree

535

(40)

Algorithms for the ADT Binary Search Tree Operations

540

(15)

A Pointer-Based Implementation of the ADT Binary Search Tree

555

(8)

The Efficiency of Binary Search Tree Operations

563

(5)

Treesort

568

(1)

Saving a Binary Search Tree in a File

568

(3)

The STL Search Algorithms

571

(4)

10.4 General Trees

575

(1)

Summary

576

(1)

Cautions

577

(1)

Self-Test Exercises

577

(2)

Exercises

579

(7)

Programming Problems

586

(3)

CHAPTER 11 Tables and Priority Queues

589

(64)

11.1 The ADT Table

590

(21)

Selecting an Implementation

596

(8)

A Sorted Array-Based Implementation of the ADT Table

604

(4)

A Binary Search Tree Implementation of the ADT Table

608

(3)

11.2 The ADT Priority Queue: A Variation of the ADT Table

611

(20)

Heaps

615

(10)

A Heap Implementation of the ADT Priority Queue

625

(3)

Heapsort

628

(3)

11.3 Tables and Priority Queues in the Standard Template Library

631

(13)

The STL Associative Containers

631

(9)

The STL priority_queue Class and Heap Algorithms

640

(4)

Summary

644

(1)

Cautions

645

(1)

Self-Test Exercises

645

(1)

Exercises

646

(4)

Programming Problems

650

(3)

CHAPTER 12 Advanced Implementations of Tables

653

(74)

12.1 Balanced Search Trees

654

(37)

2-3 Trees

655

(20)

2-3-4 Trees

675

(7)

Red-Black Trees

682

(3)

AVL Trees

685

(6)

12.2 Hashing

691

(23)

Hash Functions

695

(2)

Resolving Collisions

697

(9)

The Efficiency of Hashing

706

(3)

What Constitutes a Good Hash Function?

709

(2)

Table Traversal: An Inefficient Operation Under Hashing

711

(1)

Implementing a HashMap Class Using the STL

712

(2)

12.3 Data with Multiple Organizations

714

(5)

Summary

719

(2)

Cautions

721

(1)

Self-Test Exercises

721

(1)

Exercises

722

(3)

Programming Problems

725

(2)

CHAPTER 13 Graphs

727

(44)

13.1 Terminology

728

(3)

13.2 Graphs as ADTs

731

(7)

Implementing Graphs

732

(3)

Implementing a Graph Class Using the STL

735

(3)

13.3 Graph Traversals

738

(7)

Depth-First Search

739

(3)

Breadth-First Search

742

(1)

Implementing a BFS Class Using the STL

743

(2)

13.4 Applications of Graphs

745

(19)

Topological Sorting

746

(3)

Spanning Trees

749

(4)

Minimum Spanning Trees

753

(2)

Shortest Paths

755

(5)

Circuits

760

(3)

Some Difficult Problems

763

(1)

Summary

764

(1)

Cautions

765

(1)

Self-Test Exercises

765

(1)

Exercises

766

(4)

Programming Problems

770

(1)

CHAPTER 14 External Methods

771

(42)

14.1 A Look at External Storage

772

(3)

14.2 Sorting Data in an External File

775

(8)

14.3 External Tables

783

(24)

Indexing an External File

785

(5)

External Hashing

790

(3)

B-Trees

793

(11)

Traversals

804

(1)

Multiple Indexing

805

(2)

Summary

807

(1)

Cautions

807

(1)

Self-Test Exercises

808

(1)

Exercises

808

(4)

Programming Problems

812

(1)

APPENDIX A Review of C++ Fundamentals

813

(76)

A.1 Language Basics

814

(10)

Comments

814

(1)

Identifiers and Keywords

815

(1)

Fundamental Data Types

815

(1)

Variables

816

(1)

Literal Constants

817

(1)

Named Constants

818

(1)

Enumerations

818

(1)

The typedef Statement

819

(1)

Assignments and Expressions

820

(4)

A.2 Input and Output Using iostream

824

(4)

Input

824

(2)

Output

826

(1)

Manipulators

827

(1)

A.3 Functions

828

(4)

Standard Functions

831

(1)

A.4 Selection Statements

832

(2)

The if Statement

832

(1)

The switch Statement

833

(1)

A.5 Iteration Statements

834

(4)

The while Statement

835

(1)

The for Statement

836

(2)

The do Statement

838

(1)

A.6 Arrays

838

(6)

One-Dimensional Arrays

839

(2)

Multidimensional Arrays

841

(2)

Arrays of Arrays

843

(1)

A.7 Strings

844

(6)

C++ Strings

845

(2)

C Strings

847

(3)

A.8 Structures

850

(3)

Structures Within Structures

852

(1)

Arrays of Structures

852

(1)

A.9 C++ Exceptions

853

(7)

Catching Exceptions

853

(5)

Throwing Exceptions

858

(2)

A.10 File Input and Output

860

(14)

Text Files

862

(11)

Binary Files

873

(1)

A.11 Libraries

874

(2)

Avoiding Duplicate Header Files

876

(1)

A.12 A Comparison to Java

876

(3)

Summary

879

(4)

Cautions

883

(1)

Self-Test Exercises

884

(2)

Exercises

886

(2)

Programming Problems

888

(1)

APPENDIX B ASCII Character Codes

889

(1)

APPENDIX C C++ Header Files and Standard Functions

890

(7)

APPENDIX D Mathematical Induction

897

(6)

APPENDIX E Standard Template Library

903

(12)

Glossary

915

(19)

Answers to Self-Test Exercises

934

(20)

Index

954

Amazon no longer offers textbook rentals. We do!

Data Abstraction and Problem Solving with C++

Data Abstraction and Problem Solving with C++

9780321247254

0321247256

Summary

Table of Contents

Supplemental Materials

Write a Review

Amazon no longer offers textbook rentals. We do!

Data Abstraction and Problem Solving with C++

Data Abstraction and Problem Solving with C++

9780321247254

0321247256

Summary

Table of Contents

Supplemental Materials

Write a Review

Related Products