Data Structures and Algorithms in C++ Best Guide

Here is a complete guide on Data Structures and Algorithms in C++

Learn Data Structures and Algorithms in C++

Data Structures and Algorithms in C:

Data structure is an arrangement of data in a computer’s memory or disk. Data structures include Arrays, StacksQueues, linked lists, binary trees, and hash tables, and etc.

Data Structure = Organized Data + Allowed Operations.

An Algorithm is sequence of non ambiguous instructions for solving a problem in a finite amount of a time.

Types of Data Structures and Algorithms:

Types of Data Structure

Types of Data Structures

Types of Algorithms:

  • Simple recursive algorithms.
  • Backtracking algorithms.
  • Divide and conquer algorithms.
  • Dynamic programming algorithms.
  • Greedy algorithms.
  • Branch and bound algorithms.
  • Brute force algorithms.
  • Randomized algorithms

List of All C Programming, Data Structures and Algorithms

Data Types

Primitive Types

  • Boolean, true or false.
  • Character
  • Floating-point numbers, limited-precision approximations of real number values.
  • Including single-precision and double-precision IEEE 754 floats, among others
  • Fixed-point numbers
  • Integer, integral or fixed-precision values
  • Reference (also called a pointer or handle), a small value referring to another object’s address in memory, possibly a much larger one
  • Enumerated type, a small set of uniquely named values
  • Date Time, value referring to Date and Time

Composite types or non-primitive type

  • Array
  • Record also called structure
  • Union

Abstract Data types

  • Container
  • List
  • Tuple
  • Associative array, Map
  • Multimap
  • Set
  • Multiset (bag)
  • Stack
  • Queue (example Priority queue)
  • Double-ended queue
  • Graph (example Tree, Heap)

Linear Data Structures

  • Arrays
  • Array
  • Bit array
  • Bit field
  • Bitboard
  • Bitmap
  • Circular buffer
  • Control table
  • Image
  • Dope vector
  • Dynamic array
  • Gap buffer
  • Hashed array tree
  • Lookup table
  • Matrix
  • Parallel array
  • Sorted array
  • Sparse matrix
  • Iliffe vector
  • Variable-length array
  • Lists
  • Doubly linked list
  • Array list
  • Linked list
  • Association list
  • Self-organizing list
  • Skip list
  • Unrolled linked list
  • VList
  • Conc-tree list
  • Xor linked list
  • Zipper
  • Doubly connected edge list also known as half-edge
  • Difference list
  • Free list
  • Trees
  • Binary trees
  • AA tree
  • AVL tree
  • Binary search tree
  • Binary tree
  • Cartesian tree
  • Conc-tree list
  • Left-child right-sibling binary tree
  • Order statistic tree
  • Pagoda
  • Randomized binary search tree
  • Red–black tree
  • Rope
  • Scapegoat tree
  • Self-balancing binary search tree
  • Splay tree
  • T-tree
  • Tango tree
  • Threaded binary tree
  • Top tree
  • Treap
  • WAVL tree
  • Weight-balanced tree
  • B-trees
  • B-tree
  • B+ tree
  • B*-tree
  • B sharp tree
  • Dancing tree
  • 2–3 tree
  • 2–3–4 tree
  • Queap
  • Fusion tree
  • Bx-tree
  • AList
  • Heaps
  • Heap
  • Binary heap
  • B-heap
  • Weak heap
  • Binomial heap
  • Fibonacci heap
  • AF-heap
  • Leonardo heap
  • 2–3 heap
  • Soft heap
  • Pairing heap
  • Leftist heap
  • Treap
  • Beap
  • Skew heap
  • Ternary heap
  • D-ary heap
  • Brodal queue
  • Trees
  • In these data structures each tree node compares a bit slice of key values.

Tree

  • Radix tree
  • Suffix tree
  • Suffix array
  • Compressed suffix array
  • FM-index
  • Generalised suffix tree
  • B-tree
  • Judy array
  • X-fast trie
  • Y-fast trie
  • Merkle tree
  • C tree
  • Multi-way trees
  • Ternary tree
  • K-ary tree
  • And–or tree
  • (a,b)-tree
  • Link/cut tree
  • SPQR-tree
  • Spaghetti stack
  • Disjoint-set data structure (Union-find data structure)
  • Fusion tree
  • Enfilade
  • Exponential tree
  • Fenwick tree
  • Van Emde Boas tree
  • Rose tree
  • Space-partitioning trees
  • These are data structures used for space partitioning or binary space partitioning.

Space-partitioning trees

  • Segment tree
  • Interval tree
  • Range tree
  • Bin
  • K-d tree
  • Implicit k-d tree
  • Min/max k-d tree
  • Relaxed k-d tree
  • Adaptive k-d tree
  • Quadtree
  • Octree
  • Linear octree
  • Z-order
  • UB-tree
  • R-tree
  • R+ tree
  • R* tree
  • Hilbert R-tree
  • X-tree
  • Metric tree
  • Cover tree
  • M-tree
  • VP-tree
  • BK-tree
  • Bounding interval hierarchy
  • Bounding volume hierarchy
  • BSP tree
  • Rapidly exploring random tree

