The following function heading in a c++ program is valid: int funcexp(int u, char v, float g)

C++ PROGRAMMING: PROGRAM DESIGN INCLUDING DATA STRUCTURES

FIFTH EDITION

D.S. MALIK

Australia � Brazil � Japan � Korea � Mexico � Singapore � Spain � United Kingdom � United States

This is an electronic version of the print textbook. Due to electronic rights restrictions, some third party content may be suppressed. Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. The publisher reserves the right to remove content from this title at any time if subsequent rights restrictions require it. For valuable information on pricing, previous editions, changes to current editions, and alternate formats, please visit www.cengage.com/highered to search by ISBN#, author, title, or keyword for materials in your areas of interest.

www.cengage.com/highered

C++ Programming: Program Design Including Data Structures, Fifth Edition D.S. Malik

Executive Editor: Marie Lee

Acquisitions Editor: Amy Jollymore

Senior Product Manager: Alyssa Pratt

Editorial Assistant: Zina Kresin

Content Project Manager: Matthew Hutchinson

Art Director: Faith Brosnan

Print Buyer: Julio Esperas

Proofreader: GreenPen QA

Indexer: Elizabeth Cunningham

Cover Designer: Roycroft Design/ www.roycroftdesign.com

Cover Photo: Contemporary Building ª Steve Hix/Somos Images/Corbis

Compositor: Integra

ª 2011 Course Technology, Cengage Learning

ALL RIGHTS RESERVED. No part of this work covered by the copyright herein may be reproduced, transmitted, stored or used in any form or by any means graphic, electronic, or mechanical, including but not limited to photocopying, recording, scanning, digitizing, taping, Web distribution, information networks, or information storage and retrieval systems, except as permitted under Section 107 or 108 of the 1976 United States Copyright Act, without the prior written permission of the publisher.

For product information and technology assistance, contact us at Cengage Learning Customer & Sales Support, 1-800-354-9706 For permission to use material from this text or product, submit

all requests online at www.cengage.com/permissions

Further permissions questions can be emailed to permissionrequest@cengage.com

Library of Congress Control Number: 2010921540

ISBN-13: 978-0-538-79809-2

ISBN-10: 0-538-79809-2

Course Technology 20 Channel Center Street Boston, MA 02210 USA

Some of the product names and company names used in this book have been used for identification purposes only and may be trademarks or registered trademarks of their respective manufacturers and sellers.

Any fictional data related to persons or companies or URLs used throughout this book is intended for instructional purposes only. At the time this book was printed, any such data was fictional and not belonging to any real persons or companies.

Course Technology, a part of Cengage Learning, reserves the right to revise this publication and make changes from time to time in its content without notice.

The programs in this book are for instructional purposes only. They have been tested with care, but are not guaranteed for any particular intent beyond educational purposes. The author and the publisher do not offer any warranties or representations, nor do they accept any liabilities with respect to the programs.

Cengage Learning is a leading provider of customized learning solutions with office locations around the globe, including Singapore, the United Kingdom, Australia, Mexico, Brazil and Japan. Locate your local office at: www.cengage.com/global

Cengage Learning products are represented in Canada by Nelson Education, Ltd.

To learn more about Course Technology, visit www.cengage.com/coursetechnology

Purchase any of our products at your local college store or at our preferred online store www.CengageBrain.com

TO

My Parents

Printed in the United States of America 1 2 3 4 5 6 7 16 15 14 13 12 11 10

www.cengage.com/permissions

www.roycroftdesign.com

www.cengage.com/global

www.cengage.com/coursetechnology

www.CengageBrain.com

PREFACE xxv

1. An Overview of Computers and Programming Languages 1

2. Basic Elements of C++ 27

3. Input/Output 117

4. Control Structures I (Selection) 175

5. Control Structures II (Repetition) 247

6. User-Defined Functions I 319

7. User-Defined Functions II 361

8. User-Defined Simple Data Types, Namespaces,

and the string Type 433

9. Arrays and Strings 485

10. Records (structs) 563

11. Classes and Data Abstraction 601

12. Inheritance and Composition 675

13. Pointers, Classes, Virtual Functions, Abstract Classes, and Lists 745

14. Overloading and Templates 827

15. Exception Handling 919

16. Recursion 959

17. Linked Lists 991

18. Stacks and Queues 1083

BRIEF CONTENTS

19. Searching and Sorting Algorithms 1183

20. Binary Trees 1265

21. Graphs 1321

22. Standard Template Library (STL) 1361

APPENDIX A Reserved Words 1477

APPENDIX B Operator Precedence 1479

APPENDIX C Character Sets 1481

APPENDIX D Operator Overloading 1485

APPENDIX E Additional C++ Topics 1487

APPENDIX F Header Files 1509

