Cover -- Data Structures and Algorithms Using C++ -- Copyright -- Contents -- About the Authors -- Preface -- Acknowledgements -- Chapter 1 Introduction to C++ -- 1.1 Introduction -- 1.2 Class Overview -- 1.2.1 Class -- 1.2.2 Objects -- 1.2.3 Class Members -- 1.3 I/O Streams -- 1.4 Access Control -- 1.5 Class Scope -- 1.6 Static Class Members -- 1.6.1 Static Member Variables -- 1.6.2 Static Member Function -- 1.6.3 Static Object -- 1.7 Functions -- 1.7.1 Parameter Passing Methods -- 1.7.2 Inline Functions -- 1.7.3 The friend Function -- 1.7.4 Function Overloading -- 1.8 The this Pointer -- 1.9 Dynamic Memory Allocation and Deallocation -- 1.9.1 The new Operator -- 1.9.2 The delete Operator -- 1.10 Exception Handling -- Summary -- Exercises -- Chapter 2 Object Oriented Concepts -- 2.1 Goals and Principles -- 2.1.1 Object Oriented Design Goals -- 2.1.2 Object Oriented Design Principles -- 2.2 Constructors and Destructors -- 2.2.1 Constructors -- 2.2.2 Constructor Overloading -- 2.2.3 Destructors -- 2.3 Operator Overloading -- 2.3.1 Overloading the Plus (+) Operator -- 2.3.2 Overloading the Minus (-) Operator -- 2.3.3 Overloading Unary Operators -- 2.3.4 Postfix Form of Overloading the Unary Operator ++ -- 2.3.5 Prefix Form of Overloading the Unary Operator -- -- 2.3.6 Postfix Form of Overloading the Unary Operator -- -- 2.4 Inheritance -- 2.4.1 Base Class Access Control -- 2.4.2 Types of Inheritance -- 2.4.3 Reasons for the Usage of Inheritance -- 2.4.4 Advantages -- 2.4.5 Disadvantages -- 2.4.6 Delegation -- 2.5 Polymorphism -- 2.5.1 Virtual Functions -- 2.5.2 Pure Virtual Functions -- 2.6 Abstract Classes -- 2.7 Generic Programming with Templates -- 2.7.1 Function Templates -- 2.7.2 Class Templates -- 2.8 Recursion -- Summary -- Exercises -- Chapter 3 Algorithms -- 3.1 Introduction -- 3.2 Basic Notations -- 3.2.1 Pseudo Code.

