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