C++ Plus Data Structures, 6th Edition by Dale, Nell -- Read -- Imperial Library of Trantor

Index

Cover Page Title Page Copyright Page Contents Preface 1 Software Engineering Principles

1.1 The Software Process

Software Life Cycles A Programmer’s Toolboxes Goals of Quality Software Specification: Understanding the Problem Writing Detailed Specification

1.2 Program Design

Abstraction Information Hiding Stepwise Refinement Visual Tools

1.3 Design Approaches 17

Top-Down Design Object-Oriented Design

1.4 Verification of Software Correctness

Origin of Bugs Designing for Correctness Program Testing Testing C++ Data Structures Practical Considerations Case Study: Fraction Class

Summary

Exercises

2 Data Design and Implementation

2.1 Different Views of Data

What Do We Mean by Data? Data Abstraction Data Structures Abstract Data Type Operator Categories

2.2 Abstraction and Built-In Types

Records One-Dimensional Arrays Two-Dimensional Arrays

2.3 Higher-Level Abstraction and the C++ Class Type

Class Specification Class Implementation Member Functions with Object Parameters Difference Between Classes and Structs

2.4 Object-Oriented Programming

Concepts C++ Constructs for OOP

2.5 Constructs for Program Verification

Exceptions Namespaces

2.6 Comparison of Algorithms

Big-O Common Orders of Magnitude Example 1: Sum of Consecutive Integers Example 2: Finding a Number in a Phone Book Case Study: User-Defined Date ADT

Summary

Exercises

3 ADT Unsorted List

3.1 Lists 3.2 Abstract Data Type Unsorted List

Logical Level Abstract Data Type Operations Generic Data Types Application Level Implementation Level

3.3 Pointer Types

Logical Level Application Level Implementation Level

3.4 Implementing Class UnsortedType as a Linked Structure

Linked Structures Class UnsortedType Function PutItem Constructor Observer Operations Function MakeEmpty Function GetItem Function DeleteItem Functions ResetList and GetNextItem Class Destructors

3.5 Comparing Unsorted List Implementations

Case Study: Creating a Deck of Playing Cards

Summary

Exercises

4 ADT Sorted List

4.1 Abstract Data Type Sorted List

Logical Level Application Level Implementation Level

4.2 Dynamically Allocated Arrays 4.3 Implementing the Sorted List as a Linked Structure

Function GetItem Function PutItem Function DeleteItem Code Comparing Sorted List Implementations

4.4 Comparison of Unsorted and Sorted List ADT Algorithms 4.5 Bounded and Unbounded ADTs 4.6 Object-Oriented Design Methodology

Brainstorming Filtering Scenarios Responsibility Algorithms Final Word Case Study: Evaluating Card Hands

Summary

Exercises

5 ADTs Stack and Queue

5.1 Stacks

Logical Level Application Level Implementation Level Alternate Array-Based Implementation

5.2 Implementing a Stack as a Linked Structure

Function Push Function Pop Function Top Other Stack Functions Comparing Stack Implementations

5.3 Queues

Logical Level Application Level Implementation Level Counted Queue

5.4 Implementing a Queue as a Linked Structure

Function Enqueue Function Dequeue A Circular Linked Queue Design Comparing Queue Implementations Case Study: Simulating a Solitaire Game

Summary

Exercises

6 Lists Plus

6.1 More About Generics: C++ Templates 6.2 Circular Linked Lists

Finding a List Item Inserting Items into a Circular List Deleting Items from a Circular List

6.3 Doubly Linked Lists

Finding an Item in a Doubly Linked List Operations on a Doubly Linked List

6.4 Linked Lists with Headers and Trailers 6.5 Copy Structures

Shallow Versus Deep Copies Class Copy Constructors Copy Function Overloading Operators

6.6 A Linked List as an Array of Records

Why Use an Array? How Is an Array Used?

6.7 Polymorphism with Virtual Functions 6.8 A Specialized List ADT

Test Plan

6.9 Range-Based Iteration

Case Study: Implementing a Large Integer ADT

Summary

Exercises

7 Programming with Recursion

7.1 What Is Recursion? 7.2 The Classic Example of Recursion 7.3 Programming Recursively

Coding the Factorial Function

7.4 Verifying Recursive Functions

Three-Question Method

7.5 Writing Recursive Functions

Writing a Boolean Function

7.6 Using Recursion to Simplify Solutions 7.7 Recursive Linked List Processing 7.8 A Recursive Version of Binary Search 7.9 Recursive Versions of PutItem and DeleteItem

Function PutItem Function DeleteItem

7.10 How Recursion Works

Static Storage Allocation Dynamic Storage Allocation

7.11 Tracing the Execution of Recursive Function Insert 7.12 Recursive Quick Sort 7.13 Debugging Recursive Routines 7.14 Removing Recursion

Iteration Stacking

7.15 Deciding Whether to Use a Recursive Solution

Case Study: Escaping from a Maze

Summary

Exercises

8 Binary Search Trees

8.1 Searching

Linear Searching High-Probability Ordering Key Ordering Binary Searching

8.2 Trees 8.3 Logical Level 8.4 Application Level 8.5 Implementation Level 8.6 Recursive Binary Search Tree Operations

Functions IsFull and IsEmpty Function GetLength Function GetItem Function PutItem Function DeleteItem Function Print The Class Constructor and Destructor Copying a Tree More About Traversals Functions ResetTree and GetNextItem

8.7 Iterative Insertion and Deletion

Searching a Binary Search Tree Function PutItem Function DeleteItem Test Plan Recursion or Iteration?

8.8 Comparing Binary Search Trees and Linear Lists

Big-O Comparisons Case Study: Building an Index

Summary

Exercises

9 Heaps, Priority Queues, and Heap Sort

9.1 ADT Priority Queue

Logical Level Application Level Implementation Level

9.2 A Nonlinked Representation of Binary Trees 9.3 Heaps

Logical Level Application Level Implementation Level Application Level Revisited Heaps Versus Other Priority Queue Representations

9.4 Heap Sort Summary

Exercises

10 Trees Plus

10.1 AVL Trees

Single Rotations on AVL Trees Generalizing Single Rotations on AVL Trees Double Rotations on AVL Trees Generalizing Double Rotations on AVL Trees Application Level Logical Level Implementation Level

10.2 Red-Black Trees

Inserting into Red-Black Trees Implementing Recoloring for Red-Black Trees Red-Black Tree Summary

10.3 B-Trees Summary

Exercises

11 Sets, Maps, and Hashing

11.1 Sets

Logical Level Application Level Implementation Level

11.2 Maps

Logical Level Application Level Implementation Level

11.3 Hashing

Collisions Choosing a Good Hash Function Complexity

Summary

Exercises

12 Sorting

12.1 Sorting Revisited 12.2 Straight Selection Sort 12.3 Bubble Sort 12.4 Insertion Sort 12.5 O(N log2 N) Sorts

Merge Sort Quick Sort Heap Sort Testing

12.6 Efficiency and Other Considerations

When N Is Small Eliminating Calls to Functions Programmer Time Space Considerations Keys and Stability Sorting with Pointers Caching

12.7 Radix Sort

Analyzing the Radix Sort

12.8 Parallel Merge Sort Summary

Exercises

13 Graphs

13.1 Graphs

Logical Level Application Level Implementation Level

Summary

Exercises

Appendix A Reserved Words Appendix B Operator Precedence Appendix C A Selection of Standard Library Routines Appendix D American Standard Code for Information Interchange (ASCII) Character Sets Appendix E The Standard Template Library (STL) Glossary Index

← Prev
Back
Next →

← Prev
Back
Next →