Data Structures and Problem Solving Using C++,9780201612509

Data Structures and Problem Solving Using C++

by
Edition: 2nd
ISBN13: 9780201612509
ISBN10: 020161250X
Format: Paperback
Pub. Date: 1999-11-23
Publisher(s): Pearson
  • Free Shipping Icon

    This Item Qualifies for Free Shipping!*

    *Excludes marketplace orders.

List Price: $181.99

Buy New

Arriving Soon. Will ship when available.
$173.32
Add to Cart

Buy Used

Arriving Soon. Will ship when available.
$129.99
Add to Cart

Rent Textbook

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

eTextbook

We're Sorry
Not Available

Buy from our Marketplace starting at $3.39

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

Experienced author and teacher Mark Allen Weiss now brings his expertise to the CS2 course with Algorithms, Data Structures, and Problem Solving with C++, which introduces both data structures and algorithm design from the viewpoint of abstract thinking and problem solving. The author chooses C++ as the language of implementation, but the emphasis of the book itself remains on uniformly accepted CS2 topics such as pointers, data structures, algorithm analysis, and increasingly complex programming projects. Algorithms, Data Structures, and Problem Solving with C++ is the first CS2 textbook to clearly separate the interface and implementation of data structures. The interface and running time of data structures are presented first, and students have the opportunity to use the data structures in a host of practical examples before being introduced to the implementations. This unique approach enhances the students' ability to think abstractly.

Author Biography

Mark Allen Weiss is a Professor in the School of Computer Science at Florida International University. He received his Ph.D. in Computer Science from Princeton University where he studied under Robert Sedgewick. Dr.Weiss has received FIU's Excellence in Research Award, as well as the Teaching Incentive Program Award, which was established by the Florida Legislature to recognize teaching excellence. Mark Allen Weiss is on the Advanced Placement Computer Science Development Committee. He is the successful author of Algorithms, Data Structures, and Problem Solving with C++ and the series Data Structures and Algorithm Analysis in Pascal, Ada, C, and C++, with Addison-Wesley.



020161250XAB04062001

Table of Contents

