An edition of C++ Plus Data Structures (2016)

C++ Plus Data Structures

by , , and

  • 10 Want to read
  • 1 Currently reading
  • 1 Have read
Cover of: C++ Plus Data Structures by Nell Dale, Chip Weems, Tim Richards, Nell Dale, Chip Weems, Tim Richards
Preview Only

My Reading Lists:

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

Check nearby libraries

Buy this book

Last edited by ImportBot
April 8, 2022 | History
Edit
An edition of C++ Plus Data Structures (2016)

C++ Plus Data Structures

by , , and

  • 10 Want to read
  • 1 Currently reading
  • 1 Have read

This work doesn't have a description yet. Can you add one?

Publish Date
Publisher
Jones & Bartlett Learning, LLC
Language
English
Pages
838

Check nearby libraries

Buy this book

Previews available in: English

Subjects

C plus plus (computer program language), C++ (Computer program language), Data structures (Computer science)
Edition Availability
Cover of: C++ Plus Data Structures
C++ Plus Data Structures
2016, Jones & Bartlett Learning, LLC
in English
Cover of: C++ Plus Data Structures
C++ Plus Data Structures
2016, Jones & Bartlett Learning, LLC
in English

Add another edition?

Book Details

Table of Contents

Preface
Page xi
1. Software Engineering Principles
Page 1
1.1. The Software Process
Page 2
Software Life Cycles
Page 3
A Programmer's Toolboxes
Page 5
Goals of Quality Software
Page 6
Specification: Understanding the Problem
Page 9
Writing Detailed Specification
Page 10
1.2. Program Design
Page 11
Abstraction
Page 11
Information Hiding
Page 13
Stepwise Refinement
Page 14
Visual Tools
Page 15
1.3. Design Approaches
Page 17
Top-Down Design
Page 17
Object-Oriented Design
Page 19
1.4. Verification of Software Correctness
Page 22
Origin of Bugs
Page 23
Designing for Correctness
Page 31
Program Testing
Page 37
Testing C++ Data Structures
Page 48
Practical Considerations
Page 52
Case Study: Fraction Class
Page 54
Summary
Page 62
Exercises
Page 63
2. Data Design and Implementation
Page 67
2.1. Different Views of Data
Page 68
What Do We Mean by Data?
Page 68
Data Abstraction
Page 68
Data Structures
Page 70
Abstract Data Type Operator Categories
Page 75
2.2. Abstraction and Built-In Types
Page 76
Records
Page 77
One-Dimensional Arrays
Page 81
Two-Dimensional Arrays
Page 86
2.3. Higher-Level Abstraction and the C++ Class Type
Page 89
Class Specification
Page 90
Class Implementation
Page 92
Member Functions with Object Parameters
Page 93
Difference Between Classes and Structs
Page 95
2.4. Object-Oriented Programming
Page 95
Concepts
Page 95
C++ Constructs for OOP
Page 97
2.5. Constructs for Program Verification
Page 99
Exceptions
Page 100
Namespaces
Page 102
2.6. Comparison of Algorithms
Page 104
Big-O
Page 106
Common Orders of Magnitude
Page 107
Example 1: Sum of Consecutive Integers
Page 108
Example 2: Finding a Number in a Phone Book
Page 111
Case Study: User-Defined Date ADT
Page 115
Summary
Page 127
Exercises
Page 128
3. ADT Unsorted List
Page 133
3.1. Lists
Page 134
3.2. Abstract Data Type Unsorted List
Page 135
Logical Level
Page 135
Abstract Data Type Operations
Page 135
Generic Data Types
Page 137
Application Level
Page 141
Implementation Level
Page 143
3.3. Pointer Types
Page 160
Logical Level
Page 160
Application Level
Page 166
Implementation Level
Page 167
3.4. Implementing Class UnsortedType as a Linked Structure
Page 167
Linked Structures
Page 168
Class UnsortedType
Page 174
Function PutItem
Page 175
Constructor
Page 177
Observer Operations
Page 178
Function MakeEmpty
Page 179
Function GetItem
Page 179
Function DeleteItem
Page 181
Functions ResetList and GetNextItem
Page 183
Class Destructors
Page 188
3.5. Comparing Unsorted List Implementations
Page 189
Case Study: Creating a Deck of Playing Cards
Page 190
Summary
Page 204
Exercises
Page 205
4. ADT Sorted List
Page 213
4.1. Abstract Data Type Sorted List
Page 214
Logical Level
Page 214
Application Level
Page 216
Implementation Level
Page 216
4.2. Dynamically Allocated Arrays
Page 229
4.3. Implementing the Sorted List as a Linked Structure
Page 231
Function GetItem
Page 231
Function PutItem
Page 234
Function DeleteItem
Page 238
Code
Page 239
Comparing Sorted List Implementations
Page 243
4.4. Comparison of Unsorted and Sorted List ADT Algorithms
Page 246
4.5. Bounded and Unbounded ADTs
Page 247
4.6. Object-Oriented Design Methodology
Page 248
Brainstorming
Page 248
Filtering
Page 249
Scenarios
Page 250
Responsibility Algorithms
Page 251
Final Word
Page 251
Case Study: Evaluating Card Hands
Page 252
Summary
Page 273
Exercises
Page 273
5. ADTs Stack and Queue
Page 277
5.1. Stacks
Page 278
Logical Level
Page 278
Application Level
Page 281
Implementation Level
Page 285
Alternate Array-Based Implementation
Page 290
5.2. Implementing a Stack as a Linked Structure
Page 293
Function Push
Page 294
Function Pop
Page 295
Function Top
Page 297
Other Stack Functions
Page 297
Comparing Stack Implementations
Page 299
5.3. Queues
Page 300
Logical Level
Page 300
Application Level
Page 304
Implementation Level
Page 307
Counted Queue
Page 315
5.4. Implementing a Queue as a Linked Structure
Page 320
Function Enqueue
Page 320
Function Dequeue
Page 322
A Circular Linked Queue Design
Page 326
Comparing Queue Implementations
Page 327
Case Study: Simulating a Solitaire Game
Page 329
Summary
Page 340
Exercises
Page 341
6. Lists Plus
Page 355
6.1. More About Generics: C++ Templates
Page 356
6.2. Circular Linked Lists
Page 360
Finding a List Item
Page 362
Inserting Items into a Circular List
Page 366
Deleting Items from a Circular List
Page 369
6.3. Doubly Linked Lists
Page 371
Finding an Item in a Doubly Linked List
Page 372
Operations on a Doubly Linked List
Page 373
6.4. Linked Lists with Headers and Trailers
Page 375
6.5. Copy Structures
Page 376
Shallow Versus Deep Copies
Page 378
Class Copy Constructors
Page 378
Copy Function
Page 381
Overloading Operators
Page 383
6.6. A Linked List as an Array of Records
Page 387
Why Use an Array?
Page 388
How Is an Array Used?
Page 389
6.7. Polymorphism with Virtual Functions
Page 396
6.8. A Specialized List ADT
Page 401
Test Plan
Page 406
6.9. Range-Based Iteration
Page 407
Case Study: Implementing a Large Integer ADT
Page 413
Summary
Page 426
Exercises
Page 426
7. Programming with Recursion
Page 435
7.1. What Is Recursion?
Page 436
7.2. The Classic Example of Recursion
Page 437
7.3. Programming Recursively
Page 440
Coding the Factorial Function
Page 441
7.4. Verifying Recursive Functions
Page 443
Three-Question Method
Page 443
7.5. Writing Recursive Functions
Page 444
Writing a Boolean Function
Page 444
7.6. Using Recursion to Simplify Solutions
Page 447
7.7. Recursive Linked List Processing
Page 448
7.8. A Recursive Version of Binary Search
Page 452
7.9. Recursive Versions of PutItem and DeleteItem
Page 454
Function PutItem
Page 454
Function DeleteItem
Page 455
7.10. How Recursion Works
Page 456
Static Storage Allocation
Page 456
Dynamic Storage Allocation
Page 459
7.11. Tracing the Execution of Recursive Function Insert
Page 465
7.12. Recursive Quick Sort
Page 468
7.13. Debugging Recursive Routines
Page 475
7.14. Removing Recursion
Page 476
Iteration
Page 476
Stacking
Page 477
7.15. Deciding Whether to Use a Recursive Solution
Page 479
Case Study: Escaping from a Maze
Page 481
Summary
Page 494
Exercises
Page 495
8. Binary Search Trees
Page 503
8.1. Searching
Page 504
Linear Searching
Page 505
High-Probability Ordering
Page 505
Key Ordering
Page 506
Binary Searching
Page 507
8.2. Trees
Page 507
8.3. Logical Level
Page 512
8.4. Application Level
Page 514
8.5. Implementation Level
Page 514
8.6. Recursive Binary Search Tree Operations
Page 515
Functions IsFull and IsEmpty
Page 516
Function GetLength
Page 516
Function GetItem
Page 519
Function PutItem
Page 522
Function DeleteItem
Page 526
Function Print
Page 533
The Class Constructor and Destructor
Page 534
Copying a Tree
Page 535
More About Traversals
Page 540
Functions ResetTree and GetNextItem
Page 542
8.7. Iterative Insertion and Deletion
Page 545
Searching a Binary Search Tree
Page 545
Function PutItem
Page 548
Function DeleteItem
Page 551
Test Plan
Page 552
Recursion or Iteration?
Page 553
8.8. Comparing Binary Search Trees and Linear Lists
Page 553
Big-O Comparisons
Page 554
Case Study: Building an Index
Page 556
Summary
Page 564
Exercises
Page 564
9. Heaps, Priority Queues, and Heap Sort
Page 573
9.1. ADT Priority Queue
Page 574
Logical Level
Page 574
Application Level
Page 575
Implementation Level
Page 576
9.2. A Nonlinked Representation of Binary Trees
Page 577
9.3. Heaps
Page 580
Logical Level
Page 580
Application Level
Page 584
Implementation Level
Page 584
Application Level Revisited
Page 589
Heaps Versus Other Priority Queue Representations
Page 592
9.4. Heap Sort
Page 593
Summary
Page 598
Exercises
Page 599
10. Trees Plus
Page 607
10.1. AVL Trees
Page 608
Single Rotations on AVL Trees
Page 609
Generalizing Single Rotations on AVL Trees
Page 611
Double Rotations on AVL Trees
Page 613
Generalizing Double Rotations on AVL Trees
Page 616
Application Level
Page 618
Logical Level
Page 618
Implementation Level
Page 619
10.2. Red-Black Trees
Page 625
Inserting into Red-Black Trees
Page 626
Implementing Recoloring for Red-Black Trees
Page 630
Red-Black Tree Summary
Page 634
10.3. B-Trees
Page 634
Summary
Page 638
Exercises
Page 638
11. Sets, Maps, and Hashing
Page 641
11.1. Sets
Page 642
Logical Level
Page 642
Application Level
Page 646
Implementation Level
Page 646
11.2. Maps
Page 650
Logical Level
Page 651
Application Level
Page 652
Implementation Level
Page 653
11.3. Hashing
Page 654
Collisions
Page 657
Choosing a Good Hash Function
Page 665
Complexity
Page 669
Summary
Page 669
Exercises
Page 670
12. Sorting
Page 673
12.1. Sorting Revisited
Page 674
12.2. Straight Selection Sort
Page 675
12.3. Bubble Sort
Page 679
12.4. Insertion Sort
Page 683
12.5. O (N log2 N) Sorts
Page 686
Merge Sort
Page 687
Quick Sort
Page 694
Heap Sort
Page 695
Testing
Page 695
12.6. Efficiency and Other Considerations
Page 696
When N Is Small
Page 696
Eliminating Calls to Functions
Page 696
Programmer Time
Page 697
Space Considerations
Page 697
Keys and Stability
Page 698
Sorting with Pointers
Page 699
Caching
Page 700
12.7. Radix Sort
Page 701
Analyzing the Radix Sort
Page 705
12.8. Parallel Merge Sort
Page 705
Summary
Page 713
Exercises
Page 715
13. Graphs
Page 721
13.1. Graphs
Page 722
Logical Level
Page 722
Application Level
Page 728
Implementation Level
Page 739
Summary
Page 746
Exercises
Page 746
Appendix A. Reserved Words
Page 751
Appendix B. Operator Precedence
Page 751
Appendix C. A Selection of Standard Library Routines
Page 753
Appendix D. American Standard Code for Information Interchange (ASCII) Character Sets
Page 763
Appendix E. The Standard Template Library (STL)
Page 764
Glossary
Page 809
Index
Page 815

Classifications

Library of Congress
QA76.73.C153D334, QA76.73.C153

Edition Identifiers

Open Library
OL28605800M
ISBN 13
9781284089189
OCLC/WorldCat
973495580

Work Identifiers

Work ID
OL21131623W

Source records

Community Reviews (0)

No community reviews have been submitted for this work.

Lists

History

Download catalog record: RDF / JSON
April 8, 2022 Edited by ImportBot import existing book
August 5, 2020 Created by ImportBot import new book