Tipos de Datos Abstractos, Pilas y Colas

Resumen de la Unidad¶

Introducción¶

Desarrollo¶

Concepto y Diseño de TADs¶

Introducción¶

Un Tipo de Dato Abstracto (TAD, del inglés Abstract Data Type, ADT) es un modelo matemático que define un conjunto de datos junto con las operaciones que pueden realizarse sobre ellos, ocultando los detalles de su implementación. El concepto de TAD es fundamental en la ciencia de la computación porque establece una separación clara entre qué hace una estructura de datos (su interfaz) y cómo lo hace (su implementación).

Esta abstracción permite que el usuario de la estructura se concentre en resolver problemas de alto nivel sin preocuparse por los detalles internos de cómo se almacenan o manipulan los datos. Al mismo tiempo, el implementador tiene la libertad de optimizar o modificar la representación interna sin afectar al código que utiliza el TAD, siempre que mantenga la misma interfaz pública.

Características de un TAD¶

Un TAD se caracteriza por tres componentes esenciales:

1. Representación de datos: Estructura interna que almacena la información (oculta al usuario).

2. Operaciones: Conjunto de funciones que manipulan los datos de manera controlada.

3. Axiomas o invariantes: Propiedades que deben cumplirse en todo momento para garantizar la coherencia de la estructura.

Encapsulamiento y Abstracción¶

El principio de encapsulamiento es el pilar que sostiene a la abstracción: garantiza que los datos internos de un TAD no puedan ser manipulados de manera directa desde el código cliente. En C, este ocultamiento físico se implementa a través de la técnica de punteros opacos, declarando tipos incompletos en la cabecera e implementando sus detalles estructurales en el archivo fuente .c.

Para un análisis detallado sobre cómo funciona esta técnica a nivel del compilador, sus restricciones sintácticas y un ejemplo completo de implementación opaca, consultá el capítulo sobre Tipos Opacos.

TAD vs. Estructura de Datos¶

• TAD: Es un concepto lógico, una especificación de comportamiento (el “qué”).

• Estructura de Datos: Es una implementación concreta, una organización de datos en memoria (el “cómo”).

Ejemplos Clásicos de Tipos de Datos Abstractos¶

• Lista (List): Colección ordenada y posicionada de elementos.

• Pila (Stack): Colección LIFO (Last-In, First-Out).

• Cola (Queue): Colección FIFO (First-In, First-Out).

• Cola de Prioridad (Priority Queue): Los elementos se extraen según su prioridad.

• Mapa (Map / Diccionario): Colección de pares clave-valor únicos.

Metodología para el Diseño de un TAD Propio¶

Crear un TAD es un ejercicio de diseño centrado en la abstracción. Seguir un proceso metodológico asegura que el resultado sea robusto, claro y útil.

1. Conceptualización: Identificar la entidad a modelar, sus datos y sus reglas.

2. Definición de la Interfaz Pública: Listar las operaciones, definir sus firmas (parámetros, retorno) y documentar su comportamiento (precondiciones, poscondiciones).

3. Especificación Formal (Opcional): Definir axiomas que describan cómo interactúan las operaciones.

4. Elección de la Estructura de Datos: Evaluar candidatos (arreglos, listas, árboles) y analizar su complejidad para cada operación de la interfaz.

5. Implementación: Escribir el código, encapsulando la estructura de datos interna y exponiendo solo la interfaz pública.

Asignación de Memoria: Estática vs. Dinámica¶

El diseño e implementación de Tipos de Datos Abstractos en C requiere una gestión rigurosa de la memoria. La elección entre el ciclo de vida automático en el stack (memoria estática) o el ciclo de vida dinámico en el heap (memoria dinámica) define cómo se almacenan, acceden y destruyen los elementos del TAD.

Para un análisis detallado sobre el funcionamiento del stack, consultá la sección La Pila (Stack) en el apunte correspondiente. Asimismo, los detalles operativos de la asignación dinámica, el uso del heap y la gestión de errores mediante malloc, realloc y free se abordan en profundidad en El Montón (Heap) y Errores Comunes y Peligros.

Ejercicios de Concepto y Diseño de TADs¶

Tipificación de Acciones¶

Cuando diseñamos un TAD, las operaciones que lo componen no son arbitrarias. Cada función cumple un rol específico en la manipulación de la estructura de datos. Clasificar estas operaciones según su propósito permite crear interfaces coherentes y predecibles, facilitando tanto la implementación como el uso del TAD.

A continuación se presentan las siete categorías fundamentales de operaciones que típicamente conforman un TAD bien diseñado:

1. Constructor¶

Propósito: “Prepara el terreno”.

Función: Se encarga de la asignación de memoria e inicialización de la estructura. El constructor establece el estado inicial válido del TAD, reservando los recursos necesarios y configurando los invariantes básicos.

Ejemplos:

1
2
3
4
int** crear_matriz(int filas, int col);
int* crear_arreglo(int largo);
pila_t* crear_pila(void);
lista_t* crear_lista(void);

2. Selector¶

Propósito: “Recupera información”.

Función: Obtiene un dato específico que está guardado dentro de la estructura. Los selectores permiten acceder al contenido almacenado sin modificarlo. Son operaciones de solo lectura sobre los datos del usuario.

Ejemplos:

1
2
3
4
int valor = arreglo[i];
int item = obtener(arreglo_t, indice);
int dato = ver_tope(pila);
int primero = frente(cola);

3. Consultor¶

Propósito: “Recupera meta-información”.

Función: Informa sobre alguna propiedad intrínseca de la estructura, no sobre los datos almacenados por el usuario, sino sobre el estado y características de la estructura misma. Los consultores responden preguntas sobre la configuración, capacidad o estado actual del TAD.

Ejemplos:

1
2
3
4
5
size_t tamanio = sizeof(arreglo);
bool vacia = esta_vacia(pila);
bool encontrado = contiene(lista, valor);
int elementos = largo(lista);
size_t capacidad_actual = capacidad(arreglo_dinamico);

Diferencia con Selectores:

