Data Structures and Algorithms in C++ (Adam Drozdek) (z-library.sk, 1lib.sk, z-lib.sk)

📄 File Format: PDF

💾 File Size: 21.4 MB

📖 Read Online ⬇️ Download

Registered users can read the full content for free

Register as a Gaohf Library member to read the complete e-book online for free and enjoy a better reading experience.

📄 Page 1

C8160_fm_ptg01.indd 4 20/07/12 11:59 AM

📄 Page 2

Data Structures and Algorithms in C++ Fourth Edition Adam Drozdek Australia • Brazil • Japan • Korea • Mexico • Singapore • Spain • United Kingdom • United States C8160_fm_ptg01.indd 1 20/07/12 11:59 AM 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). Editorial 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.

📄 Page 3

C8160_fm_ptg01.indd 4 20/07/12 11:59 AM 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. 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). Editorial 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.

📄 Page 4

© 2013 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. Library of Congress Control Number: 2012942244 ISBN-13: 978-1-133-60842-4 ISBN-10: 1-133-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. To learn more about Cengage Learning, visit www.cengage.com Purchase any of our products at your local college store or at our preferred online store www.cengagebrain.com Data Structures and Algorithms in C++, Fourth Edition by Adam Drozdek Executive Editor: Marie Lee Senior Product Manager: Alyssa Pratt Associate Product Manager: Stephanie Lorenz Content Project Manager: Matthew Hutchinson Art Director: Cheryl Pearl Print Buyer: Julio Esperas Compositor: PreMediaGlobal Proofreader: Andrea Schein Indexer: Sharon Hilgenberg For product information and technology assistance, contact us at Cengage Learning Customer & Sales Support, www.cengage.com/support 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 Printed in the United States of America 1 2 3 4 5 6 7 18 17 16 15 14 13 12 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. C8160_fm_ptg01.indd 2 20/07/12 11:59 AM 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). Editorial 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.

📄 Page 5

To my daughters, Justyna and Kasia C8160_fm_ptg01.indd 3 20/07/12 11:59 AM 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). Editorial 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.

📄 Page 6

C8160_fm_ptg01.indd 4 20/07/12 11:59 AM 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). Editorial 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.

📄 Page 7

Contents 1  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 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 1.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.11 Exercises 46 1.12 Programming Assignments 48 Bibliography 50 C8160_fm_ptg01.indd 5 20/07/12 11:59 AM 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). Editorial 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.

📄 Page 8

vi    ■    C o n t e n t s 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 Ω and Θ 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 75 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 C8160_fm_ptg01.indd 6 20/07/12 11:59 AM 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). Editorial 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.

📄 Page 9

  C o n t e n t s     ■    vii 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 C8160_fm_ptg01.indd 7 20/07/12 11:59 AM 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). Editorial 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.

📄 Page 10

viii    ■    C o n t e n t s 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.1 B-Trees   311 7.1.2 B*-Trees   321 7.1.3 B+-Trees   323 7.1.4 Prefix B+-Trees   326 7.1.5 K-d B-trees   327 7.1.6 Bit-Trees   334 7.1.7 R-Trees   336 7.1.8 2–4 Trees   337 7.1.9 Sets and Multisets in the Standard Template Library   353 7.1.10 Maps and Multimaps in the Standard Template Library   359 C8160_fm_ptg01.indd 8 20/07/12 11:59 AM 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). Editorial 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.

📄 Page 11

  C o n t e n t s     ■    ix 7.2 Tries   364 7.3 Concluding Remarks   373 7.4 Case Study: Spell Checker   373 7.5 Exercises 384 7.6 Programming Assignments 385 Bibliography 389 8  Graphs 391 8.1 Graph Representation   393 8.2 Graph Traversals   395 8.3 Shortest Paths   398 8.3.1 All-to-All Shortest Path Problem   405 8.4 Cycle Detection   408 8.4.1 Union-Find Problem   409 8.5 Spanning Trees   411 8.6 Connectivity   415 8.6.1 Connectivity in Undirected Graphs   415 8.6.2 Connectivity in Directed Graphs   418 8.7 Topological Sort   421 8.8 Networks   423 8.8.1 Maximum Flows   423 8.8.2 Maximum Flows of Minimum Cost   433 8.9 Matching   438 8.9.1 Stable Matching Problem   442 8.9.2 Assignment Problem   445 8.9.3 Matching in Nonbipartite Graphs   447 8.10 Eulerian and Hamiltonian Graphs   449 8.10.1 Eulerian Graphs   449 8.10.2 Hamiltonian Graphs   453 8.11 Graph Coloring   459 8.12 NP-Complete Problems in Graph Theory   462 8.12.1 The Clique Problem   462 8.12.2 The 3-Colorability Problem   463 8.12.3 The Vertex Cover Problem   465 8.12.4 The Hamiltonian Cycle Problem   466 8.13 Case Study: Distinct Representatives   467 C8160_fm_ptg01.indd 9 20/07/12 11:59 AM 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). Editorial 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.

