Skip to content

About

No description, website, or topics provided.

Resources

Stars

1 star

Watchers

0 watching

Forks

Latest commit

 

History

11 Commits

Folders and files

Repository files navigation

DataStructures-Algorithms

🇬🇧 English · 🇪🇸 Español


English

A collection of classic data structures and algorithms written from scratch in C-style C++. Every structure lives in its own .h file, follows the same conventions and has its own automatic test, so the code is easy to read, compare and check.

Contents

Linear data structures

Structure Description File
Array Static array with a fixed maximum size array.h
Dynamic Array Array that doubles its capacity with realloc when it's full dynamicarray.h
Stack LIFO stack stored in an array stack.h
Linked Stack Stack built with nodes, without a size limit linkedstack.h
Queue FIFO circular queue stored in an array queue.h
Linked Queue Queue built with nodes, without a size limit linkedqueue.h
Deque Circular queue that inserts and removes at both ends deque.h
Linked List Singly linked list linkedlist.h
Doubly Linked List Nodes with prev and next, with head and tail doublylinkedlist.h
Circular Linked List The last node points to the first one circularlinkedlist.h

Non linear data structures

Type Structure Description File
Tree Binary Search Tree Insert, search, delete, min, max, height and four traversals (in, pre, post and level order) binarysearchtree.h
Tree AVL Tree BST that keeps itself balanced with rotations avltree.h
Tree Heap Min heap or max heap stored in an array heap.h
Tree Priority Queue Min heap of (value, priority) pairs priorityqueue.h
Tree Trie Prefix tree for lowercase words trie.h
Hash Hash Table (chaining) Each bucket is a linked list of (key, value) pairs hashtablechaining.h
Hash Hash Table (open addressing) Linear probing with tombstones hashtableopenaddressing.h
Hash Set Set built on the hash table: union, intersection, difference and subset set.h
Graph Graph (adjacency matrix) Weighted, directed or undirected, with BFS and DFS graphmatrix.h
Graph Graph (adjacency list) Weighted, directed or undirected, with BFS and DFS graphlist.h
Graph Disjoint Set (Union-Find) Union by rank and path compression disjointset.h

Algorithms

Type Algorithms File
Searching Linear search, binary search (iterative and recursive) searching.h
Sorting Bubble, selection, insertion, merge, quick and heap sort sorting.h
Graphs Dijkstra (with the priority queue), Prim, Kruskal (with the disjoint set) graphalgorithms.h

Generic versions

The structures above work with int. The Generic folder has template versions of the Array, Stack, Queue, Linked List and Binary Search Tree that work with any type (double, char, std::string, your own types...). They use the same function names, so pushStack(&stack, 3.5) works with a GenericStack<double> and the int and generic versions can be used in the same program.

Complexity

Data structures

n is the number of elements, L the length of a word, V the number of vertices and E the number of edges.

Structure Access Search Insert Delete Notes
Array O(1) O(n) O(1) at the end, O(n) at a position O(n) Fixed maximum size
Dynamic Array O(1) O(n) O(1) amortized at the end, O(n) at a position O(n) Grows by doubling
Stack / Linked Stack O(1) top - O(1) push O(1) pop
Queue / Linked Queue O(1) front - O(1) enqueue O(1) dequeue
Deque O(1) both ends - O(1) both ends O(1) both ends
Linked List O(n) O(n) O(1) head, O(n) tail O(n)
Doubly Linked List O(n) O(n) O(1) both ends O(1) both ends, O(n) by value
Circular Linked List O(n) O(n) O(1) head and tail O(1) head, O(n) by value Rotate in O(1)
Binary Search Tree - O(log n) avg, O(n) worst O(log n) avg, O(n) worst O(log n) avg, O(n) worst Traversals O(n)
AVL Tree - O(log n) O(log n) O(log n) Always balanced
Heap O(1) top O(n) O(log n) O(log n) extract Build from an array in O(n)
Priority Queue O(1) top - O(log n) O(log n)
Trie - O(L) O(L) O(L) Prefix search O(L)
Hash Table (chaining) - O(1) avg, O(n) worst O(1) avg, O(n) worst O(1) avg, O(n) worst
Hash Table (open addressing) - O(1) avg, O(n) worst O(1) avg, O(n) worst O(1) avg, O(n) worst Fixed number of slots
Set - O(1) avg O(1) avg O(1) avg Union, intersection and difference O(n + m) avg
Graph (matrix) - O(1) edge O(1) edge O(1) edge BFS/DFS O(V²), memory O(V²)
Graph (list) - O(V) edge O(V) edge O(V) edge BFS/DFS O(V + E), memory O(V + E)
Disjoint Set - ~O(1) find - - ~O(1) union (inverse Ackermann)

