Data Structures and Algorithms in C___ Pocket Primer (Pocket Primer Series)
LLICENSE. DISCLAIMER OF LIABILITY AND LIMITED WARRANTY By purchasing or using this book and disc(the"Work"), you agree that this license grants permission to use the contents contained herein including the disc, but does not give you the right of ownership to any of the textual content in the book disc or ownership to any of the information or products contained in it. This license does not permit uploading of the work onto the Internet or on a network (of any kind) without the written consent of the Publisher. Duplication or dissemination of any text, code, simulations, images, etc. contained herein is limited to and subject to licensing terms for the respective products, and permission must be obtained from the publisher or the owner of the content etc. in order to reproduce or network any portion of the textual material (in any media)that is contained in the work. MERCURY LEARNING AND INFORMATION(“MLI”or“ the publisher and anyone involved in the creation, writing, or production of the companion disc, accompanying algorithms, code, or computer programs Cthe software"), and any accompanying Web site or software of the work, cannot and do not warrant the performance or results that might be obtained by using the contents of the Work. The author, developers, and the publisher have used their best efforts to insure the accuracy and functionality of the textual material and/or programs contained in this package; we, however, make no warranty of any kind, express or implied, regarding the performance of these contents or programs. The work is sold as is"without warranty (except for defective materials used in manufacturing the book or due to faulty workmanship The author, developers, and the publisher of any accompanying content, and anyone involved in the composition, production, and manufacturing of this work will not be liable for damages of any kind arising out of the use of (or the inability to use)the algorithms, source code, computer programs or textual material contained in this publication. This includes, but is not limited to, loss of revenue or profit, or other incidental, physical, or consequential damages arising out of the use of this work The sole remedy in the event of a claim of any kind is expressly limited to replacement of the book and/or disc, and only at the discretion of the Publisher. The use of“ implied warranty” and certain“ exclusions”vary from state to state, and might not apply to the purchaser of this product Companion files for this title may be requested at info @merclearning com Data structures and Algorithms in C++ Pocket primer Lee Wittenberg MERCURY LEARNING AND INFORMATION unles g Boston massachusetts New delhi Copyright C2018 by MERCURY LEARNING AND INFORMATION LLC. All rights reserved This publication, portions of it, or any accompanying software may not be reproduced in any way, stored in a retrieval system of any type, or transmitted by any means, media, electronic display or mechanical display, including, but not limited to photocopy, recording, Internet postings, or scanning, without prior permission in writing from the publisher. Publisher: David pallan MERCURY LEARNING AND INFORMATION 22841 Quicksilver drive Dulles. va20166 Info(amerclearning com Www.merclearning.com (800)232-0223 Lee wittenberg. Data Structures and Algorithms in C++: Pocket Primer. ISBN:978-1-683920847 The publisher recognizes and respects all marks used by companies, manufacturers, and developers as a means to distinguish their products all brand names and product names mentioned in this book are trademarks or service marks of their respective companies Any omission or misuse (of any kind) of service marks or trademarks, etc is not an attempt to infringe on the property of others Library of congress Control Number: 2017934713 171819321 Printed in the United states of america This book is printed on acid-free paper Our titles are available for adoption, license, or bulk purchase by institutions, corporations, etc For additional information, please contact the Customer Service Dept. at(800)232- 0223 (toll free). Digital versions of our titles are available at www.authorcloudware.comandothere-vendors.Companionfilesforthistitlemaybe requested at info@merclearning com The sole obligation of mERCury LEARNING AND INFORMATion to the purchaser is to replace the book and/or disc, based on defective materials or faulty workmanship, but not based on the operation or functionality of the product CONTENTS Preface Acknowledgments Chapter 1: C++ Review 1.1 The auto Keyword 1.2 Classes 1.2.1 Example: A Fraction Class 1.3 Pointers and arrays 1.4 Inheritance 1.5 Templates 1.6 The Standard Template Library(STL) 1.6.1 Containers 1.6.2 Iterators 1.6.3 Algorithms 1.7 Putting It All Together: A Vector class 1.7.1 Constructors/Destructors 1.7.2 Member functions 1.7.3 Iterators Chapter 2: Algorithm Analysis 2.1 Big-O Notation 2.1.1 Terminology 2.2 Efficiency of vector operations 2.3 Estimates and Comparisons 2.4 Fast Enough Chapter 3: Linked Lists 3.1 The list Interface 3.2 List Implementation 3.2.1 Constructors / destructors 3.2.2 Member functions 3.2.3 Iterators Chapter 4: Stacks and Queues 4.1 The stack and queue Interfaces 4.2 Example: Infix and postfix 4.3 Stack and Queue Implementation 4.3.1 Constructors destructors 4.3.2 Member functions Chapter 5: Recursion 5.1 Recursive definitions 5.2 Proof by induction 5.3 Example: Binary search 5.4 Example: Tower of hanoi 5.5 Example: Recursive Descent Parsing 5.6 The efficiency of recursion Chapter 6: Binary Trees 6.1 Traversals 6.2 Example: Expression Trees 6.3 Example: Binary Search Trees 6.4 The set and map interfaces 6.5 Example: Associative Arrays 6.6 Example: Sparse Matrices 6.7 A Binary Search_ Tree Class 6.7.1 Constructors destructors 6.7.2 Member functions 6.7.3 Iterators 6.8 Set and Map Implementation 6.8.1 Constructors/ Destructors 6.8.2 Member functions 6.8.3 Iterators Chapter 7: Binary Trees(continued) 7.1 Height-Balanced Trees 7.2 General trees 7.3 Heaps 7.4 The priority queue Interface 7.5 Priority Queue Implementation 7.5.1 Constructors /destructors 7.5.2 Member functions Chapter 8: Sorting 8.1 Bubble Sort(revised 8.2 Selection sort 8. 3 Insertion sort 8.4 Shell sort 8.5 Heap Sort 8.6 Merge sort 8.7 Quick Sort 8. 8 The stl sor t function Chapter 9: Hash Tables 9. 1 Hash Functions 9. 2 Collisions 9.2.1 Probing 9. 2.2 Chaining 9.3 Load Factors and efficiency 9.4 Rehashing 9.5 The unordered_set and unordered_ map Interfaces 9. 6 A Hash table class 9. 6.1 Constructors/ destructors 9. 6.2 Member functions 9.6.3 Iterators 9.7 Unordered set and Unordered_ Map Implementation 9.7.1 Constructors destructors 9.7.2 Member functions 9.7.3 Iterators Chapter 10: Graphs 10. 1 Graph representations 10.1.1 Adjacency matrix 10.1.2 Adjacency lists 10.2 Traversals 10.2.1 Depth-First Search 10.2.2 Breadth-First search 10.3 Example: Topological Sorting 10.4 EXample: Shortest Path 10.5 A Graph Interface 10.6 Graph Implementation 10.6.1 Constructors /destructors 10.6.2 Member functions Appendix A: A Programmer's Library Appendix B: sTL Class Summary Appendix C: Chunk Index Index 10