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