C++ Data Structures and Algorithms : Learn How to Write Efficient Code to Build Scalable and Robust Applications in C++

Learn how to build efficient, secure and robust code in C++ by using data structures and algorithms - the building blocks of C++ Key Features Use data structures such as arrays, stacks, trees, lists, and graphs with real-world examples Learn the functional and reactive implementations of the traditional data structures Explore illustrations to present data structures and algorithms, as well as their analysis, in a clear, visual manner Book Description C++ is a general-purpose programming language which has evolved over the years and is used to develop software for many different sectors. This book will be your companion as it takes you through implementing classic data structures and algorithms to help you get up and running as a confident C++ programmer. We begin with an introduction to C++ data structures and algorithms while also covering essential language constructs. Next, we will see how to store data using linked lists, arrays, stacks, and queues. Then, we will learn how to implement different sorting algorithms, such as quick sort and heap sort. Along with these, we will dive into searching algorithms such as linear search, binary search and more. Our next mission will be to attain high performance by implementing algorithms to string datatypes and implementing hash structures in algorithm design. We'll also analyze Brute Force algorithms, Greedy algorithms, and more. By the end of the book, you'll know how to build components that are easy to understand, debug, and use in different applications. What you will learn Know how to use arrays and lists to get better results in complex scenarios Build enhanced applications by using hashtables, dictionaries, and sets Implement searching algorithms such as linear search, binary search, jump search, exponential search, and more Have a positive impact on the efficiency of applications with tree traversal Explore the design used in sorting algorithms like Heap sort, Quick sort, Merge sort and Radix sort Implement various common algorithms in string data types Find out how to design an algorithm for a specific task using the common algorithm paradigms Who This Book Is For This book is for developers who would like to learn the Data Structures and Algorithms in C++. Basic C++ programming knowledge is expected. Table of Contents Learning Data Structures and Algorithms in C++ Storing Data in Lists and Linked Lists Constructing stacks and queues Arranging data elements using sorting algorithm Finding out an element using searching algorithm Dealing with strings Building hierarchical tree structure Associating a value to a key in hash table Designing an algorithm Cover Title Page Copyright and Credits Packt Upsell Contributors Table of Contents Preface Chapter 1: 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 Chapter 2: 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 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 Chapter 3: 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 Chapter 4: 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 Chapter 5: 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 Chapter 6: 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 Chapter 7: 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 Chapter 8: 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 Chapter 9: 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 Index Learn how to build efficient, secure and robust code in C++ by using data structures and algorithms - the building blocks of C++ About This Book Use data structures such as arrays, stacks, trees, lists, and graphs with real-world examples Learn the functional and reactive implementations of the traditional data structures Explore illustrations to present data structures and algorithms, as well as their analysis, in a clear, visual manner Who This Book Is For This book is for developers who would like to learn the Data Structures and Algorithms in C++. Basic C++ programming knowledge is expected. What You Will Learn Know how to use arrays and lists to get better results in complex scenarios Build enhanced applications by using hashtables, dictionaries, and sets Implement searching algorithms such as linear search, binary search, jump search, exponential search, and more Have a positive impact on the efficiency of applications with tree traversal Explore the design used in sorting algorithms like Heap sort, Quick sort, Merge sort and Radix sort Implement various common algorithms in string data types Find out how to design an algorithm for a specific task using the common algorithm paradigms In Detail C++ is a general-purpose programming language which has evolved over the years and is used to develop software for many different sectors. This book will be your companion as it takes you through implementing classic data structures and algorithms to help you get up and running as a confident C++ programmer. We begin with an introduction to C++ data structures and algorithms while also covering essential language constructs. Next, we will see how to store data using linked lists, arrays, stacks, and queues. Then, we will learn how to implement different sorting algorithms, such as quick sort and heap sort. Along with these, we will dive into searching algorithms such as linear search, binary search and more. Our next mission will be to attain high performance by implementing algorithms to string datatypes and implementing hash structures in algorithm design. We'll also analyze Brute Force algorithms, Greedy algorithms, and more. By the end of the book, you'll know how to build components that are easy to understand, debug, and use in different applications. Style and approach Readers will be taken through an indispensable list of data structures and algorithms so they can confidently begin coding in C++. Downloading the example code for this book Y ..