ساختارهای داده و حل مسائل با استفاده از C++ (ویرایش دوم)

Data Structures and Problem Solving Using C++ provides a practical introduction to data structures and algorithms from the viewpoint of abstract thinking and problem solving, as well as the use of C++. It is a complete revision of Weissi successful CS2 book Algorithms, Data Structures, and Problem Solving with C++.The most unique aspect of this text is the clear separation of the interface and implementation. C++ allows the programmer to write the interface and implementation separately, to place them in separate files and compile separately, and to hide the implementation details. This book goes a step further: the interface and implementation are discussed in separate parts of the book. Part I (Objects and C++), Part II (Algorithms and Building Blocks), and Part III (Applications) lay the groundwork by discussing basic concepts and tools and providing some practical examples, but implementation of data structures is not shown until Part IV (Implementations). This separation of interface and implementation promotes abstract thinking. Class interfaces are written and used before the implementation is known, forcing the reader to think about the functionality and potential efficiency of the various data structures (e.g., hash tables are written well before the hash table is implemented).Throughout the book, Weiss has included the latest features of the C++ programming language, including a more prevalent use of the Standard Template Library (STL).Features \* Promotes abstract thinking by separating the interface and implementation of the data structures into different parts of the book \* All code is completely rewritten and tested forcompatibility with a wide range of current compilers \* Revised material makes use of the STL whenever appropriate \* Rewritten material on inheritance simplifies the initial presentation and provides the C++ details that are important for advanced uses \* Includes a new chapter on Patterns \* Provides new material on templates, vectors, and push\_back \* Illustrates both the generic interfaces and STL interfaces of data structures \* Generic data structures such as linked lists classes, search tree and hash table classes, priority\_queue, and disjoint sets class are rewritten to be much simpler and cleaner \* A simplified STL implementation is illustrated at the end of the chapters in Part IV, including vector, list, stack, queue, set, map, and priority\_queue Book Cover 1 Contents 4 Preface 20 Part I: Objects & C++ 32 Chapter 1: Arrays, Pointers & Structures 34 1.1 What are Pointers, Arrays & Structures? 34 1.2 Arrays & Strings 35 1.2.1 First-Class Versus Second-Class Objects 35 1.2.2 Using the vector 37 1.2.3 Resizing a vector 38 1.2.4 push_back, size & capacity 42 1.2.5 Parameter-Passing Mechanisms 42 1.2.6 Primitive Arrays of Constants 44 1.2.7 Multidimensional Arrays 45 1.2.8 The Standard Library string Type 45 1.3 Pointer Syntax in C++ 46 1.4 Dynamic Memory Management 51 1.4.1 The new Operator 52 1.4.2 Garbage Collection & delete 52 1.4.3 Stale Pointers, Double Deletion, and More 53 1.5 Reference Variables 55 1.6 Structures 57 1.6.1 Pointers to Structures 59 1.6.2 Exogenous Versus Indigenous Data and Shallow Versus Deep Copying 60 1.6.3 Noncontigious Lists: Linked Lists 61 Summary, Exercises etc 63 Objects of the Game 63 Common Errors 65 On the Internet 66 Exercises 66 References 69 Chapter 2: Objects & Classes 72 2.1 What is Object Oriented Programming? 72 2.2 Basic class Syntax 74 2.2.1 Class Members 74 2.2.2 Extra Constructor Syntax and Accessors 76 2.2.3 Separation of Interface and Implementation 79 2.2.4 The Big Three: Destructor, Copy Constructor, andoperator= 82 2.2.5 Default Constructor 88 2.3 Additional C++ Class Features 88 2.3.1 Initialization Versus Assignment in the ConstructorRevisited 92 2.3.2 Type Conversions 94 2.3.3 Operator Overloading 95 2.3.4 Input and Output and Friends 98 2.4 Some Common Idioms 99 2.4.1 Avoiding Friends 101 2.4.2 Static Class Members 102 2.4.3 The enum Trick for Integer Class Constants 102 2.5 Exceptions 103 2.6 A string Class 104 2.7 Recap: What Gets Called and What Are the Defaults? 113 2.8 Composotion 115 Summary 116 Objects of the Game 116 Common Errors 118 On the Internet 120 Exercises 121 References 127 Chapter 3: Templates 128 3.1 What Is a Template? 128 3.2 Function Templates 129 3.3 A Sorting Function Template 131 3.4 Class Templates 134 3.4.1 A MemoryCell Template 134 3.4.2 Implementing the vector Class Template 139 3.5 Templates of Templates: A matrix Class 139 3.5.1 The Data Members, Constructor. and Basic Accessors 142 3.5.2 operator [ ] 143 3.5.3 Destructor, Copy Assignment, and Copy Constructor 143 3.6 Fancy Templates 143 3.6.1 Multiple Template Parameters 143 3.6.2 Default Template Parameters 144 3.6.3 The Reserved Word typename 144 3.7 Bugs Associated with Templates 145 3.7.1 Bad Error Messages and Inconsistent Rules 145 3.7.2 Template-Matching Algorithms 145 3.7.3 Nested Classes in a Template 145 3.7.4 Static Members in Class Templates 146 Summary 146 Objects of the Game 146 Common Errors 146 On the Internet 147 Exercises 148 Chapter 4: Inheritance 32 Chapter 5: Design Patterns 32 Part II: Algorithms & Building Blocks 7 Chapter 6: Algorithm Analysis 7 Chapter 7: The Standard Template Library 7 Chapter 8: Recursion 7 Chapter 9: Sorting Algorithms 7 Chapter 10: Randomization 7 Part III: Applications 7 Chapter 11: Fun & Games 7 Chapter 12: Stacks & Compilers 7 Chapter 13: Utilities 7 Chapter 14: Simulation 7 Chapter 15: Graphs & Paths 7 Part IV: Implementations 7 Chapter 16: Stacks & Queues 7 Chapter 17: Linked Lists 7 Chapter 18: Trees 7 Chapter 19: Binary Search Trees 7 Chapter 20: Hash Tables 7 Chapter 21: A Priority Queue: The Binary Heap 7 Part V: Advanced Data Structures 16 Chapter 22: Splay Trees 16 Chapter 23: Merging Priority Queues 16 Chapter 24: The Disjoint Set Class 16 Appendices 16 Appendix A: Miscellaneous C++ Details 16 Appendix B: Operators 16 Appendix C: Some Library Routines 16 Appendix D: Primitive Arrays in C++ 16 Index 16 Back Cover 16

