《数据结构算法与应用 C++语言描述 英文版》

Chapter 1 Programming in C++1

CHAPTER 1 PROGRAMMING IN C++1

PARTⅠ PRELIMINARIES1

PATR ⅠPRELIMINARIES1

1.2.1 Value Parameters3

1.2 Functions and Parameters3

1.1 Introduction3

1.2.2 Template Functions4

1.2.3 Reference Parameters5

1.2.4 Const Reference Parameters6

1.2.5 Return Values7

1.2.6 Recursive Functions8

1.3.1 The Operator new14

1.3 Dyanmic Memory Allocation14

1.3.2 One-Dimensional Arrays15

1.3.3 Exception Handling15

1.3.4 The Operator delete16

1.3.5 Two-Dimensional Arrays17

1.4.1 The Class Currency20

1.4 Classes20

1.4.2 Using a Different Representation28

1.4.3 Operator Overloading29

1.4.4 Throwing Exceptions32

1.4.5 Friends and Protected Class Members33

1.4.6 Addition of#iEndef,#define,and#endif Statements36

1.5 Testing and Debugging37

1.5.1 What Is Testing?37

Roots of a quadratic37

1.5.2 Designing Test Data40

Finding the maximum element40

1.5.3 Debugging43

1.6 References and Selected Readings44

CHAPTER 2 PROGRAM PERFORMANCE45

Chapter 2 Program Performance++45

2.1 Introduction47

2.2 Space Complexity48

2.2.1 Components of Space Complexity48

2.2.2 Examples54

2.3 Time Complexity57

2.3.1 Components of Time Complexity57

2.3.2 Operation Counts58

2.3.3 Step Counts68