• Selector: Devuelve un dato del usuario almacenado → ver_tope(pila) devuelve el elemento en el tope.

• Consultor: Devuelve información sobre la estructura → esta_vacia(pila) informa si hay elementos o no.

4. Iterador¶

Propósito: “Recorre la información”.

Función: Provee una entidad que permite procesar los elementos de la estructura uno por uno, de manera secuencial, sin exponer la representación interna. Los iteradores son fundamentales para abstraer el recorrido de estructuras complejas.

Ejemplos:

1
2
3
4
5
6
7
8
9
10
iterador_t* iter = crear_iterador(lista);
while (tiene_siguiente(iter)) {
    int actual = siguiente(iter);
    // procesar actual
}
destruir_iterador(iter);

// Alternativamente, con callbacks (soporte genérico):
void procesar(void *dato, void *contexto);
recorrer(lista, procesar, contexto);

5. Mutador¶

Propósito: “Modifica la información”.

Función: Cambia el estado o los datos contenidos en la estructura. Los mutadores son las operaciones de escritura que alteran el contenido gestionado por el TAD. Deben mantener los invariantes de la estructura.

Ejemplos:

1
2
3
4
5
6
arreglo[i] = valor;
bool exito = insertar(lista, val, pos);
bool exito = apilar(pila, dato);
bool exito = encolar(cola, dato);
bool eliminado = remover(conjunto, elemento);
void modificar(matriz, fila, col, nuevo_valor);

6. Conversor¶

Propósito: “Crea una estructura similar”.

Función: Genera una nueva estructura o representación a partir del contenido de la estructura actual. Los conversores transforman el TAD en otro formatos, típicamente para interoperabilidad o presentación.

Ejemplos:

1
2
3
4
5
char* cadena = a_cadena(arreglo, largo);
int* subconjunto = rebanar(arreglo, desde, hasta);
lista_t* sublista = copiar_sublista(lista, inicio, fin);
arreglo_t* arr = lista_a_arreglo(lista);
char* representacion = serializar(estructura);

Diferencia con Selectores:

• Selector: Devuelve una referencia a datos existentes → obtener(arreglo, 5) devuelve el elemento en posición 5.

• Conversor: Crea una nueva estructura con datos derivados → rebanar(arreglo, 2, 5) crea un nuevo arreglo con copia de elementos 2-5.

7. Destructor¶

Propósito: “Libera los recursos”.

Función: Se encarga de liberar la memoria asignada y otros recursos externos (archivos, conexiones, etc.) para evitar fugas (memory leaks). El destructor es la operación final en el ciclo de vida de una instancia del TAD.

Ejemplos:

1
2
3
4
void liberar_arreglo(int** arreglo);
void destruir_matriz(int filas, int*** matriz);
void destruir_pila(pila_t** pila);
void destruir_lista(lista_t** lista, void (*destruir_dato)(void*));

Patrones comunes:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// Destructor seguro con doble puntero (datos copiados)
void destruir_pila_int(pila_t** pila) {
    if (pila == NULL || *pila == NULL) return;
    free((*pila)->elementos);
    free(*pila);
    *pila = NULL;
}

// Destructor seguro con doble puntero y callback (datos por referencia)
void destruir_lista(lista_t** lista, void (*destruir_dato)(void*)) {
    if (lista == NULL || *lista == NULL) return;
    nodo_t* actual = (*lista)->inicio;
    while (actual) {
        nodo_t* siguiente = actual->siguiente;
        if (destruir_dato != NULL && actual->dato != NULL)
            destruir_dato(actual->dato);
        free(actual);
        actual = siguiente;
    }
    free(*lista);
    *lista = NULL;
}

Resumen de Tipificación¶

La siguiente tabla resume las siete categorías de operaciones:

* El iterador puede mantener estado interno de posición, pero no modifica la estructura recorrida.

Ejercicios de Tipificación de Acciones¶

Listas Enlazadas (TAD Secuencia)¶

Una secuencia es una colección ordenada de elementos donde cada elemento tiene una posición definida. Es uno de los TADs más fundamentales en programación, ya que representa la idea abstracta de “una serie de cosas en orden”.

Interfaz del TAD Secuencia¶

El TAD Secuencia define las siguientes operaciones esenciales:

• crear(): Crea una secuencia vacía.

• insertar_al_inicio(secuencia, elemento): Agrega un elemento al principio.

• insertar_al_final(secuencia, elemento): Agrega un elemento al final.

• insertar_en_posicion(secuencia, posicion, elemento): Inserta un elemento en una posición específica.

• eliminar(secuencia, elemento): Elimina la primera ocurrencia de un elemento.

• buscar(secuencia, elemento): Busca un elemento y retorna su posición o indicador de no encontrado.

• obtener(secuencia, posicion): Retorna el elemento en una posición dada.

• tamanio(secuencia): Retorna la cantidad de elementos.

• es_vacia(secuencia): Verifica si la secuencia está vacía.

• destruir(secuencia): Libera todos los recursos asociados.

Múltiples Implementaciones¶

Lo poderoso de un TAD es que esta misma interfaz puede implementarse de diferentes maneras, cada una con sus ventajas y desventajas. Las dos implementaciones más comunes de una secuencia son:

1. Implementación con arreglo: Los elementos se almacenan en posiciones contiguas de memoria.

2. Implementación con lista enlazada: Los elementos se almacenan en nodos dispersos, conectados mediante punteros.

Comparación de Implementaciones¶

• Si el arreglo está lleno, requiere $O(n)$ para redimensionar.
  ** $O(1)$ si se mantiene puntero al final, $O(n)$ si no.

Implementación de Secuencia con Listas¶

Una lista enlazada es una implementación del TAD Secuencia donde los elementos se almacenan en nodos individuales conectados mediante punteros. A diferencia de los arreglos, los nodos no necesitan estar en posiciones contiguas de memoria, lo que permite inserciones y eliminaciones eficientes al inicio.

Esta es una de las estructuras de datos dinámicas más fundamentales y sirve como base para implementar otros TADs como pilas y colas.

