/Data-structures-and-algorithms

Data structures and algorithms – MIREA course

Primary LanguageC++

Data structures and algorithms

Implementations of some data structures and algorithms

Table of contents

Hashtable

(Back to top)

Hashtable template class implementation with Separate chaining collision resolving method

  • hash function
  • rehashing in case of load ratio limit reached
  • insert
  • remove by key
  • find by key

Substring search

(Back to top)

Rabin-Karp string-searching algorithm implementation Given a some number of patterns stored in a hashtable we need to count a number of each pattern occerrences in a string

Red-Black Tree

(Back to top)

Left leaning red-black tree implementation

  • node inserting
  • hight calculation
  • black-hight calculation
  • tree traversal
    • prefix
    • infix
    • postfix
    • breadth-first search (BFS) with Queue implementation

Graph

(Back to top)

Simple Bellman–Ford algorithm to compute the shortest path from a single vertex to all of the other vertices in a weighted digraph Also there is a BFS search implementation for graph

Encoding

(Back to top)