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:
A Data structure is an arrangement of data in a computer’s memory or disk. Data structures include Arrays, Stacks, Queues, 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
- Primitive Data Structures
- Non-primitive 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