Computer Science

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.

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

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