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