數(shù)據(jù)結構、算法與應用—C++語言描述（英文版）

     BRIEF CONTENTS
   PARTI PRELIMINARIES
    Chapter 1 Programming in C++
    Chapter 2 Program Pferformance++
   PARTII DATASTRUCTURES
    Chapter 3 Data Reprcsentation
    Chapter4 Arrays and Matrices
    Chapter 5 Stacks
    Chapter 6 Queues
    Chapter 7 Skip Lists and Hashing
    Chapter 8 Binary and Other Trees
    Chapter 9 Priority Queues
    ChapterlO ToumamentTrees
    Chapter 11 Search Trees
    Chapter12 Graphs
   PARTffl ALGORITHM-DESIGNMETHODS
    Chapter13 The Grcedy Method
    Chapter 14 Divide and Conquer
    Chapter 15 Dynamic Programming
    Chapter16 Backtracking
    Chapter 17 Branch and Bound
   INDEX
    CONTENTS
   PARTl PRELlMlNARlES
    CHAPTERl PROGRAMMlNGlNC++
    l.l Introduction
    l.2 Functions and Parameters
    l.2.l Value Parameters
    1.2.2 Template Functions
    l.2.3 Reference Parameters
    l.2.4 Const Reference Parameters
    l.2.5 RetumValues
    1.2.6 Recursive Functions
    Fibonacci nwnbers
    Factorial
    Permutations
    1.3 Dynamic Memory Allocation
    1.3.1 The Operator new
    1.3.2 One-Dimensional Arrays
    1.3.3 Exception Handling
    1.3.4 TheOperatordelete
    1.3.5 Two-Dimensional Anays
    1.4 Classes 20
    1.4.1 The Class Currency
    1.4.2 Using a Difierent Representation
    1.4.3 Operator Overioading
    1.4.4 Throwing Exceptions
    1.4.5 Friends and Protected Class Members
    1.4.6 Addition of #ifndef, #define, and #endif Statements
    1.5 Testing and Debugging
    1.5.1 What Is Testing? Roots ofa quadratic
    1.5.2 Designing Test Data Finding the maximum element
    1.5.3 Debugging
    1.6 References and Selected Readings
    CHAPTER2 PROGRAMPERFORMANCE
    2.1 Introduction
    2.2 Space Complexity
    2.2.1 Components of Space Complexity
    2.2.2 Examples
    2.3 Time Complexity
    2.3.1 Components of Time Complexity
    2.3.2 Operation Counts
    Polynomial evaluation
    Rank sort
    Selection sort
    Bubble sort
    Insertion sort
    Sequential search
    2.3.3 StepCounts
    Matrix add, multiply, and transpose
    Minimwn and maximum
    2.4 Asymptotic Notation (O, ωΩ, θ, o)
    2.4.1 BigOhNotation(O)
    2.4.2 Omega Notation (Ω)
    2.4.3 Theta Notation (θ)
    2.4.4 LittleOh(o)
    2.4.5 Properties
    2.4.6 Complexity Analysis Examples Binary search
    2.5 Practical Complexities
    2.6 Performance Measurement
    2.6.1 Choosing Instance Size
    2.6.2 Developing the Test Data
    2.6.3 Setting Up the Experiment
    2.7 References and Selected Readings
   PARTII DATA STRUCTURES
    CHAPTER3 DATAREPRESENTATION
    3.1 Introduction
    3.2 LinearLists
    3.3 Formula-Based Representation
    3.3.1 Representation
    3.3.2 The Exception Class NoMem
    3.3.3 Operations
    3.3.4 Evaluation
    3.4 Linked Representation
    3.4.1 The Classes ChainNode and Chain
    3.4.2 Operations
    3.4.3 Extensions to the Class Chain
    3.4.4 AChainIteratorClass
    3.4.5 Circular List Reprcsentation
    3.4.6 Comparison with Formula-Based Representation
    3.4.7 Doubly Linked List Representation
    3.4.8 Summary
    3.5 Indircct Addressing
    3.5.1 Representation
    3.5.2 Operations
    3.6 Simulating Pointers
    3.6.1 SimSpace Operations
    3.6.2 Chains Using Simulated Pointers
    3.7 A Comparison
    3.8 Applications
    3.8.1 BinSort
    3.8.2 RadixSort
    3.8.3 Equivalence Classes
    Machine scheduling
    Electrical nets
    3.8.4 ConvexHull
    3.9 References and Selected Readings
    CHAPTER4 ARRAYSANDMATMCES
    4.1 Arrays 191
    4.l.l The Abstract Data Type
    4.1.2 IndexingaC++Array
    4.l.3 Row- and Column-Major Mappings
    4.1.4 TheClassArraylD
    4.1.5 TheClassArray2D
    4.2 Matrices
    4.2.1 Definitions and Operations
    4.2.2 TheClassMatrix
    4.3 Special Matrices
    4.3.1 Definitions and Applications
    4.3.2 Diagooal Matrices
    4.3.3 TtidiagonalMatrix
    4.3.4 TriangularMatrices
    4.3.5 Symmetric Matrices
    4.4 Sparse Matrices
    4.4.1 Motivation
    4.4.2 Array Representation
    4.4.3 Linked Reprcsentation
    CHAPTER5 STACKS
    5.1 TheAbstractDataType
    5.2 Derived Classes and Inheritance
    5.3 Fbnnula-BasedRepresentation
    5.4 Linked Reprcsentation
    5.5 Applications
    5.5.1 Parenthesis Matching
    5.5.2 TowersofHanoi
    5.5.3 ReanangingRailroadCars
    5.5.4 Switeh Box Routing
    5.5.5 Offline Equivalence Problem
    5.5.6 RatinaMaze
    5.6 References and Selected Readings
    CHAPTER6 QUEUES
    6.l The Abstract Data Type
    6.2 Fbnnula-Based Representation
    6.3 Linked Representation
    6.4 Applications
    6.4.1 Railroad Car Rearrangement
    6.4.2 Wirc Routing
    6.4.3 Image Component Labeling
    6.4.4 Machine Shop Simulation
    6.5 References and Selected Readings
    CHAPTER7 SKlPLlSTSANDHASHlNG
    7.1 Dictionaries
    7.2 Linear List Reprcsentation
    7.3 Skip List Reprcsentation
    7.3.1 TheldealCase
    7.3.2 Insertions and Deletions
    7.3.3 Assigning Levels
    7.3.4 The Class SkipNode
    7.3.5 TheClassSkipList
    7.3.6 Complexity
    7.4 Hash Table Representation
    7.4.1 IdealHashing
    7.4.2 Hashing with Linear Open Addressing
    7.4.3 Hashing with Chains
    7.5 An Application-Text Compression
    7.5.1 LZWCompression
    7.5.2 Implementation of LZW ComDression
    7.5.3 LZW Decompression
    7.5.4 Implementation of LZW Decompression
    7.6 References and Selected Readings
    CHAPTER8 BlNARYANDOTHERTREES
    8.1 Trees
    8.2 BinaryTrees
    8.3 Properties of Binary Trees
    8.4 Representation of Binary Trees
    8.4.1 Fonnula-Based Representation
    8.4.2 Linked Representation
    8.5 Common Binary Tree Operations
    8.6 Binary Tree Traversal
    8.7 The ADT BinaryTree
    8.8 The Class BinaryTree
    8.9 ADT and Class Extensions
    8.9.1 Output
    8.9.2 Delete
    8.9.3 Height
    8.9.4 Size
    8.10 Applications
    8.10.1 PlacementofSignalBoosters
    8.10.2 Online Equivalence Classes
    8.11 References and Selected Readings
    CHAPTER9 PMORITYOUEUES
    9.1 Introduction
    9.2 LinearLists
    9.3 Heaps
    9.3.1 Definitions
    9.3.2 Insertion into a Max Heap
    9.3.3 Deletion from a Max Heap
    9.3.4 Max Heap Initialization
    9.3.5 The Class MaxHeap
    9.4 LeftistTrees
    9.4.1 Height- and Weight-Biased Min and Max Leftist Trees
    9.4.2 Insertion into a Max HBLT
    9.4.3 Deletion from a Max HBLT
    9.4.4 MeldingTwoMaxHBLTs
    9.4.5 Initialization
    9.4.6 The Class MaxHBLT
    9.5 Applications
    9.5.1 Heap Sort
    9.5.2 Machine Scheduling
    9.5.3 Huffinan Codes
    9.6 References and Selected Readings
    CHAPTERIO TOURNAMENTTREES
    10.1 Introduction
    10.2 The ADT WinnerTree
    10.3 The Class WinnerTree
    10.3.1 Representation
    10.3.2 ClassSpecification
    10.3.3 Constructor, Destructor, and Winner
    10.3.4 Initializing a Winner Tree
    10.3.5 Replaying Matches
    10.4 LoserTrees
    10.5 Applications
    10.5.1 Bin Packing Using First Fit
    10.5.2 Bin Packing Using Next Fit
    CHAPTERll SEARCHTREES
    11.1 Binary Search Trces
    11.1.1 Definition
    11.1.2 The ADTs BSTree and IndexedBSTree
    11.1.3 TheClass BSTree
    11.1.4 Searching
    11.1.5 Inserting an Eiement
    11.1.6 Deleting an Element
    11.1.7 The Class DBSTree
    11.1.8 Height of a Binary Search Tree
    11.2 AVLTrees
    11.2.1 Definition
    11.2.2 HeightofanAVLTree
    11.2.3 Representation of an AVL Tree
    11.2.4 Searching an AVL Search Tree
    11.2.5 Inserting into an AVL Search Tree
    11.2.6 Deletion from an AVL Search Tree
    11.3 Red-Black Trees
    11.3.1 Definition
    11.3.2 Representation of a Red-Black Tree
    11.3.3 Searching a Red-Black Tree
    11.3.4 Inserting into a Red-Black Trce
    11.3.5 Deletion from a Red-Black Tree
    11.3.6 Implementation Considerations and Complexity
    11.4 B-Trees 524
    11.4.1 Indexed Sequential Access Method
    11.4.2 m-way Search Trees
    11.4.3 B-TreesofOrderm
    11.4.4 HeightofaB-trce
    11.4.5 Searching a B-tree
    11.4.6 Inserting into a B-tree
    11.4.7 Deletion from a B-tree
    11.4.8 Node Structure
    11.5 Applications
    11.5.1 Histogramnung
    11.5.2 Best-FitBinPacking
    11.5.3 Crossing Distribution
    11.6 References and Selected Readings
    CHAPTER12 GRAPHS
    12.1 Definitions
    12.2 Applications
    12.3 Properties
    12.4 The ADTs Graph and Digraph
    12.5 Representation of Graphs and Digraphs
    12.5.1 Adjacency Matrix
    12.5.2 Packed-Adjacency Lists
    12.5.3 Linked-Adjacency Lists
    12.6 Representation of Networks
    12.7 Class Definitions
    12.7.1 The Diflfercnt Classes
    12.7.2 Adjacency-Matrix Classes
    12.7.3 An Extension to the Class Cha i n
    12.7.4 The Class LinkedBase
    12.7.5 Linked Classes
    12.8 Graph Iterators
    12.8.1 Specification
    12.8.2 Iterator Functions for Adjacency-Matrix Reprcsentations
    12.8.3 Iterator Functions for Linked-Adjacency Lists
    12.9 Language Features
    12.9.1 Virtual Functions and Polymorphism
    12.9.2 Pure Virtual Functions and Abstract Classes
    12.9.3 Virtual Base Classes
    12.9.4 Abstract Classes and Abstract Data Types
    12.10 Graph Search Methods
    12.10.1 Brcadth-First Search
    12.10.2 The Class Network
    12.10.3 ImplementationofNetwork: BFS
    12.10.4 ComplexityAnalysisofNetwork: BFS
    12.10.5 Depth-First Search
    12.11 Applications Revisited
    12.11.1 FindingaPath
    12.11.2 Connected Graphs and Components
    12.11.3 SpannmgTrees
   PARTIII ALGORITHM-DESIGNMETHODS
    CHAPTERI13 THEGREEDYMETHOD
    13.1 Optimization Problems
    13.2 The Greedy Method
    13.3 Applications
    13.3.1 Container Loading
    13.3.2 0/1 Knapsack Problem
    13.3.3 Topological Sorting
    13.3.4 Bipartite Cover
    13.3.5 Single-Source Shortest Paths
    13.3.6 Minimum-Cost Spanning Trees
    Kruskal 's Algorithm
    Prim's Algorithm
    Sollin's Algorithm
    13.4 Refercnces and Selected Readings
    CHAPTER 14 DIVIDE AND CONQUER
    14.1 TheMethod
    Minimwn and maximum
    Strassen's matrix multiply
    14.2 Applications
    14.2.1 Defective Chessboard
    14.2.2 Merge Sort
    14.2.3 QuickSort
    14.2.4 Selection
    14.2.5 ClosestPairofPoints
    14.3 Solving Recurrence Equations
    14.4 Lower Bounds on Complexity
    14.4.1 Lower Bound for the Minmax Problem
    14.4.2 Lower Bound for Sorting
    CHAPTERI15 DYNAMICPROGRAMMING
    15.1 TheMethod
    15.2 Applications
    15.2.1 0/1 Knapsack Problem
    15.2.2 Image Compression
    15.2.3 Matrix Multiplication Chains
    15.2.4 All Pairs Shortest Paths
    15.2.5 NoncrossingSubsetofNets
    15.2.6 Component Fblding
    15.3 References and Selected Readings
    CHAPTER16 BACKTRACKING
    16.1 TheMethod
    16.2 Applications
    16.2.1 Container Loading
    16.2.2 0/1Knapsackproblem
    16.2.3 MaxClique
    16.2.4 Traveling Salesperson
    16.2.5 Board Permutation
    CHAPTERl17 BRANCHANDBOUND
    17.1 TheMethod
    17.2 Applications
    17.2.1 ContainerLoading
    17.2.2 0/1 Knapsack Problem
    17.2.3 MaxClique
    17.2.4 Traveling Salesperson
    17.2.5 BoardPennutation
   INDEX