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

76899-4

Object-oriented programming and powerful features of C++ enable this carefully crafted text to build data structures from basic ideas into complete, fully-developed programs and interesting applications. In the process, the text explores problem solving and programming principles, data abstraction, recursion, and the comparative analysis of algorithms as fundamentals tools of software design.

Employing substantial case studies, reusable software development, and programming projects to increase understanding, successful authors Robert L. Kruse and Alexander J.Ryba include topics such as:

• C++ templates are introduced early; code for data structures is developed as templated classes in fully reusable form; the Standard Template Library (STL) is mentioned as appropriate.
• Recursion is treated early and applied throughout the text.
• Data abstraction and abstract data types (ADTs) are emphasized, with conceptual development separated from implementation issues.
• Advanced structures and algorithms are developed into complete programs, including splay trees, B-trees, red-black trees, and graph algorithms such as minimal spanning trees.

Data Structures and Program Design in C++ will prove useful to both computer science students and professionals. The authors supply all code in this book on the Web, and, as well, they provide an excellent instructor support package that includes an Instructor's Resource Manual with transparency masters, solutions, and source code to all of the programming examples and projects in the text.

Progressing from the concrete to the abstract and using numerous, substantial case studies and sample programs this book explores structured problem solving, data abstraction, software engineering principles, and the comparative analysis of algorithms as fundamental tools of program design. The book and all programs have been completely written from the Object-Oriented perspective. Uses the C++ programming language throughout. Briefly reviews the syntax of C++ and provides a brief introduction to the language. The book is native C++ making full use of C++ features and object-oriented programming. Discusses major principles of software engineering and applies them to large programming projects. Covers several more advanced, modern topics, e.g.: Splay trees, Red-black trees, Amortized algorithm analysis. Object-oriented programming and powerful features of C++ enable this carefully crafted text to build data structures from basic ideas into complete, fully developed programs and interesting applications. In the process, the text explores problem solving and programming principles, data abstraction, recursion, and the comparative analysis of algorithms as fundamentals tools of software design