Part I: Objects and C++
Arrays, Pointers, and Structures
3(38)
What Are Pointers, Arrays, and Structures?
3(1)
Arrays and Strings
4(11)
First-Class Versus Second-Class Objects
4(2)
Using the vector
6(1)
Resizing a vector
7(4)
push_back: size and capacity
11(1)
Parameter-Passing Mechanisms
11(2)
Primitive Arrays of Constants
13(1)
Multidimensional Arrays
14(1)
The Standard Library string Type
14(1)
Pointer Syntax in C++
15(5)
Dynamic Memory Management
20(4)
The new Operator
21(1)
Garbage Collection and delete
21(1)
Stale Pointers, Double Deletion, and More
22(2)
Reference Variables
24(2)
Structures
26(15)
Pointers to Structures
28(1)
Exogenous Versus Indigenous Data and Shallow Versus Deep Copying
29(1)
Noncontiguous Lists: Linked Lists
30(2)
Summary
32(1)
Objects of the Game
32(2)
Common Errors
34(1)
On the Internet
35(1)
Exercises
35(3)
References
38(3)
Objects and Classes
41(56)
What Is Object-Oriented Programming?
41(2)
Basic class Syntax
43(14)
Class Members
43(2)
Extra Constructor Syntax and Accessors
45(3)
Separation of Interface and Implementation
48(3)
The Big Three: Destructor, Copy Constructor, and operator=
51(6)
Default Constructor
57(1)
Additional C++ Class Features
57(11)
Initialization Versus Assignment in the Constructor Revisited
61(2)
Type Conversions
63(1)
Operator Overloading
64(3)
Input and Output and Friends
67(1)
Some Common Idioms
68(4)
Avoiding Friends
70(1)
Static Class Members
71(1)
The enum Trick for Integer Class Constants
71(1)
Exceptions
72(1)
A string Class
73(9)
Recap: What Gets Called and What Are the Defaults?
82(2)
Composition
84(13)
Summary
85(1)
Objects of the Game
85(2)
Common Errors
87(2)
On the Internet
89(1)
Exercises
90(6)
References
96(1)
Templates
97(22)
What Is a Template?
97(1)
Function Templates
98(2)
A Sorting Function Template
100(3)
Class Templates
103(5)
A MemoryCell Template
103(5)
Implementing the vector Class Template
108(1)
Templates of Templates: A matrix Class
108(4)
The Data Members, Constructor, and Basic Accessors
111(1)
operator []
112(1)
Destructor, Copy Assignment, and Copy Constructor
112(1)
Fancy Templates
112(2)
Multiple Template Parameters
112(1)
Default Template Parameters
113(1)
The Reserved Word typename
113(1)
Bugs Associated with Templates
114(5)
Bad Error Messages and Inconsistent Rules
114(1)
Template-Matching Algorithms
114(1)
Nested Classes in a Template
114(1)
Static Members in Class Templates
115(1)
Summary
115(1)
Objects of the Game
115(1)
Common Errors
115(1)
On the Internet
116(1)
Exercises
117(2)
Inheritance
119(36)
What Is Inheritance?
119(4)
Inheritance Basics
123(13)
Visibility Rules
124(1)
The Constructor and Base Class Initialization
125(1)
Adding Members
126(2)
Overriding a Method
128(1)
Static and Dynamic Binding
129(2)
The Default Constructor, Copy Constructor, Copy Assignment Operator, and Destructor
131(1)
Constructors and Destructors: Virtual or Not Virtual?
132(1)
Abstract Methods and Classes
133(3)
Example: Expanding the Shape Class
136(6)
Tricky C++ Details
142(5)
Static Binding of Parameters
142(1)
Default Parameters
143(1)
Derived Class Methods Hide Base Class Methods
144(1)
Compatible Return Types for Overridden Methods
145(1)
Private Inheritance
146(1)
Friends
146(1)
Call by Value and Polymorphism Do Not Mix
146(1)
Multiple Inheritance
147(8)
Summary
149(1)
Objects of the Game
149(1)
Common Errors
150(2)
On the Internet
152(1)
Exercises
152(2)
References
154(1)
Design Patterns
155(38)
What Is a Pattern?
155(1)
The Functor (Function Objects)
156(6)
Adapters and Wrappers
162(8)
Wrapper for Pointers
162(6)
A Constant Reference Wrapper
168(1)
Adapters: Changing an Interface
169(1)
Iterators
170(9)
Iterator Design 1
171(3)
Iterator Design 2
174(1)
Inheritance-Based Iterators and Factories
174(5)
Composite (Pair)
179(1)
Observer
179(14)
Summary
184(1)
Objects of the Game
184(1)
Common Errors
185(1)
On the Internet
186(1)
Exercises
186(4)
References
190(3)
Part II: Algorithms and Building Blocks
Algorithm Analysis
193(38)
What Is Algorithm Analysis?
193(5)
Examples of Algorithm Running Times
198(1)
The Maximum Contiguous Subsequence Sum Problem
199(7)
The Obvious O(N3) Algorithm
200(3)
An Improved O(N2) Algorithm
203(1)
A Linear Algorithm
204(2)
General Big-Oh Rules
206(5)
The Logarithm
211(3)
Static Searching Problem
214(5)
Sequential Search
214(1)
Binary Search
215(2)
Interpolation Search
217(2)
Checking an Algorithm Analysis
219(1)
Limitations of Big-Oh Analysis
220(11)
Summary
221(1)
Objects of the Game
221(1)
Common Errors
222(1)
On the Internet
223(1)
Exercises
223(5)
References
228(3)
The Standard Template Library
231(34)
Introduction
232(1)
Stacks and Queues
233(4)
Stacks
233(2)
Stacks and Computer Languages
235(1)
Queues
236(1)
Containers and Iterators
237(3)
Containers
238(1)
The iterator
238(2)
STL Algorithms
240(5)
STL Function Objects
240(3)
Binary Search
243(1)
Sorting
244(1)
Implementation of vector with an Iterator
245(2)
Sequences and Linked Lists
247(2)
The list Class
247(2)
Stacks and Queues
249(1)
Sets
249(2)
Maps
251(2)
Priority Queues
253(12)
Summary
257(1)
Objects of the Game
257(2)
Common Errors
259(1)
On the Internet
259(1)
Exercises
260(4)
References
264(1)
Recursion
265(56)
What Is Recursion?
265(2)
Background: Proofs by Mathematical Induction
267(2)
Basic Recursion
269(15)
Printing Numbers in Any Base
271(3)
Why It Works
274(1)
How It Works
275(1)
Too Much Recursion Can Be Dangerous
276(2)
Preview of Trees
278(1)
Additional Examples
279(5)
Numerical Applications
284(8)
Modular Arithmetic
285(1)
Modular Exponentiation
285(2)
Greatest Common Divisor and Multiplicative Inverses
287(2)
The RSA Cryptosystem
289(3)
Divide-and-Conquer Algorithms
292(11)
The Maximum Contiguous Subsequence Sum Problem
293(4)
Analysis of a Basic Divide-and-Conquer Recurrence
297(4)
A General Upper Bound for Divide-and-Conquer Running Times
301(2)
Dynamic Programming
303(5)
Backtracking
308(13)
Summary
310(2)
Objects of the Game
312(1)
Common Errors
313(1)
On the Internet
314(1)
Exercises
314(5)
References
319(2)
Sorting Algorithms
321(44)
Why Is Sorting Important?
322(1)
Preliminaries
323(1)
Analysis of the Insertion Sort and Other Simple Sorts
324(2)
Shellsort
326(4)
Performance of Shellsort
328(2)
Mergesort
330(4)
Linear-Time Merging of Sorted Arrays
330(2)
The Mergesort Algorithm
332(2)
Quicksort
334(14)
The Quicksort Algorithm
335(2)
Analysis of Quicksort
337(3)
Picking the Pivot
340(2)
A Partitioning Strategy
342(2)
Keys Equal to the Pivot
344(1)
Median-of-Three Partitioning
345(1)
Small Arrays
346(1)
C++ Quicksort Routine
346(2)
Quickselect
348(1)
A Lower Bound for Sorting
349(3)
Indirect Sorting
352(13)
Using Pionters to Reduce Comparable Copies to 2N
352(1)
Avoiding the Extra Array
353(2)
Summary
355(1)
Objects of the Game
356(1)
Common Errors
357(1)
On the Internet
357(1)
Exercises
358(5)
References
363(2)
Randomization
365(24)
Why Do We Need Random Numbers?
365(1)
Random Number Generators
366(5)
Nonuniform Random Numbers
371(2)
Generating a Random Permutation
373(2)
Randomized Algorithms
375(3)
Randomized Primality Testing
378(11)
Summary
380(2)
Objects of the Game
382(1)
Common Errors
383(1)
On the Internet
383(1)
Exercises
383(3)
References
386(3)
Part III: Applications
Fun and Games
389(20)
Word Search Puzzles
389(6)
Theory
390(1)
C++ Implementation
391(4)
The Game of Tic-Tac-toe
395(14)
Alpha-Beta Pruning
397(1)
Transposition Tables
398(6)
Computer Chess
404(1)
Summary
405(1)
Objects of the Game
405(1)
Common Errors
406(1)
On the Internet
406(1)
Exercises
406(2)
References
408(1)
Stacks and Compilers
409(30)
Balanced-Symbol Checker
409(11)
Basic Algorithm
409(2)
Implementation
411(9)
A Simple Calculator
420(19)
Postfix Machines
421(1)
Infix to Postfix Conversion
422(2)
Implementation
424(8)
Expression Trees
432(3)
Summary
435(1)
Objects of the Game
435(1)
Common Errors
436(1)
On the Internet
436(1)
Exercises
436(2)
References
438(1)
Utilities
439(32)
File Compression
439(22)
Prefix Codes
440(2)
Huffman's Algorithm
442(3)
Implementation
445(16)
A Cross-Reference Generator
461(10)
Basic Ideas
461(1)
C++ Implementation
462(4)
Summary
466(1)
Objects of the Game
466(1)
Common Errors
466(1)
On the Internet
467(1)
Exercises
467(3)
References
470(1)
Simulation
471(18)
The Josephus Problem
471(4)
The Simple Solution
473(1)
A More Efficient Algorithm
473(2)
Event-Driven Simulation
475(14)
Basic Ideas
477(1)
Example: A Modern Bank Simulation
478(8)
Summary
486(1)
Objects of the Game
486(1)
Common Errors
486(1)
On the Internet
486(1)
Exercises
486(3)
Graphs and Paths
489(48)
Definitions
489(14)
Representation
491(12)
Unweighted Shortest-Path Problem
503(6)
Theory
504(5)
C++ Implementation
509(1)
Positive-Weighted, Shortest-Path Problem
509(5)
Theory: Dijkstra's Algorithm
509(4)
C++ Implementation
513(1)
Negative-Weighted, Shortest-Path Problem
514(3)
Theory
514(3)
C++ Implementation
517(1)
Path Problems in Acyclic Graphs
517(20)
Topological Sorting
517(3)
Theory of the Acyclic Shortest-Path Algorithm
520(2)
C++ Implementation
522(1)
An Application: Critical-Path Analysis
522(4)
Summary
526(1)
Objects of the Game
527(1)
Common Errors
528(1)
On the Internet
529(1)
Exercises
529(4)
References
533(4)
Part IV: Implementations
Stacks and Queues
537(28)
Dynamic Array Implementations
537(11)
Stacks
538(3)
Queues
541(7)
Linked List Implementations
548(9)
Stacks
548(5)
Queues
553(4)
Comparison of the Two Methods
557(1)
The STL Stack and Queue Adapters
558(1)
Double-Ended Queues
558(7)
Summary
559(2)
Objects of the Game
561(1)
Common Errors
561(1)
On the Internet
561(1)
Exercises
562(3)
Linked Lists
565(40)
Basic Ideas
565(5)
Header Nodes
567(2)
Iterator Classes
569(1)
C++ Implementation
570(9)
Doubly Linked Lists and Circularly Linked Lists
579(3)
Sorted Linked Lists
582(1)
Implementing the STL list Class
582(23)
Summary
597(1)
Objects of the Game
597(1)
Common Errors
598(1)
On the Internet
598(1)
Exercises
599(6)
Trees
605(36)
General Trees
605(6)
Definitions
605(2)
Implementation
607(1)
An Application: File Systems
608(3)
Binary Trees
611(8)
Recursion and Trees
619(3)
Tree Traversal: Iterator Classes
622(19)
Postorder Traversal
624(6)
Inorder Traversal
630(1)
Preorder Traversal
630(1)
Level-Order Traversals
630(3)
Summary
633(3)
Objects of the Game
636(1)
Common Errors
637(1)
On the Internet
637(1)
Exercises
637(4)
Binary Search Trees
641(84)
Basic Ideas
641(11)
The Operations
642(2)
C++ Implementation
644(8)
Order Statistics
652(5)
C++ Implementation
653(4)
Analysis of Binary Search Tree Operations
657(4)
AVL Trees
661(9)
Properties
662(2)
Single Rotation
664(3)
Double Rotation
667(3)
Summary of AVL Insertion
670(1)
Red-Black Trees
670(15)
Bottom-Up Insertion
672(2)
Top-Down Red-Black Trees
674(2)
C++ Implementation
676(4)
Top-Down Deletion
680(5)
AA-Trees
685(8)
Insertion
686(2)
Deletion
688(2)
C++ Implementation
690(3)
Implementing the STL set and map Classes
693(14)
B-Trees
707(18)
Summary
714(1)
Objects of the Game
715(2)
Common Errors
717(1)
On the Internet
717(1)
Exercises
718(3)
References
721(4)
Hash Tables
725(30)
Basic Ideas
725(2)
Hash Function
727(2)
Linear Probing
729(6)
Naive Analysis of Linear Probing
731(1)
What Really Happens: Primary Clustering
732(1)
Analysis of the find Operation
733(2)
Quadratic Probing
735(11)
C++ Implementation
739(6)
Analysis of Quadratic Probing
745(1)
Separate Chaining Hashing
746(1)
Hash Tables Versus Binary Search Trees
746(1)
Hashing Applications
747(8)
Summary
747(1)
Objects of the Game
748(1)
Common Errors
749(1)
On the Internet
749(1)
Exercises
749(3)
References
752(3)
A Priority Queue: The Binary Heap
755(40)
Basic Ideas
755(6)
Structure Property
756(2)
Heap-Order Property
758(1)
Allowed Operations
759(2)
Implementation of the Basic Operations
761(5)
The insert Operation
762(1)
The deleteMin Operation
763(3)
The buildHeap Operation: Linear-Time Heap Construction
766(5)
STL priority_queue Implementation
771(2)
Advanced Operations; decreaseKey and merge
773(1)
Internal Sorting: Heapsort
773(5)
External Sorting
778(17)
Why We Need New Algorithms
778(1)
Model for External Sorting
778(1)
The Simple Algorithm
779(2)
Multiway Merge
781(1)
Plyphase Merge
782(1)
Replacement Selection
783(2)
Summary
785(1)
Objects of the Game
785(1)
Common Errors
786(1)
On the Internet
787(1)
Exercises
787(4)
References
791(4)
Part V: Advanced Data Structures
Splay Trees
795(28)
Self-Adjustement and Amortized Analysis
795(4)
Amortized Time Bounds
797(1)
A Simple Self-Adjusting Strategy (That Does Not Work)
797(2)
The Basic Bottom-Up Splay Tree
799(3)
Basic Splay Tree Operations
802(1)
Analysis of Bottom-Up Splaying
803(6)
Proof of the Splayin Bound
806(3)
Top-Down Splay Trees
809(3)
Implementation of Top-Down Splay Trees
812(6)
Compaison of the Splay Tree with Other Search Trees
818(5)
Summary
819(1)
Objects of the Game
819(1)
Common Errors
820(1)
On the Internet
820(1)
Exercises
820(2)
References
822(1)
Merging Priority Queues
823(22)
The Skew Heap
823(5)
Merging Is Fundamental
823(1)
Simplistic Merginal of Heap-Ordered Trees
824(1)
The Skew Heap: A Simple Modification
825(1)
Analysis of the Skew Heap
826(2)
The Pairing Heap
828(17)
Pairing Heap Operations
829(1)
Implementation of the Pairing Heap
830(6)
Application: Dijkstra's Shortest Weighted Path Algorithm
836(4)
Summary
840(1)
Objects of the Game
840(1)
Common Errors
841(1)
On the Internet
841(1)
Exercises
841(1)
References
842(3)
The Disjoint Set Class
845(32)
Equivalence Relations
845(1)
Dynamic Equivalence and Two Applications
846(11)
Application: Generating Mazes
847(3)
Application: Minimum Spanning Trees
850(3)
Application: The Nearest Common Ancestor Problem
853(4)
The Quick-Find Algorithm
857(1)
The Quick-Union Algorithm
858(5)
Smart Union Algorithms
860(2)
Path Compression
862(1)
C++ Implementation
863(2)
Worst Case for Union-by-Rank and Path Compression
865(12)
Analysis of the Union/Find Algorithm
866(7)
Summary
873(1)
Objects of the Game
873(2)
Common Errors
875(1)
On the Internet
875(1)
Exercises
875(2)
References
877
Appendices
Appendix A Miscellaneous C++ Details
A-3
A.1 None of the Compilers Implement and Standard
A-3
A.2 Usual C++ Operators
A-4
A.2.1 Autoincrement and Autodecrement Operators
A-4
A.2.2 Type Conversions
A-5
A.2.3 Bitwise Operators
A-6
A.2.4 The Conditional Operator
A-8
A.3 Command-Line Arguments
A-8
A.4 Input and Output
A-9
A.4.1 Basic Stream Operations
A-9
A.4.2 Sequenetial Filees
A-13
A.4.3 String Streams
A-13
A.5 Namespace
A-15
A.6 New C++ Features
A-17
Common C++ Errors
A-17
Appendix B Operators
A-21
Appendix C Some Library Routines
A-23
C.1 Routines Declared in <ctype.h> and <cctype>
A-23
C.2 Costants Declared in <limits.h> and <climits>
A-24
C.3 Routines Declared in <math.h> and <cmath>
A-25
C.4 Routines Declared in <stdlib.h> and <cstdlib>
A-26
Appendix D Primitive Arrays in C++
A-27
D.1 Primitive Arrays
A-27
D.1.1 The C++ Implementation: An Array Name Is a Pointer
28
D.1.2 Multidimensional Arrays
A-31
D.1.3 The char * Type, const Pointers, and Constant Strings
A-31
D.2 Dynamic Allocation of Arrays: new [ ] and delete [ ]
A-35
D.3 Pointer Arithmetic, Pointer Hopping, and Primitive Iteration
A-41
D.3.1 Implications of the Precedence of *, &, and [ ]
A-41
D.3.2 What Pointer Arithmetic Means
A-42
D.3.3 A Pointer-Hopping Example
A-44
D.3.4 Is Pointer Hopping Worthwhile?
A-45
Common C++ Errors
A-47
On the Internet
A-47
Index I-1

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.