AlgoStruct: Mastering DSA with C & C++

A comprehensive guide to Data Structures, Algorithms, and essential concepts like Pointers, OOP, Structures, Memory Management etc. Features well-documented code with clear comments and detailed Readme files, implementing all data structures and their algorithms from scratch.

AUTHOR: Mert Eldemir
SEARCH RESOURSES: Abdul Bari cplusplus geeksforgeeks leetcode wikipedia

Project divided into 3 topics. Here the table of headings and subheadings. Each topic contain code examples with explained comment lines and Readme files.

• Essential Concepts of C & C++

  • Array Basics
  • Structures
  • Pointers
  • Reference
  • Functions
  • Converting C code to C++
  • Scope Resolution
  • Object Oriented Programming
  • Generics
  • Templates

• Data Structures

  • Array Representations
  • Array ADT
  • Strings
  • Linked Lists
  • Heap

• Algorithms

  • Recursion
  • Sorting Algorithms
  • Array Algorithms
  • Bitwise Operations
  • String Algorithms
  • Linked List Algorithms

Essential Concepts of C & C++

Essential concepts of C & C++ before diving into DSA. Arrays, Structures, OOP, Pointer and a lot more with explanation and example code.

Array Basics

• Representation of Arrays in C & C++

• Declaring and initializing dynamic and static arrays

  Code: arrays.cpp

Structures

Structures in C++ are user defined data types which are used to store group of items of non-similar data types.

• Understanging the concept of Structure in C++ / Manipulating members of the structures

• Creating struct objects in Stack and heap.

  Code: structures.cpp

Pointers

Pointers are symbolic representations of addresses. They enable programs to simulate call-by-reference as well as to create and manipulate dynamic data structures. Iterating over elements in arrays or other data structures is one of the main use of pointers.

The address of the variable you’re working with is assigned to the pointer variable that points to the same data type (such as an int or string).

• Difference between Heap and Stack / Allocating & Deallocating Memory on Heap

• Creating and allocating memory on Heap and seeing difference between C style and C++ style

  Code: pointers.cpp
  Readme: Pointers.md

Reference

When a variable is declared as a reference, it becomes an alternative name for an existing variable. A variable can be declared as a reference by putting ‘&’ in the declaration.

• Creating & Manipulating references to variables

• Use cases of references in for each blocks

  Code: reference.cpp
  Readme: Reference.md

Functions

• Creating and calling functions & Formal and Actual parameters

• Parameter passing methods (by Value, Address, Reference)

• Functions that using and returning pointers

• Passing Arrays/Structures as parameters & Callback functions

  Code: functions.cpp
  Readme: Functions.md

Converting C code to C++

• Difference between writing C and C++ code

• Rewriting structure based C code into OOP based C++ code

  Code: c-code.c cpp-code.cpp

Scope Resolution

In programming, scope refers to the context within which a variable or function is accessible. C++ has several scopes, such as global scope, local scope, class scope, and namespace scope. When a variable or function is declared, it exists within a specific scope, and that scope defines where it can be accessed.

• :: operator and Scope Resolution

• Accessing Global Variables / Static Members / Namespaces

• Defining Class Member Functions Outside the Class

  Code: scope-resolution.cpp
  Readme: ScopeResolution.md

Object Oriented Programming

Object-oriented programming – As the name suggests uses objects in programming. Object-oriented programming aims to implement real-world entities like inheritance, hiding, polymorphism, etc. in programming. The main aim of OOP is to bind together the data and the functions that operate on them so that no other part of the code can access this data except that function.

• Classes and structs

• Class Members / Definition of Memeber Functions / Classes defined with struct and union

• Constructors & Member initialization in constructors

• Pointers to classes

• OOP Concepts (Encapsulation, Inheritance, Polymorphism, Abstraction etc.)

  Code: oop.cpp
  Readme: Oop.md

Generics

Generics is the idea to allow type (Integer, String, … etc and user-defined types) to be a parameter to methods, classes and interfaces. For example, classes like an array, map, etc, which can be used using generics very efficiently.

Before diving into Templates would be better to understand concept of Generics.

• Generic Functions using Template / Generic Class using Template

• Working with multi-type Generics

  Code: generics.cpp

Templates

A template is a simple yet very powerful tool in C++. The simple idea is to pass the data type as a parameter so that we don’t need to write the same code for different data types.

• Function Templates & Class Templates

  Code: templates.cpp
  Readme: Templates.md

DATA STRUCTURES

