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
鄂公网安备 42010302001612号 