Data Structures and Problem Solving Using C++

by Weiss, Mark A.

• ISBN13: 9780201612509
• ISBN10: 020161250X
• Edition: 2nd
• Format: Paperback
• Copyright: 1999-11-23
• Publisher: Pearson

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