数据结构算法与应用 C++语言描述 英文版PDF电子书下载

Chapter 1 Programming in C++ 1

CHAPTER 1 PROGRAMMING IN C++ 1

PARTⅠ PRELIMINARIES 1

PATR ⅠPRELIMINARIES 1

1.2.1 Value Parameters 3

1.2 Functions and Parameters 3

1.1 Introduction 3

1.2.2 Template Functions 4

1.2.3 Reference Parameters 5

1.2.4 Const Reference Parameters 6

1.2.5 Return Values 7

1.2.6 Recursive Functions 8

1.3.1 The Operator new 14

1.3 Dyanmic Memory Allocation 14

1.3.2 One-Dimensional Arrays 15

1.3.3 Exception Handling 15

1.3.4 The Operator delete 16

1.3.5 Two-Dimensional Arrays 17

1.4.1 The Class Currency 20

1.4 Classes 20

1.4.2 Using a Different Representation 28

1.4.3 Operator Overloading 29

1.4.4 Throwing Exceptions 32

1.4.5 Friends and Protected Class Members 33

1.4.6 Addition of#iEndef,#define,and#endif Statements 36

1.5 Testing and Debugging 37

1.5.1 What Is Testing? 37

Roots of a quadratic 37

1.5.2 Designing Test Data 40

Finding the maximum element 40

1.5.3 Debugging 43

1.6 References and Selected Readings 44

CHAPTER 2 PROGRAM PERFORMANCE 45

Chapter 2 Program Performance++ 45

2.1 Introduction 47

2.2 Space Complexity 48

2.2.1 Components of Space Complexity 48

2.2.2 Examples 54

2.3 Time Complexity 57

2.3.1 Components of Time Complexity 57

2.3.2 Operation Counts 58

2.3.3 Step Counts 68

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 Properties 91

2.4.6 Complexity Analysis Examples 91

Binary search 91

2.5 Practical Complexities 98

2.6 Performance Measurement 102

2.6.1 Choosing Instance Size 102

2.6.2 Developing the Test Data 103

2.6.3 Setting Up the Experiment 104

2.7 References and Selected Readings 110

Chapter 3 Data Representation 111

PART Ⅱ DATA STRUCTURES 111

CHAPTER 3 DATA REPRESENTATION 111

PART Ⅱ DATA STRUCTURES 111

3.1 Introduction 113

3.2 Linear Lists 114

3.3 Formula-Based Representation 116

3.3.1 Representation 116

3.3.2 The Exception Class NoMem 117

3.3.3 Operations 118

3.3.4 Evaluation 122

3.4 Linked Representation 129

3.4.1 The Classes ChainNode and Chain 129

3.4.2 Operations 130

3.4.3 Extensions the Class Chain 136

3.4.4 A Chain Iterator Class 137

3.4.5 Circular List Representation 138

3.4.6 Comparison with Formula-Based Representation 139

3.4.7 Doubly Linked List Representation 140

3.4.8 Summary 142

3.5 Indirect Addressing 146

3.5.1 Representation 146

3.5.2 Operations 147

3.6 Simulating Pointers 152

3.6.1 SimSpace Operations 153

3.6.2 Chains Using Simulated Pointers 157

3.7 A Comparison 163

3.8 Applications 164

3.8.1 Bin Sort 164

3.8.2 Radix Sort 170

3.8.3 Equivalence Classes 173

3.8.4 Convex Hull 180

3.9 References and Selected Readings 188

CHAPTER 4 ARRAYS AND MATRICES 189

Chapter 4 Arrays and Matrices 189

4.1 Arrays 191

4.1.1The Abstract Data Type 191

4.1.2 Indexing a C++Array 192

4.1.3 Row-and Column-Major Mappings 192

4.1.4 The Class Array1D 194

4.1.5 The Class Array2D 197

4.2 Matrices 204

4.2.1 Definitions and Operations 204

4.2.2 The Class Matrix 206

4.3 Special Matrices 210

4.3.1 Definitions and Applications 210

4.3.2 Diagonal Matrices 212

4.3.3 Tridiagonal Matrix 214

4.3.4 Triangular Matrices 216

4.3.5 Symmetric Matrices 218

4.4 Sparse Matrices 221

4.4.1 Motivation 221

4.4.2 Array Representation 222

4.4.3 Linked Representation 229

CHAPTER 5 STACKS 239

Chapter 5 Stacks 239

5.1 The Abstract Data Type 241

5.2 Derived Classes and Inheritance 241

5.3 Formula-Based Representation 243

5.4 Linked Representation 248

5.5 Applications 252

5.5.1 Parenthesis Matching 252

5.5.2 Towers of Hanoi 254

5.5.3 Rearranging Railroad Cars 256

5.5.4 Switch Box Routing 263

