数据结构、算法与应用—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