2.4 Asymptotic Notation(O,(,(,o)83

2.4.1 Big Oh Notation(O)84

2.4.2 Omega Notation(()88

2.4.3 Theta Notation(()89

2.4.4 Little Oh(o)90

2.4.5 Properties91

2.4.6 Complexity Analysis Examples91

Binary search91

2.5 Practical Complexities98

2.6 Performance Measurement102

2.6.1 Choosing Instance Size102

2.6.2 Developing the Test Data103

2.6.3 Setting Up the Experiment104

2.7 References and Selected Readings110

Chapter 3 Data Representation111

PART Ⅱ DATA STRUCTURES111

CHAPTER 3 DATA REPRESENTATION111

PART Ⅱ DATA STRUCTURES111

3.1 Introduction113

3.2 Linear Lists114

3.3 Formula-Based Representation116

3.3.1 Representation116

3.3.2 The Exception Class NoMem117

3.3.3 Operations118

3.3.4 Evaluation122

3.4 Linked Representation129

3.4.1 The Classes ChainNode and Chain129

3.4.2 Operations130

3.4.3 Extensions the Class Chain136

3.4.4 A Chain Iterator Class137

3.4.5 Circular List Representation138

3.4.6 Comparison with Formula-Based Representation139

3.4.7 Doubly Linked List Representation140

3.4.8 Summary142

3.5 Indirect Addressing146

3.5.1 Representation146

3.5.2 Operations147

3.6 Simulating Pointers152

3.6.1 SimSpace Operations153

3.6.2 Chains Using Simulated Pointers157

3.7 A Comparison163

3.8 Applications164

3.8.1 Bin Sort164

3.8.2 Radix Sort170

3.8.3 Equivalence Classes173

3.8.4 Convex Hull180

3.9 References and Selected Readings188

CHAPTER 4 ARRAYS AND MATRICES189

Chapter 4 Arrays and Matrices189

4.1 Arrays191

4.1.1The Abstract Data Type191

4.1.2 Indexing a C++Array192

4.1.3 Row-and Column-Major Mappings192

4.1.4 The Class Array1D194

4.1.5 The Class Array2D197

4.2 Matrices204

4.2.1 Definitions and Operations204

4.2.2 The Class Matrix206

4.3 Special Matrices210

4.3.1 Definitions and Applications210

4.3.2 Diagonal Matrices212

4.3.3 Tridiagonal Matrix214

4.3.4 Triangular Matrices216

4.3.5 Symmetric Matrices218

4.4 Sparse Matrices221

4.4.1 Motivation221

4.4.2 Array Representation222

4.4.3 Linked Representation229

CHAPTER 5 STACKS239

Chapter 5 Stacks239

5.1 The Abstract Data Type241

5.2 Derived Classes and Inheritance241

5.3 Formula-Based Representation243

5.4 Linked Representation248

5.5 Applications252

5.5.1 Parenthesis Matching252

5.5.2 Towers of Hanoi254

5.5.3 Rearranging Railroad Cars256

5.5.4 Switch Box Routing263

5.5.5 Offline Equivalence Problem264

5.5.6 Rat in a Maze268

5.6 References and Selected Readings281

CHAPTER 6 QUEUES283

Chapter 6 Queues283

6.1 The Abstract Data Type285

6.2 Formula-Based Representation286

6.3 Linked Representation292

6.4 Applications297

6.4.1 Railroad Car Rearrangement297

6.4.2 Wire Routing299

6.4.3 Image Component Labeling306

6.4.4 Machine Shop Simulation309

6.5 References and Selected Readings324

CHAPTER 7 SKIP LISTS AND HASHING325

Chapter 7 Skip Lists and Hashing325

7.1 Dictionaries327

7.2 Linear List Representation328

7.3 Skip List Representation332

7.3.1 The Ideal Case332

7.3.2 Insertions and Deletions334

7.3.3 Assigning Levels335

7.3.4 The Class SkipNode336

7.3.5 The Class SkipList337

7.3.6 Complexity342

7.4 Hash Table Representation343

7.4.1 Ideal Hashing343

7.4.2 Hashing with Linear Open Addressing344

7.4.3 Hashing with Chains350

7.5 An Application—Text Compression357

7.5.1 LZW Compression358

7.5.2 Implementation of LZW Compression359

7.5.3 LZW Decompression364

7.5.4 Implementation of LZW Decompression365

7.6 References and Selected Readings370

CHAPTER 8 BINARY AND OTHER TREES371

Chapter 8 Binary and Other Trees371

8.1 Trees373

8.2 Binary Trees378

8.3 Properties of Binary Trees379

8.4.1 Formula-Based Representation382

8.4 Representation of Binary Trees382

8.4.2 Linked Representation383

8.5 Common Binary Tree Operations385

8.6 Binary Tree Traversal386

8.8 The Class BinaryTree391

8.7 The ADT BinaryTree391

8.9 ADT and Class Extensions392

8.9.3 Height397

8.9.2 Delete397

8.9.1 Output397

8.9.4 Size398

8.10.1 Placement of Signal Boosters400

8.10 Applications400

8.10.2 Online Equivalence Classes405

8.11 References and Selected Readings416

Chapter 9 Priority Queues417

CHAPTER 9 PRIORITY QUEUES417

9.1 Introduction419

9.2 Linear Lists421

9.3 Heaps421

9.3.1 Definitions421

9.3.2 Insertion into a Max Heap423

9.3.3 Deletion from a Max Heap424

9.3.4 Max Heap Initialization424

9.3.5 The Class MaxHeap425

9.4 Liftist Trees432

9.4.1 Height-and Weight-Biased Min and Max Leftist Trees432

9.4.3 Deletion from a Max HBLT435

9.4.4 Melding Two Max HBLTs435

9.4.2 Insertion into a Max HBLT435

9.4.5 Initialization437

9.4.6 The Class MaxHBLT438

9.5 Applications444

9.5.1 Heap Sort444

9.5.2 Machine Scheduling444

9.5.3 Huffman Codes450

9.6 References and Selected Readings457

CHAPTER 10 TOURNAMENT TREES459

Chapter 10 Tournament Trees459

10.1 Introduction461

10.2 The ADT WinnerTree466

10.3 The Class WinnerTree466

10.3.1 Representation466

10.3.2 Class Specification467

10.3.3 Constructor,Destructor,and Winner467

10.3.4 Initializing a Winner Tree468

10.3.5 Replaying Matches471

10.4 Loser Trees472

10.5.1 Bin Packing Using First Fit472

10.5 Applications474

10.5.2 Bin Packing Using Next Fit480

Chapter 11 Search Trees485

CHAPTER 11 SEARCH TREES485

11.1 Binary Search Trees488

11.1.1 Definition488

11.1.2 The ADTs BSTree and IndexedBSTree490

11.1.3 The Class BSTree491

11.1.4 Searching492

11.1.5 Inserting an Element493

11.1.6 Deleting an Element493

11.1.8 Height of a Binary Search Tree496

11.1.7 The Class DBSTree496

11.2 AVL Trees500

11.2.1 Definition500

11.2.2 Height of an AVL Tree501

11.2.3 Representation of an AVL Tree501

11.2.4 Searching an AVL Search Tree502

11.2.5 Inserting into an AVL Search Tree502

11.2.6 Deletion from an AVL Search Tree506

11.3.1 Definition510

11.3 Red-Black Trees510

11.3.2 Representation of a Red-Black Tree512

11.3.3 Searching a Red-Black Tree512

11.3.4 Inserting into a Red-Black Tree513

11.3.5 Deletion from a Red-Black Tree518

11.3.6 Implementation Considerations and Complexity521

11.4 B-Trees524

11.4.1 Indexed Sequential Access Method524

11.4.2 m-way Search Trees525

11.4.3 B-Trees of Order m528

11.4.4 Height of a B-tree529

11.4.5 Searching a B-tree530

11.4.6 Inserting into a B-tree530

11.4.7 Deletion from a B-tree533

11.4.8 Node Structure537

11.5 Applications539

11.5.1 Histogramming539

11.5.2 Best-Fit Bin Packing543

11.5.3 Crossing Distribution546

11.6 References and Selected Readings553

Chapter 12 Graphs555

CHAPTER 12 GRAPHS555

12.1 Definitions557

12.2 Applications558

12.3 Properties562

12.4 The ADTs Graph and Digraph565

12.5 Representation of Graphs and Digraphs567

12.5.1 Adjacency Matrix567

12.5.2 Packed-Adjacency Lists569

12.5.3 Linked-Adjacency Lists570

12.6 Representation of Networks573

12.7 Class Definitions575

12.7.1 The Different Classes575

12.7.2 Adjacency-Matrix Classes576

12.7.3 An Extension to the Class Chain580

12.7.4 The Class LinkedBase580

12.7.5 Linked Classes581

12.8 Graph Iterators588

12.8.1 Specification588

12.8.2 Iterator Functions for Adjacency-Matrix Representations589

12.8.3 Iterator Functions for Linked-Adjacency Lists589

12.9 Language Features592

12.9.1 Virtual Functions and Polymorphism592

12.9.2 Pure Virtual Functions and Abstract Classes595

12.9.3 Virtual Base Classes596

12.9.4 Abstract Classes and Abstract Data Types598

12.10 Graph Search Methods600

12.10.1 Breadth-First Search600

12.10.3 Implementation of Network::BFS602

12.10.4 Complexity Analysis of Network::BFS602

12.10.2 The Class Network602

12.10.5 Depth-First Search605

12.11 Applications Revisited607

12.11.1 Finding a Path607

12.11.2 Connected Graphs and Components609

12.11.3 Spanning Trees611

PART Ⅲ ALGORITHM-DESIGN METHODS615

Chapter 13 The Greedy Method615

CHAPTER 13 THE GREEDY METHOD615

PART Ⅲ ALLGORITHM-DESIGN METHODS615

13.1 Optimization Problems617

13.2 The Greedy Method618

13.3 Applications623

13.3.1 Container Loading623

13.3.2 0/1 Knapsack Problem624

13.3.3 Topological Sorting628

13.3.4 Bipartite Cover633

13.3.5 Single-Source Shortest Paths642

13.3.6 Minimum-Cost Spanning Trees646

13.4 References and Selected Readings659

Chapter 14 Divide and Conquer661

CHAPTER 14 DIVIDE AND CONQUER661

14.1 The Method662

14.2 Applications672

14.2.1 Defective Chessboard672

14.2.2 Merge Sort677

14.2.3 Quick Sort682

14.2.4 Selection688

14.2.5 Closest Pair of Points691

14.3 Solving Recurrence Equations703

14.4 Lower Bounds on Complexity705

14.4.1 Lower Bound for the Minmax Problem706

14.4.2 Lower Bound for Sorting708

CHAPTER 15 DYNAMIC PROGRAMMING711

Chapter 15 Dynamic Programming711

15.1 The Method712

15.2 Applications715

15.2.1 0/1 Knapsack Problem715

15.2.2 Image Compression719

15.2.3 Matrix Multiplication Chains724

15.2.4 All Pairs Shortest Paths731

15.2.5 Noncrossing Subset of Nets735

15.2.6 Component Folding740

15.3 References and Selected Readings749

Chapter 16 Backtracking751

CHAPTER 16 BACKTRACKING751

16.1 The Method753

16.2.1 Container Loading760

16.2 Applications760

16.2.2 0/1 Knapsack Problem769

16.2.3 Max Clique772

16.2.4 Traveling Salesperson775

16.2.5 Board Permutation778

Chapter 17 Branch and Bound787

CHAPTER 17 BRANCH AND BOUND787

17.1 The Method788

17.2 Applications792

17.2.1 Container Loading792

17.2.2 0/1 Knapsack Problem802

17.2.3 Max Clique805

17.2.4 Traveling Salesperson807

17.2.5 Board Permutation810

INDEX817

INDEX817