📄 Page 12

x    ■    C o n t e n t s 8.14 Exercises 480 8.15 Programming Assignments 486 Bibliography 487 9  Sorting 491 9.1 Elementary Sorting Algorithms   492 9.1.1 Insertion Sort   492 9.1.2 Selection Sort   495 9.1.3 Bubble Sort   497 9.1.4 Comb Sort   500 9.2 Decision Trees   501 9.3 Efficient Sorting Algorithms   505 9.3.1 Shell Sort   505 9.3.2 Heap Sort   508 9.3.3 Quicksort   512 9.3.4 Mergesort   518 9.3.5 Radix Sort   521 9.3.6 Counting Sort   527 9.4 Sorting in the Standard Template Library   528 9.5 Concluding Remarks   532 9.6 Case Study: Adding Polynomials   534 9.7 Exercises 542 9.8 Programming Assignments 543 Bibliography 545 10  Hashing 548 10.1 Hash Functions   549 10.1.1 Division   549 10.1.2 Folding   549 10.1.3 Mid-Square Function   550 10.1.4 Extraction   550 10.1.5 Radix Transformation   551 10.1.6 Universal Hash Functions   551 10.2 Collision Resolution   551 10.2.1 Open Addressing   552 10.2.2 Chaining   558 10.2.3 Bucket Addressing   560 10.3 Deletion   561 C8160_fm_ptg01.indd 10 20/07/12 11:59 AM 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). Editorial 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.

📄 Page 13

  C o n t e n t s     ■    xi 10.4 Perfect Hash Functions   562 10.4.1 Cichelli’s Method   563 10.4.2 The FHCD Algorithm   566 10.5 Rehashing   568 10.5.1 The Cuckoo Hashing   568 10.6 Hash Functions for Extendible Files   571 10.6.1 Extendible Hashing   571 10.6.2 Linear Hashing   574 10.7 Case Study: Hashing with Buckets   576 10.8 Exercises 586 10.9 Programming Assignments 587 Bibliography 588 11  Data Compression 590 11.1 Conditions for Data Compression   590 11.2 Huffman Coding   592 11.2.1  Adaptive Huffman Coding   601 11.3 Run-Length Encoding   606 11.4 Ziv-Lempel Code   607 11.5 Case Study: Huffman Method with Run-Length Encoding   610 11.6 Exercises 622 11.7 Programming Assignments 622 Bibliography 624 12  Memory Management 625 12.1 The Sequential-Fit Methods   626 12.2 The Nonsequential-Fit Methods   627 12.2.1 Buddy Systems   629 12.3 Garbage Collection   636 12.3.1 Mark-and-Sweep   637 12.3.2 Copying Methods   644 12.3.3 Incremental Garbage Collection   646 12.3.4 Generational Garbage Collection   653 12.4 Concluding Remarks   657 12.5 Case Study: An In-Place Garbage Collector   658 C8160_fm_ptg01.indd 11 20/07/12 11:59 AM 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). Editorial 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.

📄 Page 14