Ventajas de las Listas Enlazadas¶

• Tamaño dinámico: Crece y decrece según las necesidades sin redimensionamiento.

• Inserción y eliminación eficientes: $O(1)$ si tenemos la referencia al nodo.

• No requiere reorganización: Al insertar o eliminar elementos intermedios.

Desventajas de las Listas Enlazadas¶

• Acceso secuencial: No hay acceso directo por índice ($O(n)$).

• Mayor uso de memoria: Cada nodo requiere espacio adicional para punteros.

• Menos eficiente en caché: La no contigüidad en memoria reduce el rendimiento.

Lista Enlazada Simple¶

En una lista enlazada simple, cada nodo apunta únicamente al siguiente nodo de la secuencia. El último nodo apunta a NULL, indicando el final de la lista.

Estructura de un Nodo¶

1
2
3
4
5
6
7
8
9
10
11
typedef struct nodo
{
    int dato;
    struct nodo *siguiente;
} nodo_t;

typedef struct lista
{
    nodo_t *inicio;
    size_t tamanio;
} lista_t;

Creación de una Lista Vacía¶

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
lista_t *crear_lista(void)
{
    lista_t *lista = NULL;
    
    lista = malloc(sizeof(lista_t));
    
    if (lista == NULL)
    {
        return NULL;
    }
    
    lista->inicio = NULL;
    lista->tamanio = 0;
    
    return lista;
}

Inserción al Inicio¶

La inserción al inicio es una operación $O(1)$ porque no requiere recorrer la lista.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
bool insertar_al_inicio(lista_t *lista, int dato)
{
    nodo_t *nuevo = NULL;
    
    if (lista == NULL)
    {
        return false;
    }
    
    nuevo = malloc(sizeof(nodo_t));
    
    if (nuevo == NULL)
    {
        return false;
    }
    
    nuevo->dato = dato;
    nuevo->siguiente = lista->inicio;
    
    lista->inicio = nuevo;
    lista->tamanio++;
    
    return true;
}

Inserción al Final¶

La inserción al final requiere recorrer toda la lista para encontrar el último nodo ($O(n)$).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
bool insertar_al_final(lista_t *lista, int dato)
{
    nodo_t *nuevo = NULL;
    nodo_t *actual = NULL;
    
    if (lista == NULL)
    {
        return false;
    }
    
    nuevo = malloc(sizeof(nodo_t));
    
    if (nuevo == NULL)
    {
        return false;
    }
    
    nuevo->dato = dato;
    nuevo->siguiente = NULL;
    
    if (lista->inicio == NULL)
    {
        lista->inicio = nuevo;
    }
    else
    {
        actual = lista->inicio;
        
        while (actual->siguiente != NULL)
        {
            actual = actual->siguiente;
        }
        
        actual->siguiente = nuevo;
    }
    
    lista->tamanio++;
    
    return true;
}

Búsqueda¶

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
nodo_t *buscar(const lista_t *lista, int dato)
{
    nodo_t *actual = NULL;
    
    if (lista == NULL)
    {
        return NULL;
    }
    
    actual = lista->inicio;
    
    while (actual != NULL)
    {
        if (actual->dato == dato)
        {
            return actual;
        }
        
        actual = actual->siguiente;
    }
    
    return NULL;
}

Eliminación¶

La eliminación de un nodo requiere mantener una referencia al nodo anterior para poder actualizar su puntero siguiente.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
bool eliminar(lista_t *lista, int dato)
{
    nodo_t *actual = NULL;
    nodo_t *anterior = NULL;
    
    if (lista == NULL || lista->inicio == NULL)
    {
        return false;
    }
    
    actual = lista->inicio;
    anterior = NULL;
    
    while (actual != NULL && actual->dato != dato)
    {
        anterior = actual;
        actual = actual->siguiente;
    }
    
    if (actual == NULL)
    {
        return false;
    }
    
    if (anterior == NULL)
    {
        lista->inicio = actual->siguiente;
    }
    else
    {
        anterior->siguiente = actual->siguiente;
    }
    
    free(actual);
    actual = NULL;
    lista->tamanio--;
    
    return true;
}

Recorrido¶

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void imprimir_lista(const lista_t *lista)
{
    nodo_t *actual = NULL;
    
    if (lista == NULL)
    {
        return;
    }
    
    actual = lista->inicio;
    
    printf("Lista: ");
    
    while (actual != NULL)
    {
        printf("%d ", actual->dato);
        actual = actual->siguiente;
    }
    
    printf("\n");
}

Destrucción de la Lista¶

Es fundamental liberar toda la memoria asignada para evitar fugas.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void destruir_lista(lista_t *lista)
{
    nodo_t *actual = NULL;
    nodo_t *siguiente = NULL;
    
    if (lista == NULL)
    {
        return;
    }
    
    actual = lista->inicio;
    
    while (actual != NULL)
    {
        siguiente = actual->siguiente;
        free(actual);
        actual = siguiente;
    }
    
    free(lista);
    lista = NULL;
}

Lista Doblemente Enlazada¶

Una lista doblemente enlazada extiende la lista simple agregando un puntero adicional en cada nodo que apunta al nodo anterior. Esto permite el recorrido bidireccional de la lista.

Estructura¶

1
2
3
4
5
6
7
8
9
10
11
12
13
typedef struct nodo_doble
{
    int dato;
    struct nodo_doble *anterior;
    struct nodo_doble *siguiente;
} nodo_doble_t;

typedef struct lista_doble
{
    nodo_doble_t *inicio;
    nodo_doble_t *fin;
    size_t tamanio;
} lista_doble_t;

Ventajas sobre la Lista Simple¶

• Recorrido bidireccional: Se puede recorrer en ambas direcciones.

• Eliminación más eficiente: Si tenemos un puntero al nodo, podemos eliminarlo sin necesidad de buscar el nodo anterior.

• Inserción antes de un nodo: Podemos insertar antes de un nodo dado sin recorrer la lista.

Desventajas¶

• Mayor uso de memoria: Cada nodo requiere un puntero adicional.