Algorithms

Algorithm Best Average Worst Extra memory Stable
Linear search O(1) O(n) O(n) O(1) -
Binary search O(1) O(log n) O(log n) O(1) iterative, O(log n) recursive -
Bubble sort O(n) O(n²) O(n²) O(1) Yes
Selection sort O(n²) O(n²) O(n²) O(1) No
Insertion sort O(n) O(n²) O(n²) O(1) Yes
Merge sort O(n log n) O(n log n) O(n log n) O(n) Yes
Quick sort O(n log n) O(n log n) O(n²) O(log n) No
Heap sort O(n log n) O(n log n) O(n log n) O(1) No
Dijkstra (matrix + priority queue) O(V² + E log E) O(V + E) -
Prim (matrix) O(V²) O(V) -
Kruskal O(E log E) O(V + E) -

Project layout

DataStructures/
├── LinearDataStructures/
│   ├── StaticDataStructure/      Array
│   └── DynamicDataStructure/     DynamicArray, Stack, LinkedStack, Queue, LinkedQueue, Deque,
│                                 LinkedList, DoublyLinkedList, CircularLinkedList
├── NonLinearDataStructures/
│   ├── Tree/                     BinarySearchTree, AVLTree, Heap, PriorityQueue, Trie
│   ├── Hash/                     HashTableChaining, HashTableOpenAddressing, Set
│   └── Graph/                    GraphMatrix, GraphList, DisjointSet
└── Generic/                      GenericArray, GenericStack, GenericQueue,
                                  GenericLinkedList, GenericBinarySearchTree
Algorithms/
├── Searching/                    searching.h
├── Sorting/                      sorting.h
└── Graph/                        graphalgorithms.h
Tests/
├── test.h                        Small testing library (CHECK, CHECK_EQUAL, CHECK_ARRAY)
├── LinearDataStructures/         One test file per structure or algorithm file
├── NonLinearDataStructures/
├── Algorithms/
└── Generic/
CMakeLists.txt                    Builds every test and registers it in CTest

How to run the tests

Every test checks the results automatically (expected value against obtained value) and returns 0 only if all the checks pass.

With CMake (any compiler):

cmake -S . -B build
cmake --build build --config Debug
ctest --test-dir build -C Debug --output-on-failure

Or compile a single test by hand from the root of the repository:

g++ Tests/LinearDataStructures/test_stack.cpp -o test_stack
./test_stack

Code conventions

  • One structure per .h file, protected with an include guard ending in _JL.
  • Structures are defined with typedef struct and initialised with an initX function.
  • Functions return 1 if the operation is successful or 0 if it is not. Values are returned through a pointer parameter.
  • Every function has a short comment explaining what it does and what it returns.
  • Every structure has a printX function that displays its elements as [1, 2, 3].
  • Each header has its own size constant (ARRAY_MAX_SIZE, STACK_MAX_SIZE...) and its own function names, so any headers can be included together.
  • Structures that reserve memory have a freeX function that releases it.

License

MIT. See LICENSE.


Español

Una colección de estructuras de datos y algoritmos clásicos escritos desde cero en C++ con estilo C. Cada estructura vive en su propio archivo .h, sigue las mismas convenciones y tiene su propia prueba automática, de forma que el código sea fácil de leer, de comparar y de comprobar.

Contenido

Estructuras de datos lineales

