ADTs, Data Structures, and Problem Solving with C++

by Nyhoff, Larry R.

• ISBN13: 9780131409095
• ISBN10: 0131409093
• Additional ISBN(s): 9780023887253
• Edition: 2nd
• Format: Paperback
• Copyright: 2004-07-26
• Publisher: Pearson
• More Book Details

Summary

Reflecting the newest trends in computer science, new and revised material throughout the Second Edition of this book places increased emphasis on abstract data types (ADTs) and object-oriented design. This book continues to offer a thorough, well-organized, and up-to-date presentation of essential principles and practices in data structures using C++. Topics include C++'s I/O and string classes, pointers and dynamic allocation, lists, array-based and linked-list implementations of stacks, queues, searching, inheritance and more. For computer professionals in companies that have computing departments or those who want advanced training in C++.

Author Biography

Larry R. Nyhoff earned the B.A. in Mathematics in 1960 from Calvin College and the M.S. in 1961 from the University of Michigan. Larry continued his study of Mathematics and received the Ph.D. in 1969 from Michigan State University. He also did graduate work in computer science from 1981-83. He is in his 41st year as a professor at Calvin College and has aided in the development of the college's computer science curriculum since its inception. In addition to authoring and co-authoring nearly 30 textbooks used worldwide, Larry is a professional member of ACM and SIGCSE. He was selected to be the 2001-02 recipient of Calvin College's Presidential Exemplary Teaching Award

Table of Contents

