S I X T H E D I T I O N Problem Solving, Abstraction, and Design Using C ++ This page intentionally left blank S I X T H E D I T I O N PPrroobblleemm SSoollvviinngg,, AAbbssttrraaccttiioonn,, aanndd DDeessiiggnn UUssiinngg C ++ FRANK L. FRIEDMAN Temple University ELLIOT B. KOFFMAN Temple University Addison-Wesley Boston Columbus Indianapolis New York San Francisco Upper Saddle River Amsterdam Cape Town Dubai London Madrid Milan Munich Paris Montréal Toronto Delhi Mexico City São Paulo Sydney Hong Kong Seoul Singapore Taipei Tokyo Editor-in-Chief:Michael Hirsch Production Supervisor:Heather McNally Editorial Assistant:Stephanie Sellinger Cover Designer:Margaret Kenselaar Director of Marketing:Margaret Waples Cover Art:iStockPhoto Marketing Coordinator:Kathryn Ferranti Full-Service Project Management:Integra Project Manager:Wanda Rockwell Access the latest information about Addison-Wesley titles from our World Wide Web site: http://www.pearsonhighered.com/cs Credits and acknowledgments borrowed from other sources and reproduced, with permission, in this textbook appear on appropriate page within text. Microsoft® and Windows® are registered trademarks of the Microsoft Corporation in the U.S.A. and other countries. Screen shots and icons reprinted with permission from the Microsoft Corporation. This book is not sponsored or endorsed by or affiliated with the Microsoft Corporation. The programs and applications presented in this book have been included for their instructional value. They have been tested with care, but are not guaranteed for any particular purpose. The publisher does not offer any warranties or representations, nor does it accept any liabilities with respect to the programs or applications. Copyright © 2011, 2007, 2004, 2000, 1997. Pearson Education, Inc., publishing as Addison-Wesley, 501 Boylston Street, Suite 900, Boston, Massachusetts 02116. All rights reserved. Manufactured 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, 501 Boylston Street, Suite 900, Boston, Massachusetts 02116. 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 Friedman, Frank L. Problem solving, abstraction, and design using C++/Frank L. Friedman, Elliot B. Koffman.—5th ed. p. cm. Includes bibliographical references and index. ISBN-13: 978-0-13-607947-7 (alk. paper) ISBN-10: 0-13-607947-4 (alk. paper) 1. C++ (Computer program language) I. Koffman, Elliot B. II. Title. QA76.73.C153F75 2011 005.13'3—dc22 2010003344 10 9 8 7 6 5 4 3 2 1—EB—14 13 12 11 10 ISBN 10: 0-13-607947-4 ISBN 13: 978-0-13-607947-7 To Martha, Dara, Shelley, and my parents George and Sylvia whose limitless support made everything possible. And to Sammy, the little miracle who brightened my life. FLF To my wife, Caryn my children, Richard, Deborah, and Robin my daughter- and son-in-law Jacquie and Jeff and my grandchildren Dustin, Jonathan, and Eliana with much thanks for your love and support. EBK This page intentionally left blank Preface This is a textbook for a one- or two-semester course in problem solving and program design. It is suitable for use by students with no programming background as well as those with a one-semester course, or the equivalent, in another programming language. Students’ backgrounds will determine the time required to cover the earlier chapters of the text and the extent of coverage possible for later chapters. The earlier editions of this book represented the culmination of an eight-year effort, partially sponsored by the National Science Foundation, to define an introductory-level course that presented the rudimentary princi- ples of software engineering and object-oriented programming along with an introduction to the C++ programming language. Our primary goal is to motivate and introduce sound principles of program design and abstraction in a first programming course. Early in the book we introduce topics such as program style, documentation, algorithm and data structuring, proce- dure- and data-oriented modularization, component reuse, and program verification. The focus throughout is on the problem solving/software design process, from problem analysis to program design and coding. The textbook fits the objectives of the first course in programming, following an imperative first approach as described in the ACM/IEEE Computing Curricula 2001 (courses CS101 or CS111). Because it also intro- duces object-oriented programming and the C++ Standard Template Library (STL) as well as recursion and dynamic data structures, it may also be used as the textbook for the second course in the three-semester sequence, CS102.The textbook can also be used in an objects early approach to the first programming course as classes are introduced in Chapter 1 and used in Chapter 3. In that case, we recommend that you move Chapter 10, Class Definition and Use, forward. It could be studied anytime after Chapter 6. vii viii Preface New to the Sixth Edition Students will benefit from a variety of new content, including: ■ Graphics coverage implemented throughout the book. Many Computer Science faculty have recommended the use of graphics to help motivate the study of introductory programming and as a vehicle to help stu- dents understand how to use libraries and to call functions. We agree with this viewpoint and have included several optional sections with graphics examples in this edition. The new graphics sections include: Section 3.8: Introduction to Computer Graphics Section 5.10: Loops in Graphics Programs Section 7.6: Using Type charData to Control a Graphics Program Section 9.12: Graphics Programs with Arrays To reduce the overhead required to introduce graphics, we decided to use WinBGIm (Windows BGI with mouse), which is a package based on the Turbo Pascal BGI (Borland Graphics Interface) library. WinBGIm was created to run on top of the Win32 library by Michael Main and his students at the University of Colorado. Several development platforms appropriate for CS 1 courses have incorporated WinBGIm. Quincy (developed by Al Stevens) is an open-source student-oriented C++ IDE that includes WinBGIm as well as more advanced libraries (http:// www.codecutter.net/tools/quincy). Acommand-line platform based on the open-source GNU g++ compiler and the emacs program editor is distributed by the University of Colorado (http://www.codecutter. net/tools/winbgim). WinBGIm is also available for Bloodshed Soft- ware’s Dev-C++ and Microsoft’s Visual Studio C++. ■ New Chapter 0 is designed to elucidate the opportunities and struc- tures of the field of computing to introductory students. We hope this chapter encourages students to consider a major or minor in computing by illustrating a world in which they can envision themselves. ■ Reorganization of coverage of multidimensional arrays and arrays of structs. These topics were moved from Chapter 11 (Data Abstraction and Object-Oriented Design) to Chapter 9 (Arrays and Structs) to keep all coverage of arrays and structs in one chapter and to enable students to complete their study of procedural programming topics before learn- ing how to write classes. ■ New Section 7.6 on iterative approximations including a case study on finding roots of an equation. ■ New case study in Chapter 11(An Address Book for an email Provider) that uses the C++ vectorclass as its underlying data structure. ■ New end-of-section exercises and updated case studies. ■ New end-of-chapter quick-check and review exercises and new program- ming project assignments including graphics programming assignments. Preface ix Balancing Object-Oriented and Procedural Approaches Object-oriented concepts and classes are introduced early in the book, starting in Section 1.3. Sections 2.4 and 3.7 discuss the use of two system-defined classes, iostream and string, and we refer to the use of classes and objects throughout most of the text. An issue of concern to faculty is the relative order of arrays, structs, and classes. As in the last edition, we introduce arrays and structs first (Chapter 9) and then introduce the definition and coding of classes (Chapter 10). Some faculty may prefer to reverse the order, and this is entirely possible. The chap- ter on classes uses arrays only in the implementation of class simpleString, which can be omitted or deferred until after arrays are covered. We continue to emphasize the design of classes and data modeling in Chapter 11, which introduces template classes, an indexed-list class, the STL vector class, friend functions, and operator overloading. We also use template classes in Chapter 13, where we discuss dynamic data structures: lists, stacks, queues, and trees. We discuss the use of the STL container classes and iterators and also show students how to implement their own classes. An illustration of the C++ inheritance and virtual func- tion mechanisms is provided in Appendix E in the publisher’s Web site. We’ve done our best to follow a balanced path between the strictly objects-first and totally procedure-focused programming metaphors. We agree with the objects-first concept, but not at the expense of the funda- mentals of algorithm organization and design. Students in a first course can and should be taught the basic elements of procedural design. Our task is to do so within the context of an early focus on the importance of data modeling, reuse, and other fundamental principles of good software development. Software Engineering and Object-Oriented Concepts Many fundamental software engineering and object-oriented concepts are illustrated in the text: user-defined types, modeling problem-domain entities and their relationships, minimal interfaces, high-level cohesion, information hiding, separation of concerns, parameterized components, and inheritance. Abstraction is stressed from the start. Numerous complete case examples are provided throughout the text; these follow a standard software development method, from the specification and analysis of a problem to the first stage of design to the final coding.