Data Structures Using C++

Front Matter
Dedication
Preface
Table of Contents
1. Fundamental Concepts
1.1 Introduction to Programming
1.2 Object-Oriented Programming
1.3 Introduction to Data Structures
1.3.1 Data
1.3.1.1 Atomic and Composite Data
1.3.2 Data Type
1.3.2.1 Built-in Data Types
1.3.2.2 User-Defined Data Types
1.3.3 Data Object
1.3.4 Data Structure
1.3.5 Abstract Data Type
1.4 Types of Data Structures
1.4.1 Primitive and Non-Primitive Data Structures
1.4.2 Linear and Non-Linear Data Structures
1.4.3 Static and Dynamic Data Structures
1.4.4 Persistent and Ephemeral Data Structures
1.4.5 Sequential Access and Direct Access Data Structures
1.5 Introduction to Algorithms
1.5.1 Characteristics of Algorithms
1.5.2 Algorithmics
1.5.3 Algorithm Design Tools: Pseudocode and Flowchart
1.6 Pseudocode
1.6.1 Pseudocode Notations
1.6.2 Algorithm Header
1.6.3 Purpose
1.6.4 Condition and Return Statements
1.6.5 Statement Numbers
1.6.6 Variables
1.6.7 Statement Constructs
1.6.7.1 Sequence
1.6.7.2 Decision
1.6.7.3 Repetition
1.6.8 Subalgorithms
1.7 Relationship among Data, Data Structures, and Algorithms
1.8 Implementation of Data Structures
1.9 Flowcharts
1.10 Analysis of Algorithms
1.10.1 Complexity of Algorithms
1.10.2 Space Complexity
1.10.2.1 Compile Time Space Complexity
1.10.2.2 Run-Time Space Complexity
1.10.3 Time Complexity
1.10.3.1 Best, Worst, and Average Cases
1.10.4 Computing Time Complexity of an Algorithm
1.10.5 Big-O Notation
1.11 From Problem to Program
1.12 Software Engineering
1.12.1 Analysis Phase
1.12.2 Design Phase
1.12.3 Implementation Phase
1.12.4 Testing Phase
1.12.5 Verification Phase
Recapitulation
Key Terms
Exercises
2. Linear Data Structure Using Arrays
2.1 Sequential Organization
2.2 Linear Data Structure Using Sequential Organization: Arrays
2.3 Array as an Abstract Data Type
2.4 Memory Representation and Address Calculation
2.5 Class Array
2.5.1 Inserting an Element into an Array
2.5.2 Deleting an Element
2.6 Arrays Using Template
2.7 Multidimensional Arrays
2.7.1 Two-Dimensional Arrays
2.7.1.1 Memory Representation of Two-Dimensional Arrays
2.7.1.2 Row-Major Representation
2.7.1.3 Column-Major Representation
2.7.2 n-Dimensional Arrays
2.7.2.1 Address Calculation for Multidimensional Array
2.7.2.2 Address Calculation for One-Dimensional Array
2.7.2.3 Address Calculation for Two-Dimensional Array
2.7.2.4 Address Calculation for Three-Dimensional Array
2.8 Concept of Ordered List
2.9 Single Variable Polynomial
2.9.1 Representation Using Arrays
2.9.2 Polynomial as Array of Structure
2.9.3 Polynomial Evaluation
2.9.4 Polynomial Addition
2.9.5 Polynomial Multiplication
2.10 Array for Frequency Count
2.11 Sparse Matrix
2.11.1 Sparse Matrix Representation
2.11.2 Sparse Matrix Addition
2.11.3 Transpose of Sparse Matrix
2.11.3.1 Simple Transpose
2.11.3.2 Fast Transpose
2.11.3.3 Time and Space Complexity Analysis of Fast Transpose
2.12 String Manipulation Using Array
2.13 Pros and Cons of Arrays
2.13.1 Characteristics
2.13.2 Advantages
2.13.3 Disadvantages
2.13.4 Applications of Arrays
Recapitulation
Key Terms
Exercises
3. Stacks
3.1 Concept of Stacks and Queues
3.2 Stacks
3.2.1 Primitive Operations
3.2.1.1 Push
3.2.1.2 Pop
3.2.1.3 GetTop
3.3 Stack Abstract Data Type
3.4 Representation of Stacks Using Sequential Organization Arrays
3.4.1 Create
3.4.2 Empty
3.4.3 GetTop
3.4.4 Push
3.4.5 Pop
3.5 Stacks Using Template
3.6 Multiple Stacks
3.7 Applications of Stack
3.8 Expression Evaluation and Conversion
3.8.1 Polish Notation and Expression Conversion
3.8.2 Need for Prefix and Postfix Expressions
3.8.3 Postfix Expression Evaluation
3.8.3.1 Infix to Postfix Conversion
3.8.3.2 Infix to Prefix Conversion
3.8.3.3 Postfix to Infix Conversion
3.8.3.4 Postfix to Prefix Conversion
3.8.3.5 Prefix to Infix Conversion
3.8.3.6 Prefix to Postfix Conversion
3.9 Processing of Function Calls
3.10 Reversing a String with a Stack
3.11 Checking Correctness of Well-Formed Parentheses
3.12 Recursion
3.13 Parsing Computer Programs
3.14 Backtracking Algorithms
3.15 Converting Decimal Numbers to Binary
Recapitulation
Key Terms
Exercises
4. Recursion
4.1 Introduction
4.2 Recurrence
4.3 Use of Stack in Recursion
4.4 Variants of Recursion
4.4.1 Direct Recursion
4.4.2 Indirect Recursion
4.4.3 Tail Recursion
4.4.4 Linear Recursion
4.4.5 Tree Recursion
4.5 Execution of Recursive Calls
4.6 Recursive Functions
4.6.1 Writing Recursive Code
4.6.2 Tower of Hanoi: An Example of Recursion
4.6.3 Checking for Correctness
4.6.4 Things to Remember
4.7 Iteration versus Recursion
4.7.1 Demerits of Recursive Algorithms
4.7.2 Demerits of Iterative Methods
4.8 Simulating Recursion Using Stack Eliminating Recursion
4.9 Applications of Recursion
Recapitulation
Key Terms
Exercises
5. Queues
5.1 Concept of Queues
5.2 Queue as Abstract Data Type
5.3 Realization of Queues Using Arrays
5.4 Circular Queue
5.4.1 Advantages of Using Circular Queues
5.5 Multi-Queues
5.6 Deque
5.7 Priority Queue
5.7.1 Array Implementation of Priority Queue
5.8 Applications of Queues
5.8.1 Josephus Problem
5.8.2 Job Scheduling
5.8.3 Simulation
5.9 Queues Using Template
Recapitulation
Key Terms
Exercises
6. Linked Lists
6.1 Introduction
6.2 Linked List
6.2.1 Comparison of Sequential and Linked Organizations
6.2.2 Linked List Terminology
6.2.3 Primitive Operations
6.3 Realization of Linked Lists
6.3.1 Realization of Linked List Using Arrays
6.3.2 Linked List Using Dynamic Memory Management
6.3.2.1 Empty Linked List
6.4 Dynamic Memory Management
6.4.1 Dynamic Memory Management in C++ with new and delete Operators
6.4.1.1 The new Operator
6.4.1.2 Syntax
6.4.1.3 The Null Pointer
6.4.1.4 The delete Operator
6.5 Linked List Abstract Data Type
6.5.1 Data Structure of Node
6.5.2 Insertion of a Node
6.5.2.1 Insertion of a Node at a Middle Position
6.5.2.2 Insertion of a Node at the First Position
6.5.2.3 Insertion of a Node at the End
6.5.2.4 Generalized Insert Routine
6.5.3 Linked List Traversal
6.5.3.1 Non-Recursive Method
6.5.3.2 Recursive Traversal Method
6.5.4 Deletion of a Node
6.5.4.1 Deleting the First Node
6.5.4.2 Deleting a Middle Node
6.6 Linked List Variants
6.6.1 Head Pointer and Header Node
6.6.2 Types of Linked List
6.6.2.1 Singly Linked List
6.6.2.2 Doubly Linked List
6.6.3 Linear and Circular Linked Lists
6.6.3.1 Linear Linked List
6.6.3.2 Circular Linked List
6.7 Doubly Linked List
6.7.1 Creation of Doubly Linked List
6.7.2 Deletion of a Node from a Doubly Linked List
6.7.3 Insertion of a Node in a Doubly Linked List
6.7.4 Traversal of DLL
6.8 Circular Linked List
6.8.1 Singly Circular Linked List
6.8.2 Circular Linked List with Header Node
6.8.3 Doubly Circular Linked List
6.9 Polynomial Manipulations
6.9.1 Polynomial Evaluation
6.9.2 Polynomial Addition
6.9.2.1 Paper-Pencil Method
6.9.2.2 Polynomial Addition Algorithm
6.9.3 Polynomial Multiplication
6.10 Representation of Sparse Matrix Using Linked List
6.11 Linked Stack
6.11.1 Class for Linked Stack
6.11.2 Operations on Linked Stack
6.12 Linked Queue
6.12.1 Erasing a Linked Queue
6.13 Generalized Linked List
6.13.1 Definition
6.13.2 Applications
6.13.3 Representation of Polynomials Using Generalized Linked List
6.13.4 Representation of Sets Using Generalized Linked List
6.13.4.1 Printing Generalized Linked Lists
6.14 More on Linked Lists
6.14.1 Copying a Linked List
6.14.2 Computing the Length of a Linked List
6.14.2.1 Calling Length
6.14.3 Reversing Singly Linked List without Temporary Storage
6.14.4 Concatenating Two Linked Lists
6.14.5 Erasing the Linked List
6.15 Application of Linked List - Garbage Collection
Recapitulation
Key Terms
Exercises
7. Trees
7.1 Introduction
7.1.1 Basic Terminology
7.1.1.1 Adjacent Nodes
7.1.1.2 Directed and Undirected Graphs
7.1.1.3 Parallel Edges and Multigraph
7.1.1.4 Weighted Graph
7.1.1.5 Null Graph and Isolated Vertex
7.1.1.6 Degree of Vertex
7.1.1.7 Paths and Circuits
7.1.1.8 Connectivity
7.1.1.9 Acyclic Graph
7.1.1.10 Trees
7.1.1.11 Forest and Trees
7.1.2 General Tree
7.1.3 Representation of a General Tree
7.2 Types of Trees
7.3 Binary Tree
7.3.1 Properties of a Binary Tree
7.3.1.1 Property 1
7.3.1.2 Property 2
7.3.1.3 Property 3
7.3.1.4 Other Properties
7.3.1.5 Relation between Number of Leaf Nodes and Degree-2 Nodes
7.3.1.6 Binary Tree with n Nodes Having n + 1 External Nodes
7.4 Binary Tree Abstract Data Type
7.5 Realization of a Binary Tree
7.5.1 Array Implementation of Binary Trees
7.5.2 Linked Implementation of Binary Trees
7.6 Insertion of a Node in Binary Tree
7.7 Binary Tree Traversal
7.7.1 Preorder Traversal
7.7.1.1 Preorder DLR Algorithm
7.7.2 Inorder Traversal
7.7.2.1 Inorder LDR Algorithm
7.7.3 Postorder Traversal
7.7.3.1 Postorder LRD Algorithm
7.7.4 Non-Recursive Implementation of Traversals
7.7.4.1 Non-Recursive Preorder Algorithm
7.7.4.2 Non-Recursive Inorder Algorithm
7.7.4.3 Non-Recursive Postorder Algorithm
7.7.5 Formation of Binary Tree from its Traversals
7.7.6 Breadth- and Depth-First Traversals
7.7.6.1 Depth-First Traversal
7.7.6.2 Breadth-First Traversal
7.8 Other Tree Operations
7.8.1 Counting Nodes
7.8.2 Counting Leaf Nodes
7.8.3 Computing Height of Binary Tree
7.8.4 Getting Mirror, Replica, or Tree Interchange of Binary Tree
7.8.5 Copying Binary Tree
7.8.6 Equality Test
7.9 Conversion of General Tree to Binary Tree
7.10 Binary Search Tree
7.10.1 Inserting a Node
7.10.2 Searching for a Key
7.10.3 Deleting a Node
7.10.4 Binary Tree and Binary Search Tree
7.11 Threaded Binary Tree
7.11.1 Threading a Binary Tree
7.11.1.1 Sample Run
7.11.2 Right-Threaded Binary Tree
7.11.3 Inorder Traversal
7.11.4 Preorder Traversal
7.11.5 Insert to Right of a Node
7.11.6 Deleting a Node
7.11.7 Pros and Cons
7.12 Applications of Binary Trees
7.12.1 Expression Tree
7.12.1.1 Construction of Expression Tree
7.12.2 Decision Tree
7.12.3 Huffman's Coding
7.12.4 Game Trees
Recapitulation
Key Terms
Exercises
8. Graphs
8.1 Introduction
8.2 Graph Abstract Data Type
8.3 Representation of Graphs
8.3.1 Adjacency Matrix
8.3.2 Adjacency List
8.3.3 Adjacency Multilist
8.3.4 Inverse Adjacency List
8.3.5 Comparison of Sequential and Linked Representations
8.4 Graph Traversal
8.4.1 Depth-First Search
8.4.2 Breadth-First Search
8.5 Spanning Tree
8.5.1 Connected Components
8.5.2 Prim's Algorithm
8.5.3 Kruskal's Algorithm
8.5.4 Biconnected Components
8.5.5 Disjoint Set Operations
8.6 Shortest Path Algorithm
Recapitulation
Key Terms
Exercises
9. Searching and Sorting
9.1 Searching
9.2 Search Techniques
9.2.1 Sequential Search
9.2.1.1 Pros and Cons of Sequential Search
9.2.1.2 Variations of Sequential Search
9.2.2 Binary Search
9.2.2.1 Time Complexity Analysis
9.2.2.2 Pros and Cons of Binary Search
9.2.3 Fibonacci Search
9.2.3.1 Time Complexity of Fibonacci Search
9.2.4 Indexed Sequential Search
9.2.5 Hashed Search
9.3 Sorting
9.3.1 Types of Sorting
9.3.1.1 Internal Sorting
9.3.1.2 External Sorting
9.3.2 General Sort Concepts
9.3.2.1 Sort Order
9.3.2.2 Sort Stability
9.3.2.3 Sort Efficiency
9.3.2.4 Passes
9.3.3 Bubble Sort
9.3.3.1 Analysis of Bubble Sort
9.3.4 Insertion Sort
9.3.4.1 Analysis of Insertion Sort
9.3.5 Selection Sort
9.3.5.1 Analysis of Selection Sort
9.3.6 Quick Sort
9.3.6.1 Analysis of Quick Sort
9.3.7 Heap Sort
9.3.8 Shell Sort
9.3.9 Bucket Sort
9.3.10 Radix Sort
9.3.11 File Sort
9.3.12 Merge Sort
9.3.12.1 Time Complexity
9.4 Multiway Merge and Polyphase Merge
9.4.1 Comparison of Ordinary Merge Sort and Polyphase Sort
9.4.1.1 Perfect Three-File Polyphase Merge Sort
9.4.1.2 Two-Phase, Multiway Merge Sort
9.5 Comparison of All Sorting Methods
Recapitulation
Key Terms
Exercises
10. Search Trees
10.1 Symbol Table
10.1.1 Representation of Symbol Table
10.1.1.1 Static Tree Tables
10.1.1.2 Dynamic Tree Tables
10.2 Optimal Binary Search Tree
10.3 AVL Tree Height-Balanced Tree
10.3.1 Implementation of AVL Technique
10.3.2 Insertions and Deletions in AVL Tree
Recapitulation
Key Terms
Exercises
11. Hashing
11.1 Introduction
11.2 Key Terms and Issues
11.3 Hash Functions
11.3.1 Good Hash Function
11.3.1.1 Features of a Good Hashing Function
11.3.2 Division Method
11.3.3 Multiplication Method
11.3.4 Extraction Method
11.3.5 Mid-Square Hashing
11.3.6 Folding Technique
11.3.7 Rotation
11.3.8 Universal Hashing
11.4 Collision Resolution Strategies
11.4.1 Open Addressing
11.4.1.1 Linear Probing
11.4.1.2 Quadratic Probing
11.4.1.3 Double Hashing
11.4.1.4 Rehashing
11.4.2 Chaining
11.5 Hash Table Overflow
11.5.1 Open Addressing for Overflow Handling
11.5.2 Overflow Handling by Chaining
11.6 Extendible Hashing
11.7 Dictionary
11.8 Skip List
11.9 Comparison of Hashing and Skip Lists
Recapitulation
Key Terms
Exercises
12. Heaps
12.1 Basic Concepts
12.1.1 Min-Heap and Max-Heap
12.1.1.1 Min-Heap
12.1.1.2 Max-Heap
12.2 Implementation of Heap
12.3 Heap as Abstract Data Type
12.3.1 Operations on Heaps
12.3.1.1 ReheapUp
12.3.1.2 ReheapDown
12.3.1.3 Insert
12.3.1.4 Delete
12.3.1.5 Creating a Heap
12.4 Heap Applications
12.5 Heap Sort
12.6 Binomial Trees and Heaps
12.6.1 Binomial Trees
12.6.2 Binomial Heap
12.6.3 Representation of Binomial Heap
12.6.4 Operations on Binomial Heaps
12.7 Fibonacci Heap
12.7.1 Representation of Fibonacci Heap
12.7.2 Operations on Fibonacci Heaps
Recapitulation
Key Terms
Exercises
13. Indexing and Multiway Trees
13.1 Introduction
13.2 Indexing
13.2.1 Indexing Techniques
13.2.1.1 Cylinder-Surface Indexing
13.2.1.2 Hashed Indexing
13.3 Types of Search Trees
13.3.1 Multiway Search Tree
13.3.2 B-Tree
13.3.2.1 B-Tree Definition
13.3.2.2 Operations on B-Tree
13.3.2.3 B-Tree as Abstract Data Type
13.3.3 B+ Tree
13.3.3.1 B+ Tree Structure
13.3.3.2 Nodes of B+ Tree
13.3.3.3 Advantages of B+ Trees over Indexed Sequential Access Method
13.3.4 Trie Tree
13.3.4.1 Declaration for Trie Tree
13.3.5 Splay Tree
13.3.6 Red-Black Tree
13.3.7 K-Dimensional Tree
13.3.8 AA Tree
13.3.8.1 Advantages of AA Trees
13.3.8.2 Representing Balance Information in AA Tree
Recapitulation
Key Terms
Exercises
14. Files
14.1 Introduction
14.2 External Storage Devices
14.2.1 Magnetic Tape
14.2.2 Magnetic Drum
14.2.3 Magnetic Disk
14.3 File Organization
14.3.1 Schemes of File Organization
14.3.2 Factors Affecting File Organization
14.3.3 Factors Involved in Selecting File Organization
14.4 Files Using C++
14.4.1 File I/O Classes
14.4.2 Primitive Functions
14.4.3 Binary and Text Files
14.5 Sequential File Organization
14.5.1 Primitive Operations
14.5.1.1 Add
14.5.1.2 Search
14.5.1.3 Delete
14.5.1.4 Updation Modification
14.5.2 Advantages
14.5.3 Drawbacks
14.6 Direct Access File Organization
14.6.1 Primitive Operations
14.7 Indexed Sequential File Organization
14.7.1 Types of Indices
14.7.2 Structure of Indexed Sequential File
14.7.3 Characteristics of Indexed Sequential File
14.8 Linked Organization
14.8.1 Multilist Files
14.8.2 Coral Rings
14.8.3 Inverted Files
14.8.4 Cellular Partitions
Recapitulation
Key Terms
Exercises
15. Standard Template Library
15.1 Abstract Data Type
15.1.1 Abstract Data Type and Data Structures
15.1.2 Creating Abstract Data Types
15.1.3 Stack Abstract Data Type
15.2 Survey of Programming Techniques
15.3 Standard Template Library
15.3.1 Containers
15.3.1.1 Sequence Containers
15.3.1.2 Associative Containers
15.3.2 Algorithms
15.3.3 Iterators
15.3.3.1 Input Iterator
15.3.3.2 Output Iterator
15.3.3.3 Forward Iterator
15.3.3.4 Bidirectional Iterator
15.3.3.5 Random Access Iterator
15.3.3.6 Operators Supported by Iterators
15.3.3.7 Pros and Cons of Standard Template Library
15.3.4 Function Objects
Recapitulation
Key Terms
Exercises
16. Algorithm Analysis and Design
16.1 Introduction
16.1.1 Algorithm Analysis
16.1.2 Asymptotic Notations Omega, theta, O
16.1.2.1 Big O or Oh
16.1.2.2 Big Omega Omega
16.1.2.3 Big Theta Theta
16.2 Divide-and-Conquer
16.2.1 Unique Characteristics and Use
16.2.2 General Method
16.2.3 Binary Search
16.2.4 Merge Sort
16.2.4.1 Analysis of Merge Sort
16.2.5 Quick Sort
16.2.5.1 Analysis of Quicksort
16.2.6 Strassen's Algorithm for Matrix Multiplication
16.3 Greedy Method
16.3.1 General Greedy Method
16.3.1.1 Elements of Greedy Strategy
16.3.2 Knapsack Problem
16.4 Dynamic Programming
16.4.1 General Method of Dynamic Programming
16.4.2 Elements of Dynamic Programming
16.4.2.1 Optimal Substructure
16.4.2.2 Overlapping Subproblems
16.4.2.3 Memorization
16.4.3 Principle of Optimality
16.4.3.1 Difference between Greedy Method and Dynamic Programming
16.4.4 Limitations of Dynamic Programming
16.4.5 Knapsack Problem
16.5 Pattern Matching
16.5.1 Brute-Force Approach
16.5.2 Boyer-Moore Algorithm
16.5.3 Knuth-Morris-Pratt Algorithm
16.5.3.1 Prefix Function pi
16.5.3.2 KMP Matcher
16.6 Tries
16.6.1 Standard Tries
16.6.2 Compressed Tries
16.6.3 Suffix Tries
Recapitulation
Key Terms
Exercises
Features of the Book
Appendix: Overview of C++ Programming
A.1 Abstract Data Type
A.2 Introduction to C++
A.2.1 Sample C++ Program
A.2.2 C++ Statements and Operators
A.2.3 Comments in C++
A.2.4 Input/Output in C++
A.3 Functions in C++
A.3.1 Inline Function
A.4 C++ Class and Abstract Data Type
A.4.1 Class
A.4.1.1 Scope Resolution Operator ::
A.4.2 Class Members: Public and Private
A.4.3 Objects
A.5 Static Class Members
A.5.1 Static Data Members
A.5.2 Static Member Functions
A.6 Object as Function Parameter
A.6.1 Passing Objects to Functions
A.6.2 Returning Objects from Functions
A.6.3 Arrays of Objects
A.6.4 Pointers to Objects
A.7 'this' Pointer
A.8 Function Overloading
A.8.1 Types of Polymorphism
A.9 Constructors and Destructors
A.9.1 Constructors
A.9.2 Destructors
A.9.3 Constructor with Default Arguments
A.10 Inheritance
A.10.1 Types of Inheritance
A.10.2 Multiple Inheritance
A.11 Abstract Classes
A.11.1 Pure Virtual Functions
A.12 Operator Overloading
A.12.1 Comparing Function Overriding and Overloading
A.13 Friend Function
A.14 Generic Programming: Templates
Acknowledgements
Index
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
V
W