Data Abstraction and Problem Solving with C++,9780321247254

Data Abstraction and Problem Solving with C++

by
Edition: 4th
ISBN13: 9780321247254
ISBN10: 0321247256
Format: Paperback
Pub. Date: 2007-01-01
Publisher(s): Addison Wesley
Upgraded Edition: Click here!
  • Free Shipping Icon

    This Item Qualifies for Free Shipping!*

    *Excludes marketplace orders.

List Price: $127.26

Rent Textbook

Select for Price
Add to Cart
There was a problem. Please try again later.

New Textbook

We're Sorry
Sold Out

Used Textbook

We're Sorry
Sold Out

eTextbook

We're Sorry
Not Available

Buy from our Marketplace starting at $5.49

How Marketplace Works:

  • This item is offered by an independent seller and not shipped from our warehouse
  • Item details like edition and cover design may differ from our description; see seller's comments before ordering.
  • Sellers much confirm and ship within two business days; otherwise, the order will be cancelled and refunded.
  • Marketplace purchases cannot be returned to eCampus.com. Contact the seller directly for inquiries; if no response within two days, contact customer service.
  • Additional shipping costs apply to Marketplace purchases. Review shipping costs at checkout.

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.

Table of Contents

Preface v
Chapter Dependency Chart vii
PART I Problem-Solving Techniques 1(278)
CHAPTER 1 Principles of Programming and Software Engineering
2(51)
1.1 Problem Solving and Software Engineering
3(12)
What Is Problem Solving?
3(1)
The Life Cycle of Software
4(9)
What Is a Good Solution?
13(2)
1.2 Achieving a Modular Design
15(11)
Abstraction and Information Hiding
15(2)
Object-Oriented Design
17(3)
Top-Down Design
20(1)
General Design Guidelines
21(1)
Modeling Object-Oriented Designs Using UML
21(4)
Advantages of an Object-Oriented Approach
25(1)
1.3 A Summary of Key Issues in Programming
26(20)
Modularity
27(1)
Modifiability
28(2)
Ease of Use
30(1)
Fail-Safe Programming
31(6)
Style
37(7)
Debugging
44(2)
Summary
46(1)
Cautions
47(1)
Self-Test Exercises
48(1)
Exercises
48(2)
Programming Problems
50(3)
CHAPTER 2 Recursion: The Mirrors
53(60)
2.1 Recursive Solutions
54(21)
A Recursive Valued Function: The Factorial of n
57(6)
A Recursive void Function: Writing a String Backward
63(12)
2.2 Counting Things
75(8)
Multiplying Rabbits (The Fibonacci Sequence)
75(3)
Organizing a Parade
78(2)
Mr. Spock's Dilemma (Choosing k Out of n Things)
80(3)
2.3 Searching an Array
83(9)
Finding the Largest Item in an Array
83(1)
Binary Search
84(4)
Finding the k th Smallest Item of an Array
88(4)
2.4 Organizing Data
92(5)
The Towers of Hanoi
92(5)
2.5 Recursion and Efficiency
97(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

An electronic version of this book is available through VitalSource.

This book is viewable on PC, Mac, iPhone, iPad, iPod Touch, and most smartphones.

By purchasing, you will be able to view this book online, as well as download it, for the chosen number of days.

Digital License

You are licensing a digital product for a set duration. Durations are set forth in the product description, with "Lifetime" typically meaning five (5) years of online access and permanent download to a supported device. All licenses are non-transferable.

More details can be found here.

A downloadable version of this book is available through the eCampus Reader or compatible Adobe readers.

Applications are available on iOS, Android, PC, Mac, and Windows Mobile platforms.

Please view the compatibility matrix prior to purchase.