3.3 Types of Algorithms -- 3.3.1 Brute Force Algorithms -- 3.3.2 Divide and Conquer Algorithms -- 3.3.3 Dynamic Programming Algorithms -- 3.3.4 Greedy Algorithms -- 3.3.5 Branch and Bound Algorithms -- 3.3.6 Recursive Algorithms -- 3.3.7 Back Tracking Algorithms -- 3.3.8 Randomized Algorithms -- 3.3.9 Hill Climbing Algorithms -- 3.4 Performance Analysis -- 3.4.1 Properties of the Best Algorithms -- 3.5 Space Complexity -- 3.5.1 Instruction Space -- 3.5.2 Text Section of a Program -- 3.5.3 Data Space -- 3.5.4 Stack Space -- 3.5.5 Calculating the Instruction Space -- 3.5.6 Calculating the Data Space -- 3.5.7 Size of Data Section -- 3.5.8 Size of Rodata Section -- 3.5.9 Size of bss Section -- 3.6 Apriori Analysis -- 3.7 Asymptotic Notation -- 3.7.1 Big oh Notation (O) -- 3.7.2 Omega Notation ((S](B) -- 3.7.3 Theta Notation ((Sk(B) -- 3.7.4 Little oh Notation(o) -- 3.8 Time Complexity -- 3.8.1 Time Complexity Analysis of Bubble Sort -- 3.8.2 Time Complexity Analysis of Selection Sort -- 3.9 Worst Case, Average Case and Best Case Complexity -- 3.9.1 Worst Case -- 3.9.2 Average Case -- 3.9.3 Best Case -- Summary -- Exercises -- Chapter 4 Arrays -- 4.1 Introduction -- 4.1.1 Array -- 4.2 Array Types -- 4.2.1 Single-dimensional Array -- 4.2.2 Multi-dimensional Array -- 4.2.3 N-dimensional Array -- 4.3 Array Representation -- 4.4 Initializing Arrays -- 4.5 Accessing Values of an Array -- 4.6 Array Operations -- 4.6.1 Traversing -- 4.6.2 Insertion -- 4.6.3 Deletion -- 4.6.4 Sorting -- 4.6.5 Searching -- 4.7 Arrays as Parameters -- 4.8 Character Sequences -- 4.9 Applications -- Summary -- Exercises -- Chapter 5 Linked List -- 5.1 Introduction -- 5.2 Representation of Linked List in Memory -- 5.2.1 Static Representation -- 5.2.2 Dynamic Representation -- 5.3 Singly Linked List -- 5.3.1 Operations -- 5.4 Circular Linked List -- 5.4.1 Merging of Two Circular Lists.

5.5 Doubly Linked Lists -- 5.5.1 Representation of Doubly Linked List -- 5.5.2 Operations -- 5.6 Comparison of Various Linked Lists -- 5.6.1 Linked Lists Versus Arrays -- 5.7 Applications -- 5.7.1 Polynomial Manipulation -- Summary -- Exercises -- Chapter 6 Stacks -- 6.1 Definition -- 6.2 Representation of a Stack -- 6.2.1 Array Representation of a Stack -- 6.2.2 Linked Representation of a Stack -- 6.3 Operations on Stack -- 6.3.1 Array Implementation of a Stack -- 6.3.2 Linked Implementation of a Stack -- 6.4 Applications of Stacks -- 6.4.1 Expression Evaluation -- 6.4.2 Postfix Evaluation -- 6.4.3 Recursion -- 6.4.4 Balancing of the Matching Parenthesis -- Summary -- Excercises -- Chapter 7 Queues -- 7.1 Introduction -- 7.2 Representation of a Queue -- 7.2.1 Array Representation -- 7.2.2 Linked Representation -- 7.3 Operations on a Queue -- 7.3.1 Enqueue and Deque Using Arrays -- 7.3.2 Enqueue and Deque Using Linked List -- 7.4 Circular Queues -- 7.4.1 Operations on Circular Queue -- 7.5 Deque -- 7.5.1 Operations on a Deque -- 7.6 Applications of Queues -- 7.6.1 Simulation of Time-sharing System -- 7.6.2 Queue ADT -- Summary -- Exercises -- Chapter 8 Dictionaries -- 8.1 Dictionaries -- 8.2 Linear List Representation -- 8.3 Skip Lists Representation -- 8.3.1 Operations -- 8.3.2 Searching -- 8.3.3 Insertion -- 8.3.4 Deletion -- 8.4 Hash Table -- 8.4.1 Hash Functions -- 8.5 Collisions -- 8.5.1 Separate Chaining -- 8.5.2 Open Addressing -- 8.6 Comparison of Chaining and Open Addressing -- 8.7 Applications -- 8.8 Dictionary ADT -- Summary -- Exercises -- Chapter 9 Trees and Binary Trees -- 9.1 Introduction -- 9.2 Terminologies -- 9.3 Representation of a Tree -- 9.4 Binary Trees -- 9.5 Representation of Binary Trees -- 9.5.1 Array Representation of a Binary Tree -- 9.5.2 Linked Representation of Binary Trees -- 9.6 Binary Tree Operations.

9.7 Binary Tree Traversals -- 9.7.1 Inorder Traversal (LVR) -- 9.7.2 Preorder Traversal (VLR) -- 9.7.3 Postorder Traversal (LRV) -- 9.7.4 Level-order Traversal -- 9.8 Conversion of a Tree into a Binary Tree -- 9.9 Threaded Binary Trees -- 9.9.1 Linked Representation of a Threaded Binary Tree -- 9.10 Applications of Binary Trees -- 9.10.1 Traversal of an Expression Tree -- 9.10.2 Operations on Expression Trees -- 9.11 ADT of Binary Tree -- Summary -- Exercises -- Chapter 10 Graphs -- 10.1 Introduction -- 10.2 Basic Terminology -- 10.3 Representation of Graphs -- 10.3.1 Sequential Representation of Graphs -- 10.3.2 Linked Representation of Graphs -- 10.4 Operations on Graphs -- 10.5 Graph Traversals -- 10.5.1 Breadth First Traversal -- 10.5.2 Depth First Traversal -- 10.6 Applications -- 10.7 Graph ADT -- Summary -- Exercises -- Chapter 11 Priority Queues -- 11.1 Introduction -- 11.2 Priority Queue ADT -- 11.3 Priority Queue Implementation Using Heaps -- 11.3.1 Priority Queue Interface -- 11.3.2 Min Heap-Insertion -- 11.3.3 Min Heap-Deletion -- 11.3.4 Max Heap-Insertion -- 11.3.5 Max Heap-Deletion -- 11.4 Applications -- 11.4.1 Job Scheduling -- 11.5 External Sorting -- 11.5.1 Polyphase Merge -- 11.5.2 Multiway Merge -- Summary -- Exercises -- Chapter 12 Binary Search Trees and AVL Trees -- 12.1 Binary Search Trees -- 12.2 Representation of a Binary Search Tree -- 12.3 Operations on Binary Search Trees -- 12.3.1 Searching -- 12.3.2 Insertion -- 12.3.3 Deletion -- 12.3.4 Disadvantages of Binary Search Tree -- 12.4 AVL Trees -- 12.5 Operation of AVL Search Trees -- 12.5.1 Searching -- 12.5.2 Insertion -- 12.5.3 Deletion -- 12.6 Applications -- Summary -- Exercises -- Chapter 13 Multiway Trees and B Trees -- 13.1 Introduction -- 13.2 Representation of a Node Structure -- 13.3 Operations on m-Way Search Trees -- 13.3.1 Searching -- 13.3.2 Insertion.

13.3.3 Deletion -- 13.3.4 Drawbacks of m-Way Search Trees -- 13.4 B Trees -- 13.5 Operations on B Trees -- 13.5.1 Searching -- 13.5.2 Insertion -- 13.5.3 Deletion -- 13.6 Height of B Trees -- 13.7 Variations of B Tree -- 13.7.1 B* Tree -- 13.7.2 B+ Tree -- 13.8 Applications -- 13.8.1 Databases -- Summary -- Exercises -- Chapter 14 Red-Black Trees and Splay Trees -- 14.1 Introduction -- 14.2 Representation of a Red-Black Tree -- 14.3 Operations -- 14.3.1 Searching -- 14.3.2 Insertion -- 14.3.3 Deletion -- 14.4 Splay Trees -- 14.4.1 Splay Rotations -- 14.4.2 Amortized Analysis -- 14.5 Applications -- Summary -- Exercises -- Chapter 15 Pattern Matching and Tries -- 15.1 Introduction -- 15.2 Terminology -- 15.3 Pattern Matching Algorithms -- 15.3.1 Fixed Pattern Matching Algorithms -- 15.3.2 Regular Expression Pattern Matching -- 15.4 Fixed Pattern Matching Algorithms -- 15.4.1 Brute Force Pattern Matching Algorithm -- 15.4.2 Th e Boyer-Moore Algorithm -- 15.4.3 Knuth-Morris-Pratt Algorithm (KMP) -- 15.5 Applications of Pattern Matching Algorithms -- 15.6 Tries -- 15.6.1 Standard Tries -- 15.6.2 Compressed Tries -- 15.6.3 Suffix Tries -- 15.7 Applications of Tries -- Summary -- Exercises -- Chapter 16 Sorting and Searching -- 16.1 Sorting -- 16.1.1 Bubble Sort -- 16.1.2 Insertion Sort -- 16.1.3 Selection Sort -- 16.1.4 Quick Sort -- 16.1.5 Merge Sort -- 16.1.6 Shell Sort -- 16.1.7 Radix Sort -- 16.1.8 Heap Sort -- 16.2 Searching -- 16.2.1 Linear Search or Sequential Search -- 16.2.2 Binary Search -- 16.2.3 Fibonacci Search -- Summary -- Exercises -- Index.

Data Structures and Algorithms Using C++ helps students to master data structures, their algorithms and the analysis of complexities of these algorithms. Each chapter includes an Abstract Data Type (ADT) and applications along with a detailed explanation of the topics. This book meets the requirements of the course curricula of all Indian universities.

Electronic reproduction. Ann Arbor, Michigan : ProQuest Ebook Central, 2018. Available via World Wide Web. Access may be limited to ProQuest Ebook Central affiliated libraries.