DATA STRUCTURES - BU

1 DATA STRUCTURESUSING C++SECOND MALIKA ustralia Brazil Japan Korea Mexico Singapore Spain United Kingdom United StatesData STRUCTURES Using C++, Second MalikExecutive Editor:Marie LeeAcquisitions Editor:Amy JollymoreSenior Product Manager:Alyssa PrattEditorial Assistant:Zina KresinMarketing Manager:Bryant ChrzanContent Project Manager:Heather FurrowArt Director:Faith BrosnanImage credit: Fancy Photography/Veer(Royalty Free)Cover Designer:Roycroft DesignCompositor:IntegraPrinted in the United States of America123456715141312111009 2010 Course Technology, Cengage LearningALL RIGHTS RESERVED.

2 No part of this work covered by the copyrightherein may be reproduced, transmitted, stored or used in any form orby any means graphic, electronic, or mechanical, including but notlimited to photocopying, recording, scanning, digitizing, taping, Webdistribution, information networks, or information storage andretrieval systems, except as permitted under Section 107 or 108 of the1976 United States Copyright Act, without the prior writtenpermission of the product information and technology assistance, contact us atCengage Learning Customer & Sales Support, 1-800-354-9706 For permission to use material from this text or product, submitall requests online permissions questions can be emailed 978-0-324-78201-1 ISBN-10: 0-324-78201-2 Course Technology20 Channel Center StreetBoston, MA 02210 USAC engage Learning is a leading provider ofcustomized learning solutionswith office locations around the globe, including Singapore, the UnitedKingdom, Australia, Mexico, Brazil, and Japan.

3 Locate your local office Learning products are represented in Canada by NelsonEducation, your lifelong learning solutions, any of our products at your local college store or at ourpreferred online of the product names and company names used in this bookhave been used for identification purposes only and may betrademarks or registered trademarks of their respectivemanufacturers and fictional data related to persons or companies or URLs usedthroughout this book is intended for instructional purposes only. Atthe time this book was printed, any such data was fictional and notbelonging to any real persons or Technology, a part of Cengage Learning, reserves the rightto revise this publication and make changes from time to time in itscontent without programs in this book are for instructional purposes have been tested with care, but are not guaranteed for anyparticular intent beyond educational purposes.

4 The author and thepublisher do not offer any warranties or representations, nor do theyaccept any liabilities with respect to the ParentsThis page intentionally left blank Engineering Principles and C++ Design (OOD) and C++ and Array-Based template library (STL) and Hashing Trees and template library (STL) II731 APPENDIX A Reserved Words807 APPENDIX B Operator Precedence809 APPENDIX C Character Sets811 APPENDIX D Operator Overloading815 APPENDIX E Header Files817 BRIEFCONTENTSAPPENDIX F Additional C++ Topics825 APPENDIX G C++ for Java Programmers833 APPENDIX H References857 APPENDIX I Answers to Odd-NumberedExercises859 INDEX879vi | Data STRUCTURES Using C++.

5 Second EditionPrefacexxiiiSOFTWARE ENGINEERING PRINCIPLESAND C++ CLASSES1 Software Life Cycle2 Software Development Phase3 Analysis3 Design3 Implementation5 Testing and Debugging7 Algorithm Analysis: The Big-O Notation8 Classes17 Constructors21 Unified Modeling Language Diagrams22 Variable (Object) Declaration23 Accessing Class Members24 Implementation of Member Functions25 Reference Parameters and Class Objects (Variables)30 Assignment Operator and Classes31 Class Scope32 Functions and Classes32 Constructors and Default Parameters32 Destructors33 Structs331 TABLE OFCONTENTSData Abstraction, Classes, and Abstract Data Types33 Programming Example.