xii    ■    C o n t e n t s 12.6 Exercises 667 12.7 Programming Assignments 668 Bibliography 671 13  String Matching 674 13.1 Exact String Matching   674 13.1.1  Straightforward Algorithms   674 13.1.2  The Knuth-Morris-Pratt Algorithm   677 13.1.3  The Boyer-Moore Algorithm   685 13.1.4  Multiple Searches   695 13.1.5  Bit-Oriented Approach   697 13.1.6  Matching Sets of Words   700 13.1.7  Regular Expression Matching   707 13.1.8  Suffix Tries and Trees   711 13.1.9  Suffix Arrays   717 13.2 Approximate String Matching   719 13.2.1  String Similarity   720 13.2.2  String Matching with k Errors   726 13.3 Case Study: Longest Common Substring   729 13.4 Exercises 738 13.5 Programming Assignments 740 Bibliography 741 Appendixes A Computing Big-O   743 A.1  Harmonic Series   743 A.2  Approximation of the Function lg(n!)   743 A.3  Big-O for Average Case of Quicksort   745 A.4   Average Path Length in a Random Binary Tree   747 A.5   The Number of Nodes in an AVL Tree   748 B Algorithms in the Standard Template Library   749 B.1  Standard Algorithms   749 C NP-Completeness   758 C.1  Cook’s Theorem   758 Index    771 C8160_fm_ptg01.indd 12 20/07/12 11:59 AM 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). Editorial 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.

📄 Page 15

The study of data structures, a fundamental component of a computer science edu- cation, serves as the foundation upon which many other computer science fields are built. Some knowledge of data structures is a must for students who wish to do work in design, implementation, testing, or maintenance of virtually any software system. The scope and presentation of material in Data Structures and Algorithms in C++ provide students with the necessary knowledge to perform such work. This book highlights three important aspects of data structures. First, a very strong emphasis is placed on the connection between data structures and their al- gorithms, including analyzing algorithms’ complexity. Second, data structures are presented in an object-oriented setting in accordance with the current design and implementation paradigm. In particular, the information-hiding principle to ad- vance encapsulation and decomposition is stressed. Finally, an important compo- nent of the book is data structure implementation, which leads to the choice of C++ as the programming language. The C++ language, an object-oriented descendant of C, is widespread in indus- try and academia as an excellent programming language. It is also useful and natural for introducing data structures. Therefore, because of the wide use of C++ in applica- tion programming and the object-oriented characteristics of the language, using C++ to teach a data structures and algorithms course, even on the introductory level, is well justified. This book provides the material for an introductory data structures course, as well as for an advanced data structures and algorithms course. It also meets the requirements for the following units specified in the Computer Science Curriculum 2008: DS/GraphsAndTrees, PF/DataStructures, PF/Recursion, PF/ObjectOriented, AL/BasicAnalysis, AL/AlgorithmicStrategies, AL/FundamentalAlgorithms, AL/ PversusNP, PL/DeclarationsAndTypes, PL/AbstractionMechanisms, PL/ ObjectOrientedProgramming. Most chapters include a case study that illustrates a complete context in which certain algorithms and data structures can be used. These case studies were chosen from different areas of computer science such as interpreters, symbolic computation, and file processing, to indicate the wide range of applications to which topics under discussion may apply. Preface xiii C8160_fm_ptg01.indd 13 20/07/12 11:59 AM 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). Editorial 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.

📄 Page 16

