Data Structures and Algorithms Using C++ by Pearson

Data Structures and Algorithms Using C++ by Pearson

by Ananda Rao Akepogu, Radhika Raju Palagiri
Released May 2024
Publisher(s): Pearson India
ISBN: 9781282839946

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 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.

About The Authors –

Ananda Rao Akepogu is Professor and Head of the Computer Science and Engineering Department and Vice Principal of Jawaharlal Nehru Technological University Anantapur College of Engineering Anantapur. He is an alumnus of IIT Madras, Chennai. He received his B.Tech. (CSE) and M.Tech. (AI and Robotics) degrees from the University of Hyderabad, Andhra Pradesh, and his Ph.D. degree from IIT Madras, Chennai. He has 18 years of teaching experience in JNT University. He has published around 50 papers in various international and national journals and conferences. He has also worked on Programming in C and Data Structures by J. R. Hanly, E. B. Koff man and A. Kamthane and Database Management Systems by Peter Rob and Carlos Coronel. His research interests include Artifi cial Intelligence, Soft ware Engineering, Cloud Computing and Object-oriented Databases.

Radhika Raju Palagiri is presently working as an ad hoc lecturer in the Computer Science and Engineering Department, Jawaharlal Nehru Technological University Anantapur College of Engineering Anantapur. She received her M.Tech. in Computer Science from JNTU Anantapur. She has 13 years of teaching experience at the undergraduate and postgraduate levels. Her areas of interest lie in Soft ware Engineering and Expert Systems.

Table of contents

  1. Cover
  2. Data Structures and Algorithms Using C++
  3. Copyright
  4. Contents
  5. About the Authors
  6. Preface
  7. Acknowledgements
  8. 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 (1/2)
    11. 1.10 Exception Handling (2/2)
      1. Summary
      2. Exercises
  9. 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
      1. Summary
      2. Exercises
  10. 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
      4. Summary
      5. Exercises
  11. 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
      1. Summary
      2. Exercises
  12. 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
      2. Summary
      3. Exercises
  13. 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. Excercises
  14. 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 (1/2)
      3. 7.3.2 Enqueue and Deque Using Linked List (2/2)
    4. 7.4 Circular Queues
      1. 7.4.1 Operations on Circular Queue (1/2)
      2. 7.4.1 Operations on Circular Queue (2/2)
    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
      3. Summary
      4. Exercises
  15. 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 (1/2)
      3. 8.5.2 Open Addressing (2/2)
    6. 8.6 Comparison of Chaining and Open Addressing
    7. 8.7 Applications
    8. 8.8 Dictionary ADT
      1. Summary
      2. Exercises
  16. 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 (1/2)
    7. 9.6 Binary Tree Operations (2/2)
    8. 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
    9. 9.8 Conversion of a Tree into a Binary Tree
    10. 9.9 Threaded Binary Trees
      1. 9.9.1 Linked Representation of a Threaded Binary Tree
    11. 9.10 Applications of Binary Trees
      1. 9.10.1 Traversal of an Expression Tree
      2. 9.10.2 Operations on Expression Trees
    12. 9.11 ADT of Binary Tree
      1. Summary
      2. Exercises
  17. 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
      1. Summary
      2. Exercises
  18. 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 (1/2)
      4. 11.3.3 Min Heap–Deletion (2/2)
      5. 11.3.4 Max Heap–Insertion
      6. 11.3.5 Max Heap–Deletion (1/2)
      7. 11.3.5 Max Heap–Deletion (2/2)
    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 (1/2)
      3. 11.5.2 Multiway Merge (2/2)
      4. Summary
      5. Exercises
  19. 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 (1/2)
      5. 12.3.4 Disadvantages of Binary Search Tree (2/2)
    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 (1/3)
      4. 12.5.3 Deletion (2/3)
      5. 12.5.3 Deletion (3/3)
    6. 12.6 Applications
      1. Summary
      2. Exercises
  20. 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 (1/3)
      4. 13.5.3 Deletion (2/3)
      5. 13.5.3 Deletion (3/3)
    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
      2. Summary
      3. Exercises
  21. 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 (1/5)
      4. 14.3.3 Deletion (2/5)
      5. 14.3.3 Deletion (3/5)
      6. 14.3.3 Deletion (4/5)
      7. 14.3.3 Deletion (5/5)
    4. 14.4 Splay Trees
      1. 14.4.1 Splay Rotations
      2. 14.4.2 Amortized Analysis (1/2)
      3. 14.4.2 Amortized Analysis (2/2)
    5. 14.5 Applications
      1. Summary
      2. Exercises
  22. 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 Th e 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
      1. Summary
      2. Exercises
  23. 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 (1/2)
      9. 16.1.8 Heap Sort (2/2)
    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
      4. Summary
      5. Exercises
  24. Index

Product information

  • Title: Data Structures and Algorithms Using C++ by Pearson
  • Author(s): Ananda Rao Akepogu, Radhika Raju Palagiri
  • Release date: May 2024
  • Publisher(s): Pearson India
  • ISBN: 9781282839946