6 Fruit Juice Machine38 Identifying Classes, Objects, and Operations48 Quick Review49 Exercises51 Programming Exercises57 OBJECT-ORIENTED DESIGN (OOD) AND C++59 Inheritance60 Redefining (Overriding) Member Functions of the Base Class 63 Constructors of Derived and Base Classes69 Header File of a Derived Class75 Multiple Inclusions of a Header File76 Protected Members of a Class78 Inheritance aspublic,protected,orprivate78 Composition79 Polymorphism: Operator and Function Overloading84 Operator Overloading85 Why Operator Overloading Is Needed85 Operator Overloading86 Syntax for Operator Functions86 Overloading an Operator: Some Restrictions87 The Pointerthis87 Friend Functions of Classes91 Operator Functions as Member Functions and NonmemberFunctions94 Overloading Binary Operators95 Overloading the Stream Insertion (<<) and Extraction (>>)Operators98 Operator Overloading: Member Versus Nonmember102 Programming Example.

7 Complex Numbers103 Function Overloading1082viii | Data STRUCTURES Using C++, Second EditionTemplates108 Function Templates109 Class Templates111 Header File and Implementation File of a Class template 112 Quick Review113 Exercises115 Programming Exercises124 POINTERS AND ARRAY-BASED LISTS131 The Pointer Data Type and Pointer Variables132 Declaring Pointer Variables132 Address of Operator (&)133 Dereferencing Operator (*)133 Pointers and Classes137 Initializing Pointer Variables138 Dynamic Variables138 Operatornew138 Operatordelete139 Operations on Pointer Variables145 Dynamic Arrays147 Array Name: A Constant Pointer148 Functions and Pointers149 Pointers and Function Return Values150 Dynamic Two-Dimensional Arrays150 Shallow Vs.

8 Deep Copy and Pointers153 Classes and Pointers: Some Peculiarities155 Destructor155 Assignment Operator157 Copy Constructor159 Inheritance, Pointers, and Virtual Functions162 Classes and Virtual Destructors168 Abstract Classes and Pure Virtual Functions1693 Table of Contents | ixArray-Based Lists170 Copy Constructor180 Overloading the Assignment Operator180 Search181 Insert182 Remove183 Time Complexity of List Operations183 Programming Example: Polynomial Operations187 Quick Review194 Exercises197 Programming Exercises204 STANDARD template library (STL) I209 Components of the STL210 Container Types211 Sequence Containers211 Sequence Container:vector211 Declaring an Iterator to a Vector Container216 Containers and the Functionsbeginandend217 Member Functions Common to All Containers220 Member Functions Common to Sequence Containers222 ThecopyAlgorithm223ostreamIterator and Functioncopy225 Sequence Container.

9 Deque227 Iterators231 Types of Iterators232 Input Iterators232 Output Iterators232 Forward Iterators233 Bidirectional Iterators234 Random Access Iterators234 Stream Iterators237 Programming Example: Grade Report2384x | Data STRUCTURES Using C++, Second EditionQuick Review254 Exercises256 Programming Exercises259 LINKED LISTS265 Linked Lists266 Linked Lists: Some Properties267 Item Insertion and Deletion270 Building a Linked List274 Linked List as an ADT278 Structure of Linked List Nodes279 Member Variables of theclass linkedListType280 Linked List Iterators280 Default Constructor286 Destroy the List286 Initialize the List287 Print the List287 Length of a List287 Retrieve the Data of the First Node288 Retrieve the Data of the Last Node288 Begin and End288 Copy the List289 Destructor290 Copy Constructor290 Overloading the Assignment Operator291 Unordered Linked Lists292 Search the List293 Insert the First

10 Node294 Insert the Last Node294 Header File of the Unordered Linked List298 Ordered Linked Lists300 Search the List301 Insert a Node3025 Table of Contents | xiInsert First and Insert Last305 Delete a Node306 Header File of the Ordered Linked List307 Doubly Linked Lists310 Default Constructor313isEmptyList313 Destroy the List313 Initialize the List314 Length of the List314 Print the List314 Reverse Print the List315 Search the List315 First and Last Elements316 STL Sequence Container:list321 Linked Lists with Header and Trailer Nodes325 Circular Linked Lists326 Programming Example: Video Store327 Quick Review343 Exercises344 Programming Exercises348 RECURSION355 Recursive Definitions356 Direct and Indirect Recursion358 Infinite Recursion359 Problem Solving Using Recursion359 Largest Element in an Array360 Print a Linked List in Reverse Order363 Fibonacci Number366 Tower of Hanoi369 Converting a Number from Decimal to Binary372 Recursion or Iteration?