xiv    ■    P r e f a c e Brief examples of C++ code are included throughout the book to illustrate the practical importance of data structures. However, theoretical analysis is equally im- portant, so presentations of algorithms are integrated with analyses of efficiency. Great care is taken in the presentation of recursion because even advanced stu- dents have problems with it. Experience has shown that recursion can be explained best if the run-time stack is taken into consideration. Changes to the stack are shown when tracing a recursive function not only in the chapter on recursion, but also in other chapters. For example, a surprisingly short function for tree traversal may re- main a mystery if work done by the system on the run-time stack is not included in the explanation. Standing aloof from the system and retaining only a purely theoreti- cal perspective when discussing data structures and algorithms are not necessarily helpful. The thrust of this book is data structures, and other topics are treated here only as much as necessary to ensure a proper understanding of this subject. Algo- rithms are discussed from the perspective of data structures, so the reader will not find a comprehensive discussion of different kinds of algorithms and all the facets that a full presentation of algorithms requires. However, as mentioned, recursion is covered in depth. In addition, complexity analysis of algorithms is presented in some detail. Chapters 1 and 3–8 present a number of different data structures and the algo- rithms that operate on them. The efficiency of each algorithm is analyzed, and im- provements to the algorithm are suggested. ■ Chapter 1 presents the basic principles of object-oriented programming, an intro- duction to dynamic memory allocation and the use of pointers, and a rudimentary presentation of the Standard Template Library (STL). ■ Chapter 2 describes some methods used to assess the efficiency of algorithms. ■ Chapter 3 presents different types of linked lists with an emphasis on their imple- mentation with pointers. ■ Chapter 4 presents stacks and queues and their applications. ■ Chapter 5 contains a detailed discussion of recursion. Different types of recursion are discussed, and a recursive call is dissected. ■ Chapter 6 discusses binary trees, including implementation, traversal, and search. Balanced trees are also included in this chapter. ■ Chapter 7 details more generalized trees such as tries, 2– 4 trees, and B-trees. ■ Chapter 8 presents graphs. Chapters 9–13 show different applications of data structures introduced in the previous chapters. They emphasize the data structure aspects of each topic under consideration. ■ Chapter 9 analyzes sorting in detail, and several elementary and nonelementary methods are presented. ■ Chapter 10 discusses hashing, one of the most important areas in searching. Various techniques are presented with an emphasis on the utilization of data structures. ■ Chapter 11 discusses data compression algorithms and data structures. C8160_fm_ptg01.indd 14 20/07/12 11:59 AM 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). Editorial 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.

📄 Page 17

  P r e f a c e     ■    xv ■ Chapter 12 presents various techniques and data structures for memory management. ■ Chapter 13 discusses many algorithms for exact and approximate string matching. ■ Appendix A discusses in greater detail big-O notation, introduced in Chapter 2. ■ Appendix B presents standard algorithms in the Standard Template Library. ■ Appendix C gives a proof of Cook’s theorem and illustrates it with an extended example. Each chapter contains a discussion of the material illustrated with appropriate diagrams and tables. Except for Chapter 2, all chapters include a case study, which is an extended example using the features discussed in that chapter. All case stud- ies have been tested using the Visual C++ compiler on a PC and the g++ compiler under Unix except the von Koch snowflake, which runs on a PC under Visual C++. At the end of each chapter is a set of exercises of varying degrees of difficulty. Except for Chapter 2, all chapters also include programming assignments and an up-to-date bibliography of relevant literature. Chapters 1–6 (excluding Sections 2.9-10, 3.4, 6.4.3, 6.7-8, and 6.10-11) contain the core material that forms the basis of any data structures course. These chapters should be studied in sequence. The remaining six chapters can be read in any or- der. A one- semester course could include Chapters 1– 6, 9, and Sections 10.1 and 10.2. The entire book could also be part of a two-semester sequence. Teaching Tools The following instructor support materials are available when this book is used in a classroom setting. All instructor teaching tools are available for download at login.cengage.com. Electronic Solution’s Manual. The Solution’s Manual that accompanies this textbook includes complete solutions to all text exercises. Electronic Figure Files. All images from the text are available for use in classroom presentations. PowerPoint Presentations. PowerPoint slides accompany each chapter. Slides may be used to guide classroom presentation, to make available for students for chapter review, or to print as classroom handouts. Instructors are encouraged to customize the slides to suit their course needs. Student Resources Source Code. The source code for the text example programs is available for down- load at cengagebrain.com and via the author’s Web site at http://www.mathcs.duq. edu/drozdek/DSinCpp. C8160_fm_ptg01.indd 15 20/07/12 11:59 AM 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). Editorial 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.

📄 Page 18

xvi    ■    P r e f a c e Changes in the Fourth Edition The new edition primarily extends the old edition by including material on new topics that are currently not covered. The additions include ■ A section on treaps (6.10) and a section on k-d trees (6.11) ■ A section on k-d B-trees (7.1.5) ■ A discussion of two additional sorting methods (Sections 9.1.3.1, 9.3.6) ■ A new hashing technique (Section 10.5.1) ■ A section on generational garbage collection (12.3.4) There are also many small modifications and additions throughout the book. C8160_fm_ptg01.indd 16 20/07/12 11:59 AM 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). Editorial 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.

📄 Page 19