• Mayor complejidad: Más punteros que actualizar en cada operación.

Inserción al Inicio¶

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
bool insertar_al_inicio_doble(lista_doble_t *lista, int dato)
{
    nodo_doble_t *nuevo = NULL;
    
    if (lista == NULL)
    {
        return false;
    }
    
    nuevo = malloc(sizeof(nodo_doble_t));
    
    if (nuevo == NULL)
    {
        return false;
    }
    
    nuevo->dato = dato;
    nuevo->anterior = NULL;
    nuevo->siguiente = lista->inicio;
    
    if (lista->inicio != NULL)
    {
        lista->inicio->anterior = nuevo;
    }
    else
    {
        lista->fin = nuevo;
    }
    
    lista->inicio = nuevo;
    lista->tamanio++;
    
    return true;
}

Eliminación de un Nodo¶

La ventaja principal es que si tenemos un puntero al nodo a eliminar, podemos hacerlo sin buscar el nodo anterior.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
bool eliminar_nodo_doble(lista_doble_t *lista, nodo_doble_t *nodo)
{
    if (lista == NULL || nodo == NULL)
    {
        return false;
    }
    
    // Actualizar el puntero siguiente del nodo anterior
    if (nodo->anterior != NULL)
    {
        nodo->anterior->siguiente = nodo->siguiente;
    }
    else
    {
        // El nodo es el primero
        lista->inicio = nodo->siguiente;
    }
    
    // Actualizar el puntero anterior del nodo siguiente
    if (nodo->siguiente != NULL)
    {
        nodo->siguiente->anterior = nodo->anterior;
    }
    else
    {
        // El nodo es el último
        lista->fin = nodo->anterior;
    }
    
    free(nodo);
    lista->tamanio--;
    
    return true;
}

Lista Circular¶

Una lista circular es una variante donde el último nodo apunta de nuevo al primero, formando un ciclo. Puede ser simple o doblemente enlazada. Son útiles en aplicaciones que requieren procesamiento cíclico, como buffers circulares o sistemas round-robin.

Ejercicios de Listas Enlazadas¶

Arreglos Dinámicos (TAD Secuencia)¶

Para demostrar el poder de la abstracción del TAD, presentamos ahora una implementación alternativa del TAD Secuencia utilizando arreglos en lugar de listas enlazadas. Esta implementación ofrece diferentes características de rendimiento, pero mantiene la misma interfaz conceptual.

Secuencia con Arreglo Dinámico¶

Un arreglo dinámico combina las ventajas del acceso aleatorio de los arreglos con la flexibilidad de tamaño de las estructuras dinámicas.

1
2
3
4
5
6
typedef struct secuencia_arreglo
{
    int *elementos;
    size_t tamanio;
    size_t capacidad;
} secuencia_arreglo_t;

Creación de una Secuencia con Arreglo¶

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#define CAPACIDAD_INICIAL 10

secuencia_arreglo_t *crear_secuencia_arreglo(void)
{
    secuencia_arreglo_t *sec = NULL;
    
    sec = malloc(sizeof(secuencia_arreglo_t));
    
    if (sec == NULL)
    {
        return NULL;
    }
    
    sec->elementos = malloc(CAPACIDAD_INICIAL * sizeof(int));
    
    if (sec->elementos == NULL)
    {
        free(sec);
        return NULL;
    }
    
    sec->tamanio = 0;
    sec->capacidad = CAPACIDAD_INICIAL;
    
    return sec;
}

Redimensionamiento Automático¶

Cuando la capacidad se agota, el arreglo debe redimensionarse. Una estrategia común es duplicar la capacidad:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
bool redimensionar(secuencia_arreglo_t *sec)
{
    size_t nueva_capacidad = 0;
    int *nuevo_arreglo = NULL;
    
    if (sec == NULL)
    {
        return false;
    }
    
    nueva_capacidad = sec->capacidad * 2;
    nuevo_arreglo = realloc(sec->elementos, nueva_capacidad * sizeof(int));
    
    if (nuevo_arreglo == NULL)
    {
        return false;
    }
    
    sec->elementos = nuevo_arreglo;
    sec->capacidad = nueva_capacidad;
    
    return true;
}

Insertar al Final¶

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
bool insertar_al_final_arreglo(secuencia_arreglo_t *sec, int dato)
{
    if (sec == NULL)
    {
        return false;
    }
    
    if (sec->tamanio >= sec->capacidad)
    {
        if (!redimensionar(sec))
        {
            return false;
        }
    }
    
    sec->elementos[sec->tamanio] = dato;
    sec->tamanio++;
    
    return true;
}

Acceso por Índice¶

Esta es la operación donde los arreglos brillan: acceso $O(1)$.

1
2
3
4
5
6
7
8
9
10
11
bool obtener_elemento(const secuencia_arreglo_t *sec, size_t indice, int *dato)
{
    if (sec == NULL || dato == NULL || indice >= sec->tamanio)
    {
        return false;
    }
    
    *dato = sec->elementos[indice];
    
    return true;
}

Insertar en Posición Específica¶

Requiere desplazar elementos, resultando en $O(n)$.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
bool insertar_en_posicion_arreglo(secuencia_arreglo_t *sec, size_t pos, int
dato)
{
    size_t i = 0;
    
    if (sec == NULL || pos > sec->tamanio)
    {
        return false;
    }
    
    if (sec->tamanio >= sec->capacidad)
    {
        if (!redimensionar(sec))
        {
            return false;
        }
    }
    
    for (i = sec->tamanio; i > pos; i--)
    {
        sec->elementos[i] = sec->elementos[i - 1];
    }
    
    sec->elementos[pos] = dato;
    sec->tamanio++;
    
    return true;
}

Destruir la Secuencia¶

1
2
3
4
5
6
7
8
9
10
11
12
void destruir_secuencia_arreglo(secuencia_arreglo_t **sec)
{
    if (sec == NULL || *sec == NULL)
    {
        return;
    }
    
    free((*sec)->elementos);
    (*sec)->elementos = NULL;
    free(*sec);
    *sec = NULL;
}

