Data Structures and Algorithms Using C++

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 (Ω)
		3.7.3 Theta Notation (θ)
		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