Data Structures And Problem Solving Using C++

Book Cover
Contents
Preface
Part I: Objects & C++
Chapter 1: Arrays, Pointers & Structures
1.1 What are Pointers, Arrays & Structures?
1.2 Arrays & Strings
1.2.1 First-Class Versus Second-Class Objects
1.2.2 Using the vector
1.2.3 Resizing a vector
1.2.4 push_back, size & capacity
1.2.5 Parameter-Passing Mechanisms
1.2.6 Primitive Arrays of Constants
1.2.7 Multidimensional Arrays
1.2.8 The Standard Library string Type
1.3 Pointer Syntax in C++
1.4 Dynamic Memory Management
1.4.1 The new Operator
1.4.2 Garbage Collection & delete
1.4.3 Stale Pointers, Double Deletion, and More
1.5 Reference Variables
1.6 Structures
1.6.1 Pointers to Structures
1.6.2 Exogenous Versus Indigenous Data and Shallow Versus Deep Copying
1.6.3 Noncontigious Lists: Linked Lists
Summary, Exercises etc
Objects of the Game
Common Errors
On the Internet
Exercises
References
Chapter 2: Objects & Classes
2.1 What is Object Oriented Programming?
2.2 Basic class Syntax
2.2.1 Class Members
2.2.2 Extra Constructor Syntax and Accessors
2.2.3 Separation of Interface and Implementation
2.2.4 The Big Three: Destructor, Copy Constructor, andoperator=
2.2.5 Default Constructor
2.3 Additional C++ Class Features
2.3.1 Initialization Versus Assignment in the ConstructorRevisited
2.3.2 Type Conversions
2.3.3 Operator Overloading
2.3.4 Input and Output and Friends
2.4 Some Common Idioms
2.4.1 Avoiding Friends
2.4.2 Static Class Members
2.4.3 The enum Trick for Integer Class Constants
2.5 Exceptions
2.6 A string Class
2.7 Recap: What Gets Called and What Are the Defaults?
2.8 Composotion
Summary
Objects of the Game
Common Errors
On the Internet
Exercises
References
Chapter 3: Templates
3.1 What Is a Template?
3.2 Function Templates
3.3 A Sorting Function Template
3.4 Class Templates
3.4.1 A MemoryCell Template
3.4.2 Implementing the vector Class Template
3.5 Templates of Templates: A matrix Class
3.5.1 The Data Members, Constructor. and Basic Accessors
3.5.2 operator [ ]
3.5.3 Destructor, Copy Assignment, and Copy Constructor
3.6 Fancy Templates
3.6.1 Multiple Template Parameters
3.6.2 Default Template Parameters
3.6.3 The Reserved Word typename
3.7 Bugs Associated with Templates
3.7.1 Bad Error Messages and Inconsistent Rules
3.7.2 Template-Matching Algorithms
3.7.3 Nested Classes in a Template
3.7.4 Static Members in Class Templates
Summary
Objects of the Game
Common Errors
On the Internet
Exercises
Chapter 4: Inheritance
Chapter 5: Design Patterns
Part II: Algorithms & Building Blocks
Chapter 6: Algorithm Analysis
Chapter 7: The Standard Template Library
Chapter 8: Recursion
Chapter 9: Sorting Algorithms
Chapter 10: Randomization
Part III: Applications
Chapter 11: Fun & Games
Chapter 12: Stacks & Compilers
Chapter 13: Utilities
Chapter 14: Simulation
Chapter 15: Graphs & Paths
Part IV: Implementations
Chapter 16: Stacks & Queues
Chapter 17: Linked Lists
Chapter 18: Trees
Chapter 19: Binary Search Trees
Chapter 20: Hash Tables
Chapter 21: A Priority Queue: The Binary Heap
Part V: Advanced Data Structures
Chapter 22: Splay Trees
Chapter 23: Merging Priority Queues
Chapter 24: The Disjoint Set Class
Appendices
Appendix A: Miscellaneous C++ Details
Appendix B: Operators
Appendix C: Some Library Routines
Appendix D: Primitive Arrays in C++
Index
Back Cover