Data Structures and Algorithms Using C++

Data Structures and Algorithms Using C++

Released July 2010
Publisher(s): Pearson India
ISBN: 9789332511996

Read it now on the O’Reilly learning platform with a 10-day free trial.

O’Reilly members get unlimited access to books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Start your free trial

Book description

Data Structures and Algorithms Using C++ helps students 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.

Table of contents

  1. Cover
  2. Title page
  3. Contents
  4. About the Authors
  5. Preface
  6. Chapter 1. Introduction to C++
    1. 1.1 Introduction
    2. 1.2 Class Overview
      1. 1.2.1 Class
      2. 1.2.2 Objects
      3. 1.2.3 Class Members
    3. 1.3 I/O Streams
    4. 1.4 Access Control
    5. 1.5 Class Scope
    6. 1.6 Static Class Members
      1. 1.6.1 Static Member Variables
      2. 1.6.2 Static Member Function
      3. 1.6.3 Static Object
    7. 1.7 Functions
      1. 1.7.1 Parameter Passing Methods
      2. 1.7.2 Inline Functions
      3. 1.7.3 The friend Function
      4. 1.7.4 Function Overloading
    8. 1.8 The this Pointer
    9. 1.9 Dynamic Memory Allocation and Deallocation
      1. 1.9.1 The new Operator
      2. 1.9.2 The delete Operator
    10. 1.10 Exception Handling
    11. Summary
    12. Exercises
  7. Chapter 2. Object Oriented Concepts
    1. 2.1 Goals and Principles
      1. 2.1.1 Object Oriented Design Goals
      2. 2.1.2 Object Oriented Design Principles
    2. 2.2 Constructors and Destructors
      1. 2.2.1 Constructors
      2. 2.2.2 Constructor Overloading
      3. 2.2.3 Destructors
    3. 2.3 Operator Overloading
      1. 2.3.1 Overloading the Plus (+) Operator
      2. 2.3.2 Overloading the Minus (-) Operator
      3. 2.3.3 Overloading Unary Operators
      4. 2.3.4 Postfix form of Overloading the Unary Operator ++
      5. 2.3.5 Prefix form of Overloading the Unary Operator−−
      6. 2.3.6 Postfix form of Overloading the Unary Operator−−
    4. 2.4 Inheritance
      1. 2.4.1 Base Class Access Control
      2. 2.4.2 Types of Inheritance
      3. 2.4.3 Reasons for the Usage of Inheritance
      4. 2.4.4 Advantages
      5. 2.4.5 Disadvantages
      6. 2.4.6 Delegation
    5. 2.5 Polymorphism
      1. 2.5.1 Virtual Functions
      2. 2.5.2 Pure Virtual Functions
    6. 2.6 Abstract Classes
    7. 2.7 Generic Programming with Templates
      1. 2.7.1 Function Templates
      2. 2.7.2 Class Templates
    8. 2.8 Recursion
    9. Summary
    10. Exercises
  8. Chapter 3. Algorithms
    1. 3.1 Introduction
    2. 3.2 Basic Notations
      1. 3.2.1 Pseudo Code
    3. 3.3 Types of Algorithms
      1. 3.3.1 Brute Force Algorithms
      2. 3.3.2 Divide and Conquer Algorithms
      3. 3.3.3 Dynamic Programming Algorithms
      4. 3.3.4 Greedy Algorithms
      5. 3.3.5 Branch and Bound Algorithms
      6. 3.3.6 Recursive Algorithms
      7. 3.3.7 Back Tracking Algorithms
      8. 3.3.8 Randomized Algorithms
      9. 3.3.9 Hill Climbing Algorithms
    4. 3.4 Performance Analysis
      1. 3.4.1 Properties of the Best Algorithms
    5. 3.5 Space Complexity
      1. 3.5.1 Instruction Space
      2. 3.5.2 Text Section of a Program
      3. 3.5.3 Data Space
      4. 3.5.4 Stack Space
      5. 3.5.5 Calculating the Instruction Space
      6. 3.5.6 Calculating the Data Space
      7. 3.5.7 Size of Data Section
      8. 3.5.8 Size of Rodata Section
      9. 3.5.9 Size of bss Section
    6. 3.6 Apriori Analysis
    7. 3.7 Asymptotic Notation
      1. 3.7.1 Big oh Notation (O)
      2. 3.7.2 Omega Notation (Ω)
      3. 3.7.3 Theta Notation (θ)
      4. 3.7.4 Little oh Notation(o)
    8. 3.8 Time Complexity
      1. 3.8.1 Time Complexity Analysis of Bubble Sort
      2. 3.8.2 Time Complexity Analysis of Selection Sort
    9. 3.9 Worst Case, Average Case and Best Case Complexity
      1. 3.9.1 Worst Case
      2. 3.9.2 Average Case
      3. 3.9.3 Best Case
    10. Summary
    11. Exercises
  9. Chapter 4. Arrays
    1. 4.1 Introduction
      1. 4.1.1 Array
    2. 4.2 Array Types
      1. 4.2.1 Single-dimensional Array
      2. 4.2.2 Multi-dimensional Array
      3. 4.2.3 N-dimensional Array
    3. 4.3 Array Representation
    4. 4.4 Initializing Arrays
    5. 4.5 Accessing Values of an Array
    6. 4.6 Array Operations
      1. 4.6.1 Traversing
      2. 4.6.2 Insertion
      3. 4.6.3 Deletion
      4. 4.6.4 Sorting
      5. 4.6.5 Searching
    7. 4.7 Arrays as Parameters
    8. 4.8 Character Sequences
    9. 4.9 Applications
    10. Summary
    11. Exercises
  10. Chapter 5. Linked List
    1. 5.1 Introduction
    2. 5.2 Representation of Linked List in Memory
      1. 5.2.1 Static Representation
      2. 5.2.2 Dynamic Representation
    3. 5.3 Singly Linked List
      1. 5.3.1 Operations
    4. 5.4 Circular Linked List
      1. 5.4.1 Merging of Two Circular Lists
    5. 5.5 Doubly Linked Lists
      1. 5.5.1 Representation of Doubly Linked List
      2. 5.5.2 Operations
    6. 5.6 Comparison of Various Linked Lists
      1. 5.6.1 Linked Lists Versus Arrays
    7. 5.7 Applications
      1. 5.7.1 Polynomial Manipulation
    8. Summary
    9. Exercises
  11. Chapter 6. Stacks
    1. 6.1 Definition
    2. 6.2 Representation of a Stack
      1. 6.2.1 Array Representation of a Stack
      2. 6.2.2 Linked Representation of a Stack
    3. 6.3 Operations on Stack
      1. 6.3.1 Array Implementation of a Stack
      2. 6.3.2 Linked Implementation of a Stack
    4. 6.4 Applications of Stacks
      1. 6.4.1 Expression Evaluation
      2. 6.4.2 Postfix Evaluation
      3. 6.4.3 Recursion
      4. 6.4.4 Balancing of the Matching Parenthesis
    5. Summary
    6. Exercises
  12. Chapter 7. Queues
    1. 7.1 Introduction
    2. 7.2 Representation of a Queue
      1. 7.2.1 Array Representation
      2. 7.2.2 Linked Representation
    3. 7.3 Operations on a Queue
      1. 7.3.1 Enqueue and Deque Using Arrays
      2. 7.3.2 Enqueue and Deque Using Linked List
    4. 7.4 Circular Queues
      1. 7.4.1 Operations on Circular Queue
    5. 7.5 Deque
      1. 7.5.1 Operations on a Deque
    6. 7.6 Applications of Queues
      1. 7.6.1 Simulation of Time-sharing System
      2. 7.6.2 Queue ADT
    7. Summary
    8. Exercises
  13. Chapter 8. Dictionaries
    1. 8.1 Dictionaries
    2. 8.2 Linear List Representation
    3. 8.3 Skip Lists Representation
      1. 8.3.1 Operations
      2. 8.3.2 Searching
      3. 8.3.3 Insertion
      4. 8.3.4 Deletion
    4. 8.4 Hash Table
      1. 8.4.1 Hash Functions
    5. 8.5 Collisions
      1. 8.5.1 Separate Chaining
      2. 8.5.2 Open Addressing
    6. 8.6 Comparison of Chaining and Open Addressing
    7. 8.7 Applications
    8. 8.8 Dictionary ADT
    9. Summary
    10. Exercises
  14. Chapter 9. Trees and Binary Trees
    1. 9.1 Introduction
    2. 9.2 Terminologies
    3. 9.3 Representation of a Tree
    4. 9.4 Binary Trees
    5. 9.5 Representation of Binary Trees
      1. 9.5.1 Array Representation of a Binary Tree
      2. 9.5.2 Linked Representation of Binary Trees
    6. 9.6 Binary Tree Operations
    7. 9.7 Binary Tree Traversals
      1. 9.7.1 Inorder Traversal (LVR)
      2. 9.7.2 Preorder Traversal (VLR)
      3. 9.7.3 Postorder Traversal (LRV)
      4. 9.7.4 Level-order Traversal
    8. 9.8 Conversion of a Tree into a Binary Tree
    9. 9.9 Threaded Binary Trees
      1. 9.9.1 Linked Representation of a Threaded Binary Tree
    10. 9.10 Applications of Binary Trees
      1. 9.10.1 Traversal of an Expression Tree
      2. 9.10.2 Operations on Expression Trees
    11. 9.11 ADT of Binary Tree
    12. Summary
    13. Exercises
  15. Chapter 10. Graphs
    1. 10.1 Introduction
    2. 10.2 Basic Terminology
    3. 10.3 Representation of Graphs
      1. 10.3.1 Sequential Representation of Graphs
      2. 10.3.2 Linked Representation of Graphs
    4. 10.4 Operations on Graphs
    5. 10.5 Graph Traversals
      1. 10.5.1 Breadth First Traversal
      2. 10.5.2 Depth First Traversal
    6. 10.6 Applications
    7. 10.7 Graph ADT
    8. Summary
    9. Exercises
  16. Chapter 11. Priority Queues
    1. 11.1 Introduction
    2. 11.2 Priority Queue ADT
    3. 11.3 Priority Queue Implementation Using Heaps
      1. 11.3.1 Priority Queue Interface
      2. 11.3.2 Min Heap-Insertion
      3. 11.3.3 Min Heap-Deletion
      4. 11.3.4 Max Heap-Insertion
      5. 11.3.5 Max Heap-Deletion
    4. 11.4 Applications
      1. 11.4.1 Job Scheduling
    5. 11.5 External Sorting
      1. 11.5.1 Polyphase Merge
      2. 11.5.2 Multiway Merge
    6. Summary
    7. Exercises
  17. Chapter 12. Binary Search Trees and AVL Trees
    1. 12.1 Binary Search Trees
    2. 12.2 Representation of a Binary Search Tree
    3. 12.3 Operations on Binary Search Trees
      1. 12.3.1 Searching
      2. 12.3.2 Insertion
      3. 12.3.3 Deletion
      4. 12.3.4 Disadvantages of Binary Search Tree
    4. 12.4 AVL Trees
    5. 12.5 Operation of AVL Search Trees
      1. 12.5.1 Searching
      2. 12.5.2 Insertion
      3. 12.5.3 Deletion
    6. 12.6 Applications
    7. Summary
    8. Exercises
  18. Chapter 13. Multiway Trees and B Trees
    1. 13.1 Introduction
    2. 13.2 Representation of a Node Structure
    3. 13.3 Operations on m-Way Search Trees
      1. 13.3.1 Searching
      2. 13.3.2 Insertion
      3. 13.3.3 Deletion
      4. 13.3.4 Drawbacks of m-Way Search Trees
    4. 13.4 B Trees
    5. 13.5 Operations on B Trees
      1. 13.5.1 Searching
      2. 13.5.2 Insertion
      3. 13.5.3 Deletion
    6. 13.6 Height of B Trees
    7. 13.7 Variations of B Tree
      1. 13.7.1 B* Tree
      2. 13.7.2 B+ Tree
    8. 13.8 Applications
      1. 13.8.1 Databases
    9. Summary
    10. Exercises
  19. Chapter 14. Red-Black Trees and Splay Trees
    1. 14.1 Introduction
    2. 14.2 Representation of a Red-Black Tree
    3. 14.3 Operations
      1. 14.3.1 Searching
      2. 14.3.2 Insertion
      3. 14.3.3 Deletion
    4. 14.4 Splay Trees
      1. 14.4.1 Splay Rotations
      2. 14.4.2 Amortized Analysis
    5. 14.5 Applications
    6. Summary
    7. Exercises
  20. Chapter 15. Pattern Matching and Tries
    1. 15.1 Introduction
    2. 15.2 Terminology
    3. 15.3 Pattern Matching Algorithms
      1. 15.3.1 Fixed Pattern Matching Algorithms
      2. 15.3.2 Regular Expression Pattern Matching
    4. 15.4 Fixed Pattern Matching Algorithms
      1. 15.4.1 Brute Force Pattern Matching Algorithm
      2. 15.4.2 The Boyer-Moore Algorithm
      3. 15.4.3 Knuth-Morris-Pratt Algorithm (KMP)
    5. 15.5 Applications of Pattern Matching Algorithms
    6. 15.6 Tries
      1. 15.6.1 Standard Tries
      2. 15.6.2 Compressed Tries
      3. 15.6.3 Suffix Tries
    7. 15.7 Applications of Tries
    8. Summary
    9. Exercises
  21. Chapter 16. Sorting and Searching
    1. 16.1 Sorting
      1. 16.1.1 Bubble Sort
      2. 16.1.2 Insertion Sort
      3. 16.1.3 Selection Sort
      4. 16.1.4 Quick Sort
      5. 16.1.5 Merge Sort
      6. 16.1.6 Shell Sort
      7. 16.1.7 Radix Sort
      8. 16.1.8 Heap Sort
    2. 16.2 Searching
      1. 16.2.1 Linear Search or Sequential Search
      2. 16.2.2 Binary Search
      3. 16.2.3 Fibonacci Search
    3. Summary
    4. Exercises
  22. Solved Question Papers
  23. Acknowledgements
  24. Copyright

Product information

  • Title: Data Structures and Algorithms Using C++
  • Author(s):
  • Release date: July 2010
  • Publisher(s): Pearson India
  • ISBN: 9789332511996