5.5.5 Offline Equivalence Problem 264

5.5.6 Rat in a Maze 268

5.6 References and Selected Readings 281

CHAPTER 6 QUEUES 283

Chapter 6 Queues 283

6.1 The Abstract Data Type 285

6.2 Formula-Based Representation 286

6.3 Linked Representation 292

6.4 Applications 297

6.4.1 Railroad Car Rearrangement 297

6.4.2 Wire Routing 299

6.4.3 Image Component Labeling 306

6.4.4 Machine Shop Simulation 309

6.5 References and Selected Readings 324

CHAPTER 7 SKIP LISTS AND HASHING 325

Chapter 7 Skip Lists and Hashing 325

7.1 Dictionaries 327

7.2 Linear List Representation 328

7.3 Skip List Representation 332

7.3.1 The Ideal Case 332

7.3.2 Insertions and Deletions 334

7.3.3 Assigning Levels 335

7.3.4 The Class SkipNode 336

7.3.5 The Class SkipList 337

7.3.6 Complexity 342

7.4 Hash Table Representation 343

7.4.1 Ideal Hashing 343

7.4.2 Hashing with Linear Open Addressing 344

7.4.3 Hashing with Chains 350

7.5 An Application—Text Compression 357

7.5.1 LZW Compression 358

7.5.2 Implementation of LZW Compression 359

7.5.3 LZW Decompression 364

7.5.4 Implementation of LZW Decompression 365

7.6 References and Selected Readings 370

CHAPTER 8 BINARY AND OTHER TREES 371

Chapter 8 Binary and Other Trees 371

8.1 Trees 373

8.2 Binary Trees 378

8.3 Properties of Binary Trees 379

8.4.1 Formula-Based Representation 382

8.4 Representation of Binary Trees 382

8.4.2 Linked Representation 383

8.5 Common Binary Tree Operations 385

8.6 Binary Tree Traversal 386

8.8 The Class BinaryTree 391

8.7 The ADT BinaryTree 391

8.9 ADT and Class Extensions 392

8.9.3 Height 397

8.9.2 Delete 397

8.9.1 Output 397

8.9.4 Size 398

8.10.1 Placement of Signal Boosters 400

8.10 Applications 400

8.10.2 Online Equivalence Classes 405

8.11 References and Selected Readings 416

Chapter 9 Priority Queues 417

CHAPTER 9 PRIORITY QUEUES 417

9.1 Introduction 419

9.2 Linear Lists 421

9.3 Heaps 421

9.3.1 Definitions 421

9.3.2 Insertion into a Max Heap 423

9.3.3 Deletion from a Max Heap 424

9.3.4 Max Heap Initialization 424

9.3.5 The Class MaxHeap 425

9.4 Liftist Trees 432

9.4.1 Height-and Weight-Biased Min and Max Leftist Trees 432

9.4.3 Deletion from a Max HBLT 435

9.4.4 Melding Two Max HBLTs 435

9.4.2 Insertion into a Max HBLT 435

9.4.5 Initialization 437

9.4.6 The Class MaxHBLT 438

9.5 Applications 444

9.5.1 Heap Sort 444

9.5.2 Machine Scheduling 444

9.5.3 Huffman Codes 450

9.6 References and Selected Readings 457

CHAPTER 10 TOURNAMENT TREES 459

Chapter 10 Tournament Trees 459

10.1 Introduction 461

10.2 The ADT WinnerTree 466

10.3 The Class WinnerTree 466

10.3.1 Representation 466

10.3.2 Class Specification 467

10.3.3 Constructor,Destructor,and Winner 467

10.3.4 Initializing a Winner Tree 468

10.3.5 Replaying Matches 471

10.4 Loser Trees 472

10.5.1 Bin Packing Using First Fit 472

10.5 Applications 474

10.5.2 Bin Packing Using Next Fit 480

Chapter 11 Search Trees 485

CHAPTER 11 SEARCH TREES 485

11.1 Binary Search Trees 488

11.1.1 Definition 488

11.1.2 The ADTs BSTree and IndexedBSTree 490

11.1.3 The Class BSTree 491

11.1.4 Searching 492

11.1.5 Inserting an Element 493

11.1.6 Deleting an Element 493

11.1.8 Height of a Binary Search Tree 496

11.1.7 The Class DBSTree 496

11.2 AVL Trees 500

11.2.1 Definition 500

11.2.2 Height of an AVL Tree 501

11.2.3 Representation of an AVL Tree 501

11.2.4 Searching an AVL Search Tree 502

11.2.5 Inserting into an AVL Search Tree 502

11.2.6 Deletion from an AVL Search Tree 506

11.3.1 Definition 510

11.3 Red-Black Trees 510

11.3.2 Representation of a Red-Black Tree 512

11.3.3 Searching a Red-Black Tree 512

