Object-Oriented Programming Using C++ 1 1.1 Abstract Data Types 1 1.2 Encapsulation 1 1.3 Inheritance 6 1.4 Pointers 9 1.4.1 Pointers and Arrays 12 1.4.2 Pointers and Copy Constructors 14 1.4.3 Pointers and Destructors 16 1.4.4 Pointers and Reference Variables 17 1.4.5 Poi
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 formatspleasevisitwww.cengage.com/higheredtosearchbyIsBn#,authortitlesorkeywordfor materials in your areas of interest Eai, copyright 2012 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s) torial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it. CENGAG Learning Data Structures and C 2013 Cengage Learning Algorithms in C++, Fourth edition ALL RIGHTS RESERVED. No part of this work covered by the copyright herein y Adam Drozdek may be reproduced, transmitted, stored or used in any form or by any means graphic, electronic, or mechanical, including but not limited to photocopying, Executive Editor: marie lee recording, scanning, digitizing, taping, Web distribution, information networks, Senior Product manager or information storage and retrieval systems, except as permitted under Section 107 or 108 of the 1976 United States Copyright Act, without the prior Alyssa Pratt written permission of the publisher. Associate Product manager Stephanie Lorenz For product information and technology assistance contact us at Content Project manager CengageLearningCustomer&SalesSupport,www.cengage.com/support Matthew hutchinson For permission to use material from this text or product, submit all Art Director: Cheryl Pearl requestsonlineatwww.cengage.com/permissions Print Buyer: Julio Esperas Further permissions questions can be emailed to permissionrequest@cengage.com Compositor: PreMedia Global Proofreader: Andrea schein Library of Congress Control Number: 2012942244 Indexer: Sharon Hilgenberg SBN-13:978-1-133-60842-4 SBN-10:1133-60842-6 Cengage Learning 20 Channel center street Boston, MA 02210 USA 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 TolearnmoreaboutCengageLearningvisitwww.cengage.com Purchase any of our products at your local college store or at our preferred onlinestorewww.cengagebrain.com 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 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 repre- sentations, nor do they accept any liabilities with respect to the programs Printed in the United States of america 123456718171615141312 Eai, copyright 2012 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s) torial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it. TO MY DAUGHTERS, JUSTYNA AND KASIA Eai, copyright 2012 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s) torial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it. Eai, copyright 2012 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s) torial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it. Contents 1 OBJECT-ORIENTED PROGRAMMING USING C++ 1.1 Abstract Data Types 1 1.2 Encapsulation 1 1. 3 Inheritance 6 1. 4 pointers 9 1.4.1 Pointers and Arrays 12 1.4.2 Pointers and Copy Constructors 14 1.4.3 Pointers and destructors 16 1.4.4 Pointers and reference variables 17 1.4.5 Pointers to functions 20 1.5 Polymorphism 21 1.6 C++ and Object-Oriented Programming 23 1.7 The Standard Template Library 24 1.7.1 Containers 24 1.7.2 Iterators 25 1.7.3 Algorithms 25 1.7.4 Function Objects 26 8 Vectors in the Standard Template Library 28 1.9 Data Structures and Object-Oriented Programming 35 1.10 Case Study: Random Access File 35 1. 1 1 Exercises 46 1.12 Programming Assignments 48 Bibliography 50 Eai, copyright 2012 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s) torial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it. Contents 2 COMPLEXITY ANALYSIS 51 2.1 Computational and Asymptotic Complexity 51 2.2 Big-O Notation 52 2.3 Properties of Big-O Notation 54 2.4 Q and o Notations 56 2.5 Possible problems 57 2.6 Examples of complexities 57 2.7 Finding asymptotic Complexity: Examples 59 2. 8 The Best, Average, and worst Cases 61 2.9 Amortized Complexity 64 2.10 NP-Completeness 68 2.11 Exercises 71 Bibliography 74 3 LINKED LISTS 3. 1 Singly Linked Lists 75 3.1.1 Insertion 81 3. 1.2 Deletion 83 3. 1.3 Search 89 3.2 Doubly Linked Lists 90 3.3 Circular lists 94 3.4 Skip Lists 96 3.5 Self-Organizing Lists 101 3.6 Sparse Tables 106 3.7 Lists in the Standard Template library 109 3.8 Concluding Remarks 113 3. 9 Case Study: A Library 114 3. 10 Exercises 125 3.11 Programming Assignments 127 Bibliography 130 Eai, copyright 2012 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s) torial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it. Contents■i 4 STACKS AND QUEUES 131 4.1 Stacks 131 4.2 Queues 139 4.3 Priority Queues 148 4.4 Stacks in the Standard Template library 149 4.5 Queues in the Standard Template Library 149 4.6 Priority Queues in the Standard Template Library 151 4.7 Deques in the Standard Template Library 153 4.8 Case Study: Exiting a Maze 158 4.9 Exercises 165 4.10 Programming Assignments 166 Bibliography 168 5 RECURSION 169 5.1 Recursive Definitions 169 5.2 Function Calls and recursion implementation 172 5.3 Anatomy of a recursive call 174 5.4 Tail recursion 177 5.5 Nontail Recursion 178 5.6 Indirect recursion 184 5.7 Nested Recursion 186 5.8 Excessive recursion 186 5.9 Backtracking 190 5.10 Concluding Remarks 197 5.11 Case Study: A Recursive Descent Interpreter 198 5.12 Exercises 207 5.13 Programming Assignments 210 Bibliography 213 6 BINARY TREES 214 6.1 Trees, Binary Trees, and Binary Search Trees 214 6.2 Implementing Binary Trees 219 6.3 Searching a Binary Search Tree 222 Eai, copyright 2012 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s) torial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it. Contents 6.4 Tree Traversal 224 6.4.1 Breadth-First Traversal 225 6.4.2 Depth-First Traversal 226 6.4.3 Stackless Depth-First Traversal 233 6.5 Insertion 240 6.6 Deletion 243 6.6.1 Deletion by Merging 244 6.6.2 Deletion by Copying 246 6.7 Balancing a Tree 250 6.7.1 The dsw algorithm 253 6.7. 2 AVL Trees 256 6.8 Self-Adjusting Trees 261 6.8.1 Self-Restructuring Trees 262 6.8.2 Splaying 263 6.9 Heaps 268 6.9.1 Heaps as Priority Queues 270 6.9.2 Organizing Arrays as Heaps 271 6.10 Treaps 276 6.11 K-d trees 280 6. 12 Polish Notation and Expression Trees 286 6. 12. 1 Operations on Expression Trees 287 6.13 Case Study: Computing Word Frequencies 290 6.14 Exercises 298 6.15 Programming Assignments 302 Bibliography 306 7 MULTIWAY TREES 309 7.1 The Family of B-Trees 310 7.1.1B- Trees311 7.1.2 B-Trees 321 7.1.3B+- Trees323 7. 1.4 Prefix B+-Trees 326 7. 1.5 K-d B-trees 327 7. 1. 6 Bit-Trees 334 7.1.7R- Trees336 7.1.82-4 Trees337 7. 1.9 Sets and Multisets in the Standard Template Library 353 7.1.10 Maps and Multimaps in the Standard Template Library 359 Eai, copyright 2012 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s) torial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.