DATA STRUCTURES WITH C++數(shù)據(jù)結(jié)構(gòu)：C++語言描述

     Preface xvll
   CHAPTER 1 INTRODUCTION
    1.1 Abstract Data Types
    ADT Format
    1.2 C++ Classes and Abstract Types
    Encapsulatlon and Information Hidlng
    Message Passing
    1.3 Objecls in C++ Appllcatlons
    Applicatlon: The Circle Class
    1.4 Oblect Design
    Objects and Composltion
    C++ Geometric Classes
    Objects and Inherltance
    Inheritance In Frogrammlng
    Ordered Llsts and Inheritance
    Software Reusability
    SeqLlst and OrderedLlsl Class Speclfications
    1.5 Applicatlons with Class Inherltance
    1.6 Object-Oriented Program Design
    Problem Analysis/Program Definition
    Deslgn
    Coding
    Tesllng
    Program Deslgn Illustratlon: A Dlce Graph
    1.7 Program Testlng and Malnlenance
    Object Testlng
    Contrul Module Testing
    Program Malntenance and Documentation
    1.8 The C++ Programming Language
    1.9 Abstract Base Classes and Polymorphism
    Polymorphlsm and Dynamic Binding
    Written Exerclses
   CHAPTER2 BASIC DATA TYMS
    2.1 IntegerTypes
    Computer Storage of Integers
    Data In Memory
    C++ Representatlon of Integers
    2.2 Character Types
    ASCIl Characlers
    2.3 Real Data Types
    Real Number Representatlons
    2.4 Enumerated Types
    Implementing C++ Enumerated Types
    2.5 Pointers
    Pointer ADT
    l'olnter Values
    2.6 The Array Type
    the Buill-In C++ Array Type
    Sloragc of One-Dimcnslonal Arrays
    Array Bounds
    Two-Dlmensional Arrays
    Storage of Two-Dimenslonal Arrays
    2.7 String Literals and Variables
    C++ Strings
    Appllcallon: Reverslng Names
    2.8 Records
    C++ Structures
    2.9 Files
    C++ Stream Hlerarchy
    2.10 Array and Record Appllcations
    Sequentlal Seareh
    Exchange Sort
    Counting C++ Reserved Words
    Wrltten Exercises
    ProgrammlIlg Exerclses
   CHAPTER 3 ABSTRACT DATA TYPES AND CLASSES
    3.1 The User Type CLASS
    Class Declaration
    Constructor
    Object Declarallon
    Class Implementatlon
    Implementing a Constructor
    Bulldlng Objects
    3.2 Sample Classes
    The Temperature Class
    The Random Number Class
    3.3 Oblects and Information Passlng
    An Object as a Return Value
    An Object as a Function Parameter
    3.4 Arrays of Objects
    The Default Conslructor
    3.5 Multlple Constructors
    3.6 Case Study: Triangular Matrices
    llpper Triangular Matrlx Properties
    Written Exerclses
    Programming Exereises
   CHAPTER 4 COLLECTION CLASSES
    4.1 Describing Llnear Collectlons
    Dlrecl Access Collections
    Sequentlal Access Collectlons
    Generalized Indexing
    4.2 Describing Nonlinear Collectlons
    Group Collectlons
    4.3 Analysls of Algorllhms
    Performance Crlteria
    Common Orders of Magnltude
    4.4 The Sequential and Blnary Search
    Blnary Search
    4.5 The Baslc Sequentlal List Class
    List Modincatlon Melhods
    Wrlllen Exerclses
    Programming Exerclses
   CHAPTER 5 STACKS AND QUEUES
    5.1 Stacks
    5.2 The Stack Class
    5.3 Expression Evaluation
    Postfix Evaluation
    Appllcatlon: A Posttlx Calculator
    5.4 Queues
    5.5 The Oueue Class
    5.6 Prlorlty Queues
    A Prlorlty Queue Class
    5.7 Case Study: Event-Drlven Slmulalion
    Wrltten Exerclses
    Programmlng Exerclses
   CHAPTER 6 ABSTRACT OPERATORS
    6.1 Describlng Operator Overloading
    Client-Defined External Functlons
    Class Members
    Frlend Functlons
    6.2 Rational Number System
    Representlng Ratlonal Numbers
    Ratlonal Number Arithtnetlc
    Ralional Number Converslon
    6.3 The Ratlonal Class
    6.4 Ratlonal Operators as Member Funclions
    Implemenllng the Ratlonal Operators
    6.5 The Ratlonal Stream Operators as Friends
    Implementlng Ratlonal Stream Operators
    6.6 Converting Rational Numbers
    Conversion to Object Type
    Converslon from Object Type
    6.7 Using Ratlonal Numbers
    Wrltten Exerclses
    Programmlng Exerclses
   CHAPTER 7 OENERIC DATA TYPES
    7.1 Template Functlons
    Template-Based Sort
    7.2 Template Classes
    Deflning a Template Class
    Declaring Template Class Oblects
    Defining Tcmplate Class Methods
    7.3 Template Llst Classes
    7.4 Infix Expression Evaluatlon
    Wrltten Exerclses
    Programming Exercises
   CHAPTER 8 CLASSES AND DYNAMIC MEMORY
    8.1 Pointers and Dynamic Data Structures
    The Memory Allocation Operator New
    Dynamlc Array Allocatlon
    The Memory Deallocatlon Operator Delete
    8.2 Dynamlcally Allocated Oblecte
    Deallocatlng Object Data: The Destructor
    8.3 Asslgnment and Inltlaltzatlon
    Asslgnment Issues
    Overloadlng the Assignment Operator
    The Thls Polnter
    Inltlallzatlon Issues
    Creating a Copy Constructor
    8.4 Safe Arrays
    The Array Class
    Memory Allocatlon for the Array Class
    Array Bounds Checklng and the Overloaded 1] Operator
    Convertlng an Object to a Polnter
    Using the Array Class
    8.5 A Strlng Class
    String Class Implemenlation
    8.6 Pattern Matehlng
    The Flnd Process
    Pattern Matchlng Algorlthm
    Analysls of the Pattern Matchlng Algorlthm
    8.7 Integral Sets
    Sets of Integral Types
    C++ Blt Handllng Operators
    Representlng Set Elements
    The Sleve of Eratosthenes
    Set Class Implementatlon
    Wrltten Exereises
    Programmlng Exerclses
    CHAPTER9 LINKIDLISTS
    Descrlbing a Llnked Llst
   Chapter 9 Overvlew
    9.1 The Node Class
    Declarlng a Node Type
    Implementlng the Node Class
    9.2 Bulldlng Llnked Llsts
    Creating a Node
    Insertlng a Node: InsertFront
    Traversing a Llnked Llst
    Insertlng a Node: InsertRear
    Appllcatlon: Student Graduatlon Llst
    Creatlng an Ordered Llst
    Appllcation: Sortlng wlth Llnked Llsts
    9.3 Deslgnlng a Llnked List Class
    Llnked Llst Data Members
    Llnked List Operatlons
    9.4 The LlnkedLlst Class
    9.5 Implementlng the LinkedList Class
    9.6 Implementlng Collectlons wlth Llnked Lists
    Llnked Queues
    Implementlng Queue Methods
    Llnked SeqLlst Class
    Implementlng SeqLlst Data Access Methods
    Appllcation: Comparlng SeqLlst Implementations
    9.7 Case Study: A Prlnt Spooler
    Implementing the Spooler Update Method
    Spooler Evaluation Methods
    9.8 Clreular Llsts
    Clrcular Node Class Implementation
    Appllcatlon: Solvlng the Josephus Problem
    9.9 Doubly Llnked Lista
    Appllcation: Doubly Linked List Sort
    DNode Class Implementation
    9.10 Case Study: Wlndow Management
    The Wlndow Llst
    WindowList Class Implementatlon
    Writlen Exerclses
    Programmlng Exercises
   CHAPTCR 10 RECURSION
    10.1 The Concept of Recurslon
    Recurslve Deflnltions
    Recursive Problems
    10.2 Deslgnlng Recurslve Functlons
    10.3 Recursive Code and the Runtlme Stack
    The Runtlme Stack
    10.4 Problem-Solvlng wlth Recurslon
    Blnary Search
    Combinatorics: The Commlttee Problem
    Combinalorlcs: Permutations
    Maze Handllng
    Maze Class Implementatlon
    10.5 Evaluatlng Recurslon
    Wrlllen Exerclses
    Programmlng Exerclses
   CHAPTER 11 TREES
    Tree Termlnology
    Binary Trees
    11.1 Binary Tree Structure
    Deslgning a TreeNode Class
    Bulldlng a Blnary Tree
    11.2 Deslgnlng TreeNode Funclions
    Recursive Tree Traversals
    11.3 Uslng Tree Scan Algorlthms
    Application: Vlsitlng Tree Nodes
    Appllcation: Tree Prlnt
    Appllcation: Copyfng and Delellng Trees
    Applicatlon: Upright Tree Prlnting
    11.4 Blnary Search Trees
    The Key in a Blnary Search Tree Node
    Operatlons on a Blnary Search Tree
    Declaring a Blnary Search Tree ADT
    11.5 LIsing Binary Search Trees
    Duplicate Nodes
    11.6 The BlnSTree Implementation
    List Operations
    11.7 Case Study: Concordance
    Written Exercises
    Programming Exercises
   CHAPTER 12 INHERITANCE AND ABSTRACT CLASSES
    12.1 A Vlew of Inheritance
    Class Inherltance Termlnology
    12.2 Inheritance In C++
    Constructors and Derived Classes
    What Cannot Be Inherited
    12.3 Polymorphism and Vlrtual Functlons
    Demonstratlng Polymorphlsm
    Appllcation: Geometrlc Figures and Virtual Methods
    Virtual Melhods and the Destructor
    12.4 Abstract Base Classes
    Abstract Base Class-List
    Derlvlng SeqLlst from Abstract Base Class List
    12.5 Iterators
    The Iterator Abstract Base Class
    Derlving Llst Iterators
    Building the SeqLlst Iterator
    Array Iterator
    Applicatlon: Merglng Sorted Runs
    Arraylterator Implementatlon
    12.6 Ordered Llsts
    OrderedLlst Class Implementatlon
    12.7 Heterogeneous Llsts
    Heterogeneous Arrays
    Heterogeneous Linked Lists
    Wrltten Exercises
    Programmlng Exerelses
   CHAPTER 13 ADVANCED NONLINEAR STRUCTURES
    13.1 Array-Based Binary Trees
    Appllcation: The Tournament Sort
    13.2 Heaps
    The Heap as a List
    The Heap Class
    13.3 Implementlng the Heap Class
    Appllcatlon: Heap Sort
    13.4 Priorlty Queues
    Appllcation: Long Runs
    13.5 AVLTrees
    AVL Tree Nodes
    13.6 The AVL Tree Class
    Memory Allocation for the AVLTree
    Evaluatlng AVL Trees
    13.7 Trce Iterators
    The Inorder Iterator
    Inorderlteralor Class Implementatlon
    Appllcation: TreeSort
    13.8 Graphs
    Connected Components
    13.9 The Graph Class
    Declaring a Graph ADT
    Graph Class Implementatlon
    Graph Traversals
    Appllcatlons
    Reachabillty and Warshall's Algorlthm
    Writlen Exercises
    Programmlng Exercises
   CHAPTER 14 ORGANIZING COLLECTIONS
    14.1 Baslc Array Sortlng Algorithms
    The Selection Sort
    The Bubble Sorl
    The Insertion Sort
    14.2 OuickSort
    OulckSort Descrlption
    OuickSort Algorithm
    Comparison of Array Sort Algorithms
    14.3 Hashing
    Keys and a Hash Function
    Hashing Functions
    Other Hash Methods
    Colllslon Resolutlon
    14.4 Hash Table Class
    Appllcation: Strlng Frequency
    HashTable Class Implementation
    HashTableIterator Class Implementation
    14.5 The Performance of Searching Methods
    14.6 Blnary Flles and External Data Operatlons
    Binary Flles
    The BlnFlle Class
    External Flle Searching
    External Flle Sort
    Long Run MergeSort
    14.7 Dictionarles
    Writlen Exerclses
    Programming Exercises
   APPENDIX ANSWERS TO SELECTED EXERCISES
   BIBLIOGRAPHY