Comparación: Arreglo vs Lista Enlazada como Secuencia¶

Ahora que hemos visto ambas implementaciones del TAD Secuencia, podemos compararlas directamente:

• $O(1)$ en promedio, pero ocasionalmente $O(n)$ cuando se redimensiona.
  ** $O(1)$ si se mantiene puntero al final, $O(n)$ si no.

Complejidad Temporal de las Operaciones¶

La eficiencia de las operaciones es un criterio fundamental al elegir una estructura de datos:

* $O(1)$ si se mantiene un puntero al final.

Comparación: Arreglos vs. Listas Enlazadas como Secuencias¶

Ya hemos visto en detalle cómo tanto los arreglos dinámicos como las listas enlazadas pueden implementar el TAD Secuencia. Esta tabla resume las diferencias clave entre ambas implementaciones:

Ejercicios de Arreglos Dinámicos¶

Genericidad y Callbacks¶

Consideraciones de Implementación¶

Manejo de Errores¶

En C no existen excepciones nativas, por lo que el manejo de errores debe realizarse mediante códigos de retorno o valores especiales. Las convenciones comunes incluyen:

• Retornar bool para indicar éxito (true) o fracaso (false).

• Retornar punteros: NULL indica error.

• Usar parámetros de salida para retornar datos cuando el valor de retorno se usa para el estado.

Invariantes¶

Un invariante es una propiedad que siempre debe ser verdadera en una estructura de datos bien formada. Por ejemplo:

• En una lista: si inicio == NULL, entonces tamanio == 0.

• En una secuencia con arreglo: tamanio <= capacidad.

Mantener estos invariantes es responsabilidad de las funciones de manipulación del TAD.

Seguridad y Robustez¶

1
2
3
4
5
6
7
8
9
10
bool operacion_segura(estructura_t *est, int dato)
{
    if (est == NULL)
    {
        fprintf(stderr, "Error: estructura NULL en operacion_segura\n");
        return false;
    }
    
    return true;
}

Introducción a la Genericidad¶

En los ejemplos anteriores, diseñamos estructuras que almacenan un tipo de dato específico (como enteros int). Sin embargo, en el desarrollo real de software a menudo necesitás estructuras reutilizables que puedan almacenar cualquier tipo de información (números reales, caracteres, structs personalizadas, etc.). Para lograr esto en C estándar sin tener que duplicar el código, se recurre a la genericidad elemental utilizando punteros genéricos void* y funciones callback.

Genericidad con void*¶

Un puntero a void (void*) es un puntero especial que puede almacenar la dirección de cualquier objeto, sin importar su tipo. En C, podés convertir cualquier puntero a void* y viceversa sin necesidad de un cast explícito.

Al diseñar un TAD genérico, la representación de datos interna no guarda el valor directamente, sino un puntero void* que apunta a la dirección de memoria donde se encuentra el dato real.

Funciones Callback¶

Como el TAD genérico maneja direcciones a ciegas (void*), no sabe cómo comparar los elementos, cómo imprimirlos o cómo destruirlos de forma segura. Para solucionar esto, el TAD delega estas tareas al código cliente mediante punteros a funciones o callbacks.

Una función callback es una función escrita por el programador cliente que se pasa como argumento a las funciones del TAD para que este la ejecute en momentos específicos de su ciclo de vida (por ejemplo, al liberar los datos en el destructor o al buscar un elemento).

Estructura de un TAD Genérico¶

Veamos cómo se define una lista enlazada simple genérica:

1
2
3
4
5
6
7
8
9
10
11
typedef struct nodo_generico
{
    void *dato;                    /* Puntero al dato de usuario */
    struct nodo_generico *siguiente;
} nodo_generico_t;

typedef struct lista_generica
{
    nodo_generico_t *inicio;
    size_t tamanio;
} lista_generica_t;

Implementación del Destructor Genérico con Callback¶

Para destruir la lista y liberar la memoria de manera segura, el TAD no puede simplemente invocar free(nodo->dato), porque el dato podría ser una estructura compleja que requiera liberar sus propios campos internos. Por ende, recibimos un callback de destrucción:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/* Firma de la función callback de destrucción */
typedef void (*destruir_dato_fn)(void *);

void destruir_lista_generica(lista_generica_t **lista, destruir_dato_fn
destruir_dato)
{
    if (lista == NULL || *lista == NULL)
    {
        return;
    }
    
    nodo_generico_t *actual = (*lista)->inicio;
    while (actual != NULL) /* Lazo de liberación */
    {
        nodo_generico_t *siguiente = actual->siguiente;
        
        if (destruir_dato != NULL && actual->dato != NULL)
        {
            destruir_dato(actual->dato);
        }
        
        free(actual);
        actual = siguiente;
    }
    
    free(*lista);
    *lista = NULL;
}

Ejemplo de Uso del Cliente¶

Imaginemos que queremos almacenar una estructura persona_t en nuestra lista genérica:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
typedef struct
{
    char *nombre;
    int edad;
} persona_t;

/* Callback personalizado para destruir una persona */
void destruir_persona(void *ptr)
{
    if (ptr == NULL) return;
    persona_t *p = (persona_t *)ptr;
    free(p->nombre); /* Liberamos el recurso interno */
    free(p);         /* Liberamos el struct */
}

/* En el programa principal: */
int main(void)
{
    lista_generica_t *mi_lista = crear_lista_generica();
    
    persona_t *juan = malloc(sizeof(persona_t));
    if (juan != NULL)
    {
        juan->nombre = malloc(strlen("Juan") + 1);
        if (juan->nombre != NULL)
        {
            strcpy(juan->nombre, "Juan");
        }
        juan->edad = 20;
    }
    
    /* Insertamos pasándolo como void* */
    insertar_al_inicio_generico(mi_lista, juan);
    
    /* ... procesamos la lista ... */
    
    /* Al finalizar, destruimos la lista delegando la liberación */
    destruir_lista_generica(&mi_lista, destruir_persona);
    
    return 0;
}

Callbacks de Comparación¶