Application-specific Trees:

  • Abstract syntax tree
  • Parse tree
  • Decision tree
  • Alternating decision tree
  • Minimax tree
  • Expectiminimax tree
  • Finger tree
  • Expression tree
  • Log-structured merge-tree
  • Lexicographic Search Tree

Hash-based Structures:

  • Bloom filter
  • Count–min sketch
  • Distributed hash table
  • Double hashing
  • Dynamic perfect hash table
  • Hash array mapped trie
  • Hash list
  • Hash table
  • Hash tree
  • Hash trie
  • Koorde
  • Prefix hash tree
  • Rolling hash
  • MinHash
  • Quotient filter
  • Ctrie

Graphs

  • Adjacency list
  • Adjacency matrix
  • Graph-structured stack
  • Scene graph
  • Decision tree
  • Binary decision diagram
  • Zero-suppressed decision diagram
  • And-inverter graph
  • Directed graph
  • Directed acyclic graph
  • Propositional directed acyclic graph
  • Multigraph
  • Hypergraph

List of All Algorithms:

Graph algorithms

  • Coloring algorithm: Graph coloring algorithm.
  • Hopcroft–Karp algorithm: convert a bipartite graph to a maximum cardinality matching
  • Hungarian algorithm: algorithm for finding a perfect matching
  • Prüfer coding: conversion between a labeled tree and its Prüfer sequence
  • Tarjan’s off-line lowest common ancestors algorithm: computes lowest common ancestors for pairs of nodes in a tree
  • Topological sort: finds linear order of nodes (e.g. jobs) based on their dependencies.
  • Minimum spanning tree
  • Borůvka’s algorithm
  • Kruskal’s algorithm
  • Prim’s algorithm
  • Reverse-delete algorithm
  • Shortest path problem
  • Bellman–Ford algorithm: computes shortest paths in a weighted graph (where some of the edge weights may be negative)
  • Dijkstra’s algorithm: computes shortest paths in a graph with non-negative edge weights
  • Floyd–Warshall algorithm: solves the all pairs shortest path problem in a weighted, directed graph
  • Johnson’s algorithm: All pairs shortest path algorithm in sparse weighted directed graph
  • Transitive closure problem: find the transitive closure of a given binary relation
  • Traveling salesman problem
  • Christofides algorithm
  • Nearest neighbour algorithm

Graph search

  • A: special case of best-first search that uses heuristics to improve speed B: a best-first graph search algorithm that finds the least-cost path from a given initial node to any goal node (out of one or more possible goals)
  • Backtracking: abandons partial solutions when they are found not to satisfy a complete solution
  • Beam search: is a heuristic search algorithm that is an optimization of best-first search that reduces its memory requirement
  • Beam stack search: integrates backtracking with beam search
  • Best-first search: traverses a graph in the order of likely importance using a priority queue
  • Bidirectional search: find the shortest path from an initial vertex to a goal vertex in a directed graph
  • Breadth-first search: traverses a graph level by level
  • Brute-force search: An exhaustive and reliable search method, but computationally inefficient in many applications.
  • D: an incremental heuristic search algorithm Depth-first search: traverses a graph branch by branch Dijkstra’s algorithm: A special case of A for which no heuristic function is used
  • General Problem Solver: a seminal theorem-proving algorithm intended to work as a universal problem solver machine.
  • Iterative deepening depth-first search (IDDFS): a state space search strategy
  • Jump point search: An optimization to A* which may reduce computation time by an order of magnitude using further heuristics.
  • Lexicographic breadth-first search (also known as Lex-BFS): a linear time algorithm for ordering the vertices of a graph
  • Uniform-cost search: a tree search that finds the lowest-cost route where costs vary

Selection Algorithms

  • Quickselect
  • Introselect

Sequence search

  • Linear search: locates an item in an unsorted sequence
  • Selection algorithm: finds the kth largest item in a sequence
  • Ternary search: a technique for finding the minimum or maximum of a function that is either strictly increasing and then strictly decreasing or vice versa
  • Sorted lists
  • Binary search algorithm: locates an item in a sorted sequence
  • Fibonacci search technique: search a sorted sequence using a divide and conquer algorithm that narrows down possible locations with the aid of Fibonacci numbers
  • Jump search (or block search): linear search on a smaller subset of the sequence
  • Predictive search: binary-like search which factors in magnitude of search term versus the high and low values in the search. Sometimes called dictionary search or interpolated search.
  • Uniform binary search: an optimization of the classic binary search algorithm

Sequence Merging:

  • Simple merge algorithm
  • k-way merge algorithm
  • Union (merge, with elements on the output not repeated)

Sequence Sorting:

  • Bubble sort: for each pair of indices, swap the items if out of order
  • Comb sort
  • Gnome sort
  • Odd–even sort
  • Quicksort: divide list into two, with all items on the first list coming before all items on the second list.; then sort the two lists. Often the method of choice

Also Read these Tutorials:

Learn Data structures in Java

Computer Science Algorithms and Data structures

data structures basics for beginners

learn Data structures in c

DSA using c++

Web References:

Naveed Tawargeri
 

Hi Everyone, Naveed Tawargeri Here. I am a graduate of Information Science Engineering and working as Digital Marketing Executive.