11.3.4 Inserting into a Red-Black Tree 513

11.3.5 Deletion from a Red-Black Tree 518

11.3.6 Implementation Considerations and Complexity 521

11.4 B-Trees 524

11.4.1 Indexed Sequential Access Method 524

11.4.2 m-way Search Trees 525

11.4.3 B-Trees of Order m 528

11.4.4 Height of a B-tree 529

11.4.5 Searching a B-tree 530

11.4.6 Inserting into a B-tree 530

11.4.7 Deletion from a B-tree 533

11.4.8 Node Structure 537

11.5 Applications 539

11.5.1 Histogramming 539

11.5.2 Best-Fit Bin Packing 543

11.5.3 Crossing Distribution 546

11.6 References and Selected Readings 553

Chapter 12 Graphs 555

CHAPTER 12 GRAPHS 555

12.1 Definitions 557

12.2 Applications 558

12.3 Properties 562

12.4 The ADTs Graph and Digraph 565

12.5 Representation of Graphs and Digraphs 567

12.5.1 Adjacency Matrix 567

12.5.2 Packed-Adjacency Lists 569

12.5.3 Linked-Adjacency Lists 570

12.6 Representation of Networks 573

12.7 Class Definitions 575

12.7.1 The Different Classes 575

12.7.2 Adjacency-Matrix Classes 576

12.7.3 An Extension to the Class Chain 580

12.7.4 The Class LinkedBase 580

12.7.5 Linked Classes 581

12.8 Graph Iterators 588

12.8.1 Specification 588

12.8.2 Iterator Functions for Adjacency-Matrix Representations 589

12.8.3 Iterator Functions for Linked-Adjacency Lists 589

12.9 Language Features 592

12.9.1 Virtual Functions and Polymorphism 592

12.9.2 Pure Virtual Functions and Abstract Classes 595

12.9.3 Virtual Base Classes 596

12.9.4 Abstract Classes and Abstract Data Types 598

12.10 Graph Search Methods 600

12.10.1 Breadth-First Search 600

12.10.3 Implementation of Network::BFS 602

12.10.4 Complexity Analysis of Network::BFS 602

12.10.2 The Class Network 602

12.10.5 Depth-First Search 605

12.11 Applications Revisited 607

12.11.1 Finding a Path 607

12.11.2 Connected Graphs and Components 609

12.11.3 Spanning Trees 611

PART Ⅲ ALGORITHM-DESIGN METHODS 615

Chapter 13 The Greedy Method 615

CHAPTER 13 THE GREEDY METHOD 615

PART Ⅲ ALLGORITHM-DESIGN METHODS 615

13.1 Optimization Problems 617

13.2 The Greedy Method 618

13.3 Applications 623

13.3.1 Container Loading 623

13.3.2 0/1 Knapsack Problem 624

13.3.3 Topological Sorting 628

13.3.4 Bipartite Cover 633

13.3.5 Single-Source Shortest Paths 642

13.3.6 Minimum-Cost Spanning Trees 646

13.4 References and Selected Readings 659

Chapter 14 Divide and Conquer 661

CHAPTER 14 DIVIDE AND CONQUER 661

14.1 The Method 662

14.2 Applications 672

14.2.1 Defective Chessboard 672

14.2.2 Merge Sort 677

14.2.3 Quick Sort 682

14.2.4 Selection 688

14.2.5 Closest Pair of Points 691

14.3 Solving Recurrence Equations 703

14.4 Lower Bounds on Complexity 705

14.4.1 Lower Bound for the Minmax Problem 706

14.4.2 Lower Bound for Sorting 708

CHAPTER 15 DYNAMIC PROGRAMMING 711

Chapter 15 Dynamic Programming 711

15.1 The Method 712

15.2 Applications 715

15.2.1 0/1 Knapsack Problem 715

15.2.2 Image Compression 719

15.2.3 Matrix Multiplication Chains 724

15.2.4 All Pairs Shortest Paths 731

15.2.5 Noncrossing Subset of Nets 735

15.2.6 Component Folding 740

15.3 References and Selected Readings 749

Chapter 16 Backtracking 751

CHAPTER 16 BACKTRACKING 751

16.1 The Method 753

16.2.1 Container Loading 760

16.2 Applications 760

16.2.2 0/1 Knapsack Problem 769

16.2.3 Max Clique 772

16.2.4 Traveling Salesperson 775

16.2.5 Board Permutation 778

Chapter 17 Branch and Bound 787

CHAPTER 17 BRANCH AND BOUND 787

17.1 The Method 788

17.2 Applications 792

17.2.1 Container Loading 792

17.2.2 0/1 Knapsack Problem 802

17.2.3 Max Clique 805

17.2.4 Traveling Salesperson 807

17.2.5 Board Permutation 810

INDEX 817

INDEX 817