Luckymet

<ul><li><p>SCHAUMS OUTLINE OF</p><p>THEORY AND PROBLEMS</p><p>of</p><p>PROGRAMMING</p><p>WITH C++</p><p>Second Edition</p><p>JOHN R. HUBBARD, Ph.D.</p><p>Professor of Mathematics and Computer ScienceUniversity of Richmond</p><p>SCHAUMS OUTLINE SERIES</p><p>McGRAW-HILL</p><p>New York San Francisco Washington, D.C. Auckland Bogota CaracasLisbon London Madrid Mexico City Milan Montreal</p><p>New Delhi San Juan Singapore Sydney Tokyo Toronto</p></li><li><p>Copyright 2000, 1996 by the McGraw-Hill Companies. All rights reserved. Manufactured in the United States of America. Except as permittedunder the United States Copyright Act of 1976, no part of this publication may be reproduced or distributed in any form or by any means, or stored ina database or retrieval system, without the prior written permission of the publisher. </p><p> 0-07-136811-6</p><p>The material in this eBook also appears in the print version of this title: ISBN 0-07-135346-1. </p><p>All trademarks are trademarks of their respective owners. Rather than put a trademark symbol after every occurrence of a trademarked name, weuse names in an editorial fashion only, and to the benefit of the trademark owner, with no intention of infringement of the trademark. Where suchdesignations appear in this book, they have been printed with initial caps. </p><p>McGraw-Hill eBooks are available at special quantity discounts to use as premiums and sales promotions, or for use in corporate training pro-grams. For more information, please contact George Hoare, Special Sales, at george_hoare@mcgraw-hill.com or (212) 904-4069. </p><p>TERMS OF USEThis is a copyrighted work and The McGraw-Hill Companies, Inc. (McGraw-Hill) and its licensors reserve all rights in and to t he work. Use ofthis work is subject to these terms. Except as permitted under the Copyright Act of 1976 and the right to store and retrieve one copy of the work,you may not decompile, disassemble, reverse engineer, reproduce, modify, create derivative works based upon, transmit, distribute, disseminate,sell, publish or sublicense the work or any part of it without McGraw-Hill s prior consent. You may use the work for your own noncommercialand personal use; any other use of the work is strictly prohibited. Your right to use the work may be terminated if you fail to comply with theseterms. </p><p>THE WORK IS PROVIDED AS IS. McGRA W-HILL AND ITS LICENSORS MAKE NO GUARANTEES OR WARRANTIES AS TO THEACCURACY, ADEQUACY OR COMPLETENESS OF OR RESULTS TO BE OBTAINED FROM USING THE WORK, INCLUDING ANYINFORMATION THAT CAN BE ACCESSED THROUGH THE WORK VIA HYPERLINK OR OTHERWISE, AND EXPRESSLY DISCLAIMANY WARRANTY, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO IMPLIED WARRANTIES OF MERCHANTABILITY ORFITNESS FOR A PARTICULAR PURPOSE. McGraw-Hill and its licensors do not warrant or guarantee that the functions contained in the workwill meet your requirements or that its operation will be uninterrupted or error free. Neither McGraw-Hill nor its licensors shall be liable to youor anyone else for any inaccuracy, error or omission, regardless of cause, in the work or for any damages resulting therefrom. McGraw-Hill hasno responsibility for the content of any information accessed through the work. Under no circumstances shall McGraw-Hill and/or its licensors beliable for any indirect, incidental, special, punitive, consequential or similar damages that result from the use of or inability to use the work, evenif any of them has been advised of the possibility of such damages. This limitation of liability shall apply to any claim or cause whatsoever whethersuch claim or cause arises in contract, tort or otherwise.</p><p> abcMcGraw-Hill </p><p>DOI: 10.1036/0071368116</p></li><li><p>iii</p><p>Preface</p><p>Like all Schaums Outline Series books, this volume is intended to be used primarily for selfstudy, preferably in conjunction with a regular course in C++ programming language orcomputer science. However, it is also well-suited for use in independent study or as a reference.</p><p>The book includes over 200 examples and solved problems. The author firmly believes thatthe principles of data structures can be learned from a well-constructed collection of exampleswith complete explanations. This book is designed to provide that support.</p><p>C++ was created by Bjarne Stroustrup in the early 1980s. Based upon C and Simula, it isnow one of the most popular languages for object-oriented programming. The language wasstandardized in 1998 by the American National Standards Institute (ANSI) and the InternationalStandards Organization (ISO). This new ANSI/ISO Standard includes the powerful StandardTemplate Library (STL). This book conforms to these standards.</p><p>Although most people who undertake to learn C++ have already had some previousprogramming experience, this book assumes none. It approaches C++ as ones first programminglanguage. Therefore, those who have had previous experience may need only skim the first fewchapters.</p><p>C++ is a difficult language for at least two reasons. It inherits from the C language aneconomy of expression that novices often find cryptic. And as an object-oriented language, itswidespread use of classes and templates presents a formidable challenge to those who have notthought in those terms before. It is the intent of this book to provide the assistance necessary forfirst-time programmers to overcome these obstacles.</p><p>Source code for all the examples and problems in this book, including the SupplementaryProblems, may be downloaded from these websites http://projectEuclid.net/schaums ,http://www.richmond.edu/~hubbard/schaums, http://hubbards.org/schaums, orhttp://jhubbard.net/schaums. Any corrections or addenda for the book will also beavailable at these sites.</p><p>I wish to thank all my friends, colleagues, students, and the McGraw-Hill staff who havehelped me with the critical review of this manuscript, including John Aliano, Arthur Biderman,Francis Minhthang Bui, Al Dawson, Peter Dailey, Mohammed El-Beltagy, Gary Galvez, LibbieGeiger, Sergei Gorlatch, Chris Hanes, John B. Hubbard, Raana Jeelani, Dick Palas, Blake Puhak,Arni Sigurjonsson, Andrew Somers, Joe Troncale, Maureen Walker, Stefan Wentzig, and NatWithers. Their editorial advice and debugging skills are gratefully appreciated.</p><p>Special thanks to my wife and colleague, Anita H. Hubbard, for her advice, encouragement,and creative ideas for this book. Many of the original problems used here are hers.</p><p>JOHN R. HUBBARDRichmond, Virginia</p><p>Copyright 2000 The McGraw-Hill Companies, Inc. Click Here for Terms of Use.</p></li><li><p>This page intentionally left blank.</p></li><li><p>v</p><p>Contents</p><p>Chapter 1 Elementary C++ Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1</p><p>1.1 GETTING STARTED . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1</p><p>1.2 SOME SIMPLE PROGRAMS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2</p><p>1.3 THE OUTPUT OPERATOR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4</p><p>1.4 CHARACTERS AND LITERALS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4</p><p>1.5 VARIABLES AND THEIR DECLARATIONS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5</p><p>1.6 PROGRAM TOKENS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6</p><p>1.7 INITIALIZING VARIABLES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7</p><p>1.8 OBJECTS, VARIABLES, AND CONSTANTS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7</p><p>1.9 THE INPUT OPERATOR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8</p><p>Chapter 2 Fundamental Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16</p><p>2.1 NUMERIC DATA TYPES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16</p><p>2.2 THE BOOLEAN TYPE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17</p><p>2.3 ENUMERATION TYPES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17</p><p>2.4 CHARACTER TYPES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19</p><p>2.5 INTEGER TYPES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19</p><p>2.6 ARITHMETIC OPERATORS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21</p><p>2.7 THE INCREMENT AND DECREMENT OPERATORS . . . . . . . . . . . . . . . . . . . . . 21</p><p>2.8 COMPOSITE ASSIGNMENT OPERATORS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22</p><p>2.9 FLOATING-POINT TYPES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23</p><p>2.10 TYPE CONVERSIONS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25</p><p>2.11 NUMERIC OVERFLOW . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26</p><p>2.12 ROUND-OFF ERROR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28</p><p>2.13 THE E-FORMAT FOR FLOATING-POINT VALUES . . . . . . . . . . . . . . . . . . . . . . 30</p><p>2.14 SCOPE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31</p><p>Chapter 3 Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36</p><p>3.1 THE if STATEMENT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36</p><p>3.2 THE if.else STATEMENT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36</p><p>3.3 KEYWORDS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37</p><p>3.4 COMPARISON OPERATORS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38</p><p>3.5 STATEMENT BLOCKS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39</p><p>3.6 COMPOUND CONDITIONS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41</p><p>3.7 SHORT-CIRCUITING . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42</p><p>3.8 BOOLEAN EXPRESSIONS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42</p><p>3.9 NESTED SELECTION STATEMENTS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43</p><p>3.10 THE else if CONSTRUCT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46</p><p>3.11 THE switch STATEMENT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47</p><p>3.12 THE CONDITIONAL EXPRESSION OPERATOR . . . . . . . . . . . . . . . . . . . . . . . . . 49</p><p>Copyright 2000 The McGraw-Hill Companies, Inc. Click Here for Terms of Use.</p></li><li><p>vi CONTENTS</p><p>Chapter 4 Iteration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60</p><p>4.1 THE while STATEMENT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60</p><p>4.2 TERMINATING A LOOP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62</p><p>4.3 THE do.while STATEMENT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64</p><p>4.4 THE for STATEMENT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65</p><p>4.5 THE break STATEMENT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71</p><p>4.6 THE continue STATEMENT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73</p><p>4.7 THE goto STATEMENT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74</p><p>4.8 GENERATING PSEUDO-RANDOM NUMBERS . . . . . . . . . . . . . . . . . . . . . . . . . 75</p><p>Chapter 5 Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87</p><p>5.1 INTRODUCTION . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87</p><p>5.2 STANDARD C++ LIBRARY FUNCTIONS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87</p><p>5.3 USER-DEFINED FUNCTIONS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90</p><p>5.4 TEST DRIVERS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90</p><p>5.5 FUNCTION DECLARATIONS AND DEFINITIONS . . . . . . . . . . . . . . . . . . . . . . . 92</p><p>5.6 LOCAL VARIABLES AND FUNCTIONS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95</p><p>5.7 void FUNCTIONS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96</p><p>5.8 BOOLEAN FUNCTIONS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98</p><p>5.9 I/O FUNCTIONS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101</p><p>5.10 PASSING BY REFERENCE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102</p><p>5.11 PASSING BY CONSTANT REFERENCE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106</p><p>5.12 INLINE FUNCTIONS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107</p><p>5.13 SCOPE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108</p><p>5.14 OVERLOADING . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109</p><p>5.15 THE main() FUNCTION . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109</p><p>5.16 DEFAULT ARGUMENTS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111</p><p>Chapter 6 Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126</p><p>6.1 INTRODUCTION . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126</p><p>6.2 PROCESSING ARRAYS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126</p><p>6.3 INITIALIZING AN ARRAY . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127</p><p>6.4 ARRAY INDEX OUT OF BOUNDS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129</p><p>6.5 PASSING AN ARRAY TO A FUNCTION . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131</p><p>6.6 THE LINEAR SEARCH ALGORITHM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133</p><p>6.7 THE BUBBLE SORT ALGORITHM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134</p><p>6.8 THE BINARY SEARCH ALGORITHM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134</p><p>6.9 USING ARRAYS WITH ENUMERATION TYPES . . . . . . . . . . . . . . . . . . . . . . . 137</p><p>6.10 TYPE DEFINITIONS . . . . . . . . . . . . . . . . . ..</p></li></ul>