Software Development	1	(44)
Problem Analysis and Specification	4	(2)
Design	6	(10)
Top-Down Design	6	(2)
Object-Oriented Design	8	(3)
Design in the Small	11	(5)
Coding	16	(14)
Testing, Execution, and Debugging	30	(8)
Maintenance	38	(7)
Quick Quiz 1.5	39	(1)
Exercises 1.5	40	(1)
Summary	41	(1)
Chapter Notes	41	(1)
Programming Pointers	41	(1)
ADT Tips	42	(1)
Programming Problems	42	(3)
Introduction to Abstract Data Types	45	(36)
A First Look at ADTs and Implementations	46	(1)
C++'s Simple Data Types	46	(13)
Integer Data	47	(5)
Real Data	52	(3)
Character Data	55	(1)
Boolean Data	56	(2)
Quick Quiz 2.2	58	(1)
Exercises 2.2	58	(1)
Programmer-Defined Data Types	59	(4)
Typedefs	59	(1)
Enumerations	60	(2)
Classes	62	(1)
Quick Quiz 2.3	62	(1)
Exercises 2.3	62	(1)
Pointers	63	(18)
Declaring and Initializing Pointers	64	(3)
Basic Pointer Operations	67	(4)
Dynamic Memory Allocation---the new Operation	71	(1)
A Note about Reference Parameters	72	(1)
Quick Quiz 2.4	73	(1)
Exercises 2.4	74	(1)
Summary	75	(1)
Chapter Notes	75	(1)
Programming Pointers	76	(1)
ADT Tips	77	(1)
Programming Problems	77	(4)
Data Structures and Abstract Data Types	81	(62)
Data Structures, Abstract Data Types, and Implementations	82	(3)
Static Arrays	85	(12)
One-Dimensional Static Arrays	87	(3)
The Subscript Operation	90	(1)
Arrays as Parameters	91	(1)
Out-of-Range Errors	92	(3)
Problems with Arrays	95	(1)
Quick Quiz 3.2	96	(1)
Exercises 3.2	97	(1)
Multidimensional Arrays (optional)	97	(10)
Two-Dimensional Arrays	97	(2)
Higher-Dimensional Arrays	99	(1)
Array of Array Declarations	100	(5)
Multidimensional Arrays as Parameters	105	(1)
Quick Quiz 3.3	106	(1)
Exercises 3.3	106	(1)
Dynamic Arrays	107	(16)
The new Operation---Dynamic Arrays	108	(13)
Other Uses of Pointers	121	(1)
Quick Quiz 3.4	122	(1)
Exercises 3.4	123	(1)
C-Style Structs (optional)	123	(5)
Pointers to Structs	127	(1)
Quick Quiz 3.5	128	(1)
Procedural Programming	128	(15)
Example of Procedural Programming	129	(6)
Summary	135	(1)
Chapter Notes	135	(1)
Programming Pointers	136	(1)
ADT Tips	137	(1)
Programming Problems	137	(6)
More about OOP and ADTs---Classes	143	(50)
Procedural vs. Object-Oriented Programming	144	(1)
Quick Quiz 4.1	145	(1)
Classes	145	(5)
Differences between ``Traditional'' (C) Structs and OOP (C++) Structs and Classes	145	(1)
Class Declarations	146	(4)
Quick Quiz 4.2	150	(1)
Example: A First Version of a User-Defined Time Class	150	(8)
Why not make all class members public?	152	(1)
Implementation of a Class	153	(3)
Some Observations	156	(2)
Class Constructors	158	(7)
Other Class Operations	165	(28)
Copy Operations---Initialization and Assignment	166	(1)
Accessors and Mutators	167	(2)
Overloading Operators	169	(1)
Overloading Input/Output Operators	170	(7)
Other Operations: Advance and the Relational Operators	177	(3)
Summary and a Few Other Items	180	(5)
Pointers to Class Objects	185	(1)
The this Pointer	185	(2)
Quick Quiz 4.5	187	(1)
Exercises 4.5	187	(1)
Summary	188	(1)
Chapter Notes	188	(1)
Programming Pointers	189	(1)
ADT Tips	190	(1)
Programming Problems	190	(3)
Standard C++ Input/Output and String Classes	193	(60)
The C++ Standard I/O Classes	194	(17)
The istream Class	195	(5)
The ostream Class	200	(4)
File I/O: if stream and of stream Classes	204	(2)
The I/O Class Hierarchy	206	(4)
Quick Quiz 5.1	210	(1)
The C++ String Types	211	(19)
C-Style Strings	212	(4)
The C++ string Class	216	(9)
String Streams	225	(3)
Quick Quiz 5.2	228	(1)
Exercises 5.2	229	(1)
Case Study: Text Editing	230	(10)
Introduction to Pattern Matching (optional)	240	(3)
Introduction to Data Encryption (optional)	243	(10)
Data Encryption Standard	245	(1)
Public-Key Encryption	246	(1)
Summary	247	(1)
Chapter Notes	247	(1)
Programming Pointers	248	(1)
ADT Tips	249	(1)
Programming Problems	249	(4)
Lists	253	(62)
List as an ADT	254	(3)
Designing and Building a List Class	256	(1)
An Array-Based Implementation of Lists	257	(12)
Selecting a Storage Structure	257	(1)
Implementing the Operations	258	(2)
A List Class With Static Array Storage	260	(9)
An Array-Based Implementation of Lists with Dynamic Allocation	269	(18)
Dynamic Allocation in Classes---Destructors, Copy Constructors, and Assignment	275	(8)
A Final Note	283	(3)
Quick Quiz 6.3	286	(1)
Exercises 6.3	287	(1)
Introduction to Linked Lists	287	(8)
What Are They?	287	(1)
Implementing the Basic List Operations	288	(5)
Summary	293	(1)
Quick Quiz 6.4	294	(1)
Exercises 6.4	294	(1)
A Pointer-Based Implementation of Linked Lists in C++	295	(8)
Node Structure	295	(2)
Data Members for Linked-List Implementation	297	(1)
Function Members for Linked-List Implementation	298	(3)
Exercises 6.5	301	(2)
An Array-Based Implementation of Linked Lists (optional)	303	(12)
Node Structure	303	(3)
Organizing the Storage Pool	306	(2)
Exercises 6.6	308	(1)
Summary	309	(1)
Chapter Notes	309	(1)
Programming Pointers	309	(1)
ADT Tips	310	(2)
Programming Problems	312	(3)
Stacks	315	(74)
Introduction to Stacks	316	(5)
Problem 1	316	(1)
Problem 2	316	(1)
Problem 3	316	(1)
Problem 4	317	(4)
Designing and Building a Stack Class---Array-Based	321	(32)
Selecting Storage Structures	322	(3)
Implementing the Operations	325	(2)
The Complete Stack Class	327	(6)
Using a Dynamic Array to Store the Stack Elements	333	(15)
A Look Ahead	348	(1)
Quick Quiz 7.2	349	(1)
Exercises 7.2	350	(3)
Linked Stacks	353	(13)
Selecting a Storage Structure	353	(1)
Implementing the Operations	354	(3)
The Complete Stack Class: Linked List Version	357	(8)
Exercises 7.3	365	(1)
Use of Stacks in Function Calls	366	(5)
Quick Quiz 7.4	370	(1)
Exercises 7.4	370	(1)
Case Study: Postfix (RPN) Notation	371	(18)
Evaluating Postfix Expressions	372	(2)
Converting Infix Expressions to Postfix	374	(9)
Quick Quiz 7.5	383	(1)
Exercises 7.5	384	(2)
Summary	386	(1)
Chapter Notes	386	(1)
Programming Pointers	386	(1)
ADT Tips	386	(1)
Programming Problems	386	(3)
Queues	389	(56)
Introduction to Queues	389	(11)
Example: Drill and Practice Problems	391	(9)
Designing and Building a Queue Class---Array-Based	400	(12)
Using a Static Array to Store the Queue Elements	403	(5)
Using a Dynamic Array to Store the Queue Elements	408	(1)
Quick Quiz 8.2	409	(1)
Exercises 8.2	410	(2)
Linked Queues	412	(14)
A Natural Linked-List Implementation	413	(10)
Using a Circular Linked List	423	(1)
Quick Quiz 8.3	424	(1)
Exercises 8.3	424	(2)
Application of Queues: Buffers and Scheduling	426	(3)
Quick Quiz 8.4	429	(1)
Exercises 8.4	429	(1)
Case Study: Information Center Simulation	429	(16)
Problem Analysis and Specification	430	(1)
Building a Simulation Class	430	(11)
The Timer and Call Classes	441	(1)
Summary	441	(1)
Chapter Notes	441	(1)
Programming Pointers	442	(1)
ADT Tips	442	(1)
Programming Problems	442	(3)
ADT Implementations: Templates and Standard Containers	445	(76)
Introduction: The Evolution of Reusability and Genericity	446	(2)
From Algorithms to Algorithms	446	(2)
From Data to Containers	448	(1)
Function Genericity---Overloading and Templates	448	(9)
Overloading	449	(2)
Function Templates	451	(4)
Another Example: Displaying an Array	455	(2)
Class Genericity---Templates	457	(18)
What's Wrong with typedef?	457	(1)
Class Templates	458	(14)
An Alternative Version of the Stack Class Template	472	(1)
A Quick Peek at the Standard C++ Container Class Templates	473	(1)
Quick Quiz 9.3	474	(1)
Exercises 9.3	475	(1)
The vector Container	475	(19)
Declaring vector Objects	476	(2)
Some vector Operations	478	(4)
A First Look Under the Hood---Increasing the Capacity	482	(3)
A First Look at Iterators	485	(4)
Some vector Methods Involving Iterators	489	(1)
Wrap-up: vectors versus Arrays	490	(1)
Quick Quiz 9.4	491	(1)
Exercises 9.4	492	(2)
Case Study: Counting Computer Logins	494	(5)
Multidimensional vectors (Optional)	499	(4)
Two-Dimensional vector Objects	499	(1)
Two-Dimensional vector Operations	500	(3)
Exercises 9.6	503	(1)
Other Standard Containers---deque, stack, and queue	503	(8)
STL's deque Class Template	503	(4)
A New (But Unnecessary) Version of Our Stack Class Template	507	(2)
STL's stack Adapter	509	(1)
STL's queue Adapter	510	(1)
Quick Quiz 9.7	510	(1)
Bitsets and Valarrays (optional)	511	(10)
Bitsets	511	(2)
Valarrays	513	(2)
Slices, Masks, and Indirect Arrays	515	(1)
Summary	516	(1)
Chapter Notes	516	(1)
Programming Pointers	516	(1)
ADT Tips	517	(1)
Programming Problems	517	(4)
ADT Implementation: Recursion, Algorithm Analysis, and Standard Algorithms	521	(64)
Recursion	522	(16)
Examples of Recursive Functions	522	(2)
Coding Recursive Functions	524	(3)
Example of Inappropriate Recursion: Fibonacci Numbers	527	(2)
Example: Binary Search	529	(3)
Example: Palindrome Checker	532	(2)
Quick Quiz 10.1	534	(1)
Exercises 10.1	534	(4)
Examples of Recursion: Towers of Hanoi; Parsing	538	(10)
Towers of Hanoi	538	(3)
Parsing	541	(6)
Exercises 10.2	547	(1)
Implementing Recursion	548	(3)
Algorithm Efficiency	551	(13)
Quick Quiz 10.4	562	(1)
Exercises 10.4	563	(1)
Standard Algorithms in C++	564	(9)
Example: STL's sort Algorithm	564	(6)
A Sample of STL Algorithms	570	(2)
Algorithms from the <numeric> Library	572	(1)
Example: Judging Figure Skating	572	(1)
Quick Quiz 10.5	573	(1)
Proving Algorithms Correct (optional)	573	(12)
Example: Calculating the Mean	574	(2)
Example: Recursive Power Function	576	(1)
Summary	577	(1)
Exercises 10.6	578	(1)
Summary	579	(1)
Chapter Notes	579	(1)
Programming Pointers	579	(1)
ADT Tips	579	(1)
Programming Problems	580	(5)
More Linking Up with Linked Lists	585	(60)
Some Variants of Singly-Linked Lists	586	(7)
Linked Lists with Head Nodes	586	(3)
Circular Linked Lists	589	(2)
Quick Quiz 11.1	591	(1)
Exercises 11.1	592	(1)
Linked Implementation of Sparse Polynomials	593	(9)
Exercises 11.2	602	(1)
Doubly-Linked Lists and the Standard C++ list	602	(19)
Doubly-Linked Lists	602	(2)
The Standard list Class Template	604	(8)
Example: Internet Addresses	612	(4)
A Look under the Hood at C++'s list	616	(4)
Exercises 11.3	620	(1)
Case Study: Large-Integer Arithmetic	621	(10)
Problem	621	(1)
Design	621	(2)
Implementation	623	(8)
Exercises 11.4	631	(1)
Other Multiply-Linked Lists	631	(14)
Multiply-Ordered Lists	631	(1)
Sparse Matrices	632	(3)
Generalized Lists	635	(2)
Exercises 11.5	637	(2)
Summary	639	(1)
Chapter Notes	639	(1)
Programming Pointers	639	(1)
ADT Tips	639	(1)
Programming Problems	640	(5)
Searching: Binary Trees and Hash Tables	645	(76)
Review of Linear Search and Binary Search	646	(5)
Linear Search	646	(2)
Binary Search	648	(2)
Exercises 12.1	650	(1)
Introduction to Binary Trees	651	(9)
Tree Terminology	652	(1)
Some Examples of Binary Trees	653	(2)
Array Representation of Binary Trees	655	(2)
Linked Representation of Binary Trees	657	(1)
Quick Quiz 12.2	658	(1)
Exercises 12.2	659	(1)
Binary Trees as Recursive Data Structures	660	(7)
Traversals	661	(4)
Quick Quiz 12.3	665	(1)
Exercises 12.3	665	(2)
Binary Search Trees	667	(31)
Implementing BSTs	667	(3)
BST Traversals	670	(4)
Searching a BST	674	(3)
Inserting into a BST	677	(4)
Removing a Node from a BST	681	(12)
Problem of Lopsidedness	693	(1)
Quick Quiz 12.4	694	(1)
Exercises 12.4	695	(3)
Case Study: Validating Computer Logins	698	(4)
Problem	698	(1)
Design	698	(1)
Coding	699	(3)
Threaded Binary Search Trees (Optional)	702	(5)
Quick Quiz 12.6	706	(1)
Exercises 12.6	706	(1)
Hash Tables	707	(14)
Hash Functions	708	(1)
Collision Strategies	709	(1)
Improvements	710	(4)
Quick Quiz 12.7	714	(1)
Exercises 12.7	714	(1)
Summary	715	(1)
Chapter Notes	715	(1)
Programming Pointers	715	(1)
ADT Tips	716	(1)
Programming Problems	716	(5)
Sorting	721	(58)
Some O(n2) Sorting Schemes	722	(13)
Selection Sorts	722	(3)
Exchange Sorts	725	(3)
Insertion Sorts	728	(2)
Evaluation of These Sorting Schemes	730	(1)
Indirect Sorting	731	(1)
Quick Quiz 13.1	732	(1)
Exercises 13.1	733	(2)
Heaps, Heapsort, and Priority Queues	735	(18)
Heaps	736	(1)
Basic Heap Operations	737	(4)
Heapsort	741	(4)
Heap Algorithms in STL	745	(3)
Heaps and Priority Queues	748	(3)
Quick Quiz 13.2	751	(1)
Exercises 13.2	752	(1)
Quicksort	753	(9)
The Split Operation	754	(3)
Quicksort	757	(3)
Improvements	760	(1)
Quick Quiz 13.3	760	(1)
Exercises 13.3	761	(1)
Mergesort	762	(8)
Merging Lists	762	(2)
Binary Mergesort	764	(2)
Natural Mergesort	766	(3)
Quick Quiz 13.4	769	(1)
Exercises 13.4	769	(1)
Radix Sort	770	(9)
Exercises 13.5	773	(1)
Summary	774	(1)
Chapter Notes	774	(1)
Programming Pointers	774	(1)
ADT Tips	775	(1)
Programming Problems	775	(4)
OOP and ADTs	779	(52)
A Brief History and Overview of OOP and ADTs	780	(4)
Encapsulation	781	(1)
Inheritance	781	(2)
Polymorphism and Dynamic Binding	783	(1)
Quick Quiz 14.1	784	(1)
Inheritance and Object-Oriented Design	784	(10)
Example 1: Licenses	786	(3)
Public, Private, and Protected Sections	789	(1)
The Form of Derived Classes	790	(1)
The Is-a, Has-a, and Uses-a Relationships Between Classes	791	(2)
Quick Quiz 14.2	793	(1)
Exercises 14.2	793	(1)
Building Derived Classes	794	(7)
Derived Class Constructors	794	(1)
Accessing Inherited Data Members	794	(1)
Reusing Operations	795	(2)
Example: Stacks and Bounded Stacks	797	(4)
Case Study: Payroll	801	(9)
Problem	801	(1)
Design	802	(8)
Polymorphism, Virtual Functions, and ADTs	810	(13)
Why Polymorphism is Needed: a Binding Problem	810	(2)
Virtual Functions and Dynamic Binding	812	(4)
Example 1: Using Handles	816	(1)
Example 2: Stacks and Bounded Stacks	817	(3)
Pure Virtual Functions and Abstract Classes	820	(2)
Quick Quiz 14.5	822	(1)
Exercises 14.5	823	(1)
Case Study: A Heterogeneous Data Structure	823	(8)
The Need for Virtual Functions	824	(4)
Summary	828	(1)
Chapter Notes	828	(1)
Programming Pointers	828	(1)
ADT Tips	828	(1)
Programming Problems	829	(2)
Trees	831	(52)
Case Study: Huffman Codes	832	(7)
Variable-Length Codes	832	(1)
Immediate Decodability	833	(1)
Huffman Codes	833	(5)
Exercises 15.1	838	(1)
Tree Balancing: AVL Trees	839	(16)
Example: A BST of State Abbreviations	840	(9)
The Basic Rebalancing Rotations	849	(5)
Quick Quiz 15.2	854	(1)
Exercises 15.2	854	(1)
2-3-4 Trees, Red--Black Trees, B-Trees, and Other Trees	855	(19)
2-3-4 Trees	856	(7)
Red-Black Trees	863	(5)
B-Trees	868	(1)
Representing Trees and Forests as Binary Trees	869	(3)
Quick Quiz 15.3	872	(1)
Exercises 15.3	873	(1)
Associative Containers in STL---maps (optional)	874	(9)
Quick Quiz 15.4	880	(1)
Summary	880	(1)
Chapter Notes	880	(1)
Programming Pointers	880	(1)
ADT Tips	880	(1)
Programming Problems	881	(2)
Graphs and Digraphs	883
Directed Graphs	883	(9)
Adjacency-Matrix Representation	885	(2)
Adjacency-List Representation	887	(1)
Quick Quiz 16.1	888	(1)
Exercises 16.1	889	(3)
Searching and Traversing Digraphs	892	(19)
Depth-First Search	894	(2)
Breadth-First Search	896	(1)
Traversal and Shortest-Path Problems	897	(11)
NP-Complete Problems	908	(1)
Quick Quiz 16.2	909	(1)
Exercises 16.2	909	(2)
Graphs	911
Adjacency-Matrix and Adjacency-List Representations	912	(1)
Edge-List Representation	913	(1)
Connectedness	913	(9)
Quick Quiz 16.3	922	(1)
Exercises 16.3	922	(4)
Summary	926	(1)
Chapter Notes	926	(1)
Programming Pointers	927	(1)
ADT Tips	927	(1)
Programming Problems	927
Appendixes
A ASCII Character Set	1	(1)
B Number Systems	1	(1)
C Basic C++	1	(1)
C.1 C++ Program Structure	1	(1)
C.2 Compiler Directives	2	(1)
C.3 Standard Libraries	2	(3)
C.4 Comments	5	(1)
C.5 Identifiers and Keywords	6	(3)
C.6 Fundamental Data Types	9	(1)
C.7 Literals	9	(1)
C.8 Declarations	10	(1)
C.9 Operators and Expressions	10	(6)
C.10 Control Structures	16	(6)
C.11 Functions	22	(6)
C.12 Lifetimes, Scopes, and Namespaces	28	(2)
C.13 Files	30
D Other C++ Features	1	(1)
D.1 Stream Operations	1	(4)
D.2 String Operations	5	(9)
D.3 Exceptions	14	(3)
D.4 More About Function Templates	17	(2)
D.5 Other Applications of Pointers	19
E From Java to C++	1	(1)
E.1 Program Structure	1	(1)
E.2 Using and Compiler Directives	1	(1)
E.3 Input and Output (§C.9, §C.13, & §D.1)	2	(3)
E.4 Data Types	5	(1)
E.5 Variables and Constants	6	(1)
E.6 Functions	7	(2)
E.7 Operator Overloading	9	(1)
E.8 Things the Same in Both C++ and Java	10	(1)
E.9 More Differences Between C++ and Java	11
F Answers to Quick Quizzes	1	(1)
Index	1

