book

Data Structures and Algorithms Using C++ by Pearson

Name: Data Structures and Algorithms Using C++ by Pearson
ISBN: 9781282839946

by Ananda Rao Akepogu, Radhika Raju Palagiri

May 2024

Intermediate to advanced

578 pages

17h 12m

English

Pearson India

Read now

Unlock full access

Cover
Data Structures and Algorithms Using C++
Copyright
About the Authors
Contents
Preface
Acknowledgements
Chapter 1 Introduction to C++
1.1 Introduction1.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 (1/2)
1.10 Exception Handling (2/2)
Summary
Exercises
Chapter 2 Object Oriented Concepts
2.1 Goals and Principles2.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 Disadvantages2.4.6 Delegation2.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 Introduction3.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 Algorithms3.3.3 Dynamic Programming Algorithms3.3.4 Greedy Algorithms3.3.5 Branch and Bound Algorithms3.3.6 Recursive Algorithms
3.3.7 Back Tracking Algorithms
3.3.8 Randomized Algorithms3.3.9 Hill Climbing Algorithms3.4 Performance Analysis3.4.1 Properties of the Best Algorithms
3.5 Space Complexity
3.5.1 Instruction Space3.5.2 Text Section of a Program3.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 Section3.5.8 Size of Rodata Section3.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 Case3.9.2 Average Case3.9.3 Best CaseSummary
Exercises
Chapter 4 Arrays
4.1 Introduction
4.1.1 Array
4.2 Array Types4.2.1 Single-dimensional Array4.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 List5.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 Representation7.2.2 Linked Representation7.3 Operations on a Queue
7.3.1 Enqueue and Deque Using Arrays
7.3.2 Enqueue and Deque Using Linked List (1/2)
7.3.2 Enqueue and Deque Using Linked List (2/2)
7.4 Circular Queues
7.4.1 Operations on Circular Queue (1/2)
7.4.1 Operations on Circular Queue (2/2)
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 Dictionaries8.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 (1/2)
8.5.2 Open Addressing (2/2)
8.6 Comparison of Chaining and Open Addressing
8.7 Applications
8.8 Dictionary ADT
SummaryExercises
Chapter 9 Trees and Binary Trees
9.1 Introduction9.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 (1/2)
9.6 Binary Tree Operations (2/2)
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 Tree9.10.2 Operations on Expression Trees
9.11 ADT of Binary Tree
Summary
Exercises
Chapter 10 Graphs
10.1 Introduction10.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 (1/2)
11.3.3 Min Heap–Deletion (2/2)
11.3.4 Max Heap–Insertion
11.3.5 Max Heap–Deletion (1/2)
11.3.5 Max Heap–Deletion (2/2)
11.4 Applications
11.4.1 Job Scheduling
11.5 External Sorting
11.5.1 Polyphase Merge
11.5.2 Multiway Merge (1/2)
11.5.2 Multiway Merge (2/2)
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 Trees12.3.1 Searching
12.3.2 Insertion
12.3.3 Deletion
12.3.4 Disadvantages of Binary Search Tree (1/2)
12.3.4 Disadvantages of Binary Search Tree (2/2)
12.4 AVL Trees
12.5 Operation of AVL Search Trees
12.5.1 Searching12.5.2 Insertion
12.5.3 Deletion (1/3)
12.5.3 Deletion (2/3)
12.5.3 Deletion (3/3)
12.6 Applications
SummaryExercises
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 Searching13.3.2 Insertion13.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 Searching13.5.2 Insertion
13.5.3 Deletion (1/3)
13.5.3 Deletion (2/3)
13.5.3 Deletion (3/3)
13.6 Height of B Trees
13.7 Variations of B Tree13.7.1 B* Tree
13.7.2 B+ Tree
13.8 Applications13.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 (1/5)
14.3.3 Deletion (2/5)
14.3.3 Deletion (3/5)
14.3.3 Deletion (4/5)
14.3.3 Deletion (5/5)
14.4 Splay Trees
14.4.1 Splay Rotations
14.4.2 Amortized Analysis (1/2)
14.4.2 Amortized Analysis (2/2)
14.5 Applications
Summary
Exercises
Chapter 15 Pattern Matching and Tries
15.1 Introduction15.2 Terminology
15.3 Pattern Matching Algorithms
15.3.1 Fixed Pattern Matching Algorithms15.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 Sorting16.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 (1/2)
16.1.8 Heap Sort (2/2)
16.2 Searching
16.2.1 Linear Search or Sequential Search
16.2.2 Binary Search
16.2.3 Fibonacci Search
Summary
Exercises
Index

Content preview from Data Structures and Algorithms Using C++ by Pearson

Chapter 16 Sorting and Searching | 16.9

Pass

[1] [2] [3] [4] [5] [6] [7] [8]

K=1, POS=4 88 44 55 22 99 33 77 66

K=2, POS=6 22 44 55 88 99 33 77 66

K=3, POS=6 22 33 55 88 99 44 77 66

K=4, POS=6 22 33 44 88 99 55 77 66

K=5, POS=8 22 33 44 55 99 88 77 66

K=6, POS=7 22 33 44 55 66 88 77 99

K=7, POS=7 22 33 44 55 66 77 88 99

Sorted array is 22 33 44 55 66 77 88 99

Figure 16.3

Trace of selection sort

Observe that in Figure 16.3 POS gives the smallest among DATA[K], DATA[K+1], ..., DATA[N] during

pass K.  e circled elements indicate the elements which are to be swapped. In a similar way all the elements

will be sorted.

Complexity: ...

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.

Read now

Unlock full access

More than 5,000 organizations count on O’Reilly

O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.

Julian F.

Head of Cybersecurity

I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.

Addison B.

Field Engineer

I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.

Amir M.

Data Platform Tech Lead

I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.

Mark W.

Embedded Software Engineer

Data Structures and Algorithms Using C++

Publisher Resources

ISBN: 9781282839946Publisher Website Publisher Website

Cloud Computing

Data Engineering

Data Science

AI & ML

Programming Languages

Software Architecture

IT/Ops

Security

Design

Business

Soft Skills

Data Structures and Algorithms Using C++ by Pearson

by Ananda Rao Akepogu, Radhika Raju Palagiri

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.

More than 5,000 organizations count on O’Reilly

Julian F.

Addison B.

Amir M.

Mark W.

You might also like

Data Structures and Algorithms Using C++

C++ Data Structures and Algorithms

Data Structures and Algorithms with the C++ STL

C++ Data Structures and Algorithm Design Principles

Publisher Resources