Estructura Descripción Archivo
Array Array estático con un tamaño máximo fijo array.h
Array dinámico Array que duplica su capacidad con realloc cuando se llena dynamicarray.h
Pila (Stack) Pila LIFO almacenada en un array stack.h
Pila con nodos Pila construida con nodos, sin límite de tamaño linkedstack.h
Cola (Queue) Cola FIFO circular almacenada en un array queue.h
Cola con nodos Cola construida con nodos, sin límite de tamaño linkedqueue.h
Deque Cola circular que inserta y extrae por ambos extremos deque.h
Lista enlazada Lista simplemente enlazada linkedlist.h
Lista doblemente enlazada Nodos con prev y next, con cabeza y cola doublylinkedlist.h
Lista enlazada circular El último nodo apunta al primero circularlinkedlist.h

Estructuras de datos no lineales

Tipo Estructura Descripción Archivo
Árbol Árbol binario de búsqueda Insertar, buscar, eliminar, mínimo, máximo, altura y cuatro recorridos (in, pre, post y por niveles) binarysearchtree.h
Árbol Árbol AVL BST que se mantiene equilibrado mediante rotaciones avltree.h
Árbol Heap Heap de mínimos o de máximos almacenado en un array heap.h
Árbol Cola de prioridad Heap de mínimos de pares (valor, prioridad) priorityqueue.h
Árbol Trie Árbol de prefijos para palabras en minúsculas trie.h
Hash Tabla hash (encadenamiento) Cada posición es una lista enlazada de pares (clave, valor) hashtablechaining.h
Hash Tabla hash (direccionamiento abierto) Sondeo lineal con marcas de borrado hashtableopenaddressing.h
Hash Conjunto (Set) Conjunto sobre la tabla hash: unión, intersección, diferencia y subconjunto set.h
Grafo Grafo (matriz de adyacencia) Con pesos, dirigido o no dirigido, con BFS y DFS graphmatrix.h
Grafo Grafo (lista de adyacencia) Con pesos, dirigido o no dirigido, con BFS y DFS graphlist.h
Grafo Conjuntos disjuntos (Union-Find) Unión por rango y compresión de caminos disjointset.h

Algoritmos

Tipo Algoritmos Archivo
Búsqueda Búsqueda lineal, búsqueda binaria (iterativa y recursiva) searching.h
Ordenación Burbuja, selección, inserción, merge sort, quick sort y heap sort sorting.h
Grafos Dijkstra (con la cola de prioridad), Prim, Kruskal (con los conjuntos disjuntos) graphalgorithms.h

Versiones genéricas

Las estructuras anteriores trabajan con int. La carpeta Generic contiene versiones con plantillas del Array, la Pila, la Cola, la Lista enlazada y el Árbol binario de búsqueda que funcionan con cualquier tipo (double, char, std::string, tipos propios...). Usan los mismos nombres de función, así que pushStack(&stack, 3.5) funciona con un GenericStack<double> y las versiones int y genéricas se pueden usar en el mismo programa.

Complejidad

Estructuras de datos

n es el número de elementos, L la longitud de una palabra, V el número de vértices y E el número de aristas.

Estructura Acceso Búsqueda Inserción Borrado Notas
Array O(1) O(n) O(1) al final, O(n) en una posición O(n) Tamaño máximo fijo
Array dinámico O(1) O(n) O(1) amortizado al final, O(n) en una posición O(n) Crece duplicando
Pila / Pila con nodos O(1) cima - O(1) push O(1) pop
Cola / Cola con nodos O(1) frente - O(1) encolar O(1) desencolar
Deque O(1) ambos extremos - O(1) ambos extremos O(1) ambos extremos
Lista enlazada O(n) O(n) O(1) cabeza, O(n) cola O(n)
Lista doblemente enlazada O(n) O(n) O(1) ambos extremos O(1) ambos extremos, O(n) por valor
Lista enlazada circular O(n) O(n) O(1) cabeza y cola O(1) cabeza, O(n) por valor Rotar en O(1)
Árbol binario de búsqueda - O(log n) medio, O(n) peor O(log n) medio, O(n) peor O(log n) medio, O(n) peor Recorridos O(n)
Árbol AVL - O(log n) O(log n) O(log n) Siempre equilibrado
Heap O(1) cima O(n) O(log n) O(log n) extraer Construir desde un array en O(n)
Cola de prioridad O(1) cima - O(log n) O(log n)
Trie - O(L) O(L) O(L) Búsqueda de prefijo O(L)
Tabla hash (encadenamiento) - O(1) medio, O(n) peor O(1) medio, O(n) peor O(1) medio, O(n) peor
Tabla hash (direccionamiento abierto) - O(1) medio, O(n) peor O(1) medio, O(n) peor O(1) medio, O(n) peor Número fijo de posiciones
Conjunto - O(1) medio O(1) medio O(1) medio Unión, intersección y diferencia O(n + m) medio
Grafo (matriz) - O(1) arista O(1) arista O(1) arista BFS/DFS O(V²), memoria O(V²)
Grafo (lista) - O(V) arista O(V) arista O(V) arista BFS/DFS O(V + E), memoria O(V + E)
Conjuntos disjuntos - ~O(1) find - - ~O(1) union (inversa de Ackermann)

