C++ Data Structures and Algorithms

Title Page
Copyright and Credits
C++ Data Structures and Algorithms
Packt Upsell
Why subscribe?
PacktPub.com
Contributors
About the author
About the reviewer
Packt is searching for authors like you
Preface
Who this book is for
What this book covers
To get the most out of this book
Download the example code files
Download the color images
Conventions used
Get in touch
Reviews
Learning Data Structures and Algorithms in C++
Technical requirements
Introduction to basic C++
Creating your first code in C++
Enhancing code development experience with IDE
Defining the variables using fundamental data types
Controlling the flow of the code
Conditional statement
Loop statement
Leveraging the variable capability using advanced data types
Developing abstract data types
Applying C++ classes to build user-defined ADTs
Playing with templates
Function templates
Class templates
Standard Template Library
Analyzing the algorithm
Asymptotic analysis
Worst, average, and best cases
Big Theta, Big-O, and Big Omega
Recursive method
Amortized analysis
Summary
QA section
Further reading
Storing Data in Lists and Linked Lists
Technical requirements
Getting closer to an array
Building a List ADT
Fetching an item in the List
Inserting an item into the List ADT
Finding out the index of a selected item in the List ADT
Removing an item from the List ADT
Consuming a List ADT
Introduction to node
Building a Singly Linked List ADT
Fetching an item in the LinkedList class
Inserting an item in the LinkedList class
Getting the index of the selected item in the LinkedList
Removing an item from the LinkedList ADT
Consuming the LinkedList ADT
Building the Doubly Linked List ADT
Refactoring the Node<T> data type
Refactoring several operations in the LinkedList ADT
Removing an element
Inserting an element
Consuming the DoublyLinkedList ADT
Applying List and LinkedList using STL
std::vector
std::list
Summary
QA section
Further reading
Constructing Stacks and Queues
Technical requirements
Building a Stack ADT
Fetching the item's value in the Stack ADT
Pushing the items of the Stack ADT
Popping the items from the Stack ADT
Consuming a Stack ADT
Another example of Stack ADT implementation
Building a Queue ADT
Getting a value from Queue ADT
Inserting an element into the Queue ADT
Removing an element from the Queue ADT
Consuming the Queue ADT
Building a Deque ADT
Fetching a value from a Deque
Enqueueing an element into the Deque ADT
Dequeuing an element from the Deque ADT
Consuming the Deque ADT
Summary
QA section
Further reading
Arranging Data Elements Using a Sorting Algorithm
Technical requirements
Bubble sort
Selection sort
Insertion sort
Merge sort
Quick sort
Counting sort
Radix sort
Summary
QA section
Further reading
Finding out an Element Using Searching Algorithms
Technical requirements
Linear search
Developing a linear search algorithm
Implementing the linear search algorithm
Binary search
Developing binary search algorithm
Implementing binary search algorithm 
Ternary search
Developing ternary search algorithm
Applying the ternary search algorithm
Interpolation search
Developing interpolation search algorithm
Applying interpolation search algorithm
Jump search
Developing jump search algorithm
Applying jump search algorithm
Exponential search
Developing exponential search algorithm
Invoking the ExponentialSearch() function
Sublist search
Designing sublist search algorithm
Performing sublist search algorithm
Summary
QA section
Further reading
Dealing with the String Data Type
Technical requirement
String in C++
Constructing a string using character array
Using std::string for more flexibility features
Playing with words
Rearranging a word to create an anagram
Detecting whether a word is a palindrome
Constructing a string from binary digits
Converting decimal to binary string
Converting binary string to decimal
Subsequence string
Generating subsequences from a string
Checking whether a string is a subsequence of another string
Pattern searching
Summary
QA section
Further reading
Building a Hierarchical Tree Structure
Technical requirements
Building a binary tree ADT
Building a binary search tree ADT
Inserting a new key into a BST
Traversing a BST in order
Finding out whether a key exists in a BST
Retrieving the minimum and maximum key values
Finding out the successor of a key in a BST
Finding out the predecessor of a key in a BST
Removing a node based on a given key
Implementing the BST ADT
Building a balanced BST (AVL) ADT
Rotating nodes
Inserting a new key
Removing a given key
Implementing AVL ADT
Building a binary heap ADT
Checking if the heap is empty
Inserting a new element into the heap
Fetching the element's maximum value
Removing the maximum element
Implementing a binary heap as a priority queue
Summary
QA section
Further reading
Associating a Value to a Key in a Hash Table
Technical requirement
Getting acquainted with hash tables
Big data in small cells
Storing data in a hash table
Collision handling
Implementing a separate chaining technique
Generating a hash key
Developing an Insert() operation
Developing a Search() operation
Developing a Remove() operation
Developing an IsEmpty() operation
Applying a HashTable ADT using a separate chaining technique in the code
Implementing the open addressing technique
Developing the Insert() operation
Developing a Search() operation
Developing the Remove() operation
Developing an IsEmpty() operation
Developing a PrintHashTable() operation
Applying an HashTable ADT using a linear probing technique in the code
Summary
QA section
Further reading
Implementation of Algorithms in Real Life
Technical requirements
Greedy algorithms
Solving the coin-changing problem
Applying the Huffman coding algorithm
Divide and conquer algorithms
Solving selection problems
Solving matrix multiplication calculations
Dynamic programming
Fibonacci numbers
Dynamic programming and the coin-change problem
Brute-force algorithms
Brute-force search and sort
Strengths and weaknesses of brute-force algorithms
Randomized algorithms
Rаndоm algorіthm classification
Random number generators
Applications of randomized algorithms
Backtracking algorithms
Arranging furniture in a new house
Playing tic-tac-toe
Summary
QA section
Further reading
Other Books You May Enjoy
Leave a review - let other readers know what you think