[PDF] Data Structures and Program Design in C++ By Robert L. Kruse Book Free Download

1.Data StructuresandProgram Designin C++ 2. NAVIGATING THE DISKFor information on using the Acrobat toolbar and other Acrobat commands, consultthe Help document within Acrobat. See especially the section Navigating Pages.Material displayed in green enables jumps to other locations in the book, totransparency masters, and to run sample demonstration programs. These come inthree varieties: The green menu boxes in the left margin of each page perform jumps to fre-quently used parts of the book: Green material in the text itself will jump to the place indicated. After takingsuch a jump, you may return by selecting the icon (go back) in the Acrobattoolbar. The transparency-projector icon ( ) brings up a transparency master on thecurrent topic. Return by selecting the icon (go back) in the Acrobat toolbar. The Windows ( ) icon in the left margin select and run a demonstration pro-gram, which will operate only on the Windows platform.This CD contains a folder textprog that contains the source code for all programsand program segments appearing in the book. These les cannot be compileddirectly, but they can be copied and used for writing other programs.HINTS FOR PAGE NAVIGATION Each chapter (or other major section) of the book is in a separate pdf le, soyou may start Acrobat directly on a desired chapter. To nd a particular section in the current chapter, hit the Home key, or select| in the Acrobat toolbar or in the green menu bar, which will jump to therst page of the chapter where there is a table of contents for the chapter. After jumping to a new location in the book, you can easily return to yourprevious location by selecting (go back) in the Acrobat toolbar. To nd a particular topic, select the index icon ( ) in the left margin. To nd a particular word in the current chapter, use the binoculars icon in theAcrobat toolbar. The PgDown and Enter (or Return) keys advance one screenful, whereas , ,, and advance one page. Of these, only will move from the last page ofone chapter to the rst page of the next chapter. To move backwards, PgUp and Shift+Enter move up one screenful, whereas, , , and move back one page. Of these, only will move from the rstpage of one chapter to the last page of the previous chapter. 3. Data StructuresandProgram Designin C++Robert L. KruseAlexander J. RybaCD-ROM prepared byPaul A. MailhotPrentice HallUpper Saddle River, New Jersey 07458 4. Library of Congress CataloginginPublication DataKRUSE, ROBERT L.Data structures and program design in C++ / Robert L. Kruse,Alexander J. Ryba.p. cm.Includes bibliographical references and index.ISBN 01308769761. C++ (Computer program language) 2. Data Structures(Computer Science) I. Ryba, Alexander J. II. Title.QA76.73.C153K79 1998 9835979005.133dc21 CIPPublisher: Alan AptEditor in Chief: Marcia HortonAcquisitions Editor: Laura SteeleProduction Editor: Rose KernanManaging Editor: Eileen ClarkArt Director: Heather ScottAssistant to Art Director: John ChristianaCopy Editor: Patricia DalyCover Designer: Heather ScottManufacturing Buyer: Pat BrownAssistant Vice President of Production andManufacturing: David W. RiccardiEditorial Assistant: Kate KaibniInterior Design: Robert L. KrusePage Layout: Ginnie Masterson (PreTEX, Inc.)Art Production: Blake MacLean (PreTEX, Inc.)Cover art: Orange, 1923, by Wassily Kandinsky (1866-1944), Lithograph in Colors. Source: Christies Images 2000 by Prentice-Hall, Inc.Simon & Schuster/A Viacom CompanyUpper Saddle River, New Jersey 07458The typesetting for this book was done with PreTEX, a preprocessor and macro package for the TEX typesetting systemand the POSTSCRIPT page-description language. PreTEX is a trademark of PreTEX, Inc.; TEX is a trademark of the AmericanMathematical Society; POSTSCRIPT is a registered trademarks of Adobe Systems, Inc.The authors and publisher of this book have used their best efforts in preparing this book. These efforts include the re-search, development, and testing of the theory and programs in the book to determine their effectiveness. The authorsand publisher make no warranty of any kind, expressed or implied, with regard to these programs or the documenta-tion contained in this book. The authors and publisher shall not be liable in any event for incidental or consequentialdamages in connection with, or arising out of, the furnishing, performance, or use of these programs.All rights reserved. No part of this book may be reproduced, in any form or by any means, without permission in writ-ing from the publisher.Printed in the United States of America10 9 8 7 6 5 4 3 2 1ISBN 0-13-087697-6Prentice-Hall International (U.K.) Limited, LondonPrentice-Hall of Australia Pty. Limited, SydneyPrentice-Hall Canada Inc., TorontoPrentice-Hall Hispanoamericana, S.A., MexicoPrentice-Hall of India Private Limited, New DelhiPrentice-Hall of Japan, Inc., TokyoSimon & Schuster Asia Pte. Ltd., SingaporeEditora Prentice-Hall do Brasil, Ltda., Rio de Janeiro 5. ContentsPreface ixSynopsis xiiCourse Structure xivSupplementary Materials xvBook Production xviAcknowledgments xvi1 ProgrammingPrinciples 11.1 Introduction 21.2 The Game of Life 41.2.1 Rules for the Game of Life 41.2.2 Examples 51.2.3 The Solution: Classes, Objects,and Methods 71.2.4 Life: The Main Program 81.3 Programming Style 101.3.1 Names 101.3.2 Documentation and Format 131.3.3 Renement and Modularity 151.4 Coding, Testing,and Further Renement 201.4.1 Stubs 201.4.2 Denition of the Class Life 221.4.3 Counting Neighbors 231.4.4 Updating the Grid 241.4.5 Input and Output 251.4.6 Drivers 271.4.7 Program Tracing 281.4.8 Principles of Program Testing 291.5 Program Maintenance 341.5.1 Program Evaluation 341.5.2 Review of the Life Program 351.5.3 Program Revisionand Redevelopment 381.6 Conclusions and Preview 391.6.1 Software Engineering 391.6.2 Problem Analysis 401.6.3 Requirements Specication 411.6.4 Coding 41Pointers and Pitfalls 45Review Questions 46References for Further Study 47C++ 47Programming Principles 47The Game of Life 47Software Engineering 482 Introductionto Stacks 492.1 Stack Specications 502.1.1 Lists and Arrays 502.1.2 Stacks 502.1.3 First Example: Reversing a List 512.1.4 Information Hiding 542.1.5 The Standard Template Library 55v 6. vi Contents2.2 Implementation of Stacks 572.2.1 Specication of Methodsfor Stacks 572.2.2 The Class Specication 602.2.3 Pushing, Popping,and Other Methods 612.2.4 Encapsulation 632.3 Application: A Desk Calculator 662.4 Application: Bracket Matching 692.5 Abstract Data Typesand Their Implementations 712.5.1 Introduction 712.5.2 General Denitions 732.5.3 Renement of Data Specication 74Pointers and Pitfalls 76Review Questions 76References for Further Study 773 Queues 783.1 Denitions 793.1.1 Queue Operations 793.1.2 Extended Queue Operations 813.2 Implementations of Queues 843.3 Circular Implementationof Queues in C++ 893.4 Demonstration and Testing 933.5 Application of Queues: Simulation 963.5.1 Introduction 963.5.2 Simulation of an Airport 963.5.3 Random Numbers 993.5.4 The Runway Class Specication 993.5.5 The Plane Class Specication 1003.5.6 Functions and Methodsof the Simulation 1013.5.7 Sample Results 107Pointers and Pitfalls 110Review Questions 110References for Further Study 1114 Linked Stacksand Queues 1124.1 Pointers and Linked Structures 1134.1.1 Introduction and Survey 1134.1.2 Pointers and Dynamic Memoryin C++ 1164.1.3 The Basics of Linked Structures 1224.2 Linked Stacks 1274.3 Linked Stacks with Safeguards 1314.3.1 The Destructor 1314.3.2 Overloading theAssignment Operator 1324.3.3 The Copy Constructor 1354.3.4 The ModiedLinked-Stack Specication 1364.4 Linked Queues 1374.4.1 Basic Declarations 1374.4.2 Extended Linked Queues 1394.5 Application: Polynomial Arithmetic 1414.5.1 Purpose of the Project 1414.5.2 The Main Program 1414.5.3 The Polynomial Data Structure 1444.5.4 Reading and WritingPolynomials 1474.5.5 Addition of Polynomials 1484.5.6 Completing the Project 1504.6 Abstract Data Typesand Their Implementations 152Pointers and Pitfalls 154Review Questions 1555 Recursion 1575.1 Introduction to Recursion 1585.1.1 Stack Frames for Subprograms 1585.1.2 Tree of Subprogram Calls 1595.1.3 Factorials:A Recursive Denition 1605.1.4 Divide and Conquer:The Towers of Hanoi 1635.2 Principles of Recursion 1705.2.1 Designing Recursive Algorithms 1705.2.2 How Recursion Works 1715.2.3 Tail Recursion 1745.2.4 When Not to Use Recursion 1765.2.5 Guidelines and Conclusions 180 7. Contents vii5.3 Backtracking: Postponing the Work 1835.3.1 Solving the Eight-Queens Puzzle 1835.3.2 Example: Four Queens 1845.3.3 Backtracking 1855.3.4 Overall Outline 1865.3.5 Renement: The First Data Structureand Its Methods 1885.3.6 Review and Renement 1915.3.7 Analysis of Backtracking 1945.4 Tree-Structured Programs:Look-Ahead in Games 1985.4.1 Game Trees 1985.4.2 The Minimax Method 1995.4.3 Algorithm Development 2015.4.4 Renement 2035.4.5 Tic-Tac-Toe 204Pointers and Pitfalls 209Review Questions 210References for Further Study 2116 Lists andStrings 2126.1 List Denition 2136.1.1 Method Specications 2146.2 Implementation of Lists 2176.2.1 Class Templates 2186.2.2 Contiguous Implementation 2196.2.3 Simply Linked Implementation 2216.2.4 Variation: Keeping the CurrentPosition 2256.2.5 Doubly Linked Lists 2276.2.6 Comparison of Implementations 2306.3 Strings 2336.3.1 Strings in C++ 2336.3.2 Implementation of Strings 2346.3.3 Further String Operations 2386.4 Application: A Text Editor 2426.4.1 Specications 2426.4.2 Implementation 2436.5 Linked Lists in Arrays 2516.6 Application:Generating Permutations 260Pointers and Pitfalls 265Review Questions 266References for Further Study 2677 Searching 2687.1 Searching:Introduction and Notation 2697.2 Sequential Search 2717.3 Binary Search 2787.3.1 Ordered Lists 2787.3.2 Algorithm Development 2807.3.3 The Forgetful Version 2817.3.4 Recognizing Equality 2847.4 Comparison Trees 2867.4.1 Analysis for n = 10 2877.4.2 Generalization 2907.4.3 Comparison of Methods 2947.4.4 A General Relationship 2967.5 Lower Bounds 2977.6 Asymptotics 3027.6.1 Introduction 3027.6.2 Orders of Magnitude 3047.6.3 The Big-Oand Related Notations 3107.6.4 Keeping the Dominant Term 311Pointers and Pitfalls 314Review Questions 315References for Further Study 3168 Sorting 3178.1 Introduction and Notation 3188.1.1 Sortable Lists 3198.2 Insertion Sort 3208.2.1 Ordered Insertion 3208.2.2 Sorting by Insertion 3218.2.3 Linked Version 3238.2.4 Analysis 3258.3 Selection Sort 3298.3.1 The Algorithm 3298.3.2 Contiguous Implementation 3308.3.3 Analysis 3318.3.4 Comparisons 3328.4 Shell Sort 3338.5 Lower Bounds 336 8. viii Contents8.6 Divide-and-Conquer Sorting 3398.6.1 The Main Ideas 3398.6.2 An Example 3408.7 Mergesort for Linked Lists 3448.7.1 The Functions 3458.7.2 Analysis of Mergesort 3488.8 Quicksort for Contiguous Lists 3528.8.1 The Main Function 3528.8.2 Partitioning the List 3538.8.3 Analysis of Quicksort 3568.8.4 Average-Case Analysis ofQuicksort 3588.8.5 Comparison with Mergesort 3608.9 Heaps and Heapsort 3638.9.1 Two-Way Trees as Lists 3638.9.2 Development of Heapsort 3658.9.3 Analysis of Heapsort 3688.9.4 Priority Queues 3698.10 Review: Comparison of Methods 372Pointers and Pitfalls 375Review Questions 376References for Further Study 3779 Tables and InformationRetrieval 3799.1 Introduction:Breaking the lg n Barrier 3809.2 Rectangular Tables 3819.3 Tables of Various Shapes 3839.3.1 Triangular Tables 3839.3.2 Jagged Tables 3859.3.3 Inverted Tables 3869.4 Tables: A New Abstract Data Type 3889.5 Application: Radix Sort 3919.5.1 The Idea 3929.5.2 Implementation 3939.5.3 Analysis 3969.6 Hashing 3979.6.1 Sparse Tables 3979.6.2 Choosing a Hash Function 3999.6.3 Collision Resolution with OpenAddressing 4019.6.4 Collision Resolution by Chaining 4069.7 Analysis of Hashing 4119.8 Conclusions:Comparison of Methods 4179.9 Application:The Life Game Revisited 4189.9.1 Choice of Algorithm 4189.9.2 Specication of Data Structures 4199.9.3 The Life Class 4219.9.4 The Life Functions 421Pointers and Pitfalls 426Review Questions 427References for Further Study 42810 Binary Trees 42910.1 Binary Trees 43010.1.1 Denitions 43010.1.2 Traversal of Binary Trees 43210.1.3 Linked Implementationof Binary Trees 43710.2 Binary Search Trees 44410.2.1 Ordered Listsand Implementations 44610.2.2 Tree Search 44710.2.3 Insertion into a Binary SearchTree 45110.2.4 Treesort 45310.2.5 Removal from a Binary SearchTree 45510.3 Building a Binary Search Tree 46310.3.1 Getting Started 46410.3.2 Declarationsand the Main Function 46510.3.3 Inserting a Node 46610.3.4 Finishing the Task 46710.3.5 Evaluation 46910.3.6 Random Search Treesand Optimality 47010.4 Height Balance: AVL Trees 47310.4.1 Denition 47310.4.2 Insertion of a Node 47710.4.3 Removal of a Node 48410.4.4 The Height of an AVL Tree 48510.5 Splay Trees:A Self-Adjusting Data Structure 49010.5.1 Introduction 49010.5.2 Splaying Steps 49110.5.3 Algorithm Development 495 9. Contents ix10.5.4 Amortized Algorithm Analysis:Introduction 50510.5.5 Amortized Analysisof Splaying 509Pointers and Pitfalls 515Review Questions 516References for Further Study 51811 MultiwayTrees 52011.1 Orchards, Trees, and Binary Trees 52111.1.1 On the Classication ofSpecies 52111.1.2 Ordered Trees 52211.1.3 Forests and Orchards 52411.1.4 The Formal Correspondence 52611.1.5 Rotations 52711.1.6 Summary 52711.2 Lexicographic Search Trees: Tries 53011.2.1 Tries 53011.2.2 Searching for a Key 53011.2.3 C++ Algorithm 53111.2.4 Searching a Trie 53211.2.5 Insertion into a Trie 53311.2.6 Deletion from a Trie 53311.2.7 Assessment of Tries 53411.3 External Searching: B-Trees 53511.3.1 Access Time 53511.3.2 Multiway Search Trees 53511.3.3 Balanced Multiway Trees 53611.3.4 Insertion into a B-Tree 53711.3.5 C++ Algorithms:Searching and Insertion 53911.3.6 Deletion from a B-Tree 54711.4 Red-Black Trees 55611.4.1 Introduction 55611.4.2 Denition and Analysis 55711.4.3 Red-Black Tree Specication 55911.4.4 Insertion 56011.4.5 Insertion MethodImplementation 56111.4.6 Removal of a Node 565Pointers and Pitfalls 566Review Questions 567References for Further Study 56812 Graphs 56912.1 Mathematical Background 57012.1.1 Denitions and Examples 57012.1.2 Undirected Graphs 57112.1.3 Directed Graphs 57112.2 Computer Representation 57212.2.1 The Set Representation 57212.2.2 Adjacency Lists 57412.2.3 Information Fields 57512.3 Graph Traversal 57512.3.1 Methods 57512.3.2 Depth-First Algorithm 57712.3.3 Breadth-First Algorithm 57812.4 Topological Sorting 57912.4.1 The Problem 57912.4.2 Depth-First Algorithm 58012.4.3 Breadth-First Algorithm 58112.5 A Greedy Algorithm:Shortest Paths 58312.5.1 The Problem 58312.5.2 Method 58412.5.3 Example 58512.5.4 Implementation 58612.6 Minimal Spanning Trees 58712.6.1 The Problem 58712.6.2 Method 58912.6.3 Implementation 59012.6.4 Vericationof Prims Algorithm 59312.7 Graphs as Data Structures 594Pointers and Pitfalls 596Review Questions 597References for Further Study 59713Case Study:The PolishNotation 59813.1 The Problem 59913.1.1 The Quadratic Formula 59913.2 The Idea 60113.2.1 Expression Trees 60113.2.2 Polish Notation 603 10. x Contents13.3 Evaluation of Polish Expressions 60413.3.1 Evaluation of an Expressionin Prex Form 60513.3.2 C++ Conventions 60613.3.3 C++ Functionfor Prex Evaluation 60713.3.4 Evaluationof Postx Expressions 60813.3.5 Proof of the Program:Counting Stack Entries 60913.3.6 Recursive Evaluationof Postx Expressions 61213.4 Translation from Inx Formto Polish Form 61713.5 An InteractiveExpression Evaluator 62313.5.1 Overall Structure 62313.5.2 Representation of the Data:Class Specications 62513.5.3 Tokens 62913.5.4 The Lexicon 63113.5.5 Expressions: Token Lists 63413.5.6 AuxiliaryEvaluation Functions 63913.5.7 Graphing the Expression:The Class Plot 64013.5.8 A Graphics-EnhancedPlot Class 643References for Further Study 645A MathematicalMethods 647A.1 Sums of Powers of Integers 647A.2 Logarithms 650A.2.1 Denition of Logarithms 651A.2.2 Simple Properties 651A.2.3 Choice of Base 652A.2.4 Natural Logarithms 652A.2.5 Notation 653A.2.6 Change of Base 654A.2.7 Logarithmic Graphs 654A.2.8 Harmonic Numbers 656A.3 Permutations, Combinations,Factorials 657A.3.1 Permutations 657A.3.2 Combinations 657A.3.3 Factorials 658A.4 Fibonacci Numbers 659A.5 Catalan Numbers 661A.5.1 The Main Result 661A.5.2 The Proof by One-to-OneCorrespondences 662A.5.3 History 664A.5.4 Numerical Results 665References for Further Study 665B RandomNumbers 667B.1 Introduction 667B.2 Strategy 668B.3 Program Development 669References for Further Study 673C Packages andUtility Functions 674C.1 Packages and C++ Translation Units 674C.2 Packages in the Text 676C.3 The Utility Package 678C.4 Timing Methods 679D Programming Precepts,Pointers, and Pitfalls 681D.1 Choice of Data Structuresand Algorithms 681D.1.1 Stacks 681D.1.2 Lists 681D.1.3 Searching Methods 682D.1.4 Sorting Methods 682D.1.5 Tables 682D.1.6 Binary Trees 683D.1.7 General Trees 684D.1.8 Graphs 684D.2 Recursion 685D.3 Design of Data Structures 686D.4 Algorithm Design and Analysis 687D.5 Programming 688D.6 Programming with Pointer Objects 689D.7 Debugging and Testing 690D.8 Maintenance 690Index 693 11. PrefaceTHE APPRENTICE CARPENTER may want only a hammer and a saw, but a masterbuilder employs many precision tools. Computer programming likewiserequires sophisticated tools to cope with the complexity of real applications,and only practice with these tools will build skill in their use. This book treatsstructured problem solving, object-oriented programming, data abstraction, andthe comparative analysis of algorithms as fundamental tools of program design.Several case studies of substantial size are worked out in detail, to show how allthe tools are used together to build complete programs.Many of the algorithms and data structures we study possess an intrinsic el-egance, a simplicity that cloaks the range and power of their applicability. Beforelong the student discovers that vast improvements can be made over the navemethods usually used in introductory courses. Yet this elegance of method is tem-pered with uncertainty. The student soon nds that it can be far from obvious whichof several approaches will prove best in particular applications. Hence comes anearly opportunity to introduce truly difcult problems of both intrinsic interest andpractical importance and to exhibit the applicability of mathematical methods toalgorithm verication and analysis.Many students nd difculty in translating abstract ideas into practice. Thisbook, therefore, takes special care in the formulation of ideas into algorithms and inthe renement of algorithms into concrete programs that can be applied to practicalproblems. The process of data specication and abstraction, similarly, comes beforethe selection of data structures and their implementations.We believe in progressing from the concrete to the abstract, in the careful de-velopment of motivating examples, followed by the presentation of ideas in a moregeneral form. At an early stage of their careers most students need reinforcementfrom seeing the immediate application of the ideas that they study, and they requirethe practice of writing and running programs to illustrate each important conceptthat they learn. This book therefore contains many sample programs, both shortxi 12. xii Prefacefunctions and complete programs of substantial length. The exercises and pro-gramming projects, moreover, constitute an indispensable part of the book. Manyof these are immediate applications of the topic under study, often requesting thatprograms be written and run, so that algorithms may be tested and compared.Some are larger projects, and a few are suitable for use by a small group of studentsworking together.Our programs are written in the popular object-oriented language C++. Wetake the view that many object-oriented techniques provide natural implemen-tations for basic principles of data-structure design. In this way, C++ allows usto construct safe, efcient, and simple implementations of data-structures. Werecognize that C++ is sufciently complex that students will need to use the ex-perience of a data structures courses to develop and rene their understandingof the language. We strive to support this development by carefully introducingand explaining various object-oriented features of C++ as we progress through thebook. Thus, we begin Chapter 1 assuming that the reader is comfortable with theelementary parts of C++ (essentially, with the C subset), and gradually we addin such object-oriented elements of C++ as classes, methods, constructors, inheri-tance, dynamic memory management, destructors, copy constructors, overloadedfunctions and operations, templates, virtual functions, and the STL. Of course, ourprimary focus is on the data structures themselves, and therefore students withrelatively little familiarity with C++ will need to supplement this text with a C++programming text.SYNOPSISBy working through the rst large project (CONWAYs game of Life), Chapter 1ProgrammingPrinciples expounds principles of object-oriented program design, top-down renement, re-view, and testing, principles that the student will see demonstrated and is expectedto follow throughout the sequel. At the same time, this project provides an oppor-tunity for the student to review the syntax of elementary features of C++, theprogramming language used throughout the book.Chapter 2 introduces the rst data structure we study, the stack. The chapterIntroduction to Stacksapplies stacks to the development of programs for reversing input, for modellinga desk calculator, and for checking the nesting of brackets. We begin by utilizingthe STL stack implementation, and later develop and use our own stack imple-mentation. A major goal of Chapter 2 is to bring the student to appreciate theideas behind information hiding, encapsulation and data abstraction and to applymethods of top-down design to data as well as to algorithms. The chapter closeswith an introduction to abstract data types.Queues are the central topic of Chapter 3. The chapter expounds several dif-Queuesferent implementations of the abstract data type and develops a large applicationprogram showing the relative advantages of different implementations. In thischapter we introduce the important object-oriented technique of inheritance.Chapter 4 presents linked implementations of stacks and queues. The chapterLinked Stacks andQueues begins with a thorough introduction to pointers and dynamic memory manage-ment in C++. After exhibiting a simple linked stack implementation, we discuss 13. Preface Synopsis xiiidestructors, copy constructors, and overloaded assignment operators, all of whichare needed in the safe C++ implementation of linked structures.Chapter 5 continues to elucidate stacks by studying their relationship to prob-Recursionlem solving and programming with recursion. These ideas are reinforced by ex-ploring several substantial applications of recursion, including backtracking andtree-structured programs. This chapter can, if desired, be studied earlier in a coursethan its placement in the book, at any time after the completion of Chapter 2.More general lists with their linked and contiguous implementations provideLists and Stringsthe theme for Chapter 6. The chapter also includes an encapsulated string im-plementation, an introduction to C++ templates, and an introduction to algorithmanalysis in a very informal way.Chapter 7, Chapter 8, and Chapter 9 present algorithms for searching, sorting,Searchingand table access (including hashing), respectively. These chapters illustrate theinterplay between algorithms and the associated abstract data types, data struc-Sortingtures, and implementations. The text introduces the big-O and related notationsfor elementary algorithm analysis and highlights the crucial choices to be maderegarding best use of space, time, and programming effort. These choices requireTables andInformation Retrieval that we nd analytical methods to assess algorithms, and producing such analysesis a battle for which combinatorial mathematics must provide the arsenal. At anelementary level we can expect students neither to be well armed nor to possess themathematical maturity needed to hone their skills to perfection. Our goal, there-fore, is to help students recognize the importance of such skills in anticipation oflater chances to study mathematics.Binary trees are surely among the most elegant and useful of data structures.Their study, which occupies Chapter 10, ties together concepts from lists, searching,Binary Treesand sorting. As recursively dened data structures, binary trees afford an excellentopportunity for the student to become comfortable with recursion applied both todata structures and algorithms. The chapter begins with elementary topics andprogresses as far as such advanced topics as splay trees and amortized algorithmanalysis.Chapter 11 continues the study of more sophisticated data structures, includingMultiway Treestries, B-trees, and red-black trees.Chapter 12 introduces graphs as more general structures useful for problemGraphssolving, and introduces some of the classical algorithms for shortest paths andminimal spanning trees in graphs.The case study in Chapter 13 examines the Polish notation in considerabledetail, exploring the interplay of recursion, trees, and stacks as vehicles for problemCase Study:The Polish Notation solving and algorithm development. Some of the questions addressed can serveas an informal introduction to compiler design. As usual, the algorithms are fullydeveloped within a functioning C++ program. This program accepts as input anexpression in ordinary (inx) form, translates the expression into postx form, andevaluates the expression for specied values of the variable(s). Chapter 13 may bestudied anytime after the completion of Section 10.1.The appendices discuss several topics that are not properly part of the bookssubject but that are often missing from the students preparation.Appendix A presents several topics from discrete mathematics. Its nal twoMathematicalMethods sections, Fibonacci numbers amd Catalan numbers, are more advanced and not 14. xiv Prefaceneeded for any vital purpose in the text, but are included to encourage combina-torial interest in the more mathematically inclined.Appendix B discusses pseudorandom numbers, generators, and applications,Random Numbersa topic that many students nd interesting, but which often does not t anywherein the curriculum.Appendix C catalogues the various utility and data-structure packages that arePackages andUtility Functions developed and used many times throughout this book. Appendix C discusses dec-laration and denition les, translation units, the utility package used throughoutthe book, and a package for calculating CPU times.Appendix D, nally, collects all the Programming Precepts and all the PointersProgrammingPrecepts, Pointers,and Pitfallsand Pitfalls scattered through the book and organizes them by subject for conve-nience of reference.COURSE STRUCTUREThe prerequisite for this book is a rst course in programming, with experienceprerequisiteusing the elementary features of C++. However, since we are careful to introducesophisticated C++ techniques only gradually, we believe that, used in conjunctionwith a supplementary C++ textbook and extra instruction and emphasis on C++language issues, this text provides a data structures course in C++ that remainssuitable even for students whose programming background is in another languagesuch as C, Pascal, or Java.A good knowledge of high school mathematics will sufce for almost all thealgorithm analyses, but further (perhaps concurrent) preparation in discrete math-ematics will prove valuable. Appendix A reviews all required mathematics.This book is intended for courses such as the ACM Course CS2 (Program Designcontentand Implementation), ACM Course CS7 (Data Structures and Algorithm Analysis), ora course combining these. Thorough coverage is given to most of the ACM/IEEEknowledge units1 on data structures and algorithms. These include:AL1 Basic data structures, such as arrays, tables, stacks, queues, trees, and graphs;AL2 Abstract data types;AL3 Recursion and recursive algorithms;AL4 Complexity analysis using the big Oh notation;AL6 Sorting and searching; andAL8 Practical problem-solving strategies, with large case studies.The three most advanced knowledge units, AL5 (complexity classes, NP-completeproblems), AL7 (computability and undecidability), and AL9 (parallel and dis-tributed algorithms) are not treated in this book.1 See Computing Curricula 1991: Report of the ACM/IEEE-CS Joint Curriculum Task Force, ACMPress, New York, 1990. 15. Preface Supplementary Materials xvMost chapters of this book are structured so that the core topics are presentedrst, followed by examples, applications, and larger case studies. Hence, if timeallows only a brief study of a topic, it is possible, with no loss of continuity, to moverapidly from chapter to chapter covering only the core topics. When time permits,however, both students and instructor will enjoy the occasional excursion into thesupplementary topics and worked-out projects.A two-term course can cover nearly the entire book, thereby attaining a satis-two-term coursefying integration of many topics from the areas of problem solving, data structures,program development, and algorithm analysis. Students need time and practice tounderstand general methods. By combining the studies of data abstraction, datastructures, and algorithms with their implementations in projects of realistic size,an integrated course can build a solid foundation on which, later, more theoreticalcourses can be built. Even if it is not covered in its entirety, this book will provideenough depth to enable interested students to continue using it as a reference inlater work. It is important in any case to assign major programming projects andto allow adequate time for their completion.SUPPLEMENTARY MATERIALSA CD-ROM version of this book is anticipated that, in addition to the entire contentsof the book, will include: All packages, programs, and other C++ code segments from the text, in a formready to incorporate as needed into other programs; Executable versions (for DOS or Windows) of several demonstration programsand nearly all programming projects from the text; Brief outlines or summaries of each section of the text, suitable for use as astudy guide.These materials will also be available from the publishers internet site. To reachthese les with ftp, log in as user anonymous to the site ftp.prenhall.com andchange to the directorypub/esm/computer_science.s-041/kruse/cppInstructors teaching from this book may obtain, at no charge, an instructorsversion on CD-ROM which, in addition to all the foregoing materials, includes: Brief teaching notes on each chapter; Full solutions to nearly all exercises in the textbook; Full source code to nearly all programming projects in the textbook; Transparency masters. 16. xvi PrefaceBOOK PRODUCTIONThis book and its supplements were written and produced with software calledPreTEX, a preprocessor and macro package for the TEX typesetting system.2 PreTEX,by exploiting context dependency, automatically supplies much of the typesettingmarkup required by TEX. PreTEX also supplies several tools that greatly simplifysome aspects of an authors work. These tools include a powerful cross-referencesystem, simplied typesetting of mathematics and computer-program listings, andautomatic generation of the index and table of contents, while allowing the pro-cessing of the book in conveniently small les at every stage. Solutions, placedwith exercises and projects, are automatically removed from the text and placed ina separate document.For a book such as this, PreTEXs treatment of computer programs is its mostimportant feature. Computer programs are not included with the main body of thetext; instead, they are placed in separate, secondary les, along with any desiredexplanatory text, and with any desired typesetting markup in place. By placingtags at appropriate places in the secondary les, PreTEX can extract arbitrary partsof a secondary le, in any desired order, for typesetting with the text. Anotherutility removes all the tags, text, and markup, producing as its output a programready to be compiled. The same input le thus automatically produces both type-set program listings and compiled program code. In this way, the reader gainsincreased condence in the accuracy of the computer program listings appearingin the text. In fact, with just two exceptions, all of the programs developed in thisbook have been compiled and succesfully tested under the g++ and Borland C++compilers (versions 2.7.2.1 and 5.0, respectively). The two exceptions are the rstprogram in Chapter 2 (which requires a compiler with a full ANSI C++ standardlibrary) and the last program of Chapter 13 (which requires a compiler with certainBorland graphics routines).ACKNOWLEDGMENTSOver the years, the Pascal and C antecedents of this book have benetted greatlyfrom the contributions of many people: family, friends, colleagues, and students,some of whom are noted in the previous books. Many other people, while studyingthese books or their translations into various languages, have kindly forwardedtheir comments and suggestions, all of which have helped to make this a betterbook.We are happy to acknowledge the suggestions of the following reviewers,who have helped in many ways to improve the presentation in this book: KEITHVANDER LINDEN (Calvin College), JENS GREGOR (University of Tennessee), VICTORBERRY (Boston University), JEFFERY LEON (University of Illinois at Chicago), SUSAN2 TEX was developed by DONALD E. KNUTH, who has also made many important research contri-butions to data structures and algorithms. (See the entries under his name in the index.) 17. Preface Acknowledgments xviiHUTT (University of MissouriColumbia), FRED HARRIS (University of Nevada), ZHI-LI ZHANG (University of Minnesota), and ANDREW SUNG (New Mexico Institute ofTechnology).ALEX RYBA especially acknowledges the helpful suggestions and encouragingadvice he has received over the years from WIM RUITENBURG and JOHN SIMMS ofMarquette University, as well as comments from former students RICK VOGEL andJUN WANG.It is a special pleasure for ROBERT KRUSE to acknowledge the continuing adviceand help of PAUL MAILHOT of PreTEX, Inc., who was from the rst an outstandingstudent, then worked as a dependable research assistant, and who has now becomea valued colleague making substantial contributions in software development forbook production, in project management, in problem solving for the publisher, theprinter, and the authors, and in providing advice and encouragement in all aspectsof this work. The CD-ROM versions of this book, with all their hypertext features(such as extensive cross-reference links and execution of demonstration programsfrom the text), are entirely his accomplishment.Without the continuing enthusiastic support, faithful encouragement, and pa-tience of the editorial staff of Prentice Hall, especially ALAN APT, Publisher, LAURASTEELE, Acquisitions Editor, and MARCIA HORTON, Editor in Chief, this project wouldnever have been started and certainly could never have been brought to comple-tion. Their help, as well as that of the production staff named on the copyrightpage, has been invaluable.ROBERT L. KRUSEALEXANDER J. RYBA 18. ProgrammingPrinciples 1THIS CHAPTER summarizes important principles of good programming, es-peciallyasappliedtolargeprojects, andintroducesmethodssuchasobject-oriented design and top-down design for discovering effective algorithms.In the process we raise questions in program design and data-storagemethods that we shall address in later chapters, and we also review some ofthe elementary features of the language C++ by using them to write programs.1.1 Introduction 21.2 The Game of Life 41.2.1 Rules for the Game of Life 41.2.2 Examples 51.2.3 The Solution: Classes, Objects, andMethods 71.2.4 Life: The Main Program 81.3 Programming Style 101.3.1 Names 101.3.2 Documentation and Format 131.3.3 Renement and Modularity 151.4 Coding, Testing, and Further Renement 201.4.1 Stubs 201.4.2 Denition of the Class Life 221.4.3 Counting Neighbors 231.4.4 Updating the Grid 241.4.5 Input and Output 251.4.6 Drivers 271.4.7 Program Tracing 281.4.8 Principles of Program Testing 291.5 Program Maintenance 341.5.1 Program Evaluation 341.5.2 Review of the Life Program 351.5.3 Program Revision andRedevelopment 381.6 Conclusions and Preview 391.6.1 Software Engineering 391.6.2 Problem Analysis 401.6.3 Requirements Specication 411.6.4 Coding 41Pointers and Pitfalls 45Review Questions 46References for Further Study 47C++ 47Programming Principles 47The Game of Life 47Software Engineering 481 19. 1.1 INTRODUCTIONThe greatest difculties of writing large computer programs are not in decidingwhat the goals of the program should be, nor even in nding methods that canbe used to reach these goals. The president of a business might say, Lets get acomputer to keep track of all our inventory information, accounting records, and2personnel les, and let it tell us when inventories need to be reordered and budgetlines are overspent, and let it handle the payroll. With enough time and effort, astaff of systems analysts and programmers might be able to determine how variousstaff members are now doing these tasks and write programs to do the work in thesame way.This approach, however, is almost certain to be a disastrous failure. Whileinterviewing employees, the systems analysts will nd some tasks that can be puton the computer easily and will proceed to do so. Then, as they move other workproblems of largeprograms to the computer, they will nd that it depends on the rst tasks. The output fromthese, unfortunately, will not be quite in the proper form. Hence they need moreprogramming to convert the data from the form given for one task to the formneeded for another. The programming project begins to resemble a patchworkquilt. Some of the pieces are stronger, some weaker. Some of the pieces are carefullysewn onto the adjacent ones, some are barely tacked together. If the programmersare lucky, their creation may hold together well enough to do most of the routinework most of the time. But if any change must be made, it will have unpredictableconsequences throughout the system. Later, a new request will come along, or anunexpected problem, perhaps even an emergency, and the programmers effortswill prove as effective as using a patchwork quilt as a safety net for people jumpingfrom a tall building.The main purpose of this book is to describe programming methods and toolsthat will prove effective for projects of realistic size, programs much larger thanthose ordinarily used to illustrate features of elementary programming. Since apiecemeal approach to large problems is doomed to fail, we must rst of all adopta consistent, unied, and logical approach, and we must also be careful to observeimportant principles of program design, principles that are sometimes ignored inwriting small programs, but whose neglect will prove disastrous for large projects.The rst major hurdle in attacking a large problem is deciding exactly whatthe problem is. It is necessary to translate vague goals, contradictory requests,problem specicationand perhaps unstated desires into a precisely formulated project that can be pro-grammed. And the methods or divisions of work that people have previously usedare not necessarily the best for use in a machine. Hence our approach must be todetermine overall goals, but precise ones, and then slowly divide the work intosmaller problems until they become of manageable size.The maxim that many programmers observe, First make your program work,program designthen make it pretty, may be effective for small programs, but not for large ones.Each part of a large program must be well organized, clearly written, and thor-oughly understood, or else its structure will have been forgotten, and it can nolonger be tied to the other parts of the project at some much later time, perhaps byanother programmer. Hence we do not separate style from other parts of programdesign, but from the beginning we must be careful to form good habits.2 20. Section 1.1 Introduction 3Even with very large projects, difculties usually arise not from the inability tond a solution but, rather, from the fact that there can be so many different methodsand algorithms that might work that it can be hard to decide which is best, whichmay lead to programming difculties, or which may be hopelessly inefcient. Thegreatest room for variability in algorithm design is generally in the way in whichchoice ofdata structures the data of the program are stored: How they are arranged in relation to each other. Which data are kept in memory. Which are calculated when needed. Which are kept in les, and how the les are arranged.A second goal of this book, therefore, is to present several elegant, yet fundamen-tally simple ideas for the organization and manipulation of data. Lists, stacks, andqueues are the rst three such organizations that we study. Later, we shall developseveral powerful algorithms for important tasks within data processing, such assorting and searching.When there are several different ways to organize data and devise algorithms,it becomes important to develop criteria to recommend a choice. Hence we devoteattention to analyzing the behavior of algorithms under various conditions.analysis of algorithmsThe difculty of debugging a program increases much faster than its size. Thatis, if one program is twice the size of another, then it will likely not take twice aslong to debug, but perhaps four times as long. Many very large programs (suchtesting andverication as operating systems) are put into use still containing errors that the programmershave despaired of nding, because the difculties seem insurmountable. Some-times projects that have consumed years of effort must be discarded because it isimpossible to discover why they will not work. If we do not wish such a fate forour own projects, then we must use methods that will Reduce the number of errors, making it easier to spot those that remain.program correctness Enable us to verify in advance that our algorithms are correct. Provide us with ways to test our programs so that we can be reasonably con-dent that they will not misbehave.Development of such methods is another of our goals, but one that cannot yet befully within our grasp.Even after a program is completed, fully debugged, and put into service, agreat deal of work may be required to maintain the usefulness of the program. Inmaintenancetime there will be new demands on the program, its operating environment willchange, new requests must be accommodated. For this reason, it is essential that alarge project be written to make it as easy to understand and modify as possible.The programming language C++ is a particularly convenient choice to expressC++the algorithms we shall encounter. The language was developed in the early 1980s,by Bjarne Stroustrup, as an extension of the popular C language. Most of the newfeatures that Stroustrup incorporated into C++ facilitate the understanding andimplementation of data structures. Among the most important features of C++ forour study of data structures are: 21. 4 Chapter 1 Programming Principles C++ allows data abstraction: This means that programmers can create newtypes to represent whatever collections of data are convenient for their appli-cations. C++ supports object-oriented design, in which the programmer-dened typesplay a central role in the implementation of algorithms. Importantly, as well as allowing for object-oriented approaches, C++ allowsfor the use of the top-down approach, which is familiar to C programmers. C++ facilitates code reuse, and the construction of general purpose libraries.The language includes an extensive, efcient, and convenient standard library. C++ improves on several of the inconvenient and dangerous aspects of C. C++ maintains the efciency that is the hallmark of the C language.It is the combination of exibility, generality and efciency that has made C++ oneof the most popular choices for programmers at the present time.We shall discover that the general principles that underlie the design of alldata structures are naturally implemented by the data abstraction and the object-oriented features of C++. Therefore, we shall carefully explain how these aspectsof C++ are used and briey summarize their syntax (grammar) wherever they rstarise in our book. In this way, we shall illustrate and describe many of the featuresof C++ that do not belong to its small overlap with C. For the precise details of C++syntax, consult a textbook on C++ programmingwe recommend several suchbooks in the references at the end of this chapter.1.2 THE GAME OF LIFEIf we may take the liberty to abuse an old proverb,One concrete problem is worth a thousand unapplied abstractions.Throughout this chapter we shall concentrate on one case study that, while notlarge by realistic standards, illustrates both the principles of program design andthepitfallsthatweshouldlearntoavoid. Sometimestheexamplemotivatesgeneralprinciples; sometimes the general discussion comes rst; always it is with the viewof discovering general principles that will prove their value in a range of practicalapplications. In later chapters we shall employ similar methods for larger projects.3The example we shall use is the game called Life, which was introduced by theBritish mathematician J. H. CONWAY in 1970.1.2.1 Rules for the Game of LifeLife is really a simulation, not a game with players. It takes place on an unboundedrectangular grid in which each cell can either be occupied by an organism or not.Occupied cells are called alive; unoccupied cells are called dead. Which cells aredenitionsalive changes from generation to generation according to the number of neighbor-ing cells that are alive, as follows: 22. Section 1.2 The Game of Life 51. The neighbors of a given cell are the eight cells that touch it vertically, horizon-transition rulestally, or diagonally.2. If a cell is alive but either has no neighboring cells alive or only one alive, thenin the next generation the cell dies of loneliness.3. If a cell is alive and has four or more neighboring cells also alive, then in thenext generation the cell dies of overcrowding.4. A living cell with either two or three living neighbors remains alive in the nextgeneration.5. If a cell is dead, then in the next generation it will become alive if it has exactlythree neighboring cells, no more or fewer, that are already alive. All other deadcells remain dead in the next generation.6. All births and deaths take place at exactly the same time, so that dying cellscan help to give birth to another, but cannot prevent the death of others byreducing overcrowding; nor can cells being born either preserve or kill cellsliving in the previous generation.A particular arrangement of living and dead cells in a grid is called a conguration.congurationThe preceding rules explain how one conguration changes to another at eachgeneration.1.2.2 ExamplesAs a rst example, consider the congurationThe counts of living neighbors for the cells are as follows:40 0 0 0 0 00 1 2 2 1 00 1 1 1 1 00 1 2 2 1 00 0 0 0 0 0 23. 6 Chapter 1 Programming PrinciplesBy rule 2 both the living cells will die in the coming generation, and rule 5 showsmoribund examplethat no cells will become alive, so the conguration dies out.On the other hand, the conguration0 0 0 0 0 00 1 2 2 1 00 2 3 3 2 00 2 3 3 2 00 0 0 0 0 00 1 2 2 1 0has the neighbor counts as shown. Each of the living cells has a neighbor count ofstabilitythree, and hence remains alive, but the dead cells all have neighbor counts of twoor less, and hence none of them becomes alive.The two congurations0 0 0 0 01 2 3 2 11 1 2 1 11 2 3 2 10 0 0 0 00 1 1 1 00 2 1 2 00 3 2 3 00 2 1 2 00 1 1 1 0andcontinue to alternate from generation to generation, as indicated by the neighboralternationcounts shown.It is a surprising fact that, from very simple initial congurations, quite compli-cated progressions of Life congurations can develop, lasting many generations,and it is usually not obvious what changes will happen as generations progress.Some very small initial congurations will grow into large congurations; othersvarietywill slowly die out; many will reach a state where they do not change, or wherethey go through a repeating pattern every few generations.Not long after its invention, MARTIN GARDNER discussed the Life game in hispopularitycolumn in Scientic American, and, from that time on, it has fascinated many people,so that for several years there was even a quarterly newsletter devoted to relatedtopics. It makes an ideal display for home microcomputers.Our rst goal, of course, is to write a program that will show how an initialconguration will change from generation to generation. 24. Section 1.2 The Game of Life 71.2.3 The Solution: Classes, Objects, and MethodsIn outline, a program to run the Life game takes the form:Set up a Life conguration as an initial arrangement of living and dead cells.algorithmPrint the Life conguration.While the user wants to see further generations:Update the conguration by applying the rules of the Life game.Print the current conguration.The important thing for us to study in this algorithm is the Life conguration. InclassC++, we use a class to collect data and the methods used to access or change thedata. Such a collection of data and methods is called an object belonging to theobjectgiven class. For the Life game, we shall call the class Life, so that congurationbecomes a Life object. We shall then use three methods for this object: initialize( )will set up the initial conguration of living and dead cells; print( ) will print out5the current conguration; and update( ) will make all the changes that occur inmoving from one generation to the next.Every C++ class, in fact, consists of members that represent either variables orC++ classesfunctions. The members that represent variables are called the data members; theseare used to store data values. The members that represent functions belonging toa class are called the methods or member functions. The methods of a class aremethodsnormally used to access or alter the data members.Clients, that is, user programs with access to a particular class, can declare andclientsmanipulate objects of that class. Thus, in the Life game, we shall declare a Lifeobject by:Life conguration;We can now apply methods to work with conguration, using the C++ operator. (the member selection operator). For example, we can print out the data inmember selectionoperator conguration by writing:conguration.print( );It is important to realize that, while writing a client program, we can use aC++ class so long as we know the specications of each of its methods, that is,specicationsstatements of precisely what each method does. We do not need to know how6the data are actually stored or how the methods are actually programmed. Forexample, to use a Life object, we do not need to know exactly how the object isstored, or how the methods of the class Life are doing their work. This is our rstinformation hidingexample of an important programming strategy known as information hiding.When the time comes to implement the class Life, we shall nd that moregoes on behind the scenes: We shall need to decide how to store the data, andwe shall need variables and functions to manipulate this data. All these variablesprivate and publicand functions, however, are private to the class; the client program does not needto know what they are, how they are programmed, or have any access to them.Instead, the client program only needs the public methods that are specied anddeclared for the class. 25. 8 Chapter 1 Programming PrinciplesIn this book, we shall always distinguish between methods and functions asfollows, even though their actual syntax (programming grammar) is the same:ConventionMethods of a class are public.Functions in a class are private.1.2.4 Life: The Main ProgramThe preceding outline of an algorithm for the game of Life translates into the fol-lowing C++ program.7#include “utility.h”#include “life.h”int main( ) // Program to play Conways game of Life./* Pre: The user supplies an initial conguration of living cells.Post: The program prints a sequence of pictures showing the changes in theconguration of living cells according to the rules for the game of Life.Uses: The class Life and its methods initialize( ), print( ), and update( ).The functions instructions( ), user_says_yes( ). */{Life conguration;instructions( );conguration.initialize( );conguration.print( );cout orange) return(orange); elsereturn(peach); else return(apple); }E6. The following statement is designed to check the relative sizes of three integers,which you may assume to be different from each other:if (x < z) if (x < y) if (y < z) c = 1; else c = 2; elseif (y < z) c = 3; else c = 4; else if (x < y)if (x < z) c = 5; else c = 6; else if (y < z) c = 7; elseif (z < x) if (z < y) c = 8; else c = 9; else c = 10;(a) Rewrite this statement in a form that is easier to read.(b) Since there are only six possible orderings for the three integers, only sixof the ten cases can actually occur. Find those that can never occur, andeliminate the redundant checks.(c) Write a simpler, shorter statement that accomplishes the same result.E7. The following C++ function calculates the cube root of a oating-point number(by the Newton approximation), using the fact that, if y is one approximationto the cube root of x, thenz =2y + x/y23is a closer approximation.cube rootsoat function fcn(oat stuff){ oat april, tim, tiny, shadow, tom, tam, square; int ag;tim = stuff; tam = stuff; tiny = 0.00001;if (stuff != 0) do {shadow = tim + tim; square = tim * tim;tom = (shadow + stuff/square); april = tom/3.0;if (april*april * april tam > tiny) if (april*april*april tam< tiny) ag = 1; else ag = 0; else ag = 0;if (ag == 0) tim = april; else tim = tam; } while (ag != 1);if (stuff == 0) return(stuff); else return(april); }(a) Rewrite this function with meaningful variable names, without the extravariablesthatcontributenothingtotheunderstanding, withabetterlayout,and without the redundant and useless statements.(b) Write a function for calculating the cube root of x directly from the mathe-matical formula, by starting with the assignment y = x and then repeatingy = (2 * y + (x/(y * y)))/3until abs(y * y * y x) < 0.00001.(c) Which of these tasks is easier? 37. 20 Chapter 1 Programming PrinciplesE8. The mean of a sequence of numbers is their sum divided by the count of num-bers in the sequence. The (population) variance of the sequence is the meanof the squares of all numbers in the sequence, minus the square of the meanstatisticsof the numbers in the sequence. The standard deviation is the square root ofthe variance. Write a well-structured C++ function to calculate the standarddeviation of a sequence of n oating-point numbers, where n is a constant andthe numbers are in an array indexed from 0 to n 1, which is a parameter tothe function. Use, then write, subsidiary functions to calculate the mean andvariance.E9. Design a program that will plot a given set of points on a graph. The inputto the program will be a text le, each line of which contains two numbersthat are the x and y coordinates of a point to be plotted. The program willuse a function to plot one such pair of coordinates. The details of the functioninvolve the specic method of plotting and cannot be written since they dependplottingon the requirements of the plotting equipment, which we do not know. Beforeplotting the points the program needs to know the maximum and minimumvalues of x and y that appear in its input le. The program should thereforeuse another function bounds that will read the whole le and determine thesefour maxima and minima. Afterward, another function is used to draw andlabel the axes; then the le can be reset and the individual points plotted.(a) Write the main program, not including the functions.(b) Write the function bounds.(c) Write the preconditions and postconditions for the remaining functions to-gether with appropriate documentation showing their purposes and theirrequirements.1.4 CODING, TESTING, AND FURTHER REFINEMENTThe three processes in the section title go hand-in-hand and must be done together.Yet it is important to keep them separate in our thinking, since each requires its ownapproach and method. Coding, of course, is the process of writing an algorithmin the correct syntax (grammar) of a computer language like C++, and testing isthe process of running the program on sample data chosen to nd errors if theyare present. For further renement, we turn to the functions not yet written andrepeat these steps.1.4.1 StubsAfter coding the main program, most programmers will wish to complete thewriting and coding of the required classes and functions as soon as possible, tosee if the whole project will work. For a project as small as the Life game, thisearly debugging andtesting approach may work, but for larger projects, the writing and coding will be such alarge job that, by the time it is complete, many of the details of the main programand the classes and functions that were written early will have been forgotten. Infact, different people may be writing different functions, and some of those who 38. Section 1.4 Coding, Testing, and Further Renement 21started the project may have left it before all functions are written. It is much easierto understand and debug a program when it is fresh in your mind. Hence, forlarger projects, it is much more efcient to debug and test each class and functionas soon as it is written than it is to wait until the project has been completely coded.Even for smaller projects, there are good reasons for debugging classes andfunctions one at a time. We might, for example, be unsure of some point of C++syntax that will appear in several places through the program. If we can compileeach function separately, then we shall quickly learn to avoid errors in syntax inlater functions. As a second example, suppose that we have decided that the majorsteps of the program should be done in a certain order. If we test the main programas soon as it is written, then we may nd that sometimes the major steps are donein the wrong order, and we can quickly correct the problem, doing so more easilythan if we waited until the major steps were perhaps obscured by the many detailscontained in each of them.To compile the main program correctly, there must be something in the placeof each function that is used, and hence we must put in short, dummy functions,stubscalled stubs. The simplest stubs are those that do little or nothing at all:void instructions( ) { }bool user_says_yes( ) { return(true); }Note that in writing the stub functions we must at least pin down their associated14parameters and return types. For example, in designing a stub for user_says_yes( ),we make the decision that it should return a natural answer of true or false. Thismeans that we should give the function a return type bool. The type bool has onlyrecently been added to C++ and some older compilers do not recognize it, but wecan always simulate it with the following statementswhich can conveniently beplaced in the utility package, if they are needed:typedef int bool;const bool false = 0;const bool true = 1;In addition to the stub functions, our program also needs a stub denition forthe class Life. For example, in the le life.h, we could dene this class withoutdata members as follows:class Life {public:void initialize( );void print( );void update( );};We must also supply the following stubs for its methods in life.c:void Life :: initialize( ) {}void Life :: print( ) {}void Life :: update( ) {} 39. 22 Chapter 1 Programming PrinciplesNote that these method denitions have to use the C++ scope resolution opera-tor :: 4 to indicate that they belong to the scope of the class Life.Even with these minimal stubs we can at least compile the program and makesure that the denitions of types and variables are syntactically correct. Normally,however, each stub function should print a message stating that the function wasinvoked. When we execute the program, we nd that it runs into an innite loop,because the function user_says_yes( ) always returns a value of true. However,the main program compiles and runs, so we can go on to rene our stubs. For asmall project like the Life game, we can simply write each class or function in turn,substitute it for its stub, and observe the effect on program execution.1.4.2 Denition of the Class LifeEach Life object needs to include a rectangular array,5 which we shall call grid, tostore a Life conguration. We use an integer entry of 1 in the array grid to denote a1: living cell0: dead cell living cell, and 0 to denote a dead cell. Thus to count the number of neighbors of aparticular cell, we just add the values of the neighboring cells. In fact, in updatinga Life conguration, we shall repeatedly need to count the number of living neigh-bors of individual cells in the conguration. Hence, the class Life should include a13member function neighbor_count that does this task. Moreover, since the memberneighbor_count is not needed by client code, we shall give it private visibility. Incontrast, the earlier Life methods all need to have public visibility. Finally, we mustsettle on dimensions for the rectangular array carried in a Life conguration. Wecode these dimensions as global constants, so that a single simple change is all thatwe need to reset grid sizes in our program. Note that constant denitions can besafely placed in .h les.14const int maxrow = 20, maxcol = 60; // grid dimensionsclass Life {public:void initialize( );void print( );void update( );private:int grid[maxrow + 2][maxcol + 2];// allows for two extra rows and columnsint neighbor_count(int row, int col);};We can test the denition, without writing the member functions, by using ourearlier stub methods together with a similar stub for the private function neigh-bor_count.4 Consult a C++ textbook for discussion of the scope resolution operator and the syntax for classmethods.5 An array with two indices is called rectangular. The rst index determines the row in the arrayand the second the column. 40. Section 1.4 Coding, Testing, and Further Renement 231.4.3 Counting NeighborsLet us now rene our program further. The function that counts neighbors of thecell with coordinates row, col requires that we look in the eight adjoining cells. Wefunctionneighbor_count shall use a pair of for loops to do this, one running from row1 to row + 1 andthe other from col1 to col + 1. We need only be careful, when row, col is on aboundary of the grid, that we look only at legitimate cells in the grid. Rather thanusing several if statements to make sure that we do not go outside the grid, wehedgeintroduce a hedge around the grid: We shall enlarge the grid by adding two extrarows, one before the rst real row of the grid and one after the last, and two extracolumns, one before the rst column and one after the last. In our denition ofthe class Life, we anticipated the hedge by dening the member grid as an arraywith maxrow + 2 rows and maxcol + 2 columns. The cells in the hedge rows andcolumns will always be dead, so they will not affect the counts of living neighborsat all. Their presence, however, means that the for loops counting neighbors needmake no distinction between rows or columns on the boundary of the grid and anyother rows or columns. See the examples in Figure 1.2.15hedgehedgehedge0 1 2 maxcolmaxcol + 1012Color tintshowsneighbors ofblack cells.hedgemaxrowmaxrow + 1Figure 1.2. Life grid with a hedgeAnother term often used instead of hedge is sentinel: A sentinel is an extraentry put into a data structure so that boundary conditions need not be treated assentinela special case.int Life :: neighbor_count(int row, int col)/* Pre: The Life object contains a conguration, and the coordinates row and coldene a cell inside its hedge.Post: The number of living neighbors of the specied cell is returned. */ 41. 24 Chapter 1 Programming Principles{int i, j;int count = 0;for (i = row 1; i