Excerpts

The first edition of this text grew out of the author''s experience teaching an introductory data structures course (commonly referred to as CS2) for nearly two decades. It has served as a sequel to the widely used C++: An Introduction to Computingby Joel Adams and Larry Nyhoff, which grew out of their many years of teaching a first programming course (CS1) in C++. But computer science curricula change as do teaching pedagogy and methodology. In keeping with these changes, the introductory C++ text underwent revisions and has recently appeared in a third edition. The content of the second course in computing also has changed, with the broadening of the traditional study of data structures to a study of abstract data types (ADTs) being one of the major trends. Consequently, there is an increased emphasis on ADTs in this new edition and a name change thus seemed appropriate: ADTs, Data Structures, and Problem Solving with C++.And as one might expect, there is a corresponding increased emphasis on object-oriented design. In addition, the author''s pedagogy has been honed over many years of successful teaching. Reflecting this, the presentation in this new edition has been improved by reordering some topics, rewriting several sections, and adding new material. Many suggestions also came from those who diligently and thoroughly reviewed the manuscript and its several revisions. Their constructive comments and positive evaluations were very encouraging and much appreciated. If you used the first edition and liked it, I trust you will like this new edition even more. Scan the overview and list of new features that appear later in this preface to see what some of the improvements are. Those of you who haven''t used or who stopped using the first edition and are looking at this edition as one of several candidates for your course will, I hope, give it serious consideration. I have tried to preserve the best features of the first edition and made changes based on feedback from many CS2 teachers and users of the previous edition. Approach.As an illustration of the approach that has worked well in my classes, take a look at Chapter 7 on stacks. Some examples of real-world phenomena that are best modeled by a LIFO structure lead to abstracting from these examples the common features, yielding a stack ADT. But ADTs must be implemented with data structures provided in some language, and so we build a stack class. (Incidentally, while we are doing this in class, my students are working on building a queue class in their lab period.) Once this new Stack type has been created and tested, we use it to solve one or more of the original problems and usually at least one new application. I also believe in starting with a simple implementation--e.g., using a static C-style array--and get a working version. Then, emphasizing the need to preserve the public interface of an ADT, we refine it--e.g., use a dynamic array so the user can specify the stack''s capacity; then use a linked list so an a priori capacity specification is not needed; and finally, convert it to a template so the ADT can be used with arbitrary type elements. This spiral/successive-refinement approach demonstrates clearly the "abstract" part of an ADT--that it is independent of the implementation. I also cover many of the containers provided in the C++ Standard Template Library (STL), because several of them such as vector are very useful and powerful, and it does not make sense to reinvent the wheel by building our own versions. Others, however, such as STL''s stacks and queues, are adapters of other containers and waste a lot of the horsepower of these inner containers. For these it makes sense to build our own "lean and mean" implementations, using lower-level data structures such as arrays and linked lists. It also provides practice for students with building customized container types for problems for which none of the standard containers is really suitable. How to Use this Book.There is considerable flexibility in the kind of course that can be taught from this text. In particular, many of the topics can be covered in an order different from that used in the text. The diagram on the next page shows the major dependencies of the various chapters. An arrow running from one box to another indicates a significant dependence of the material in the second box on that in the first; for example, the material in Chapter 9 draws on the material in both Chapters 7 and 8. A dashed arrow indicates that the material in the first box may have been covered in a first course and might be omitted or assigned for review. Boxes not connected are, for the most part, independent of each other (for example, Chapters 7 and 8). To Students (and Other Users of this Text) You probably don''t read prefaces of most textbooks unless your instructor assigns them and then perhaps only if you will be quizzed on it. For this text, however, you should at least read the section "Overview of the Text," because it is intended to provide an orientation to what the book is about, what its major themes are, and how they fit together. And you should also look through the Table of Contents for this same reason. The topics covered in this text are typical of those in a course that follows a first course in programming. The aim of these two courses together is to provide you with a solid introduction to computing. You develop the skills to write substantial programs for solving non-trivial problems but are also introduced to important concepts and techniques in computing. These two courses should provide you with a solid base for using the computer as a problem-solving tool in whatever areas of study you pursue. If you do more coursework in computer science, it is important that you work hard at mastering the material of this second course, because the topics covered are fundamental to several upper-level courses. In fact, at many colleges and universities, this course is a prerequisite for intermediate and advanced courses in computer science. This text assumes that you have had an introduction to programming, preferably using C++ or Java. Appendix C ( Basic C++) reviews the basic features of C++ that are typically covered in a first programming course, and Appendix D ( Other C++ Features) covers some features that are more advanced. Students in my classes have found these two appendixes to be handy references when they need to look up something about the C++ language. If your first course was in Java, you should study Appendix E ( From Java to C++), which provides a comparison of the main features of the two languages. It has been used successfully in my classes to get students with a background in Java up to speed with the basic features of C++ in the first couple of weeks. As you read through the text, you should by all means use the Quick Quizzes to check your understanding of some of the main ideas from the reading. The answers to these can be found in Appendix F. These self-test quizzes are usually followed by sets of exercises, some of which your instructor may assign for homework. You are encouraged to try some of these on your own, even if it isn''t required, because it will increase your mastery of the material. The same is true of the programming problems at the end of each chapter. All of the C++ code in the program examples of this text can be downloaded from the author''s website for the book: http://cs.calvin.edu/books/c++/ds. So if you see a particular function in an example that you can use in a program or class library you are writing, feel free to download and use it-unless your instructor forbids it, of course! Hopefully, you will enjoy reading and learning from the text. Several hundreds of my students have used earlier versions of this text with very few compla