1 1.1 Abstract Data Types Before a program is written, we should have a fairly good idea of how to accom- plish the task being implemented by this program. Hence, an outline of the program containing its requirements should precede the coding process. The larger and more complex the project, the more detailed the outline phase should be. The implemen- tation details should be delayed to the later stages of the project. In particular, the details of the particular data structures to be used in the implementation should not be specified at the beginning. From the start, it is important to specify each task in terms of input and output. At the beginning stages, we should be more concerned with what the program should do, not how it should or could be done. Behavior of the program is more important than the gears of the mechanism accomplishing it. For example, if an item is needed to accomplish some tasks, the item is specified in terms of operations performed on it rather than in terms of its inner structure. These operations may act upon this item, for example, modifying it, searching for some details in it, or storing something in it. After these operations are precisely specified, the implementation of the program may start. The implementation decides which data structure should be used to make execution most efficient in terms of time and space. An item specified in terms of op- erations is called an abstract data type. An abstract data type is not a part of a program, because a program written in a programming language requires the definition of a data structure, not just the operations on the data structure. However, an object- oriented language (OOL) such as C++ has a direct link to abstract data types by im- plementing them as a class. 1.2 Encapsulation Object-oriented programming (OOP) revolves around the concept of an object. Objects, however, are created using a class definition. A class is a template in accor- dance to which objects are created. A class is a piece of software that includes a data Object-Oriented Programming Using C++ 1 © Cengage Learning 2013 C8160_ch01_ptg01.indd 1 18/07/12 10:31 AM 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). Editorial 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.

📄 Page 20

2    ■    C h a p t e r   1   O b j e c t - O r i e n t e d   P r o g r a m m i n g   U s i n g   C + + specification and functions operating on these data and possibly on the data belong- ing to other class instances. Functions defined in a class are called methods, member functions, or function members, and variables used in a class are called data members (more properly, they should be called datum members). This combining of the data and related operations is called data encapsulation. An object is an instance of a class, an entity created using a class definition. In contradistinction to functions in languages that are not object-oriented, ob- jects make the connection between data and member functions much tighter and more meaningful. In languages that are not object-oriented, declarations of data and definitions of functions can be interspersed through the entire program, and only the program documentation indicates that there is a connection between them. In OOLs, a connection is established right at the outset; in fact, the program is based on this connection. An object is defined by related data and operations, and because there may be many objects used in the same program, the objects communicate by exchanging messages that reveal as little detail about their internal structure as neces- sary for adequate communication. Structuring programs in terms of objects allows us to accomplish several goals. First, this strong coupling of data and operations can be used much better in modeling a fragment of the world, which is emphasized especially by software engi- neering. Not surprisingly, OOP has its roots in simulation; that is, in modeling real- world events. The first OOL was called Simula, and it was developed in the 1960s in Norway. Second, objects allow for easier error finding because operations are localized to the confines of their objects. Even if side effects occur, they are easier to trace. Third, objects allow us to conceal certain details of their operations from other objects so that these operations may not be adversely affected by other objects. This is known as the information-hiding principle. In languages that are not object-ori- ented, this principle can be found to some extent in the case of local variables, or as in Pascal, in local functions or procedures, which can be used and accessed only by the function defining them. This is, however, a very tight hiding or no hiding at all. Sometimes we may need to use (again, as in Pascal) a function f 2 defined in f 1 outside of f 1, but we cannot. Sometimes we may need to access some data local to f 1 without exactly knowing the structure of these data, but we cannot. Hence, some modification is needed, and it is accomplished in OOLs. An object in OOL is like a watch. As users, we are interested in what the hands show, but not in the inner workings of the watch. We are aware that there are gears and springs inside the watch, but because we usually know very little about why all these parts are in a particular configuration, we should not have access to this mecha- nism so that we do not damage it, inadvertently or on purpose. This mechanism is hidden from us, we have no immediate access to it, and the watch is protected and works better than when its mechanism is open for everyone to see. An object is like a black box whose behavior is very well defined, and we use the object because we know what it does, not because we have an insight into how it does it. This opacity of objects is extremely useful for maintaining them independently of each other. If communication channels between the objects are well defined, then changes made inside an object can affect other objects only as much as these changes affect the communication channels. Knowing the kind of information sent out and C8160_ch01_ptg01.indd 2 18/07/12 10:31 AM 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). Editorial 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.