En colecciones genéricas (void*), el tipo de dato subyacente es desconocido por la estructura. Por lo tanto, operaciones que dependen del valor de los elementos (como la búsqueda de un elemento específico, el ordenamiento o la inserción ordenada) no pueden realizarse con los operadores tradicionales (==, <, >).

Para resolver esto, delegamos la lógica de comparación al cliente a través de un callback de comparación (comparar_fn).

Definición del Tipo¶

El callback sigue la firma estándar de funciones de comparación (como strcmp o la de qsort en <stdlib.h>):

1
typedef int (*comparar_fn)(const void *a, const void *b);

Esta función debe recibir dos punteros genéricos constantes y retornar:

• Un valor menor a cero si el primer elemento es menor que el segundo.

• Cero si ambos elementos son equivalentes.

• Un valor mayor a cero si el primer elemento es mayor que el segundo.

Ejemplo Práctico: Búsqueda Genérica¶

A continuación se presenta cómo el módulo de la lista genérica implementa la búsqueda secuencial, y cómo el código cliente la consume.

En la biblioteca (lista_generica.c):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void *lista_buscar_generica(const lista_generica_t *lista, const void *clave,
comparar_fn comparar) {
    if (lista == NULL || comparar == NULL) {
        return NULL;
    }
    
    nodo_generico_t *actual = lista->inicio;
    // Recorremos la lista con un lazo buscando coincidencia
    while (actual != NULL) {
        if (comparar(actual->dato, clave) == 0) {
            return actual->dato; // Retorna el dato coincidente hallado
        }
        actual = actual->siguiente;
    }
    
    return NULL; // No encontrado
}

En el programa cliente (main.c):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// Callback de comparación personalizado para el tipo persona_t
int comparar_personas_por_nombre(const void *a, const void *b) {
    const persona_t *p1 = (const persona_t *)a;
    const char *nombre_buscado = (const char *)b;
    return strcmp(p1->nombre, nombre_buscado);
}

int main(void) {
    // ... supongamos que la lista ya está creada y poblada con personas ...
    
    const char *buscar_nombre = "Juan";
    persona_t *encontrado = (persona_t *)lista_buscar_generica(
        mi_lista, 
        buscar_nombre, 
        comparar_personas_por_nombre
    );
    
    if (encontrado != NULL) {
        printf("Persona hallada: %s, edad: %d\n", encontrado->nombre,
        encontrado->edad);
    } else {
        printf("Persona '%s' no encontrada.\n", buscar_nombre);
    }
    
    // ... destruir lista ...
    return 0;
}

Ejercicios de Genericidad y Callbacks¶

Ejercicios de Autoevaluación¶

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#ifndef PUNTO_H
#define PUNTO_H

#include <stdbool.h>

/* Declaración incompleta del tipo. La estructura se define en punto.c */
typedef struct punto punto_t;

/* 
 * Constructor: Crea un nuevo punto en el heap.
 * Retorna un puntero al punto creado o NULL si falla la asignación de memoria.
 */
punto_t *punto_crear(double x, double y);

/*
 * Selectores: Retornan las coordenadas del punto.
 * Precondición: el punto no debe ser NULL.
 */
double punto_obtener_x(const punto_t *punto);
double punto_obtener_y(const punto_t *punto);

/*
 * Consultor: Calcula la distancia euclídea entre p1 y p2.
 * Precondición: ambos puntos deben ser válidos (no NULL).
 */
double punto_distancia(const punto_t *p1, const punto_t *p2);

/*
 * Mutador: Modifica las coordenadas del punto.
 * Retorna true si la operación fue exitosa, o false si el punto es NULL.
 */
bool punto_modificar(punto_t *punto, double nuevo_x, double nuevo_y);

/*
 * Destructor: Libera toda la memoria asociada al punto.
 */
void punto_destruir(punto_t **punto);

#endif /* PUNTO_H */

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#ifndef FRACCION_H
#define FRACCION_H

#include <stdbool.h>

/* Tipo de dato abstracto fraccion_t como puntero opaco */
typedef struct fraccion fraccion_t;

/* 
 * Constructor: Crea una fracción simplificada en el heap.
 * Precondición: el denominador no debe ser cero.
 * Retorna NULL si el denominador es cero o si falla la memoria.
 */
fraccion_t *fraccion_crear(int numerador, int denominador);

/*
 * Mutador: Suma dos fracciones y retorna una nueva fracción simplificada.
 * Retorna NULL en caso de error de memoria.
 */
fraccion_t *fraccion_sumar(const fraccion_t *f1, const fraccion_t *f2);

/*
 * Conversor: Devuelve el valor decimal equivalente de la fracción.
 */
double fraccion_a_decimal(const fraccion_t *fraccion);

/*
 * Destructor: Libera la memoria de la fracción.
 */
void fraccion_destruir(fraccion_t **fraccion);

#endif /* FRACCION_H */