Algoritmos

Algoritmo Mejor Medio Peor Memoria extra Estable
Búsqueda lineal O(1) O(n) O(n) O(1) -
Búsqueda binaria O(1) O(log n) O(log n) O(1) iterativa, O(log n) recursiva -
Burbuja O(n) O(n²) O(n²) O(1) Sí
Selección O(n²) O(n²) O(n²) O(1) No
Inserción O(n) O(n²) O(n²) O(1) Sí
Merge sort O(n log n) O(n log n) O(n log n) O(n) Sí
Quick sort O(n log n) O(n log n) O(n²) O(log n) No
Heap sort O(n log n) O(n log n) O(n log n) O(1) No
Dijkstra (matriz + cola de prioridad) O(V² + E log E) O(V + E) -
Prim (matriz) O(V²) O(V) -
Kruskal O(E log E) O(V + E) -

Estructura del proyecto

DataStructures/
├── LinearDataStructures/
│   ├── StaticDataStructure/      Array
│   └── DynamicDataStructure/     DynamicArray, Stack, LinkedStack, Queue, LinkedQueue, Deque,
│                                 LinkedList, DoublyLinkedList, CircularLinkedList
├── NonLinearDataStructures/
│   ├── Tree/                     BinarySearchTree, AVLTree, Heap, PriorityQueue, Trie
│   ├── Hash/                     HashTableChaining, HashTableOpenAddressing, Set
│   └── Graph/                    GraphMatrix, GraphList, DisjointSet
└── Generic/                      GenericArray, GenericStack, GenericQueue,
                                  GenericLinkedList, GenericBinarySearchTree
Algorithms/
├── Searching/                    searching.h
├── Sorting/                      sorting.h
└── Graph/                        graphalgorithms.h
Tests/
├── test.h                        Pequeña librería de pruebas (CHECK, CHECK_EQUAL, CHECK_ARRAY)
├── LinearDataStructures/         Un archivo de pruebas por estructura o archivo de algoritmos
├── NonLinearDataStructures/
├── Algorithms/
└── Generic/
CMakeLists.txt                    Compila todas las pruebas y las registra en CTest

Cómo ejecutar las pruebas

Cada prueba comprueba los resultados automáticamente (valor esperado frente a valor obtenido) y devuelve 0 solo si todas las comprobaciones pasan.

Con CMake (cualquier compilador):

cmake -S . -B build
cmake --build build --config Debug
ctest --test-dir build -C Debug --output-on-failure

O compila una sola prueba a mano desde la raíz del repositorio:

g++ Tests/LinearDataStructures/test_stack.cpp -o test_stack
./test_stack

Convenciones del código

  • Una estructura por archivo .h, protegido con un include guard terminado en _JL.
  • Las estructuras se definen con typedef struct y se inicializan con una función initX.
  • Las funciones devuelven 1 si la operación tiene éxito o 0 si no. Los valores se devuelven a través de un parámetro puntero.
  • Cada función tiene un comentario breve que explica qué hace y qué devuelve.
  • Cada estructura tiene una función printX que muestra sus elementos como [1, 2, 3].
  • Cada cabecera tiene su propia constante de tamaño (ARRAY_MAX_SIZE, STACK_MAX_SIZE...) y sus propios nombres de función, así que se pueden incluir varias cabeceras a la vez.
  • Las estructuras que reservan memoria tienen una función freeX que la libera.

Licencia

MIT. Consulta LICENSE.

About

No description, website, or topics provided.

Resources

Stars

1 star

Watchers

0 watching

Forks

Releases

Packages

Contributors

Languages