Data Structures and Program Design in C++

Navigating the Disk......Page 1
Hints for Page Navigation......Page 2
Synopsis......Page 12
Course Structure......Page 14
Supplementary Materials......Page 15
Acknowledgments......Page 16
1.1 Introduction......Page 18
1.2.1 Rules for the Game of Life......Page 21
1.2.2 Examples......Page 22
1.2.3 The Solution: Classes, Objects, and Methods......Page 24
1.2.4 Life: The Main Program......Page 25
1.3.1 Names......Page 27
1.3.2 Documentation and Format......Page 30
1.3.3 Refinement and Modularity......Page 32
1.4.1 Stubs......Page 37
1.4.2 Definition of the Class Life......Page 39
1.4.3 Counting Neighbors......Page 40
1.4.4 Updating the Grid......Page 41
1.4.5 Input and Output......Page 42
1.4.6 Drivers......Page 44
1.4.7 Program Tracing......Page 45
1.4.8 Principles of Program Testing......Page 46
1.5.1 Program Evaluation......Page 51
1.5.2 Review of the Life Program......Page 52
1.5.3 Program Revision and Redevelopment......Page 55
1.6.1 Software Engineering......Page 56
1.6.2 Problem Analysis......Page 57
1.6.4 Coding......Page 58
Pointers and Pitfalls......Page 62
Review Questions......Page 63
The Game of Life......Page 64
Software Engineering......Page 65
2.1 Stack Specifications......Page 66
2.1.2 Stacks......Page 67
2.1.3 First Example: Reversing a List......Page 68
2.1.4 Information Hiding......Page 71
2.1.5 The Standard Template Library......Page 72
2.2.1 Specification of Methods for Stacks......Page 74
2.2.2 The Class Specification......Page 77
2.2.3 Pushing, Popping, and Other Methods......Page 78
2.2.4 Encapsulation......Page 80
2.3 Application: A Desk Calculator......Page 83
2.4 Application: Bracket Matching......Page 86
2.5.1 Introduction......Page 88
2.5.2 General Definitions......Page 90
2.5.3 Refinement of Data Specification......Page 91
Review Questions......Page 93
References for Further Study......Page 94
3.1 Definitions......Page 95
3.1.1 Queue Operations......Page 96
3.1.2 Extended Queue Operations......Page 98
3.2 Implementations of Queues......Page 101
3.3 Circular Implementation of Queues in C++......Page 106
3.4 Demonstration and Testing......Page 110
3.5.2 Simulation of an Airport......Page 113
3.5.4 The Runway Class Specification......Page 116
3.5.5 The Plane Class Specification......Page 117
3.5.6 Functions and Methods of the Simulation......Page 118
3.5.7 Sample Results......Page 124
Review Questions......Page 127
References for Further Study......Page 128
4.1 Pointers and Linked Structures......Page 129
4.1.1 Introduction and Survey......Page 130
4.1.2 Pointers and Dynamic Memory in C++......Page 133
4.1.3 The Basics of Linked Structures......Page 139
4.2 Linked Stacks......Page 144
4.3.1 The Destructor......Page 148
4.3.2 Overloading the Assignment Operator......Page 149
4.3.3 The Copy Constructor......Page 152
4.3.4 The Modified Linked-Stack Specification......Page 153
4.4.1 Basic Declarations......Page 154
4.4.2 Extended Linked Queues......Page 156
4.5.2 The Main Program......Page 158
4.5.3 The Polynomial Data Structure......Page 161
4.5.4 Reading and Writing Polynomials......Page 164
4.5.5 Addition of Polynomials......Page 165
4.5.6 Completing the Project......Page 167
4.6 Abstract Data Types and Their Implementations......Page 169
Pointers and Pitfalls......Page 171
Review Questions......Page 172
5.1 Introduction to Recursion......Page 174
5.1.1 Stack Frames for Subprograms......Page 175
5.1.2 Tree of Subprogram Calls......Page 176
5.1.3 Factorials: A Recursive Definition......Page 177
5.1.4 Divide and Conquer: The Towers of Hanoi......Page 180
5.2.1 Designing Recursive Algorithms......Page 187
5.2.2 How Recursion Works......Page 188
5.2.3 Tail Recursion......Page 191
5.2.4 When Not to Use Recursion......Page 193
5.2.5 Guidelines and Conclusions......Page 197
5.3.1 Solving the Eight-Queens Puzzle......Page 200
5.3.2 Example: Four Queens......Page 201
5.3.3 Backtracking......Page 202
5.3.4 Overall Outline......Page 203
5.3.5 Refinement: The First Data Structure and Its Methods......Page 205
5.3.6 Review and Refinement......Page 208
5.3.7 Analysis of Backtracking......Page 211
5.4.1 Game Trees......Page 215
5.4.2 The Minimax Method......Page 216
5.4.3 Algorithm Development......Page 218
5.4.4 Refinement......Page 220
5.4.5 Tic-Tac-Toe......Page 221
Pointers and Pitfalls......Page 226
Review Questions......Page 227
References for Further Study......Page 228
6.1 List Definition......Page 229
6.1.1 Method Specifications......Page 231
6.2 Implementation of Lists......Page 234
6.2.1 Class Templates......Page 235
6.2.2 Contiguous Implementation......Page 236
6.2.3 Simply Linked Implementation......Page 238
6.2.4 Variation: Keeping the Current Position......Page 242
6.2.5 Doubly Linked Lists......Page 244
6.2.6 Comparison of Implementations......Page 247
6.3.1 Strings in C++......Page 250
6.3.2 Implementation of Strings......Page 251
6.3.3 Further String Operations......Page 255
6.4.1 Specifications......Page 259
6.4.2 Implementation......Page 260
6.5 Linked Lists in Arrays......Page 268
6.6 Application: par penalty -500 Generating Permutations......Page 277
Pointers and Pitfalls......Page 282
Review Questions......Page 283
References for Further Study......Page 284
7.1 Searching: Introduction and Notation......Page 285
7.2 Sequential Search......Page 288
7.3.1 Ordered Lists......Page 295
7.3.2 Algorithm Development......Page 297
7.3.3 The Forgetful Version......Page 298
7.3.4 Recognizing Equality......Page 301
7.4 Comparison Trees......Page 303
7.4.1 Analysis for $n = 10$......Page 304
7.4.2 Generalization......Page 307
7.4.3 Comparison of Methods......Page 311
7.4.4 A General Relationship......Page 313
7.5 Lower Bounds......Page 314
7.6.1 Introduction......Page 319
7.6.2 Orders of Magnitude......Page 321
7.6.3 The Big-O and Related Notations......Page 327
7.6.4 Keeping the Dominant Term......Page 328
Pointers and Pitfalls......Page 331
Review Questions......Page 332
References for Further Study......Page 333
8.1 Introduction and Notation......Page 334
8.1.1 Sortable Lists......Page 336
8.2.1 Ordered Insertion......Page 337
8.2.2 Sorting by Insertion......Page 338
8.2.3 Linked Version......Page 340
8.2.4 Analysis......Page 342
8.3.1 The Algorithm......Page 346
8.3.2 Contiguous Implementation......Page 347
8.3.3 Analysis......Page 348
8.3.4 Comparisons......Page 349
8.4 Shell Sort......Page 350
8.5 Lower Bounds......Page 353
8.6.1 The Main Ideas......Page 356
8.6.2 An Example......Page 357
8.7 Mergesort for Linked Lists......Page 361
8.7.1 The Functions......Page 362
8.7.2 Analysis of Mergesort......Page 365
8.8.1 The Main Function......Page 369
8.8.2 Partitioning the List......Page 370
8.8.3 Analysis of Quicksort......Page 373
8.8.4 Average-Case Analysis of Quicksort......Page 375
8.8.5 Comparison with Mergesort......Page 377
8.9.1 Two-Way Trees as Lists......Page 380
8.9.2 Development of Heapsort......Page 382
8.9.3 Analysis of Heapsort......Page 385
8.9.4 Priority Queues......Page 386
8.10 Review: Comparison of Methods......Page 389
Pointers and Pitfalls......Page 392
Review Questions......Page 393
References for Further Study......Page 394
9.1 Introduction: Breaking the lowercase {lg n} Barrier......Page 396
9.2 Rectangular Tables......Page 398
9.3.1 Triangular Tables......Page 400
9.3.2 Jagged Tables......Page 402
9.3.3 Inverted Tables......Page 403
9.4 Tables: A New Abstract Data Type......Page 405
9.5 Application: Radix Sort......Page 408
9.5.1 The Idea......Page 409
9.5.2 Implementation......Page 410
9.5.3 Analysis......Page 413
9.6.1 Sparse Tables......Page 414
9.6.2 Choosing a Hash Function......Page 416
9.6.3 Collision Resolution with Open Addressing......Page 418
9.6.4 Collision Resolution by Chaining......Page 423
9.7 Analysis of Hashing......Page 428
9.8 Conclusions: Comparison of Methods......Page 434
9.9.1 Choice of Algorithm......Page 435
9.9.2 Specification of Data Structures......Page 436
9.9.4 The Life Functions......Page 438
Pointers and Pitfalls......Page 443
Review Questions......Page 444
References for Further Study......Page 445
10.1 Binary Trees......Page 446
10.1.1 Definitions......Page 447
10.1.2 Traversal of Binary Trees......Page 449
10.1.3 Linked Implementation of Binary Trees......Page 454
10.2 Binary Search Trees......Page 461
10.2.1 Ordered Lists and Implementations......Page 463
10.2.2 Tree Search......Page 464
10.2.3 Insertion into a Binary Search Tree......Page 468
10.2.4 Treesort......Page 470
10.2.5 Removal from a Binary Search Tree......Page 472
10.3 Building a Binary Search Tree......Page 480
10.3.1 Getting Started......Page 481
10.3.2 Declarations and the Main Function......Page 482
10.3.3 Inserting a Node......Page 483
10.3.4 Finishing the Task......Page 484
10.3.5 Evaluation......Page 486
10.3.6 Random Search Trees and Optimality......Page 487
10.4.1 Definition......Page 490
10.4.2 Insertion of a Node......Page 494
10.4.3 Removal of a Node......Page 501
10.4.4 The Height of an AVL Tree......Page 502
10.5.1 Introduction......Page 507
10.5.2 Splaying Steps......Page 508
10.5.3 Algorithm Development......Page 512
10.5.4 Amortized Algorithm Analysis: Introduction......Page 522
10.5.5 Amortized Analysis of Splaying......Page 526
Pointers and Pitfalls......Page 532
Review Questions......Page 533
References for Further Study......Page 535
11.1 Orchards, Trees, and Binary Trees......Page 537
11.1.1 On the Classification of Species......Page 538
11.1.2 Ordered Trees......Page 539
11.1.3 Forests and Orchards......Page 541
11.1.4 The Formal Correspondence......Page 543
11.1.6 Summary......Page 544
11.2.2 Searching for a Key......Page 547
11.2.3 C++ Algorithm......Page 548
11.2.4 Searching a Trie......Page 549
11.2.6 Deletion from a Trie......Page 550
11.2.7 Assessment of Tries......Page 551
11.3.2 Multiway Search Trees......Page 552
11.3.3 Balanced Multiway Trees......Page 553
11.3.4 Insertion into a B-Tree......Page 554
11.3.5 C++ Algorithms: Searching and Insertion......Page 556
11.3.6 Deletion from a B-Tree......Page 564
11.4.1 Introduction......Page 573
11.4.2 Definition and Analysis......Page 574
11.4.3 Red-Black Tree Specification......Page 576
11.4.4 Insertion......Page 577
11.4.5 Insertion Method Implementation......Page 578
11.4.6 Removal of a Node......Page 582
Pointers and Pitfalls......Page 583
Review Questions......Page 584
References for Further Study......Page 585
12.1 Mathematical Background......Page 586
12.1.1 Definitions and Examples......Page 587
12.1.3 Directed Graphs......Page 588
12.2.1 The Set Representation......Page 589
12.2.2 Adjacency Lists......Page 591
12.3.1 Methods......Page 592
12.3.2 Depth-First Algorithm......Page 594
12.3.3 Breadth-First Algorithm......Page 595
12.4.1 The Problem......Page 596
12.4.2 Depth-First Algorithm......Page 597
12.4.3 Breadth-First Algorithm......Page 598
12.5.1 The Problem......Page 600
12.5.2 Method......Page 601
12.5.3 Example......Page 602
12.5.4 Implementation......Page 603
12.6.1 The Problem......Page 604
12.6.2 Method......Page 606
12.6.3 Implementation......Page 607
12.6.4 Verification of Prim's Algorithm......Page 610
12.7 Graphs as Data Structures......Page 611
Pointers and Pitfalls......Page 613
References for Further Study......Page 614
13.1 The Problem......Page 615
13.1.1 The Quadratic Formula......Page 616
13.2.1 Expression Trees......Page 618
13.2.2 Polish Notation......Page 620
13.3 Evaluation of Polish Expressions......Page 621
13.3.1 Evaluation of an Expression in Prefix Form......Page 622
13.3.2 C++ Conventions......Page 623
13.3.3 C++ Function for Prefix Evaluation......Page 624
13.3.4 Evaluation of Postfix Expressions......Page 625
13.3.5 Proof of the Program: Counting Stack Entries......Page 626
13.3.6 Recursive Evaluation of Postfix Expressions......Page 629
13.4 Translation from Infix Form to Polish Form......Page 634
13.5.1 Overall Structure......Page 640
13.5.2 Representation of the Data: Class Specifications......Page 642
13.5.3 Tokens......Page 646
13.5.4 The Lexicon......Page 648
13.5.5 Expressions: Token Lists......Page 651
13.5.6 Auxiliary Evaluation Functions......Page 656
13.5.7 Graphing the Expression: The Class Plot......Page 657
13.5.8 A Graphics-Enhanced Plot Class......Page 660
References for Further Study......Page 662
A.1 Sums of Powers of Integers......Page 664
A.2 Logarithms......Page 667
A.2.2 Simple Properties......Page 668
A.2.4 Natural Logarithms......Page 669
A.2.5 Notation......Page 670
A.2.7 Logarithmic Graphs......Page 671
A.2.8 Harmonic Numbers......Page 673
A.3.2 Combinations......Page 674
A.3.3 Factorials......Page 675
A.4 Fibonacci Numbers......Page 676
A.5.1 The Main Result......Page 678
A.5.2 The Proof by One-to-One Correspondences......Page 679
A.5.3 History......Page 681
References for Further Study......Page 682
B.1 Introduction......Page 684
B.2 Strategy......Page 685
B.3 Program Development......Page 686
References for Further Study......Page 690
C.1 Packages and C++ Translation Units......Page 691
C.2 Packages in the Text......Page 693
C.3 The Utility Package......Page 695
C.4 Timing Methods......Page 696
D.1.2 Lists......Page 698
D.1.5 Tables......Page 699
D.1.6 Binary Trees......Page 700
D.1.8 Graphs......Page 701
D.2 Recursion......Page 702
D.3 Design of Data Structures......Page 703
D.4 Algorithm Design and Analysis......Page 704
D.5 Programming......Page 705
D.6 Programming with Pointer Objects......Page 706
D.8 Maintenance......Page 707
A......Page 710
B......Page 712
C......Page 713
D......Page 715
E......Page 716
G......Page 718
H......Page 719
I......Page 720
L......Page 721
N......Page 723
P......Page 724
Q......Page 726
R......Page 727
S......Page 728
T......Page 731
W......Page 733
Z......Page 734