Data Structures and Algorithm Analysis in C++ 4th Edition PDF

Fourth Edition Data Structures and Algorithm Analysis in C ++ This page intentionally left blank Fourth Edition Data Structures and Algorithm Analysis in C ++ Mark Allen Weiss Florida International University Boston Columbus Indianapolis New York San Francisco Upper Saddle River Amsterdam Cape Town Dubai London Madrid Milan Munich Paris Montreal Toronto Delhi Mexico City Sao Paulo Sydney Hong Kong Seoul Singapore Taipei Tokyo Editorial Director, ECS: Marcia Horton Cover Designer: Bruce Kenselaar Executive Editor: Tracy Johnson Permissions Supervisor: Michael Joyce Editorial Assistant: Jenah Blitz-Stoehr Permissions Administrator: Jenell Forschler Director of Marketing: Christy Lesko Cover Image: c De-kay | Dreamstime.com Marketing Manager: Yez Alayan Media Project Manager: Renata Butera Senior Marketing Coordinator: Kathryn Ferranti Full-Service Project Management: Integra Software Marketing Assistant: Jon Bryant Services Pvt. Ltd. Director of Production: Erin Gregg Composition: Integra Software Services Pvt. Ltd. Senior Managing Editor: Scott Disanno Text and Cover Printer/Binder: Courier Westford Senior Production Project Manager: Marilyn Lloyd Manufacturing Buyer: Linda Sager Art Director: Jayne Conte Copyright c 2014, 2006, 1999 Pearson Education, Inc., publishing as Addison-Wesley. All rights reserved. Printed in the United States of America. This publication is protected by Copyright, and permission should be obtained from the publisher prior to any prohibited reproduction, storage in a retrieval system, or transmission in any form or by any means, electronic, mechanical, photocopying, recording, or likewise. To obtain permission(s) to use material from this work, please submit a written request to Pearson Education, Inc., Permissions Department, One Lake Street, Upper Saddle River, New Jersey 07458, or you may fax your request to 201-236-3290. Many of the designations by manufacturers and sellers to distinguish their products are claimed as trademarks. Where those designations appear in this book, and the publisher was aware of a trademark claim, the designations have been printed in initial caps or all caps. Library of Congress Cataloging-in-Publication Data Weiss, Mark Allen. Data structures and algorithm analysis in C++ / Mark Allen Weiss, Florida International University. — Fourth edition. pages cm ISBN-13: 978-0-13-284737-7 (alk. paper) ISBN-10: 0-13-284737-X (alk. paper) 1. C++ (Computer program language) 2. Data structures (Computer science) 3. Computer algorithms. I. Title. QA76.73.C153W46 2014 005.7 3—dc23 2013011064 10 9 8 7 6 5 4 3 2 1 ISBN-10: 0-13-284737-X www.pearsonhighered.com ISBN-13: 978-0-13-284737-7 To my kind, brilliant, and inspiring Sara. This page intentionally left blank CO NTE NTS Preface xv Chapter 1 Programming: A General Overview 1 1.1 What’s This Book About? 1 1.2 Mathematics Review 2 1.2.1 Exponents 3 1.2.2 Logarithms 3 1.2.3 Series 4 1.2.4 Modular Arithmetic 5 1.2.5 The P Word 6 1.3 A Brief Introduction to Recursion 8 1.4 C++ Classes 12 1.4.1 Basic class Syntax 12 1.4.2 Extra Constructor Syntax and Accessors 13 1.4.3 Separation of Interface and Implementation 16 1.4.4 vector and string 19 1.5 C++ Details 21 1.5.1 Pointers 21 1.5.2 Lvalues, Rvalues, and References 23 1.5.3 Parameter Passing 25 1.5.4 Return Passing 27 1.5.5 std::swap and std::move 29 1.5.6 The Big-Five: Destructor, Copy Constructor, Move Constructor, Copy Assignment operator=, Move Assignment operator= 30 1.5.7 C-style Arrays and Strings 35 1.6 Templates 36 1.6.1 Function Templates 37 1.6.2 Class Templates 38 1.6.3 Object, Comparable, and an Example 39 1.6.4 Function Objects 41 1.6.5 Separate Compilation of Class Templates 44 1.7 Using Matrices 44 1.7.1 The Data Members, Constructor, and Basic Accessors 44 1.7.2 operator[] 45 vii viii Contents 1.7.3 Big-Five 46 Summary 46 Exercises 46 References 48 Chapter 2 Algorithm Analysis 51 2.1 Mathematical Background 51 2.2 Model 54 2.3 What to Analyze 54 2.4 Running-Time Calculations 57 2.4.1 A Simple Example 58 2.4.2 General Rules 58 2.4.3 Solutions for the Maximum Subsequence Sum Problem 60 2.4.4 Logarithms in the Running Time 66 2.4.5 Limitations of Worst-Case Analysis 70 Summary 70 Exercises 71 References 76 Chapter 3 Lists, Stacks, and Queues 77 3.1 Abstract Data Types (ADTs) 77 3.2 The List ADT 78 3.2.1 Simple Array Implementation of Lists 78 3.2.2 Simple Linked Lists 79 3.3 vector and list in the STL 80 3.3.1 Iterators 82 3.3.2 Example: Using erase on a List 83 3.3.3 const_iterators 84 3.4 Implementation of vector 86 3.5 Implementation of list 91 3.6 The Stack ADT 103 3.6.1 Stack Model 103 3.6.2 Implementation of Stacks 104 3.6.3 Applications 104 3.7 The Queue ADT 112 3.7.1 Queue Model 113 3.7.2 Array Implementation of Queues 113 3.7.3 Applications of Queues 115 Summary 116 Exercises 116 Contents ix Chapter 4 Trees 121 4.1 Preliminaries 121 4.1.1 Implementation of Trees 122 4.1.2 Tree Traversals with an Application 123 4.2 Binary Trees 126 4.2.1 Implementation 128 4.2.2 An Example: Expression Trees 128 4.3 The Search Tree ADT—Binary Search Trees 132 4.3.1 contains 134 4.3.2 findMin and findMax 135 4.3.3 insert 136 4.3.4 remove 139 4.3.5 Destructor and Copy Constructor 141 4.3.6 Average-Case Analysis 141 4.4 AVL Trees 144 4.4.1 Single Rotation 147 4.4.2 Double Rotation 149 4.5 Splay Trees 158 4.5.1 A Simple Idea (That Does Not Work) 158 4.5.2 Splaying 160 4.6 Tree Traversals (Revisited) 166 4.7 B-Trees 168 4.8 Sets and Maps in the Standard Library 173 4.8.1 Sets 173 4.8.2 Maps 174 4.8.3 Implementation of set and map 175 4.8.4 An Example That Uses Several Maps 176 Summary 181 Exercises 182 References 189 Chapter 5 Hashing 193 5.1 General Idea 193 5.2 Hash Function 194 5.3 Separate Chaining 196 5.4 Hash Tables without Linked Lists 201 5.4.1 Linear Probing 201 5.4.2 Quadratic Probing 202 5.4.3 Double Hashing 207 5.5 Rehashing 208 5.6 Hash Tables in the Standard Library 210 x Contents 5.7 Hash Tables with Worst-Case O(1) Access 212 5.7.1 Perfect Hashing 213 5.7.2 Cuckoo Hashing 215 5.7.3 Hopscotch Hashing 227 5.8 Universal Hashing 230 5.9 Extendible Hashing 233 Summary 236 Exercises 237 References 241 Chapter 6 Priority Queues (Heaps) 245 6.1 Model 245 6.2 Simple Implementations 246 6.3 Binary Heap 247 6.3.1 Structure Property 247 6.3.2 Heap-Order Property 248 6.3.3 Basic Heap Operations 249 6.3.4 Other Heap Operations 252 6.4 Applications of Priority Queues 257 6.4.1 The Selection Problem 258 6.4.2 Event Simulation 259 6.5 d-Heaps 260 6.6 Leftist Heaps 261 6.6.1 Leftist Heap Property 261 6.6.2 Leftist Heap Operations 262 6.7 Skew Heaps 269 6.8 Binomial Queues 271 6.8.1 Binomial Queue Structure 271 6.8.2 Binomial Queue Operations 271 6.8.3 Implementation of Binomial Queues 276 6.9 Priority Queues in the Standard Library 282 Summary 283 Exercises 283 References 288 Chapter 7 Sorting 291 7.1 Preliminaries 291 7.2 Insertion Sort 292 7.2.1 The Algorithm 292 7.2.2 STL Implementation of Insertion Sort 293 7.2.3 Analysis of Insertion Sort 294 7.3 A Lower Bound for Simple Sorting Algorithms 295 Contents xi 7.4 Shellsort 296 7.4.1 Worst-Case Analysis of Shellsort 297 7.5 Heapsort 300 7.5.1 Analysis of Heapsort 301 7.6 Mergesort 304 7.6.1 Analysis of Mergesort 306 7.7 Quicksort 309 7.7.1 Picking the Pivot 311 7.7.2 Partitioning Strategy 313 7.7.3 Small Arrays 315 7.7.4 Actual Quicksort Routines 315 7.7.5 Analysis of Quicksort 318 7.7.6 A Linear-Expected-Time Algorithm for Selection 321 7.8 A General Lower Bound for Sorting 323 7.8.1 Decision Trees 323 7.9 Decision-Tree Lower Bounds for Selection Problems 325 7.10 Adversary Lower Bounds 328 7.11 Linear-Time Sorts: Bucket Sort and Radix Sort 331 7.12 External Sorting 336 7.12.1 Why We Need New Algorithms 336 7.12.2 Model for External Sorting 336 7.12.3 The Simple Algorithm 337 7.12.4 Multiway Merge 338 7.12.5 Polyphase Merge 339 7.12.6 Replacement Selection 340 Summary 341 Exercises 341 References 347 Chapter 8 The Disjoint Sets Class 351 8.1 Equivalence Relations 351 8.2 The Dynamic Equivalence Problem 352 8.3 Basic Data Structure 353 8.4 Smart Union Algorithms 357 8.5 Path Compression 360 8.6 Worst Case for Union-by-Rank and Path Compression 361 8.6.1 Slowly Growing Functions 362 8.6.2 An Analysis by Recursive Decomposition 362 8.6.3 An O( M log * N ) Bound 369 8.6.4 An O( M α(M, N) ) Bound 370 8.7 An Application 372 xii Contents Summary 374 Exercises 375 References 376 Chapter 9 Graph Algorithms 379 9.1 Deﬁnitions 379 9.1.1 Representation of Graphs 380 9.2 Topological Sort 382 9.3 Shortest-Path Algorithms 386 9.3.1 Unweighted Shortest Paths 387 9.3.2 Dijkstra’s Algorithm 391 9.3.3 Graphs with Negative Edge Costs 400 9.3.4 Acyclic Graphs 400 9.3.5 All-Pairs Shortest Path 404 9.3.6 Shortest Path Example 404 9.4 Network Flow Problems 406 9.4.1 A Simple Maximum-Flow Algorithm 408 9.5 Minimum Spanning Tree 413 9.5.1 Prim’s Algorithm 414 9.5.2 Kruskal’s Algorithm 417 9.6 Applications of Depth-First Search 419 9.6.1 Undirected Graphs 420 9.6.2 Biconnectivity 421 9.6.3 Euler Circuits 425 9.6.4 Directed Graphs 429 9.6.5 Finding Strong Components 431 9.7 Introduction to NP-Completeness 432 9.7.1 Easy vs. Hard 433 9.7.2 The Class NP 434 9.7.3 NP-Complete Problems 434 Summary 437 Exercises 437 References 445 Chapter 10 Algorithm Design Techniques 449 10.1 Greedy Algorithms 449 10.1.1 A Simple Scheduling Problem 450 10.1.2 Huffman Codes 453 10.1.3 Approximate Bin Packing 459 10.2 Divide and Conquer 467 10.2.1 Running Time of Divide-and-Conquer Algorithms 468 10.2.2 Closest-Points Problem 470 Contents xiii 10.2.3 The Selection Problem 475 10.2.4 Theoretical Improvements for Arithmetic Problems 478 10.3 Dynamic Programming 482 10.3.1 Using a Table Instead of Recursion 483 10.3.2 Ordering Matrix Multiplications 485 10.3.3 Optimal Binary Search Tree 487 10.3.4 All-Pairs Shortest Path 491 10.4 Randomized Algorithms 494 10.4.1 Random-Number Generators 495 10.4.2 Skip Lists 500 10.4.3 Primality Testing 503 10.5 Backtracking Algorithms 506 10.5.1 The Turnpike Reconstruction Problem 506 10.5.2 Games 511 Summary 518 Exercises 518 References 527 Chapter 11 Amortized Analysis 533 11.1 An Unrelated Puzzle 534 11.2 Binomial Queues 534 11.3 Skew Heaps 539 11.4 Fibonacci Heaps 541 11.4.1 Cutting Nodes in Leftist Heaps 542 11.4.2 Lazy Merging for Binomial Queues 544 11.4.3 The Fibonacci Heap Operations 548 11.4.4 Proof of the Time Bound 549 11.5 Splay Trees 551 Summary 555 Exercises 556 References 557 Chapter 12 Advanced Data Structures and Implementation 559 12.1 Top-Down Splay Trees 559 12.2 Red-Black Trees 566 12.2.1 Bottom-Up Insertion 567 12.2.2 Top-Down Red-Black Trees 568 12.2.3 Top-Down Deletion 570 12.3 Treaps 576 xiv Contents 12.4 Sufﬁx Arrays and Sufﬁx Trees 579 12.4.1 Sufﬁx Arrays 580 12.4.2 Sufﬁx Trees 583 12.4.3 Linear-Time Construction of Sufﬁx Arrays and Sufﬁx Trees 586 12.5 k-d Trees 596 12.6 Pairing Heaps 602 Summary 606 Exercises 608 References 612 Appendix A Separate Compilation of Class Templates 615 A.1 Everything in the Header 616 A.2 Explicit Instantiation 616 Index 619 P R E FAC E Purpose/Goals The fourth edition of Data Structures and Algorithm Analysis in C++ describes data structures, methods of organizing large amounts of data, and algorithm analysis, the estimation of the running time of algorithms. As computers become faster and faster, the need for programs that can handle large amounts of input becomes more acute. Paradoxically, this requires more careful attention to efﬁciency, since inefﬁciencies in programs become most obvious when input sizes are large. By analyzing an algorithm before it is actually coded, students can decide if a particular solution will be feasible. For example, in this text students look at speciﬁc problems and see how careful implementations can reduce the time constraint for large amounts of data from centuries to less than a second. Therefore, no algorithm or data structure is presented without an explanation of its running time. In some cases, minute details that affect the running time of the implementation are explored. Once a solution method is determined, a program must still be written. As computers have become more powerful, the problems they must solve have become larger and more complex, requiring development of more intricate programs. The goal of this text is to teach students good programming and algorithm analysis skills simultaneously so that they can develop such programs with the maximum amount of efﬁciency. This book is suitable for either an advanced data structures course or a ﬁrst-year graduate course in algorithm analysis. Students should have some knowledge of inter- mediate programming, including such topics as pointers, recursion, and object-based programming, as well as some background in discrete math. Approach Although the material in this text is largely language-independent, programming requires the use of a speciﬁc language. As the title implies, we have chosen C++ for this book. C++ has become a leading systems programming language. In addition to ﬁxing many of the syntactic ﬂaws of C, C++ provides direct constructs (the class and template) to implement generic data structures as abstract data types. The most difﬁcult part of writing this book was deciding on the amount of C++ to include. Use too many features of C++ and one gets an incomprehensible text; use too few and you have little more than a C text that supports classes. The approach we take is to present the material in an object-based approach. As such, there is almost no use of inheritance in the text. We use class templates to describe generic data structures. We generally avoid esoteric C++ features and use the vector and string classes that are now part of the C++ standard. Previous editions have implemented class templates by separating the class template interface from its implementation. Although this is arguably the preferred approach, it exposes compiler problems that have made it xv xvi Preface difﬁcult for readers to actually use the code. As a result, in this edition the online code represents class templates as a single unit, with no separation of interface and implementa- tion. Chapter 1 provides a review of the C++ features that are used throughout the text and describes our approach to class templates. Appendix A describes how the class templates could be rewritten to use separate compilation. Complete versions of the data structures, in both C++ and Java, are available on the Internet. We use similar coding conventions to make the parallels between the two languages more evident. Summary of the Most Signiﬁcant Changes in the Fourth Edition The fourth edition incorporates numerous bug ﬁxes, and many parts of the book have undergone revision to increase the clarity of presentation. In addition, r Chapter 4 includes implementation of the AVL tree deletion algorithm—a topic often requested by readers. r Chapter 5 has been extensively revised and enlarged and now contains material on two newer algorithms: cuckoo hashing and hopscotch hashing. Additionally, a new section on universal hashing has been added. Also new is a brief discussion of the unordered_set and unordered_map class templates introduced in C++11. r Chapter 6 is mostly unchanged; however, the implementation of the binary heap makes use of move operations that were introduced in C++11. r Chapter 7 now contains material on radix sort, and a new section on lower-bound proofs has been added. Sorting code makes use of move operations that were introduced in C++11. r Chapter 8 uses the new union/ﬁnd analysis by Seidel and Sharir and shows the O( M α(M, N) ) bound instead of the weaker O( M log∗ N ) bound in prior editions. r Chapter 12 adds material on sufﬁx trees and sufﬁx arrays, including the linear-time sufﬁx array construction algorithm by Karkkainen and Sanders (with implementation). The sections covering deterministic skip lists and AA-trees have been removed. r Throughout the text, the code has been updated to use C++11. Notably, this means use of the new C++11 features, including the auto keyword, the range for loop, move construction and assignment, and uniform initialization. Overview Chapter 1 contains review material on discrete math and recursion. I believe the only way to be comfortable with recursion is to see good uses over and over. Therefore, recursion is prevalent in this text, with examples in every chapter except Chapter 5. Chapter 1 also includes material that serves as a review of basic C++. Included is a discussion of templates and important constructs in C++ class design. Chapter 2 deals with algorithm analysis. This chapter explains asymptotic analysis and its major weaknesses. Many examples are provided, including an in-depth explana- tion of logarithmic running time. Simple recursive programs are analyzed by intuitively converting them into iterative programs. More complicated divide-and-conquer programs are introduced, but some of the analysis (solving recurrence relations) is implicitly delayed until Chapter 7, where it is performed in detail. Preface xvii Chapter 3 covers lists, stacks, and queues. This chapter includes a discussion of the STL vector and list classes, including material on iterators, and it provides implementations of a signiﬁcant subset of the STL vector and list classes. Chapter 4 covers trees, with an emphasis on search trees, including external search trees (B-trees). The UNIX ﬁle system and expression trees are used as examples. AVL trees and splay trees are introduced. More careful treatment of search tree implementation details is found in Chapter 12. Additional coverage of trees, such as ﬁle compression and game trees, is deferred until Chapter 10. Data structures for an external medium are considered as the ﬁnal topic in several chapters. Included is a discussion of the STL set and map classes, including a signiﬁcant example that illustrates the use of three separate maps to efﬁciently solve a problem. Chapter 5 discusses hash tables, including the classic algorithms such as sepa- rate chaining and linear and quadratic probing, as well as several newer algorithms, namely cuckoo hashing and hopscotch hashing. Universal hashing is also discussed, and extendible hashing is covered at the end of the chapter. Chapter 6 is about priority queues. Binary heaps are covered, and there is additional material on some of the theoretically interesting implementations of priority queues. The Fibonacci heap is discussed in Chapter 11, and the pairing heap is discussed in Chapter 12. Chapter 7 covers sorting. It is very speciﬁc with respect to coding details and analysis. All the important general-purpose sorting algorithms are covered and compared. Four algorithms are analyzed in detail: insertion sort, Shellsort, heapsort, and quicksort. New to this edition is radix sort and lower bound proofs for selection-related problems. External sorting is covered at the end of the chapter. Chapter 8 discusses the disjoint set algorithm with proof of the running time. This is a short and speciﬁc chapter that can be skipped if Kruskal’s algorithm is not discussed. Chapter 9 covers graph algorithms. Algorithms on graphs are interesting, not only because they frequently occur in practice but also because their running time is so heavily dependent on the proper use of data structures. Virtually all of the standard algorithms are presented along with appropriate data structures, pseudocode, and analysis of running time. To place these problems in a proper context, a short discussion on complexity theory (including NP-completeness and undecidability) is provided. Chapter 10 covers algorithm design by examining common problem-solving tech- niques. This chapter is heavily fortiﬁed with examples. Pseudocode is used in these later chapters so that the student’s appreciation of an example algorithm is not obscured by implementation details. Chapter 11 deals with amortized analysis. Three data structures from Chapters 4 and 6 and the Fibonacci heap, introduced in this chapter, are analyzed. Chapter 12 covers search tree algorithms, the sufﬁx tree and array, the k-d tree, and the pairing heap. This chapter departs from the rest of the text by providing complete and careful implementations for the search trees and pairing heap. The material is structured so that the instructor can integrate sections into discussions from other chapters. For example, the top-down red-black tree in Chapter 12 can be discussed along with AVL trees (in Chapter 4). Chapters 1 to 9 provide enough material for most one-semester data structures courses. If time permits, then Chapter 10 can be covered. A graduate course on algorithm analysis could cover chapters 7 to 11. The advanced data structures analyzed in Chapter 11 can easily be referred to in the earlier chapters. The discussion of NP-completeness in Chapter 9 xviii Preface is far too brief to be used in such a course. You might ﬁnd it useful to use an additional work on NP-completeness to augment this text. Exercises Exercises, provided at the end of each chapter, match the order in which material is pre- sented. The last exercises may address the chapter as a whole rather than a speciﬁc section. Difﬁcult exercises are marked with an asterisk, and more challenging exercises have two asterisks. References References are placed at the end of each chapter. Generally the references either are his- torical, representing the original source of the material, or they represent extensions and improvements to the results given in the text. Some references represent solutions to exercises. Supplements The following supplements are available to all readers at http://cssupport.pearsoncmg.com/ r Source code for example programs r Errata In addition, the following material is available only to qualiﬁed instructors at Pearson Instructor Resource Center (www.pearsonhighered.com/irc). Visit the IRC or contact your Pearson Education sales representative for access. r Solutions to selected exercises r Figures from the book r Errata Acknowledgments Many, many people have helped me in the preparation of books in this series. Some are listed in other versions of the book; thanks to all. As usual, the writing process was made easier by the professionals at Pearson. I’d like to thank my editor, Tracy Johnson, and production editor, Marilyn Lloyd. My wonderful wife Jill deserves extra special thanks for everything she does. Finally, I’d like to thank the numerous readers who have sent e-mail messages and pointed out errors or inconsistencies in earlier versions. My website www.cis.ﬁu.edu/~weiss will also contain updated source code (in C++ and Java), an errata list, and a link to submit bug reports. M.A.W. Miami, Florida C H A P T E R 1 Programming: A General Overview In this chapter, we discuss the aims and goals of this text and brieﬂy review programming concepts and discrete mathematics. We will... r See that how a program performs for reasonably large input is just as important as its performance on moderate amounts of input. r Summarize the basic mathematical background needed for the rest of the book. r Brieﬂy review recursion. r Summarize some important features of C++ that are used throughout the text. 1.1 What’s This Book About? Suppose you have a group of N numbers and would like to determine the kth largest. This is known as the selection problem. Most students who have had a programming course or two would have no difﬁculty writing a program to solve this problem. There are quite a few “obvious” solutions. One way to solve this problem would be to read the N numbers into an array, sort the array in decreasing order by some simple algorithm such as bubble sort, and then return the element in position k. A somewhat better algorithm might be to read the ﬁrst k elements into an array and sort them (in decreasing order). Next, each remaining element is read one by one. As a new element arrives, it is ignored if it is smaller than the kth element in the array. Otherwise, it is placed in its correct spot in the array, bumping one element out of the array. When the algorithm ends, the element in the kth position is returned as the answer. Both algorithms are simple to code, and you are encouraged to do so. The natural ques- tions, then, are: Which algorithm is better? And, more important, Is either algorithm good enough? A simulation using a random ﬁle of 30 million elements and k = 15,000,000 will show that neither algorithm ﬁnishes in a reasonable amount of time; each requires several days of computer processing to terminate (albeit eventually with a correct answer). An alternative method, discussed in Chapter 7, gives a solution in about a second. Thus, although our proposed algorithms work, they cannot be considered good algorithms, 1 2 Chapter 1 Programming: A General Overview 1 2 3 4 1 t h i s 2 w a t s 3 o a h g 4 f g d t Figure 1.1 Sample word puzzle because they are entirely impractical for input sizes that a third algorithm can handle in a reasonable amount of time. A second problem is to solve a popular word puzzle. The input consists of a two- dimensional array of letters and a list of words. The object is to ﬁnd the words in the puzzle. These words may be horizontal, vertical, or diagonal in any direction. As an example, the puzzle shown in Figure 1.1 contains the words this, two, fat, and that. The word this begins at row 1, column 1, or (1,1), and extends to (1,4); two goes from (1,1) to (3,1); fat goes from (4,1) to (2,3); and that goes from (4,4) to (1,1). Again, there are at least two straightforward algorithms that solve the problem. For each word in the word list, we check each ordered triple (row, column, orientation) for the pres- ence of the word. This amounts to lots of nested for loops but is basically straightforward. Alternatively, for each ordered quadruple (row, column, orientation, number of characters) that doesn’t run off an end of the puzzle, we can test whether the word indicated is in the word list. Again, this amounts to lots of nested for loops. It is possible to save some time if the maximum number of characters in any word is known. It is relatively easy to code up either method of solution and solve many of the real-life puzzles commonly published in magazines. These typically have 16 rows, 16 columns, and 40 or so words. Suppose, however, we consider the variation where only the puzzle board is given and the word list is essentially an English dictionary. Both of the solutions proposed require considerable time to solve this problem and therefore might not be acceptable. However, it is possible, even with a large word list, to solve the problem very quickly. An important concept is that, in many problems, writing a working program is not good enough. If the program is to be run on a large data set, then the running time becomes an issue. Throughout this book we will see how to estimate the running time of a program for large inputs and, more important, how to compare the running times of two programs without actually coding them. We will see techniques for drastically improving the speed of a program and for determining program bottlenecks. These techniques will enable us to ﬁnd the section of the code on which to concentrate our optimization efforts. 1.2 Mathematics Review This section lists some of the basic formulas you need to memorize, or be able to derive, and reviews basic proof techniques. 1.2 Mathematics Review 3 1.2.1 Exponents XA XB = XA+B XA = XA−B XB (XA )B = XAB XN + XN = 2XN = X2N 2N + 2N = 2N+1 1.2.2 Logarithms In computer science, all logarithms are to the base 2 unless speciﬁed otherwise. Deﬁnition 1.1 XA = B if and only if logX B = A Several convenient equalities follow from this deﬁnition. Theorem 1.1 logC B logA B = ; A, B, C > 0, A = 1 logC A Proof Let X = logC B, Y = logC A, and Z = logA B. Then, by the deﬁnition of loga- rithms, CX = B, CY = A, and AZ = B. Combining these three equalities yields B = CX = (CY )Z. Therefore, X = YZ, which implies Z = X/Y, proving the theorem. Theorem 1.2 log AB = log A + log B; A, B > 0 Proof Let X = log A, Y = log B, and Z = log AB. Then, assuming the default base of 2, 2X = A, 2Y = B, and 2Z = AB. Combining the last three equalities yields 2X 2Y = AB = 2Z. Therefore, X + Y = Z, which proves the theorem. Some other useful formulas, which can all be derived in a similar manner, follow. log A/B = log A − log B log(AB ) = B log A log X < X for all X > 0 log 1 = 0, log 2 = 1, log 1,024 = 10, log 1,048,576 = 20 4 Chapter 1 Programming: A General Overview 1.2.3 Series The easiest formulas to remember are N 2i = 2N+1 − 1 i=0 and the companion, N AN+1 − 1 Ai = A−1 i=0 In the latter formula, if 0 < A < 1, then N 1 Ai ≤ 1−A i=0 and as N tends to ∞, the sum approaches 1/(1 − A). These are the “geometric series” formulas. We can derive the last formula for ∞i=0 A (0 < A < 1) in the following manner. Let i S be the sum. Then S = 1 + A + A2 + A3 + A4 + A5 + · · · Then AS = A + A2 + A3 + A4 + A5 + · · · If we subtract these two equations (which is permissible only for a convergent series), virtually all the terms on the right side cancel, leaving S − AS = 1 which implies that 1 S= 1−A We can use this same technique to compute ∞ i i=1 i/2 , a sum that occurs frequently. We write 1 2 3 4 5 S = + 2 + 3 + 4 + 5 + ··· 2 2 2 2 2 and multiply by 2, obtaining 2 3 4 5 6 2S = 1 + + + 3 + 4 + 5 + ··· 2 22 2 2 2 Subtracting these two equations yields 1 1 1 1 1 S=1+ + + 3 + 4 + 5 + ··· 2 22 2 2 2 Thus, S = 2. 1.2 Mathematics Review 5 Another type of common series in analysis is the arithmetic series. Any such series can be evaluated from the basic formula: N N(N + 1) N2 i= ≈ 2 2 i=1 For instance, to ﬁnd the sum 2 + 5 + 8 + · · · + (3k − 1), rewrite it as 3(1 + 2 + 3 + · · · + k) − (1 + 1 + 1 + · · · + 1), which is clearly 3k(k + 1)/2 − k. Another way to remember this is to add the ﬁrst and last terms (total 3k + 1), the second and next-to-last terms (total 3k + 1), and so on. Since there are k/2 of these pairs, the total sum is k(3k + 1)/2, which is the same answer as before. The next two formulas pop up now and then but are fairly uncommon. N N(N + 1)(2N + 1) N3 i2 = ≈ 6 3 i=1 N Nk+1 ik ≈ k = −1 |k + 1| i=1 When k = −1, the latter formula is not valid. We then need the following formula, which is used far more in computer science than in other mathematical disciplines. The numbers HN are known as the harmonic numbers, and the sum is known as a harmonic sum. The error in the following approximation tends to γ ≈ 0.57721566, which is known as Euler’s constant. N 1 HN = ≈ loge N i i=1 These two formulas are just general algebraic manipulations: N f(N) = Nf(N) i=1 N N 0 −1 n f(i) = f(i) − f(i) i=n0 i=1 i=1 1.2.4 Modular Arithmetic We say that A is congruent to B modulo N, written A ≡ B (mod N), if N divides A − B. Intuitively, this means that the remainder is the same when either A or B is divided by N. Thus, 81 ≡ 61 ≡ 1 (mod 10). As with equality, if A ≡ B (mod N), then A + C ≡ B + C (mod N) and AD ≡ BD (mod N). 6 Chapter 1 Programming: A General Overview Often, N is a prime number. In that case, there are three important theorems: First, if N is prime, then ab ≡ 0 (mod N) is true if and only if a ≡ 0 (mod N) or b ≡ 0 (mod N). In other words, if a prime number N divides a product of two numbers, it divides at least one of the two numbers. Second, if N is prime, then the equation ax ≡ 1 (mod N) has a unique solution (mod N) for all 0 < a < N. This solution, 0 < x < N, is the multiplicative inverse. Third, if N is prime, then the equation x2 ≡ a (mod N) has either two solutions (mod N) for all 0 < a < N, or it has no solutions. There are many theorems that apply to modular arithmetic, and some of them require extraordinary proofs in number theory. We will use modular arithmetic sparingly, and the preceding theorems will sufﬁce. 1.2.5 The P Word The two most common ways of proving statements in data-structure analysis are proof by induction and proof by contradiction (and occasionally proof by intimidation, used by professors only). The best way of proving that a theorem is false is by exhibiting a counterexample. Proof by Induction A proof by induction has two standard parts. The ﬁrst step is proving a base case, that is, establishing that a theorem is true for some small (usually degenerate) value(s); this step is almost always trivial. Next, an inductive hypothesis is assumed. Generally this means that the theorem is assumed to be true for all cases up to some limit k. Using this assumption, the theorem is then shown to be true for the next value, which is typically k + 1. This proves the theorem (as long as k is ﬁnite). As an example, we prove that the Fibonacci numbers, F0 = 1, F1 = 1, F2 = 2, F3 = 3, F4 = 5,... , Fi = Fi−1 + Fi−2 , satisfy Fi < (5/3)i , for i ≥ 1. (Some deﬁnitions have F0 = 0, which shifts the series.) To do this, we ﬁrst verify that the theorem is true for the trivial cases. It is easy to verify that F1 = 1 < 5/3 and F2 = 2 < 25/9; this proves the basis. We assume that the theorem is true for i = 1, 2,... , k; this is the inductive hypothesis. To prove the theorem, we need to show that Fk+1 < (5/3)k+1. We have Fk+1 = Fk + Fk−1 by the deﬁnition, and we can use the inductive hypothesis on the right-hand side, obtaining Fk+1 < (5/3)k + (5/3)k−1 < (3/5)(5/3)k+1 + (3/5)2 (5/3)k+1 < (3/5)(5/3)k+1 + (9/25)(5/3)k+1 which simpliﬁes to 1.2 Mathematics Review 7 Fk+1 < (3/5 + 9/25)(5/3)k+1 < (24/25)(5/3)k+1 < (5/3)k+1 proving the theorem. As a second example, we establish the following theorem. Theorem 1.3 N N(N+1)(2N+1) If N ≥ 1, then i=1 i 2 = 6 Proof The proof is by induction. For the basis, it is readily seen that the theorem is true when N = 1. For the inductive hypothesis, assume that the theorem is true for 1 ≤ k ≤ N. We will establish that, under this assumption, the theorem is true for N + 1. We have N+1 N i2 = i2 + (N + 1)2 i=1 i=1 Applying the inductive hypothesis, we obtain N+1 N(N + 1)(2N + 1) i2 = + (N + 1)2 6 i=1 N(2N + 1) = (N + 1) + (N + 1) 6 2N2 + 7N + 6 = (N + 1) 6 (N + 1)(N + 2)(2N + 3) = 6 Thus, N+1 (N + 1)[(N + 1) + 1][2(N + 1) + 1] i2 = 6 i=1 proving the theorem. Proof by Counterexample The statement Fk ≤ k2 is false. The easiest way to prove this is to compute F11 = 144 > 112. Proof by Contradiction Proof by contradiction proceeds by assuming that the theorem is false and showing that this assumption implies that some known property is false, and hence the original assumption was erroneous. A classic example is the proof that there is an inﬁnite number of primes. To prove this, we assume that the theorem is false, so that there is some largest prime Pk. Let P1 , P2 ,... , Pk be all the primes in order and consider 8 Chapter 1 Programming: A General Overview N = P1 P 2 P 3 · · · P k + 1 Clearly, N is larger than Pk , so, by assumption, N is not prime. However, none of P1 , P2 ,... , Pk divides N exactly, because there will always be a remainder of 1. This is a con- tradiction, because every number is either prime or a product of primes. Hence, the original assumption, that Pk is the largest prime, is false, which implies that the theorem is true. 1.3 A Brief Introduction to Recursion Most mathematical functions that we are familiar with are described by a simple formula. For instance, we can convert temperatures from Fahrenheit to Celsius by applying the formula C = 5(F − 32)/9 Given this formula, it is trivial to write a C++ function; with declarations and braces removed, the one-line formula translates to one line of C++. Mathematical functions are sometimes deﬁned in a less standard form. As an example, we can deﬁne a function f, valid on nonnegative integers, that satisﬁes f(0) = 0 and f(x) = 2f(x − 1) + x2. From this deﬁnition we see that f(1) = 1, f(2) = 6, f(3) = 21, and f(4) = 58. A function that is deﬁned in terms of itself is called recursive. C++ allows functions to be recursive.1 It is important to remember that what C++ provides is merely an attempt to follow the recursive spirit. Not all mathematically recursive functions are efﬁciently (or correctly) implemented by C++’s simulation of recursion. The idea is that the recursive function f ought to be expressible in only a few lines, just like a nonrecursive function. Figure 1.2 shows the recursive implementation of f. Lines 3 and 4 handle what is known as the base case, that is, the value for which the function is directly known without resorting to recursion. Just as declaring f(x) = 2f(x − 1) + x2 is meaningless, mathematically, without including the fact that f(0) = 0, the recursive C++ function doesn’t make sense without a base case. Line 6 makes the recursive call. 1 int f( int x ) 2 { 3 if( x == 0 ) 4 return 0; 5 else 6 return 2 * f( x - 1 ) + x * x; 7 } Figure 1.2 A recursive function 1 Using recursion for numerical calculations is usually a bad idea. We have done so to illustrate the basic points. 1.3 A Brief Introduction to Recursion 9 There are several important and possibly confusing points about recursion. A common question is: Isn’t this just circular logic? The answer is that although we are deﬁning a function in terms of itself, we are not deﬁning a particular instance of the function in terms of itself. In other words, evaluating f(5) by computing f(5) would be circular. Evaluating f(5) by computing f(4) is not circular—unless, of course, f(4) is evaluated by eventually computing f(5). The two most important issues are probably the how and why questions. In Chapter 3, the how and why issues are formally resolved. We will give an incomplete description here. It turns out that recursive calls are handled no differently from any others. If f is called with the value of 4, then line 6 requires the computation of 2 ∗ f(3) + 4 ∗ 4. Thus, a call is made to compute f(3). This requires the computation of 2 ∗ f(2) + 3 ∗ 3. Therefore, another call is made to compute f(2). This means that 2 ∗ f(1) + 2 ∗ 2 must be evaluated. To do so, f(1) is computed as 2∗f(0)+1∗1. Now, f(0) must be evaluated. Since this is a base case, we know a priori that f(0) = 0. This enables the completion of the calculation for f(1), which is now seen to be 1. Then f(2), f(3), and ﬁnally f(4) can be determined. All the bookkeeping needed to keep track of pending function calls (those started but waiting for a recursive call to complete), along with their variables, is done by the computer automatically. An important point, however, is that recursive calls will keep on being made until a base case is reached. For instance, an attempt to evaluate f(−1) will result in calls to f(−2), f(−3), and so on. Since this will never get to a base case, the program won’t be able to compute the answer (which is undeﬁned anyway). Occasionally, a much more subtle error is made, which is exhibited in Figure 1.3. The error in Figure 1.3 is that bad(1) is deﬁned, by line 6, to be bad(1). Obviously, this doesn’t give any clue as to what bad(1) actually is. The computer will thus repeatedly make calls to bad(1) in an attempt to resolve its values. Eventually, its bookkeeping system will run out of space, and the program will terminate abnormally. Generally, we would say that this function doesn’t work for one special case but is correct otherwise. This isn’t true here, since bad(2) calls bad(1). Thus, bad(2) cannot be evaluated either. Furthermore, bad(3), bad(4), and bad(5) all make calls to bad(2). Since bad(2) is not evaluable, none of these values are either. In fact, this program doesn’t work for any nonnegative value of n, except 0. With recursive programs, there is no such thing as a “special case.” These considerations lead to the ﬁrst two fundamental rules of recursion: 1. Base cases. You must always have some base cases, which can be solved without recursion. 2. Making progress. For the cases that are to be solved recursively, the recursive call must always be to a case that makes progress toward a base case. 1 int bad( int n ) 2 { 3 if( n == 0 ) 4 return 0; 5 else 6 return bad( n / 3 + 1 ) + n - 1; 7 } Figure 1.3 A nonterminating recursive function 10 Chapter 1 Programming: A General Overview Throughout this book, we will use recursion to solve problems. As an example of a nonmathematical use, consider a large dictionary. Words in dictionaries are deﬁned in terms of other words. When we look up a word, we might not always understand the deﬁnition, so we might have to look up words in the deﬁnition. Likewise, we might not understand some of those, so we might have to continue this search for a while. Because the dictionary is ﬁnite, eventually either (1) we will come to a point where we understand all of the words in some deﬁnition (and thus understand that deﬁnition and retrace our path through the other deﬁnitions) or (2) we will ﬁnd that the deﬁnitions are circular and we are stuck, or that some word we need to understand for a deﬁnition is not in the dictionary. Our recursive strategy to understand words is as follows: If we know the meaning of a word, then we are done; otherwise, we look the word up in the dictionary. If we understand all the words in the deﬁnition, we are done; otherwise, we ﬁgure out what the deﬁnition means by recursively looking up the words we don’t know. This procedure will terminate if the dictionary is well deﬁned but can loop indeﬁnitely if a word is either not deﬁned or circularly deﬁned. Printing Out Numbers Suppose we have a positive integer, n, that we wish to print out. Our routine will have the heading printOut(n). Assume that the only I/O routines available will take a single-digit number and output it. We will call this routine printDigit; for example, printDigit(4) will output a 4. Recursion provides a very clean solution to this problem. To print out 76234, we need to ﬁrst print out 7623 and then print out 4. The second step is easily accomplished with the statement printDigit(n%10), but the ﬁrst doesn’t seem any simpler than the original problem. Indeed it is virtually the same problem, so we can solve it recursively with the statement printOut(n/10). This tells us how to solve the general problem, but we still need to make sure that the program doesn’t loop indeﬁnitely. Since we haven’t deﬁned a base case yet, it is clear that we still have something to do. Our base case will be printDigit(n) if 0 ≤ n < 10. Now printOut(n) is deﬁned for every positive number from 0 to 9, and larger numbers are deﬁned in terms of a smaller positive number. Thus, there is no cycle. The entire function is shown in Figure 1.4. We have made no effort to do this efﬁciently. We could have avoided using the mod routine (which can be very expensive) because n%10 = n − n/10 ∗ 10 is true for positive n.2 1 void printOut( int n ) // Print nonnegative n 2 { 3 if( n >= 10 ) 4 printOut( n / 10 ); 5 printDigit( n % 10 ); 6 } Figure 1.4 Recursive routine to print an integer 2 x is the largest integer that is less than or equal to x. 1.3 A Brief Introduction to Recursion 11 Recursion and Induction Let us prove (somewhat) rigorously that the recursive number-printing program works. To do so, we’ll use a proof by induction. Theorem 1.4 The recursive number-printing algorithm is correct for n ≥ 0. Proof (By induction on the number of digits in n) First, if n has one digit, then the program is trivially correct, since it merely makes a call to printDigit. Assume then that printOut works for all numbers of k or fewer digits. A number of k + 1 digits is expressed by its ﬁrst k digits followed by its least signiﬁcant digit. But the number formed by the ﬁrst k digits is exactly n/10 , which, by the inductive hypothesis, is correctly printed, and the last digit is n mod 10, so the program prints out any (k+1)-digit number correctly. Thus, by induction, all numbers are correctly printed. This proof probably seems a little strange in that it is virtually identical to the algorithm description. It illustrates that in designing a recursive program, all smaller instances of the same problem (which are on the path to a base case) may be assumed to work correctly. The recursive program needs only to combine solutions to smaller problems, which are “mag- ically” obtained by recursion, into a solution for the current problem. The mathematical justiﬁcation for this is proof by induction. This gives the third rule of recursion: 3. Design rule. Assume that all the recursive calls work. This rule is important because it means that when designing recursive programs, you generally don’t need to know the details of the bookkeeping arrangements, and you don’t have to try to trace through the myriad of recursive calls. Frequently, it is extremely difﬁcult to track down the actual sequence of recursive calls. Of course, in many cases this is an indication of a good use of recursion, since the computer is being allowed to work out the complicated details. The main problem with recursion is the hidden bookkeeping costs. Although these costs are almost always justiﬁable, because recursive programs not only simplify the algo- rithm design but also tend to give cleaner code, recursion should not be used as a substitute for a simple for loop. We’ll discuss the overhead involved in recursion in more detail in Section 3.6. When writing recursive routines, it is crucial to keep in mind the four basic rules of recursion: 1. Base cases. You must always have some base cases, which can be solved without recursion. 2. Making progress. For the cases that are to be solved recursively, the recursive call must always be to a case that makes progress toward a base case. 3. Design rule. Assume that all the recursive calls work. 4. Compound interest rule. Never duplicate work by solving the same instance of a problem in separate recursive calls. 12 Chapter 1 Programming: A General Overview The fourth rule, which will be justiﬁed (along with its nickname) in later sections, is the reason that it is generally a bad idea to use recursion to evaluate simple mathematical func- tions, such as the Fibonacci numbers. As long as you keep these rules in mind, recursive programming should be straightforward. 1.4 C++ Classes In this text, we will write many data structures. All of the data structures will be objects that store data (usually a collection of identically typed items) and will provide functions that manipulate the collection. In C++ (and other languages), this is accomplished by using a class. This section describes the C++ class. 1.4.1 Basic class Syntax A class in C++ consists of its members. These members can be either data or functions. The functions are called member functions. Each instance of a class is an object. Each object contains the data components speciﬁed in the class (unless the data components are static, a detail that can be safely ignored for now). A member function is used to act on an object. Often member functions are called methods. As an example, Figure 1.5 is the IntCell class. In the IntCell class, each instance of the IntCell—an IntCell object—contains a single data member named storedValue. Everything else in this particular class is a method. In our example, there are four methods. Two of these methods are read and write. The other two are special methods known as constructors. Let us describe some key features. First, notice the two labels public and private. These labels determine visibility of class members. In this example, everything except the storedValue data member is public. storedValue is private. A member that is public may be accessed by any method in any class. A member that is private may only be accessed by methods in its class. Typically, data members are declared private, thus restricting access to internal details of the class, while methods intended for general use are made public. This is known as information hiding. By using private data members, we can change the internal representation of the object without having an effect on other parts of the program that use the object. This is because the object is accessed through the public member functions, whose viewable behavior remains unchanged. The users of the class do not need to know internal details of how the class is implemented. In many cases, having this access leads to trouble. For instance, in a class that stores dates using month, day, and year, by making the month, day, and year private, we prohibit an outsider from setting these data members to illegal dates, such as Feb 29, 2013. However, some methods may be for internal use and can be private. In a class, all members are private by default, so the initial public is not optional. Second, we see two constructors. A constructor is a method that describes how an instance of the class is constructed. If no constructor is explicitly deﬁned, one that initial- izes the data members using language defaults is automatically generated. The IntCell class deﬁnes two constructors. The ﬁrst is called if no parameter is speciﬁed. The second is called if an int parameter is provided, and uses that int to initialize the storedValue member. 1.4 C++ Classes 13 1 4 class IntCell 5 { 6 public: 7 11 IntCell( ) 12 { storedValue = 0; } 13 14 18 IntCell( int initialValue ) 19 { storedValue = initialValue; } 20 21 24 int read( ) 25 { return storedValue; } 26 27 30 void write( int x ) 31 { storedValue = x; } 32 33 private: 34 int storedValue; 35 }; Figure 1.5 A complete declaration of an IntCell class 1.4.2 Extra Constructor Syntax and Accessors Although the class works as written, there is some extra syntax that makes for better code. Four changes are shown in Figure 1.6 (we omit comments for brevity). The differences are as follows: Default Parameters The IntCell constructor illustrates the default parameter. As a result, there are still two IntCell constructors deﬁned. One accepts an initialValue. The other is the zero-parameter 14 Chapter 1 Programming: A General Overview constructor, which is implied because the one-parameter constructor says that initialValue is optional. The default value of 0 signiﬁes that 0 is used if no para- meter is provided. Default parameters can be used in any function, but they are most commonly used in constructors. Initialization List The IntCell constructor uses an initialization list (Figure 1.6, line 8) prior to the body of the constructor. The initialization list is used to initialize the data members directly. In Figure 1.6, there’s hardly a difference, but using initialization lists instead of an assignment statement in the body saves time in the case where the data members are class types that have complex initializations. In some cases it is required. For instance, if a data member is const (meaning that it is not changeable after the object has been constructed), then the data member’s value can only be initialized in the initialization list. Also, if a data member is itself a class type that does not have a zero-parameter constructor, then it must be initialized in the initialization list. Line 8 in Figure 1.6 uses the syntax : storedValue{ initialValue } { } instead of the traditional : storedValue( initialValue ) { } The use of braces instead of parentheses is new in C++11 and is part of a larger effort to provide a uniform syntax for initialization everywhere. Generally speaking, anywhere you can initialize, you can do so by enclosing initializations in braces (though there is one important exception, in Section 1.4.4, relating to vectors). 1 4 class IntCell 5 { 6 public: 7 explicit IntCell( int initialValue = 0 ) 8 : storedValue{ initialValue } { } 9 int read( ) const 10 { return storedValue; } 11 void write( int x ) 12 { storedValue = x; } 13 14 private: 15 int storedValue; 16 }; Figure 1.6 IntCell class with revisions 1.4 C++ Classes 15 explicit Constructor The IntCell constructor is explicit. You should make all one-parameter constructors explicit to avoid behind-the-scenes type conversions. Otherwise, there are somewhat lenient rules that will allow type conversions without explicit casting operations. Usually, this is unwanted behavior that destroys strong typing and can lead to hard-to-ﬁnd bugs. As an example, consider the following: IntCell obj; // obj is an IntCell obj = 37; // Should not compile: type mismatch The code fragment above constructs an IntCell object obj and then performs an assign- ment statement. But the assignment statement should not work, because the right-hand side of the assignment operator is not another IntCell. obj’s write method should have been used instead. However, C++ has lenient rules. Normally, a one-parameter constructor deﬁnes an implicit type conversion, in which a temporary object is created that makes an assignment (or parameter to a function) compatible. In this case, the compiler would attempt to convert obj = 37; // Should not compile: type mismatch into IntCell temporary = 37; obj = temporary; Notice that the construction of the temporary can be performed by using the one- parameter constructor. The use of explicit means that a one-parameter constructor cannot be used to generate an implicit temporary. Thus, since IntCell’s constructor is declared explicit, the compiler will correctly complain that there is a type mismatch. Constant Member Function A member function that examines but does not change the state of its object is an accessor. A member function that changes the state is a mutator (because it mutates the state of the object). In the typical collection class, for instance, isEmpty is an accessor, while makeEmpty is a mutator. In C++, we can mark each member function as being an accessor or a mutator. Doing so is an important part of the design process and should not be viewed as simply a com- ment. Indeed, there are important semantic consequences. For instance, mutators cannot be applied to constant objects. By default, all member functions are mutators. To make a member function an accessor, we must add the keyword const after the closing parenthesis that ends the parameter type list. The const-ness is part of the signature. const can be used with many different meanings. The function declaration can have const in three different contexts. Only the const after a closing parenthesis signiﬁes an accessor. Other uses are described in Sections 1.5.3 and 1.5.4. In the IntCell class, read is clearly an accessor: it does not change the state of the IntCell. Thus it is made a constant member function at line 9. If a member function 16 Chapter 1 Programming: A General Overview is marked as an accessor but has an implementation that changes the value of any data member, a compiler error is generated.3 1.4.3 Separation of Interface and Implementation The class in Figure 1.6 contains all the correct syntactic constructs. However, in C++ it is more common to separate the class interface from its implementation. The interface lists the class and its members (data and functions). The implementation provides implementations of the functions. Figure 1.7 shows the class interface for IntCell, Figure 1.8 shows the implementation, and Figure 1.9 shows a main routine that uses the IntCell. Some important points follow. Preprocessor Commands The interface is typically placed in a ﬁle that ends with.h. Source code that requires knowledge of the interface must #include the interface ﬁle. In our case, this is both the implementation ﬁle and the ﬁle that contains main. Occasionally, a complicated project will have ﬁles including other ﬁles, and there is the danger that an interface might be read twice in the course of compiling a ﬁle. This can be illegal. To guard against this, each header ﬁle uses the preprocessor to deﬁne a symbol when the class interface is read. This is shown on the ﬁrst two lines in Figure 1.7. The symbol name, IntCell_H, should not appear in any other ﬁle; usually, we construct it from the ﬁlename. The ﬁrst line of the interface ﬁle 1 #ifndef IntCell_H 2 #define IntCell_H 3 4 7 class IntCell 8 { 9 public: 10 explicit IntCell( int initialValue = 0 ); 11 int read( ) const; 12 void write( int x ); 13 14 private: 15 int storedValue; 16 }; 17 18 #endif Figure 1.7 IntCell class interface in ﬁle IntCell.h 3 Data members can be marked mutable to indicate that const-ness should not apply to them. 1.4 C++ Classes 17 1 #include "IntCell.h" 2 3 6 IntCell::IntCell( int initialValue ) : storedValue{ initialValue } 7 { 8 } 9 10 13 int IntCell::read( ) const 14 { 15 return storedValue; 16 } 17 18 21 void IntCell::write( int x ) 22 { 23 storedValue = x; 24 } Figure 1.8 IntCell class implementation in ﬁle IntCell.cpp 1 #include 2 #include "IntCell.h" 3 using namespace std; 4 5 int main( ) 6 { 7 IntCell m; 8 9 m.write( 5 ); 10 cout prev = p->prev->next = new Node{ x, p->prev, p } }; 11 } Figure 3.22 List insert with additional error checks 3.6 The Stack ADT 103 3.6 The Stack ADT A stack is a list with the restriction that insertions and deletions can be performed in only one position, namely, the end of the list, called the top. 3.6.1 Stack Model The fundamental operations on a stack are push, which is equivalent to an insert, and pop, which deletes the most recently inserted element. The most recently inserted element can be examined prior to performing a pop by use of the top routine. A pop or top on an empty stack is generally considered an error in the stack ADT. On the other hand, running out of space when performing a push is an implementation limit but not an ADT error. Stacks are sometimes known as LIFO (last in, ﬁrst out) lists. The model depicted in Figure 3.23 signiﬁes only that pushes are input operations and pops and tops are output. The usual operations to make empty stacks and test for emptiness are part of the repertoire, but essentially all that you can do to a stack is push and pop. Figure 3.24 shows an abstract stack after several operations. The general model is that there is some element that is at the top of the stack, and it is the only element that is visible. pop push Stack top Figure 3.23 Stack model: Input to a stack is by push; output is by pop and top top 2 4 1 3 6 Figure 3.24 Stack model: Only the top element is accessible 104 Chapter 3 Lists, Stacks, and Queues 3.6.2 Implementation of Stacks Since a stack is a list, any list implementation will do. Clearly list and vector support stack operations; 99% of the time they are the most reasonable choice. Occasionally it can be faster to design a special-purpose implementation. Because stack operations are constant- time operations, this is unlikely to yield any discernable improvement except under very unique circumstances. For these special times, we will give two popular stack implementations. One uses a linked structure, and the other uses an array, and both simplify the logic in vector and list, so we do not provide code. Linked List Implementation of Stacks The ﬁrst implementation of a stack uses a singly linked list. We perform a push by inserting at the front of the list. We perform a pop by deleting the element at the front of the list. A top operation merely examines the element at the front of the list, returning its value. Sometimes the pop and top operations are combined into one. Array Implementation of Stacks An alternative implementation avoids links and is probably the more popular solution. It uses the back, push_back, and pop_back implementation from vector, so the implementation is trivial. Associated with each stack is theArray and topOfStack, which is −1 for an empty stack (this is how an empty stack is initialized). To push some element x onto the stack, we increment topOfStack and then set theArray[topOfStack] = x. To pop, we set the return value to theArray[topOfStack] and then decrement topOfStack. Notice that these operations are performed in not only constant time but very fast con- stant time. On some machines, pushes and pops (of integers) can be written in one machine instruction, operating on a register with auto-increment and auto-decrement addressing. The fact that most modern machines have stack operations as part of the instruction set enforces the idea that the stack is probably the most fundamental data structure in computer science, after the array. 3.6.3 Applications It should come as no surprise that if we restrict the operations allowed on a list, those oper- ations can be performed very quickly. The big surprise, however, is that the small number of operations left are so powerful and important. We give three of the many applications of stacks. The third application gives a deep insight into how programs are organized. Balancing Symbols Compilers check your programs for syntax errors, but frequently a lack of one symbol (such as a missing brace or comment starter) can cause the compiler to spill out a hundred lines of diagnostics without identifying the real error. A useful tool in this situation is a program that checks whether everything is balanced. Thus, every right brace, bracket, and parenthesis must correspond to its left counterpart. 3.6 The Stack ADT 105 The sequence [()] is legal, but [(]) is wrong. Obviously, it is not worthwhile writing a huge program for this, but it turns out that it is easy to check these things. For simplicity, we will just check for balancing of parentheses, brackets, and braces and ignore any other character that appears. The simple algorithm uses a stack and is as follows: Make an empty stack. Read characters until end of ﬁle. If the character is an opening symbol, push it onto the stack. If it is a closing symbol and the stack is empty, report an error. Otherwise, pop the stack. If the symbol popped is not the corresponding opening symbol, then report an error. At end of ﬁle, if the stack is not empty, report an error. You should be able to convince yourself that this algorithm works. It is clearly linear and actually makes only one pass through the input. It is thus online and quite fast. Extra work can be done to attempt to decide what to do when an error is reported—such as identifying the likely cause. Postﬁx Expressions Suppose we have a pocket calculator and would like to compute the cost of a shopping trip. To do so, we add a list of numbers and multiply the result by 1.06; this computes the purchase price of some items with local sales tax added. If the items are 4.99, 5.99, and 6.99, then a natural way to enter this would be the sequence 4.99 + 5.99 + 6.99 ∗ 1.06 = Depending on the calculator, this produces either the intended answer, 19.05, or the sci- entiﬁc answer, 18.39. Most simple four-function calculators will give the ﬁrst answer, but many advanced calculators know that multiplication has higher precedence than addition. On the other hand, some items are taxable and some are not, so if only the ﬁrst and last items were actually taxable, then the sequence 4.99 ∗ 1.06 + 5.99 + 6.99 ∗ 1.06 = would give the correct answer (18.69) on a scientiﬁc calculator and the wrong answer (19.37) on a simple calculator. A scientiﬁc calculator generally comes with parentheses, so we can always get the right answer by parenthesizing, but with a simple calculator we need to remember intermediate results. A typical evaluation sequence for this example might be to multiply 4.99 and 1.06, saving this answer as A1. We then add 5.99 and A1 , saving the result in A1. We multiply 6.99 and 1.06, saving the answer in A2 , and ﬁnish by adding A1 and A2 , leaving the ﬁnal answer in A1. We can write this sequence of operations as follows: 4.99 1.06 ∗ 5.99 + 6.99 1.06 ∗ + This notation is known as postﬁx, or reverse Polish notation, and is evaluated exactly as we have described above. The easiest way to do this is to use a stack. When a number is seen, it is pushed onto the stack; when an operator is seen, the operator is applied to the 106 Chapter 3 Lists, Stacks, and Queues two numbers (symbols) that are popped from the stack, and the result is pushed onto the stack. For instance, the postﬁx expression 6 5 2 3 + 8 ∗ +3 + ∗ is evaluated as follows: The ﬁrst four symbols are placed on the stack. The resulting stack is topOfStack → 3 2 5 6 Next, a ‘+’ is read, so 3 and 2 are popped from the stack, and their sum, 5, is pushed. topOfStack → 5 5 6 Next, 8 is pushed. topOfStack → 8 5 5 6 Now a ‘∗’ is seen, so 8 and 5 are popped, and 5 ∗ 8 = 40 is pushed. topOfStack → 40 5 6 3.6 The Stack ADT 107 Next, a ‘+’ is seen, so 40 and 5 are popped, and 5 + 40 = 45 is pushed. topOfStack → 45 6 Now, 3 is pushed. topOfStack → 3 45 6 Next, ‘+’ pops 3 and 45 and pushes 45 + 3 = 48. topOfStack → 48 6 Finally, a ‘∗’ is seen and 48 and 6 are popped; the result, 6 ∗ 48 = 288, is pushed. topOfStack → 288 The time to evaluate a postﬁx expression is O(N), because processing each element in the input consists of stack operations and therefore takes constant time. The algorithm to do so is very simple. Notice that when an expression is given in postﬁx notation, there is no need to know any precedence rules; this is an obvious advantage. 108 Chapter 3 Lists, Stacks, and Queues Inﬁx to Postﬁx Conversion Not only can a stack be used to evaluate a postﬁx expression, but we can also use a stack to convert an expression in standard form (otherwise known as inﬁx) into postﬁx. We will concentrate on a small version of the general problem by allowing only the operators +, *, (, ), and insisting on the usual precedence rules. We will further assume that the expression is legal. Suppose we want to convert the inﬁx expression a + b * c + ( d * e + f ) * g into postﬁx. A correct answer is a b c * + d e * f + g * +. When an operand is read, it is immediately placed onto the output. Operators are not immediately output, so they must be saved somewhere. The correct thing to do is to place operators that have been seen, but not placed on the output, onto the stack. We will also stack left parentheses when they are encountered. We start with an initially empty stack. If we see a right parenthesis, then we pop the stack, writing symbols until we encounter a (corresponding) left parenthesis, which is popped but not output. If we see any other symbol (+, *, (), then we pop entries from the stack until we ﬁnd an entry of lower priority. One exception is that we never remove a ( from the stack except when processing a ). For the purposes of this operation, + has lowest priority and ( highest. When the popping is done, we push the operator onto the stack. Finally, if we read the end of input, we pop the stack until it is empty, writing symbols onto the output. The idea of this algorithm is that when an operator is seen, it is placed on the stack. The stack represents pending operators. However, some of the operators on the stack that have high precedence are now known to be completed and should be popped, as they will no longer be pending. Thus prior to placing the operator on the stack, operators that are on the stack, and which are to be completed prior to the current operator, are popped. This is illustrated in the following table: Stack When Third Expression Operator Is Processed Action a*b-c+d - - is completed; + is pushed a/b+c*d + Nothing is completed; * is pushed a-b*c/d - * * is completed; / is pushed a-b*c+d - * * and - are completed; + is pushed Parentheses simply add an additional complication. We can view a left parenthesis as a high-precedence operator when it is an input symbol (so that pending operators remain pending) and a low-precedence operator when it is on the stack (so that it is not accidentally removed by an operator). Right parentheses are treated as the special case. To see how this algorithm performs, we will convert the long inﬁx expression above into its postﬁx form. First, the symbol a is read, so it is passed through to the output. 3.6 The Stack ADT 109 Then + is read and pushed onto the stack. Next b is read and passed through to the output. The state of affairs at this juncture is as follows: + ab Stack Output Next, a * is read. The top entry on the operator stack has lower precedence than *, so nothing is output and * is put on the stack. Next, c is read and output. Thus far, we have * + abc Stack Output The next symbol is a +. Checking the stack, we ﬁnd that we will pop a * and place it on the output; pop the other +, which is not of lower but equal priority, on the stack; and then push the +. + abc*+ Stack Output The next symbol read is a (. Being of highest precedence, this is placed on the stack. Then d is read and output. ( + abc*+d Stack Output We continue by reading a *. Since open parentheses do not get removed except when a closed parenthesis is being processed, there is no output. Next, e is read and output. * ( + abc*+de Stack Output 110 Chapter 3 Lists, Stacks, and Queues The next symbol read is a +. We pop and output * and then push +. Then we read and output f. + ( + abc*+de*f Stack Output Now we read a ), so the stack is emptied back to the (. We output a +. + abc*+de*f+ Stack Output We read a * next; it is pushed onto the stack. Then g is read and output. * + abc*+de*f+g Stack Output The input is now empty, so we pop and output symbols from the stack until it is empty. abc*+de*f+g*+ Stack Output As before, this conversion requires only O(N) time and works in one pass through the input. We can add subtraction and division to this repertoire by assigning subtraction and addition equal priority and multiplication and division equal priority. A subtle point is that the expression a - b - c will be converted to a b - c - and not a b c - -. Our algorithm does the right thing, because these operators associate from left to right. This 3 is not necessarily the case in general, since exponentiation associates right to left: 22 = 28 = 256, not 43 = 64. We leave as an exercise the problem of adding exponentiation to the repertoire of operators. Function Calls The algorithm to check balanced symbols suggests a way to implement function calls in compiled procedural and object-oriented languages. The problem here is that when a call is made to a new function, all the variables local to the calling routine need to be saved by the system, since otherwise the new function will overwrite the memory used by the calling routine’s variables. Furthermore, the current location in the routine must be saved 3.6 The Stack ADT 111 so that the new function knows where to go after it is done. The variables have generally been assigned by the compiler to machine registers, and there are certain to be conﬂicts (usually all functions get some variables assigned to register #1), especially if recursion is involved. The reason that this problem is similar to balancing symbols is that a function call and function return are essentially the same as an open parenthesis and closed parenthesis, so the same ideas should work. When there is a function call, all the important information that needs to be saved, such as register values (corresponding to variable names) and the return address (which can be obtained from the program counter, which is typically in a register), is saved “on a piece of paper” in an abstract way and put at the top of a pile. Then the control is transferred to the new function, which is free to replace the registers with its values. If it makes other function calls, it follows the same procedure. When the function wants to return, it looks at the “paper” at the top of the pile and restores all the registers. It then makes the return jump. Clearly, all of this work can be done using a stack, and that is exactly what happens in virtually every programming language that implements recursion. The information saved is called either an activation record or stack frame. Typically, a slight adjustment is made: The current environment is represented at the top of the stack. Thus, a return gives the previous environment (without copying). The stack in a real computer frequently grows from the high end of your memory partition downward, and on many systems there is no checking for overﬂow. There is always the possibility that you will run out of stack space by having too many simultaneously active functions. Needless to say, running out of stack space is always a fatal error. In languages and systems that do not check for stack overﬂow, programs crash with- out an explicit explanation. In normal events, you should not run out of stack space; doing so is usually an indication of runaway recursion (forgetting a base case). On the other hand, some perfectly legal and seemingly innocuous programs can cause you to run out of stack space. The routine in Figure 3.25, which prints out a container, is perfectly legal and actually correct. It properly handles the base case of an empty container, and the recursion is ﬁne. This program can be proven correct. Unfortunately, if the container 1 4 template 5 void print( Iterator start, Iterator end, ostream & out = cout ) 6 { 7 if( start == end ) 8 return; 9 10 out right will make changes. 136 Chapter 4 Trees 1 template 2 class BinarySearchTree 3 { 4 public: 5 6 // Same methods, with Object replacing Comparable 7 8 private: 9 10 BinaryNode *root; 11 Comparator isLessThan; 12 13 // Same methods, with Object replacing Comparable 14 15 20 bool contains( const Object & x, BinaryNode *t ) const 21 { 22 if( t == nullptr ) 23 return false; 24 else if( isLessThan( x, t->element ) ) 25 return contains( x, t->left ); 26 else if( isLessThan( t->element, x ) ) 27 return contains( x, t->right ); 28 else 29 return true; // Match 30 } 31 }; Figure 4.19 Illustrates use of a function object to implement binary search tree 4.3.3 insert The insertion routine is conceptually simple. To insert X into tree T, proceed down the tree as you would with a contains. If X is found, do nothing. Otherwise, insert X at the last spot on the path traversed. Figure 4.22 shows what happens. To insert 5, we traverse the tree as though a contains were occurring. At the node with item 4, we need to go right, but there is no subtree, so 5 is not in the tree, and this is the correct spot to place 5. Duplicates can be handled by keeping an extra ﬁeld in the node record indicating the frequency of occurrence. This adds some extra space to the entire tree but is better than putting duplicates in the tree (which tends to make the tree very deep). Of course, 4.3 The Search Tree ADT—Binary Search Trees 137 1 5 BinaryNode * findMin( BinaryNode *t ) const 6 { 7 if( t == nullptr ) 8 return nullptr; 9 if( t->left == nullptr ) 10 return t; 11 return findMin( t->left ); 12 } Figure 4.20 Recursive implementation of findMin for binary search trees 1 5 BinaryNode * findMax( BinaryNode *t ) const 6 { 7 if( t != nullptr ) 8 while( t->right != nullptr ) 9 t = t->right; 10 return t; 11 } Figure 4.21 Nonrecursive implementation of findMax for binary search trees 6 6 2 8 2 8 1 4 1 4 3 3 5 Figure 4.22 Binary search trees before and after inserting 5 138 Chapter 4 Trees this strategy does not work if the key that guides the < operator is only part of a larger structure. If that is the case, then we can keep all of the structures that have the same key in an auxiliary data structure, such as a list or another search tree. Figure 4.23 shows the code for the insertion routine. Lines 12 and 14 recursively insert and attach x into the appropriate subtree. Notice that in the recursive routine, the only time that t changes is when a new leaf is created. When this happens, it means that the recursive routine has been called from some other node, p, which is to be the leaf’s parent. The call 1 7 void insert( const Comparable & x, BinaryNode * & t ) 8 { 9 if( t == nullptr ) 10 t = new BinaryNode{ x, nullptr, nullptr }; 11 else if( x < t->element ) 12 insert( x, t->left ); 13 else if( t->element < x ) 14 insert( x, t->right ); 15 else 16 ; // Duplicate; do nothing 17 } 18 19 25 void insert( Comparable && x, BinaryNode * & t ) 26 { 27 if( t == nullptr ) 28 t = new BinaryNode{ std::move( x ), nullptr, nullptr }; 29 else if( x < t->element ) 30 insert( std::move( x ), t->left ); 31 else if( t->element < x ) 32 insert( std::move( x ), t->right ); 33 else 34 ; // Duplicate; do nothing 35 } Figure 4.23 Insertion into a binary search tree 4.3 The Search Tree ADT—Binary Search Trees 139 will be insert(x,p->left) or insert(x,p->right). Either way, t is now a reference to either p->left or p->right, meaning that p->left or p->right will be changed to point at the new node. All in all, a slick maneuver. 4.3.4 remove As is common with many data structures, the hardest operation is deletion. Once we have found the node to be deleted, we need to consider several possibilities. If the node is a leaf, it can be deleted immediately. If the node has one child, the node can be deleted after its parent adjusts a link to bypass the node (we will draw the link directions explicitly for clarity). See Figure 4.24. The complicated case deals with a node with two children. The general strategy is to replace the data of this node with the smallest data of the right subtree (which is easily found) and recursively delete that node (which is now empty). Because the smallest node in the right subtree cannot have a left child, the second remove is an easy one. Figure 4.25 shows an initial tree and the result of a deletion. The node to be deleted is the left child of the root; the key value is 2. It is replaced with the smallest data in its right subtree (3), and then that node is deleted as before. The code in Figure 4.26 performs deletion. It is inefﬁcient because it makes two passes down the tree to ﬁnd and delete the smallest node in the right subtree when this is appro- priate. It is easy to remove this inefﬁciency by writing a special removeMin method, and we have left it in only for simplicity. If the number of deletions is expected to be small, then a popular strategy to use is lazy deletion: When an element is to be deleted, it is left in the tree and merely marked as being deleted. This is especially popular if duplicate items are present, because then the data member that keeps count of the frequency of appearance can be decremented. If the number of real nodes in the tree is the same as the number of “deleted” nodes, then the depth of the tree is only expected to go up by a small constant (why?), so there is a very small time penalty associated with lazy deletion. Also, if a deleted item is reinserted, the overhead of allocating a new cell is avoided. 6 6 2 8 2 8 1 4 1 4 3 3 Figure 4.24 Deletion of a node (4) with one child, before and after 140 Chapter 4 Trees 6 6 2 8 3 8 1 5 1 5 3 3 4 4 Figure 4.25 Deletion of a node (2) with two children, before and after 1 7 void remove( const Comparable & x, BinaryNode * & t ) 8 { 9 if( t == nullptr ) 10 return; // Item not found; do nothing 11 if( x < t->element ) 12 remove( x, t->left ); 13 else if( t->element < x ) 14 remove( x, t->right ); 15 else if( t->left != nullptr && t->right != nullptr ) // Two children 16 { 17 t->element = findMin( t->right )->element; 18 remove( t->element, t->right ); 19 } 20 else 21 { 22 BinaryNode *oldNode = t; 23 t = ( t->left != nullptr

Data Structures and Algorithm Analysis in C++ 4th Edition PDF

Document Details

Tags

Related

Summary

Full Transcript

Upgrade to continue