Data structures in programming are ways to organize, store, and manage data efficiently for operations like searching, sorting, and modification. Examples include arrays, strings, linked lists, stacks, queues, trees, graphs etc. Each is designed for specific tasks to optimize performance.

Array Representations

• Declaring & Initializing arrays on Stack and Heap

• Dimensional Arrays (2D & 3D)

• Row-Column Major formulas, Address Formulas for 1D, 2D, 3D and nD Arrays

  Folder: Arrays-Representations
  Address Formulas: Address-Formulas

ARRAY ADT

The array is a basic abstract data type that holds an ordered collection of items accessible by an integer index. These items can be anything from primitive types such as integers to more complex types like instances of classes.

• Console program that create and manipulate with Array from scratch

• Functions like Display, Append, Insert, Search, Get & Set, Max/Min, Reverse, Shift/Rotate

  Code: Array.c

STRINGS

In computer programming, a string is traditionally a sequence of characters, either as a literal constant or as some kind of variable.

• Characters & Character Arrays

• Null-Termination & Mutability & Efficient Copying & Concatenation

• std::string

  Code: Strings.cpp Readme: Strings.md ASCII TABLE: ASCII-Table.png

LINKED LIST

Linked list is a linear data structure that allows the users to store data in non-contiguous memory locations. A linked list is defined as a collection of nodes where each node consists of two members which represents its value and a next pointer which stores the address for the next node.

• Linked List, Nodes

• Single & Double & Circular Linked Lists

  Folder: Linked-Lists Readme: LinkedLists.md

HEAP

A Heap is a complete binary tree data structure that satisfies the heap property:

Max Heap: Every node should have the element greater or equal to it's all descendants. Min Heap: Every node should have the element less or equal to it's all descendants.

Heaps are usually used to implement priority queues, where the smallest (or largest) element is always at the root of the tree.

• Max-Heap & Min-Heap Data Structure

• Heap functions such as: MaxHeapify, extractMax, Parent, Left, Right, insert

• Building and Sorting array using Heapify method

  Code: Heap.cpp
  Readme: Heap.md
  Priority Queue using Binary Heap

ALGORITHMS

The algorithms are used to solve problems or provide functionality. Algorithms work exclusively on values; they don't affect the size or storage of a container. Simple algorithms can be implemented within a function. Complex algorithms might require several functions or even a class to implement them.

Recursion

Generalising Recursion

• Behaviour of Recursion

• Ascending & Descending Phases

• CALLING time & RETURNING time

• Local and Static variables in Recursion

  Code: recursion.cpp

Types Of Recursion

• Tail Recursion - Head Recursion - Tree Recursion - Indirect Recursion - Nested Recursion

  Folder: Types-of-Recursion

Algorithms & Problems

Common algorithm problems using recursion vs iterative approach.

• nCr Combination - Tower of Hanoi Problem - Factorial - Fibonacci - Power - Sum Of Natural Nums - Taylor Series

  Algorithms: Recursion-Algorithms

Sorting Algorithms

A Sorting Algorithm is used to rearrange a given array or list of elements in an order. Selecting best sorting algoritms in a certain cases is crutial for system performans and stability.

• Bubble Sort - Selection Sort - Insertion Sort - Merge Sort - Quick Sort - Bin / Bucket Sort - Radix Sort - Shell Sort - Heap Sort

  Folder: Sorting-Techniques
  Time and Space Complexity Table: Sorting-Techniques

Array Algorithms

• Find Duplicates - Find Max Min - Find Multiple Missing - Find Single Missing - Merge Sorted Arrays - Rotate Array - Pair Sum

  Folder: Array-Algorithms

Bitwise Operations

In C+, Bitwise Operators are the operators that are used to perform bit-level operations on the integers. While performing these operations, integers are considered as sequences of binary digits. These operators are useful for low-level programming, system programming, and optimizing performance.

• AND, OR, XOR, NOT, Left Shift, Right Shift

• hammingWeight - swapVariables

  Folder: Bitwise-Operations
  Readme: Bitwise.md

String Algorithms

• changingCase - permutationString - countWordsAndVowels - findDuplicates - findDuplicatesBitwise - findStringLength - isPalindrome - reverseString - validateString - isAnagram

  Folder: String-Algorithms

Linked List Algorithms

• reverseLinkedList - displayLinkedList - countNodes - findMaxMin - isSorted - removeDuplicates - mergeLinkedLists

  Folder: Linked-List-Algorithms