Data Structures and Problem Solving Using C++ provides a practical introduction to data structures and algorithms from the viewpoint of abstract thinking and problem solving, as well as the use of C++. It is a complete revision of Weissi successful CS2 book Algorithms, Data Structures, and Problem Solving with C++.

The most unique aspect of this text is the clear separation of the interface and implementation. C++ allows the programmer to write the interface and implementation separately, to place them in separate files and compile separately, and to hide the implementation details. This book goes a step further: the interface and implementation are discussed in separate parts of the book. Part I (Objects and C++), Part II (Algorithms and Building Blocks), and Part III (Applications) lay the groundwork by discussing basic concepts and tools and providing some practical examples, but implementation of data structures is not shown until Part IV (Implementations). This separation of interface and implementation promotes abstract thinking. Class interfaces are written and used before the implementation is known, forcing the reader to think about the functionality and potential efficiency of the various data structures (e.g., hash tables are written well before the hash table is implemented).

Throughout the book, Weiss has included the latest features of the C++ programming language, including a more prevalent use of the Standard Template Library (STL).

Features

• Promotes abstract thinking by separating the interface and implementation of the data structures into different parts of the book
• All code is completely rewritten and tested for compatibility with a wide range of current compilers
• Revised material makes use of the STL whenever appropriate
• Rewritten material on inheritance simplifies the initial presentation and provides the C++ details that are important for advanced uses
• Includes a new chapter on Patterns
• Provides new material on templates, vectors, and push_back
• Illustrates both the generic interfaces and STL interfaces of data structures
• Generic data structures such as linked lists classes, search tree and hash table classes, priority_queue, and disjoint sets class are rewritten to be much simpler and cleaner
• A simplified STL implementation is illustrated at the end of the chapters in Part IV, including vector, list, stack, queue, set, map, and priority_queue

020161250XB04062001

Data Structures and Problem Solving Using C++ provides a practical introduction to data structures and algorithms from the viewpoint of abstract thinking and problem solving, as well as the use of C++. It is a complete revision of Weiss' successful CS2 book Algorithms, Data Structures, and Problem Solving with C++. The most unique aspect of this text is the clear separation of the interface and implementation. C++ allows the programmer to write the interface and implementation separately, to place them in separate files and compile separately, and to hide the implementation details. This book goes a step further: the interface and implementation are discussed in separate parts of the book. Part I (Objects and C++), Part II (Algorithms and Building Blocks), and Part III (Applications) lay the groundwork by discussing basic concepts and tools and providing some practical examples, but implementation of data structures is not shown until Part IV (Implementations). This separation of interface and implementation promotes abstract thinking. Class interfaces are written and used before the implementation is known, forcing the reader to think about the functionality and potential efficiency of the various data structures (e.g., hash tables are written well before the hash table is implemented). Throughout the book, Weiss has included the latest features of the C++ programming language, including a more prevalent use of the Standard Template Library (STL).