APPENDIX G Memory Size on a System and Random

Number Generator 1519

APPENDIX H References 1521

APPENDIX I Answers to Odd-Numbered Exercises 1523

INDEX 1555

iv | C++ Programming: Program Design Including Data Structures, Fifth Edition

TABLE OF CONTENTS

Preface xxv

AN OVERVIEW OF COMPUTERS AND PROGRAMMING

LANGUAGES 1

Introduction 2

A Brief Overview of the History of Computers 2

Elements of a Computer System 3

Hardware 4

Central Processing Unit and Main Memory 4

Input /Output Devices 5

Software 6

The Language of a Computer 6

The Evolution of Programming Languages 8

Processing a C++ Program 10

Programming with the Problem Analysis–Coding–Execution Cycle 12

Programming Methodologies 20

Structured Programming 20

Object-Oriented Programming 20

ANSI/ISO Standard C++ 22

Quick Review 22

Exercises 23

BASIC ELEMENTS OF C++ 27

A C++ Program 28

The Basics of a C++ Program 31

Comments 32

Special Symbols 32

1

2

Reserved Words (Keywords) 33

Identifiers 33

Whitespaces 34

Data Types 35

Simple Data Types 35

Floating-Point Data Types 38

Arithmetic Operators and Operator Precedence 39

Order of Precedence 43

Expressions 44

Mixed Expressions 45

Type Conversion (Casting) 47

string Type 49

Input 50

Allocating Memory with Constants and Variables 50

Putting Data into Variables 53

Assignment Statement 53

Saving and Using the Value of an Expression 56

Declaring and Initializing Variables 57

Input (Read) Statement 58

Variable Initialization 61

Increment and Decrement Operators 65

Output 67

Preprocessor Directives 75

namespace and Using cin and cout in a Program 76

Using the string Data Type in a Program 76

Creating a C++ Program 77

Debugging: Understanding and Fixing Syntax Errors 80

Program Style and Form 84

Syntax 84

Use of Blanks 85

Use of Semicolons, Brackets, and Commas 85

Semantics 85

Naming Identifiers 85

Prompt Lines 86

Documentation 87

Form and Style 87

More on Assignment Statements 89

Programming Example: Convert Length 91

vi | C++ Programming: Program Design Including Data Structures, Fifth Edition

Programming Example: Make Change 94

Quick Review 98

Exercises 100

Programming Exercises 109

INPUT/OUTPUT 117

I/O Streams and Standard I/O Devices 118

cin and the Extraction Operator >> 119

Using Predefined Functions in a Program 124

cin and the get Function 127

cin and the ignore Function 128

The putback and peek Functions 130

The Dot Notation between I/O Stream Variables

and I/O Functions: A Precaution 132

Input Failure 133

The clear Function 135

Output and Formatting Output 137

setprecision Manipulator 137

fixed Manipulator 138

showpoint Manipulator 139

setw 142

Additional Output Formatting Tools 144

setfill Manipulator 144

left and right Manipulators 146

Input/Output and the string Type 148

Debugging: Understanding Logic Errors

and Debugging with cout Statements 149

File Input/Output 152

Programming Example: Movie Tickets Sale and Donation to Charity 156

Programming Example: Student Grade 162

Quick Review 165

Exercises 166

Programming Exercises 170

CONTROL STRUCTURES I (SELECTION) 175

Control Structures 176

Relational Operators 177

Relational Operators and Simple Data Types 178

3

4

Table of Contents | vii

Comparing Characters 179

Relational Operators and the string Type 180

Logical (Boolean) Operators and Logical Expressions 182

Order of Precedence 184

int Data Type and Logical (Boolean) Expressions 187

bool Data Type and Logical (Boolean) Expressions 188

Selection: if and if...else 188

One-Way Selection 189

Two-Way Selection 191

Compound (Block of) Statements 195

Multiple Selections: Nested if 195

Comparing if...else Statements with a Series of if Statements 198

Short-Circuit Evaluation 199

Comparing Floating-Point Numbers for Equality: A Precaution 200

Associativity of Relational Operators: A Precaution 201

Avoiding Bugs by Avoiding Partially Understood

Concepts and Techniques 203

Input Failure and the if Statement 206

Confusion between the Equality Operator (==) and

the Assignment Operator (=) 209

Conditional Operator (?:) 211

Program Style and Form (Revisited): Indentation 211

Using Pseudocode to Develop, Test, and Debug a Program 212

switch Structures 215

Avoiding Bugs by Avoiding Partially Understood Concepts

and Techniques (Revisited) 221

Terminating a Program with the assert Function 223

Programming Example: Cable Company Billing 225

Quick Review 231

Exercises 232

Programming Exercises 241

CONTROL STRUCTURES II (REPETITION) 247

Why Is Repetition Needed? 248