Estructuras de Datos

0x0042 INICIALIZANDO...
0x7ffe-stack
*p = malloc(sizeof(Node))
0x3b2a - heap
ptr -> next = NULL
Unidad 12

Conjuntos y mapas

Un Set (Conjunto) es una colección de elementos únicos. Si intentas insertar un dato que ya existe, el Set lo ignora. Es la implementación informática directa de la teoría de conjuntos matemática.

Imagen 47. Operaciones de conjuntos (Venn)

Imagen 47. Operaciones de conjuntos (Venn)

Operaciones fundamentales: Visualización de Unión (A ∪ B), Intersección (A ∩ B) y Diferencia (A - B). Estas son las operaciones lógicas que programaremos.

12.1 Sets (Conjuntos): Matemáticas en C
Mirar en YouTube
main.cpp
// Lógica conceptual de Unión
Set* union(Set* A, Set* B) {
    Set* resultado = clonar(A);
    for (elemento en B) {
        if (!contiene(resultado, elemento)) {
            agregar(resultado, elemento);
        }
    }
    return resultado;
}
// Lógica conceptual de Unión
Set* union(Set* A, Set* B) {
    Set* resultado = clonar(A);
    for (elemento en B) {
        if (!contiene(resultado, elemento)) {
            agregar(resultado, elemento);
        }
    }
    return resultado;
}

En C no existe la clase "Set" nativa. Debemos construirla. Tenemos dos opciones principales: usar una Tabla Hash (HashSet) para velocidad O(1) pero sin orden, o usar un Árbol Binario de Búsqueda (TreeSet) para velocidad O(log n) manteniendo los datos ordenados.

Imagen 48. HashSet vs TreeSet: Memoria y Estructura

Imagen 48. HashSet vs TreeSet: Memoria y Estructura

Arquitectura interna: A la izquierda, un HashSet usando buckets dispersos. A la derecha, un TreeSet organizando los mismos datos jerárquicamente.

12.2 Hash Set vs Tree Set
Mirar en YouTube

Un Mapa (o Diccionario) es una estructura que asocia una "Clave" (Key) única con un "Valor" (Value). Es como un array, pero en lugar de usar índices numéricos (0, 1, 2), puedes usar cualquier tipo de dato como índice (ej: nombres, códigos de producto).

Imagen 49. El modelo Clave-Valor (Key-Value)

Imagen 49. El modelo Clave-Valor (Key-Value)

Flujo de datos: La Clave entra, se procesa (hashing o búsqueda en árbol) y nos da acceso directo al Valor asociado. La Clave es el "ID", el Valor es la "Información".

main.cpp
struct Entry {
    char* key;   // La clave es única
    int value;   // El valor asociado
    struct Entry* next; // Para colisiones (si es Hash Map)
};

struct HashMap {
    struct Entry** buckets;
    int size;
};
struct Entry {
    char* key;   // La clave es única
    int value;   // El valor asociado
    struct Entry* next; // Para colisiones (si es Hash Map)
};

struct HashMap {
    struct Entry** buckets;
    int size;
};
12.3 Diccionarios (Mapas): Key-Value
Mirar en YouTube
Volver al nivel