An edition of ADTs, data structures, and problem solving with C++ (2005)

ADTs, data structures, and problem solving with C++

2nd ed.

by

  • 7 Want to read
  • 1 Currently reading
Cover of: ADTs, data structures, and problem solving with C++ by Larry R. Nyhoff, Larry R. Nyhoff
Read

My Reading Lists:

Create a new list
Notes
  • 7 Want to read
  • 1 Currently reading
Notes

Download Options

Check nearby libraries

Buy this book

Last edited by Drini
September 22, 2025 | History
Edit
An edition of ADTs, data structures, and problem solving with C++ (2005)

ADTs, data structures, and problem solving with C++

2nd ed.

by

  • 7 Want to read
  • 1 Currently reading

"Designed for CS2 courses, this book thoroughly covers ADTs (Abstract Data Types), data structures, and their use in problem solving. The text guides the student through the development of ADTs such as stacks, queues, and binary trees, the use of key data structures such as arrays, classes, and linked lists to implement ADTs, and problem solving using Object-Oriented Design (OOD) methodologies. Algorithms required to design and implement ADTs in C++ are given through treatment along with a solid introduction to the Standard Template Library (STL). C++ topics such as recursion, inheritance, and polymorphism are introduced and some C-style topics relative to data structures and also provided. Using examples, case studies and exercises from various areas of computer science, author Larry Nyhoff offers the student a solid foundation for further studies in CS while providing concrete tools for unlocking the power of C++."--BOOK JACKET.

Publish Date
Publisher
Pearson/Prentice Hall
Language
English
Pages
1072

Check nearby libraries

Buy this book

Previews available in: English

Subjects

C++ (Computer program language), Data structures (Computer science), C plus plus (computer program language)
Edition Availability
Cover of: ADTs, data structures, and problem solving with C++
ADTs, data structures, and problem solving with C++
2005, Pearson/Prentice Hall
Hardcover in English - 2nd ed.

Add another edition?

Book Details

Table of Contents

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

Edition Notes

Rev. ed. of: C++: an introduction to data structures. 1999.
"An Alan R. Apt book."
Includes index.

Published in
Upper Saddle River, NJ

Classifications

Dewey Decimal Class
005.13/3
Library of Congress
QA76.73.C153 N868 2005, QA76.73

The Physical Object

Format
Hardcover
Pagination
xxiv, 928p, appendices
Number of pages
1072

Edition Identifiers

Open Library
OL3383674M
Internet Archive
adtsdatastructur00nyho
ISBN 10
0131409093
LCCN
2004559326
OCLC/WorldCat
56385906
LibraryThing
1451881
Goodreads
343815

Work Identifiers

Work ID
OL1994130W

Source records

Internet Archive item record
Internet Archive item record
Better World Books record
Library of Congress MARC record
Internet Archive item record
Promise Item
ISBNdb
marc_columbia MARC record

Community Reviews (0)

No community reviews have been submitted for this work.

Lists

Loading indicator
Loading carousel

History

Download catalog record: RDF / JSON / OPDS | Wikipedia citation
September 22, 2025 Edited by Drini Add TOC from Tocky
August 11, 2024 Edited by MARC Bot import existing book
December 19, 2023 Edited by ImportBot import existing book
December 7, 2022 Edited by ImportBot import existing book
April 1, 2008 Created by an anonymous user Imported from Scriblio MARC record