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

Software Development

(44)

Problem Analysis and Specification

(2)

Design

(10)

Top-Down Design

(2)

Object-Oriented Design

(3)

Design in the Small

(5)

Coding

(14)

Testing, Execution, and Debugging

(8)

Maintenance

(7)

Quick Quiz 1.5

(1)

Exercises 1.5

(1)

Summary

(1)

Chapter Notes

(1)

Programming Pointers

(1)

ADT Tips

(1)

Programming Problems

(3)

Introduction to Abstract Data Types

(36)

A First Look at ADTs and Implementations

(1)

C++'s Simple Data Types

(13)

Integer Data

(5)

Real Data

(3)

Character Data

(1)

Boolean Data

(2)

Quick Quiz 2.2

(1)

Exercises 2.2

(1)

Programmer-Defined Data Types

(4)

Typedefs

(1)

Enumerations

(2)

Classes

(1)

Quick Quiz 2.3

(1)

Exercises 2.3

(1)

Pointers

(18)

Declaring and Initializing Pointers

(3)

Basic Pointer Operations

(4)

Dynamic Memory Allocation---the new Operation

(1)

A Note about Reference Parameters

(1)

Quick Quiz 2.4

(1)

Exercises 2.4

(1)

Summary

(1)

Chapter Notes

(1)

Programming Pointers

(1)

ADT Tips

(1)

Programming Problems

(4)

Data Structures and Abstract Data Types

(62)

Data Structures, Abstract Data Types, and Implementations

(3)

Static Arrays

(12)

One-Dimensional Static Arrays

(3)

The Subscript Operation

(1)

Arrays as Parameters

(1)

Out-of-Range Errors

(3)

Problems with Arrays

(1)

Quick Quiz 3.2

(1)

Exercises 3.2

(1)

Multidimensional Arrays (optional)

(10)

Two-Dimensional Arrays

(2)

Higher-Dimensional Arrays

(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)

Supplemental Materials

What is included with this book?

The New copy of this book will include any supplemental materials advertised. Please check the title of the book to determine if it should include any access cards, study guides, lab manuals, CDs, etc.

The Used, Rental and eBook copies of this book are not guaranteed to include any supplemental materials. Typically, only the book itself is included. This is true even if the title states it includes any access cards, study guides, lab manuals, CDs, etc.

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