struct fecha {
    int dia;
    int mes;
    int anio;
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <stdlib.h>
#include <stdbool.h>

/* Suponemos la existencia de las funciones públicas del TAD pila_t */
typedef struct pila pila_t;
pila_t *pila_crear(void);
bool pila_apilar(pila_t *p, int dato);
int pila_desapilar(pila_t *p);
int pila_ver_tope(const pila_t *p);
bool pila_esta_vacia(const pila_t *p);
void pila_destruir(pila_t **p);

int *pila_a_arreglo(const pila_t *pila, size_t *cantidad)
{
    if (pila == NULL || cantidad == NULL)
    {
        return NULL;
    }

    /* Creamos dos pilas auxiliares para no alterar el estado final */
    pila_t *aux = pila_crear();
    if (aux == NULL)
    {
        return NULL;
    }

    size_t count = 0;
    
    /* Desapilamos de la pila (suponiendo que removemos el const para la copia interna) */
    pila_t *pila_trabajo = (pila_t *)pila; /* Cast de conveniencia para usar la interfaz */
    
    while (!pila_esta_vacia(pila_trabajo))
    {
        int valor = pila_desapilar(pila_trabajo);
        pila_apilar(aux, valor);
        count++;
    }

    int *arreglo = malloc(count * sizeof(int));
    if (arreglo == NULL)
    {
        /* Si falla la asignación, restauramos la pila original antes de salir */
        while (!pila_esta_vacia(aux))
        {
            pila_apilar(pila_trabajo, pila_desapilar(aux));
        }
        pila_destruir(&aux);
        return NULL;
    }

    /* Al reconstruir, guardamos en el arreglo.
       Los elementos en aux están invertidos.
       Para guardarlos del tope a la base en el arreglo: */
    size_t i = 0;
    while (!pila_esta_vacia(aux))
    {
        int valor = pila_desapilar(aux);
        arreglo[i] = valor;
        pila_apilar(pila_trabajo, valor); /* Restauramos el elemento a la pila original */
        i++;
    }

    pila_destruir(&aux);
    *cantidad = count;
    return arreglo;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <stdlib.h>

typedef struct nodo_hash
{
    char *clave;
    void *valor;
    struct nodo_hash *siguiente;
} nodo_hash_t;

struct tabla_hash
{
    nodo_hash_t **baldes;
    size_t capacidad;
    size_t cantidad;
};

void tabla_destruir(tabla_hash_t **tabla, void (*destruir_dato)(void *))
{
    if (tabla == NULL || *tabla == NULL)
    {
        return;
    }

    tabla_hash_t *t = *tabla;
    /* Recorremos todos los baldes del arreglo */
    for (size_t i = 0; i < t->capacidad; i++)
    {
        nodo_hash_t *actual = t->baldes[i];
        
        /* Lazo para recorrer y liberar la lista enlazada de colisiones */
        while (actual != NULL)
        {
            nodo_hash_t *siguiente = actual->siguiente;
            
            /* Liberamos la clave */
            free(actual->clave);
            actual->clave = NULL;
            
            /* Si el cliente pasó un callback, liberamos el valor genérico */
            if (destruir_dato != NULL && actual->valor != NULL)
            {
                destruir_dato(actual->valor);
            }
            
            /* Liberamos el nodo en sí */
            free(actual);
            actual = siguiente;
        }
    }

    /* Liberamos el arreglo de baldes y la estructura contenedora */
    free(t->baldes);
    t->baldes = NULL;
    free(t);
    *tabla = NULL;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <stdlib.h>
#include <stdbool.h>

/* Suponemos declaradas las estructuras lista_t y nodo_t del apunte */

lista_t *fusionar_listas(const lista_t *lista1, const lista_t *lista2)
{
    if (lista1 == NULL || lista2 == NULL)
    {
        return NULL;
    }

    lista_t *resultado = crear_lista();
    if (resultado == NULL)
    {
        return NULL;
    }

    nodo_t *n1 = lista1->inicio;
    nodo_t *n2 = lista2->inicio;

    /* Lazo principal de comparación */
    while (n1 != NULL && n2 != NULL)
    {
        if (n1->dato <= n2->dato)
        {
            if (!insertar_al_final(resultado, n1->dato))
            {
                destruir_lista(resultado);
                return NULL;
            }
            n1 = n1->siguiente;
        }
        else
        {
            if (!insertar_al_final(resultado, n2->dato))
            {
                destruir_lista(resultado);
                return NULL;
            }
            n2 = n2->siguiente;
        }
    }

    /* Lazo para vaciar los elementos restantes de la lista 1, si quedan */
    while (n1 != NULL)
    {
        if (!insertar_al_final(resultado, n1->dato))
        {
            destruir_lista(resultado);
            return NULL;
        }
        n1 = n1->siguiente;
    }

    /* Lazo para vaciar los elementos restantes de la lista 2, si quedan */
    while (n2 != NULL)
    {
        if (!insertar_al_final(resultado, n2->dato))
        {
            destruir_lista(resultado);
            return NULL;
        }
        n2 = n2->siguiente;
    }

    return resultado;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <stdbool.h>
#include <stdlib.h>

bool tiene_ciclo(const lista_t *lista)
{
    if (lista == NULL || lista->inicio == NULL)
    {
        return false;
    }

    nodo_t *lento = lista->inicio;
    nodo_t *rapido = lista->inicio;

    /* Lazo de recorrido a dos velocidades */
    while (rapido != NULL && rapido->siguiente != NULL)
    {
        lento = lento->siguiente;
        rapido = rapido->siguiente->siguiente;

        /* Si los punteros coinciden en la misma dirección de memoria, hay un ciclo */
        if (lento == rapido)
        {
            return true;
        }
    }

    return false;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <stdlib.h>

void invertir_lista(lista_t *lista)
{
    if (lista == NULL || lista->inicio == NULL)
    {
        return;
    }

    nodo_t *anterior = NULL;
    nodo_t *actual = lista->inicio;
    nodo_t *siguiente = NULL;

    /* Lazo para invertir los enlaces */
    while (actual != NULL)
    {
        siguiente = actual->siguiente;  /* Guardamos el resto de la lista */
        actual->siguiente = anterior;  /* Invertimos el enlace del nodo */
        
        /* Avanzamos los punteros de control hacia la derecha */
        anterior = actual;
        actual = siguiente;
    }

    /* El último nodo procesado (anterior) es el nuevo inicio de la lista */
    lista->inicio = anterior;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <stdlib.h>
#include <stdbool.h>

/* Suponemos definida la estructura secuencia_arreglo_t del apunte */

bool insertar_en_posicion_arreglo(secuencia_arreglo_t *sec, size_t pos, int dato)
{
    if (sec == NULL || pos > sec->tamanio)
    {
        return false;
    }

    /* Redimensionamiento si el arreglo está lleno */
    if (sec->tamanio >= sec->capacidad)
    {
        if (!redimensionar(sec))
        {
            return false;
        }
    }

    /* Desplazamos los elementos hacia la derecha para abrir espacio */
    for (size_t i = sec->tamanio; i > pos; i--)
    {
        sec->elementos[i] = sec->elementos[i - 1];
    }

    /* Insertamos el nuevo valor en la posición libre y actualizamos el tamaño */
    sec->elementos[pos] = dato;
    sec->tamanio++;

    return true;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <stdlib.h>
#include <stdbool.h>

#define CAPACIDAD_INICIAL 10

bool eliminar_en_posicion_arreglo(secuencia_arreglo_t *sec, size_t pos)
{
    if (sec == NULL || pos >= sec->tamanio)
    {
        return false;
    }

    /* Desplazamos los elementos siguientes hacia la izquierda */
    for (size_t i = pos; i < sec->tamanio - 1; i++)
    {
        sec->elementos[i] = sec->elementos[i + 1];
    }
    
    sec->tamanio--;

    /* Verificamos si podemos encoger la capacidad para ahorrar memoria */
    if (sec->tamanio < sec->capacidad / 4 && sec->capacidad / 2 >= CAPACIDAD_INICIAL)
    {
        size_t nueva_capacidad = sec->capacidad / 2;
        int *nuevo_arreglo = realloc(sec->elementos, nueva_capacidad * sizeof(int));
        
        /* Si falla realloc al achicar, no consideramos error fatal, mantenemos capacidad */
        if (nuevo_arreglo != NULL)
        {
            sec->elementos = nuevo_arreglo;
            sec->capacidad = nueva_capacidad;
        }
    }

    return true;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <stdlib.h>

/* Suponemos definidas las estructuras de lista genérica del apunte */

void *lista_buscar_generica(const lista_generica_t *lista, const void *clave, int (*comparar)(const void *, const void *))
{
    if (lista == NULL || comparar == NULL)
    {
        return NULL;
    }

    nodo_generico_t *actual = lista->inicio;

    /* Lazo de búsqueda lineal */
    while (actual != NULL)
    {
        /* Invocamos al callback pasándole el dato del nodo y la clave buscada */
        if (comparar(actual->dato, clave) == 0)
        {
            return actual->dato; /* Retornamos el dato original hallado */
        }
        
        actual = actual->siguiente;
    }

    return NULL; /* No se encontró coincidencia en la lista */
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <stdlib.h>
#include <stdbool.h>

void lista_filtrar_generica(lista_generica_t *lista, bool (*predicado)(const void *), void (*destruir_dato)(void *))
{
    if (lista == NULL || predicado == NULL)
    {
        return;
    }

    nodo_generico_t *actual = lista->inicio;
    nodo_generico_t *anterior = NULL;

    /* Lazo de recorrido y filtrado */
    while (actual != NULL)
    {
        nodo_generico_t *siguiente = actual->siguiente;

        if (!predicado(actual->dato))
        {
            /* El elemento no cumple el predicado: debe eliminarse */
            if (anterior == NULL)
            {
                /* Eliminamos el primer elemento */
                lista->inicio = siguiente;
            }
            else
            {
                /* Saltamos el nodo actual en el encadenamiento */
                anterior->siguiente = siguiente;
            }

            /* Liberamos los recursos del dato de usuario si se proveyó callback */
            if (destruir_dato != NULL && actual->dato != NULL)
            {
                destruir_dato(actual->dato);
            }

            /* Liberamos la memoria física del nodo */
            free(actual);
            lista->tamanio--;
        }
        else
        {
            /* Si se conserva el nodo, este pasa a ser el anterior para el siguiente paso */
            anterior = actual;
        }

        actual = siguiente;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <string.h>

typedef struct {
    int padron;
    char *nombre;
    double promedio;
} alumno_t;

int comparar_alumnos(const void *a, const void *b)
{
    /* Casting de punteros genéricos constantes a tipos concretos */
    const alumno_t *alumno_a = (const alumno_t *)a;
    const alumno_t *alumno_b = (const alumno_t *)b;

    /* Comparación por promedio en orden descendente */
    if (alumno_a->promedio > alumno_b->promedio)
    {
        return -1; /* alumno_a va antes porque tiene mayor promedio */
    }
    if (alumno_a->promedio < alumno_b->promedio)
    {
        return 1;  /* alumno_b va antes */
    }

    /* Desempate por padrón en orden ascendente */
    if (alumno_a->padron < alumno_b->padron)
    {
        return -1; /* Menor padrón primero */
    }
    if (alumno_a->padron > alumno_b->padron)
    {
        return 1;
    }

    return 0; /* Alumnos equivalentes en promedio y padrón */
}

Glosario¶

Síntesis y Resumen¶

Resumen de la Unidad¶

En este apunte hemos cubierto:

• El concepto de TAD y la separación de interfaz e implementación.

• El TAD Secuencia como abstracción fundamental, implementado mediante arreglos dinámicos y listas enlazadas.

• Listas enlazadas simples, dobles y circulares, con sus operaciones fundamentales.

• Diferencia física de asignación estática y dinámica en memoria.

Para continuar con estructuras lineales de acceso restringido, consultá Referencias y Lecturas Complementarias.

Referencias y Lecturas Complementarias¶

• King, K. N. King, 2008. C Programming: A Modern Approach (2.ª edición). W. W. Norton & Company.

  • Revisá el Capítulo 19: Program Design, que introduce el concepto de encapsulamiento, ocultamiento de información y la distinción entre interfaz y TAD en C.

• Sedgewick, R. y Wayne, K. Sedgewick & Wayne, 2011. Algorithms (4.ª edición). Addison-Wesley.

  • Consultá el Capítulo 1: Fundamentals, sección de APIs y tipos de datos abstractos, para una perspectiva sobre cómo estructurar colecciones genéricas mediante listas enlazadas.

• Cormen, T. H. y otros Cormen et al., 2009. Introduction to Algorithms (3.ª edición). MIT Press.

  • Estudiá el Capítulo 10: Elementary Data Structures, donde se explica en detalle el funcionamiento lógico de listas enlazadas y estructuras lineales elementales.

• Hanson, D. R. Hanson, 1996. C Interfaces and Implementations. Addison-Wesley.

  • Consultá los capítulos iniciales para comprender el diseño de APIs abstractas basadas en punteros opacos de forma profesional.