Estructuras y listas enlazadas en C: pilas, colas y árboles

Una estructura agrupa valores relacionados en un solo registro. Sus miembros tienen nombres y pueden tener distintos tipos. Una lectura de un sensor, por ejemplo, necesita tanto un identificador como una temperatura.

Define e inicializa un registro

struct reading {
    int id;
    double temp_c;
};
struct reading r = {.temp_c = 21.5, .id = 7};
r.temp_c += 0.5;

La definición introduce el tipo struct reading; reading es su etiqueta. El punto y coma final va después de la llave de cierre. Definir el tipo no reserva ningún objeto. La declaración de r crea un objeto y . selecciona sus miembros. Aquí la temperatura pasa a ser 22,0 °C. Si solo se ha declarado una etiqueta, el nombre del tipo incluye struct: reading r; necesita un typedef independiente.

Un inicializador como {7, 21.5} sigue el orden de declaración. Los designadores como .id = 7 permiten nombrar miembros en otro orden. Los miembros omitidos en un inicializador reciben valores cero, por lo que {0} inicializa todo el registro. Una declaración local struct reading r; sin inicializador deja sus miembros indeterminados hasta que se les asignan valores.

Un miembro tiene su propio tipo y dirección. Para leer una temperatura con scanf, usa scanf("%lf", &r.temp_c) y comprueba que el valor de retorno sea 1. El punto tiene mayor precedencia que &, por lo que esto pasa la dirección del miembro double.

Copia y compara los valores

struct reading s = r;
s.temp_c = -4.0;
int same = r.id == s.id && r.temp_c == s.temp_c;

La asignación copia todos los miembros. Modificar s.temp_c deja r.temp_c en 22,0. Los arrays fijos dentro de estructuras también se copian: un miembro char name[32] pertenece al registro. Esto funciona aunque los arrays independientes de C no puedan asignarse con =. Los miembros de tipo puntero requieren más cuidado porque el puntero copiado sigue apuntando al mismo objeto.

C no define == para estructuras completas. Compara los miembros que definen la igualdad para tu tarea. memcmp compara los bytes de memoria, incluido el relleno, y puede indicar una diferencia entre registros cuyos valores de los miembros son iguales.

Sigue la distribución en memoria

Los miembros aparecen en orden de declaración, sin relleno antes del primero. El compilador puede añadir bytes sin usar entre los miembros y al final para cumplir los requisitos de alineación. En una plataforma habitual de 64 bits con int de 4 bytes y alineación de 4 bytes, struct { char c; int i; char d; } ocupa 12 bytes. Sus miembros empiezan en los desplazamientos 0, 4 y 8. Cambiar el orden a int i; char c; char d; suele reducir el tamaño a 8 bytes. Usa sizeof para el tamaño real y offsetof de <stddef.h> para obtener un desplazamiento.

Las estructuras pueden anidarse. Con struct point { double x_m, y_m; }; y struct rect { struct point corner; double width_m, height_m; };, box.corner.x_m accede a la coordenada x de la esquina en metros. Una estructura no puede contener un miembro completo de su propio tipo: eso requeriría un objeto de tamaño infinito. Un puntero a su propio tipo tiene un tamaño fijo y hace posibles los nodos enlazados.

Un typedef da otro nombre a un tipo existente. Cambia cómo escribes el tipo, no cómo se comportan sus objetos. typedef double meters; convierte meters en otro nombre para double.

Da nombre a una estructura y pásala por valor

typedef struct {
    int id;
    double temp_c;
} reading;

reading make_reading(int id, double t) {
    reading r = {id, t};
    return r;
}
void warm_copy(reading r) {
    r.temp_c += 1.0;
}

Ahora puedes declarar reading r = make_reading(7, 21.5);. Devolver una estructura devuelve su valor. Llamar a warm_copy(r) proporciona a la función una copia, por lo que la temperatura de la función llamadora sigue siendo 21,5 °C. Una copia de un registro pequeño suele ser la interfaz más clara cuando el objeto de la función llamadora debe permanecer sin cambios.

Un tipo autorreferencial necesita su etiqueta dentro de la definición:

typedef struct node {
    int number;
    struct node *next;
} node;

El alias node está disponible después de la declaración. Dentro de estas llaves, struct node ya da nombre al tipo incompleto y puede usarse para un puntero. La etiqueta y el alias pueden escribirse igual porque las etiquetas usan su propio espacio de nombres.

Accede al objeto de la función llamadora mediante un puntero

void warm(reading *p) {
    p->temp_c += 1.0;
}
reading r = {7, 21.5};
reading *p = &r;
p->temp_c -= 1.5;
warm(&r);

La resta cambia r.temp_c a 20,0; después, warm lo cambia a 21,0. La función recibe una copia de la dirección y ambos punteros siguen permitiendo acceder al mismo registro. Usa -> con un puntero y . con un objeto de tipo estructura. p->temp_c significa (*p).temp_c. Los paréntesis son necesarios porque el acceso a miembros tiene mayor precedencia que la desreferenciación: *p.temp_c intenta seleccionar un miembro de p antes de aplicar *.

Para leer sin copiar la estructura, recibe const reading *p. Se rechaza la asignación a p->temp_c mediante ese puntero. La variable de tipo puntero aún puede cambiar, por ejemplo, cuando recorre un array. En cambio, reading *const p hace que el propio puntero sea fijo. En estructuras con miembros de tipo puntero, un puntero a datos constantes no convierte en datos de solo lectura los datos reservados por separado a los que apuntan esos miembros.

Asigna un propietario a un registro en el montículo

Incluye <stdlib.h> para la reserva de memoria y <stdbool.h> para este resultado de éxito:

bool make_heap_reading(reading **out, int id, double t) {
    reading *p = malloc(sizeof *p);
    if (p == NULL) return false;
    *p = (reading){.id = id, .temp_c = t};
    *out = p;
    return true;
}

La función escribe en *out solo después de que la reserva tenga éxito. La función llamadora puede declarar reading *item = NULL;, llamar a make_heap_reading(&item, 8, -2.0), gestionar un resultado falso y llamar más tarde a free(item). sizeof *p mide el tipo al que se apunta incluso antes de que p apunte a un registro inicializado; esta expresión no lee ese registro.

Un puntero a una estructura local automática se vuelve colgante cuando la función retorna. Devuelve el valor de la estructura o un bloque reservado en el montículo con un propietario claramente definido. Devolver &r desde una función cuya variable local es r no puede prolongar su tiempo de vida.

Un array de estructuras mantiene registros uno junto a otro. Usa un índice para seleccionar un registro y después un punto para seleccionar un miembro. Esto permite recorrer, buscar y ordenar de forma muy parecida a como se hace con un array de números.

Recorre registros con un número de elementos explícito

reading readings[4] = {
    {1, 21.5}, {2, -3.0}, {3, 18.25}, {4, 30.0}
};
size_t n = sizeof readings / sizeof readings[0];
size_t best = 0;
for (size_t i = 1; i < n; ++i) {
    if (readings[i].temp_c > readings[best].temp_c)
        best = i;
}

Aquí reading es el alias de la estructura con identificador y temperatura. El mejor índice pasa de 0 a 3, por lo que el registro más cálido tiene id 4 y temperatura 30,0 °C. Empezar con un elemento real también funciona cuando todas las temperaturas son negativas; empezar con un supuesto máximo de cero puede fallar. Este recorrido requiere al menos un elemento. Una búsqueda reutilizable debe informar de que el array está vacío antes de leer el elemento 0.

El cálculo del número de elementos con sizeof funciona donde readings es un array. En un parámetro de función, una declaración de array se convierte en un puntero, por lo que debes pasar n por separado. (items + i)->temp_c e items[i].temp_c acceden al mismo miembro.

Proporciona una función de comparación para qsort

Incluye <stdlib.h>. Para valores finitos de temperatura, esta función de comparación devuelve un signo sin convertir una pequeña diferencia de temperatura en un entero:

int cmp_temp(const void *a, const void *b) {
    const reading *x = a;
    const reading *y = b;
    return (x->temp_c > y->temp_c)
         - (x->temp_c < y->temp_c);
}
/* With the array above: */
qsort(readings, n, sizeof readings[0], cmp_temp);

La función de comparación recibe direcciones de elementos. Un resultado negativo significa que el primero va antes, cero significa que son iguales y uno positivo, que va después. El orden de los id tras la ordenación es 2, 3, 1, 4. Devolver directamente la diferencia de tipo double trunca una diferencia como −0,25 a cero. Restar claves enteras puede causar un desbordamiento. Comparar primero evita esos errores. qsort no conserva el orden original de los elementos iguales.

Amplía un array sin perder su espacio de almacenamiento

Mantén por separado el número de elementos utilizados y la capacidad. Para un array reservado con cap positivo, usa un puntero temporal al duplicar la capacidad. Incluye <stdint.h> para SIZE_MAX:

if (cap > SIZE_MAX / 2 / sizeof *items) return false;
size_t new_cap = 2 * cap;
reading *tmp = realloc(items, new_cap * sizeof *items);
if (tmp == NULL) return false;
items = tmp;
cap = new_cap;

Estas sentencias pertenecen a una función que devuelve bool; items es su puntero al array y cap, su capacidad positiva. Si falla, el bloque de memoria anterior sigue disponible. Si tiene éxito, el bloque puede moverse, por lo que hay que sustituir los punteros antiguos a sus elementos. Una capacidad inicial de cero necesita su propia reserva inicial.

Decide de qué es propietaria una copia

Con typedef struct { char *name; int age; } person;, person b = a; copia la dirección en name. Ambos registros acceden a la misma cadena. Liberar ambas copias como propietarias liberaría dos veces el mismo bloque de memoria. Para obtener una copia independiente, reserva strlen(a.name) + 1 bytes, comprueba que la reserva haya tenido éxito y usa strcpy de <string.h>. Un miembro fijo char name[32] se copia junto con la estructura. strdup realiza la reserva y la copia, pero pertenece a POSIX y C23, no a la biblioteca estándar de C17.

Una enumeración da nombres fáciles de leer a opciones enteras. Nombres como HIGH muestran el propósito de una condición sin obligar a quien lee el código a recordar qué representa el número 10.

Sigue la numeración

enum weekday { MON, TUE, WED, THU, FRI, SAT, SUN };
enum level { LOW = 1, MEDIUM, HIGH = 10, CRITICAL };
enum level alert = HIGH;

Si se omite el primer valor, es cero. Los valores omitidos posteriores aumentan en uno el valor anterior. Así, MON es 0 y SUN es 6; los niveles son 1, 2, 10 y 11. Un valor explícito reinicia la numeración en ese punto. Distintas constantes pueden compartir un valor, pero los valores idénticos no pueden aparecer como etiquetas case separadas en el mismo switch.

Un alias puede acortar una declaración: typedef enum { RED, YELLOW, GREEN } light; permite escribir light signal = RED;. Las constantes de enumeración comparten el espacio de nombres de los identificadores ordinarios en su ámbito. Dos enumeraciones diferentes no pueden declarar ambas RED en el mismo ámbito. Los prefijos como LIGHT_RED y PAINT_RED mantienen los nombres diferenciados.

Gestiona cada opción

const char *level_name(enum level value) {
    switch (value) {
        case LOW: return "low";
        case MEDIUM: return "medium";
        case HIGH: return "high";
        case CRITICAL: return "critical";
    }
    return "unknown";
}

Cada return termina su caso. Si, en cambio, un caso realiza una acción y después debe detenerse, añade un break; llegar a la siguiente etiqueta continúa allí la ejecución. Con GCC, -Wall activa las advertencias por casos de enumeración ausentes cuando no hay default; Clang también diagnostica esas omisiones de forma predeterminada. Una advertencia puede revelar un caso ausente cuando añadas una constante más adelante.

Valida la entrada como un conjunto de opciones

El tipo de enumeración no exige que el valor pertenezca al conjunto de constantes con nombre. C17 permite la asignación desde un entero, por lo que enum level x = 42; puede compilar. Una comprobación de que el número está entre 1 y 11 sigue admitiendo valores sin nombre como 6. Comprueba los valores permitidos concretos:

#include <stdbool.h>
bool valid_level(int value) {
    return value == LOW || value == MEDIUM
        || value == HIGH || value == CRITICAL;
}

Solo después de esa comprobación debe convertirse la entrada en un nivel. Para los días consecutivos de la semana, basta con una comprobación de rango desde MON hasta SUN. En una enumeración ordinaria de C17, las constantes de enumeración tienen tipo int. C23 también permite especificar un tipo subyacente, como enum color : unsigned char; esa sintaxis no es de C17.

Muestra nombres y usa recuentos

printf("%d\n", SUN) muestra «6», no «SUN». Para valores consecutivos que empiezan en cero, un array de nombres proporciona el texto: const char *day_names[] = {"Mon", "Tue", "Wed", "Thu", "Fri", "Sat", "Sun"};. Después de validar un índice, day_names[SUN] es «Sun». Usar un valor de nivel como HIGH para indexar un array de este tipo requeriría otra correspondencia porque los valores de nivel tienen huecos.

Añadir DAY_COUNT inmediatamente después de SUN le da el valor 7, útil como límite de un bucle o tamaño de un array. Cuenta los días, pero no es en sí mismo un día válido. Los nombres de enumeración siguen las reglas de ámbito de C y los depuradores pueden mostrarlos; en cambio, #define realiza una sustitución de texto mediante el preprocesador.

Una unión proporciona el mismo espacio de almacenamiento a varios miembros. Es adecuada para un valor que puede ser de varios tipos. Una estructura proporciona a cada miembro su propio espacio de almacenamiento y es adecuada para un registro que necesita todos esos valores juntos.

Almacena una alternativa

union value {
    int i;
    double d;
    char c;
};
union value v = {.d = 2.5};

Todos los miembros empiezan en la misma dirección. La unión debe poder contener su miembro más grande y cumplir los requisitos de alineación; con un double de 8 bytes en plataformas habituales, esta unión ocupa 8 bytes. Un inicializador simple {42} inicializa su primer miembro, i; .d = 2.5 elige d explícitamente.

Escribir v.i = 42 después del inicializador sustituye la alternativa almacenada. Leer v.d después no convierte 42 en un double: interpreta los bytes almacenados usando otra representación. Esa representación puede ser inválida. Lee el miembro correspondiente al valor que almacenaste.

Registra qué miembro es válido

Combina la unión con una enumeración. La enumeración es la etiqueta y la unión contiene los datos de la variante:

enum kind { K_INT, K_DOUBLE, K_CHAR };
struct tagged {
    enum kind kind;
    union value as;
};
struct tagged make_double(double d) {
    return (struct tagged){.kind = K_DOUBLE, .as = {.d = d}};
}

Una función auxiliar establece ambas partes juntas. El código que escribe mantiene sincronizados los dos campos. Si el código escribe t.as.i pero deja t.kind como K_DOUBLE, una lectura posterior elige la representación incorrecta.

#include <stdio.h>
void print_cell(struct tagged t) {
    switch (t.kind) {
        case K_INT: printf("%d", t.as.i); break;
        case K_DOUBLE: printf("%.1f", t.as.d); break;
        case K_CHAR: printf("%c", t.as.c); break;
    }
}

Llamar a esta función para celdas que contienen 42, 2,5 y 'x', con espacios entre las llamadas, produce «42 2.5 x». Cada caso elige tanto el miembro como el formato correspondientes. Un token de calculadora puede contener de forma similar un número o un operador.

En plataformas habituales de 64 bits, una enumeración de 4 bytes, el relleno y esta unión de 8 bytes hacen que struct tagged ocupe 16 bytes. Una estructura que almacena la enumeración y las tres alternativas por separado suele ocupar 24 bytes. Estos son ejemplos de distribución; consulta los tipos reales con sizeof.

Agrupa indicadores pequeños en campos de bits

struct flags {
    unsigned int ready : 1;
    unsigned int mode : 3;
};

El ancho sigue a los dos puntos. Un campo sin signo de 1 bit contiene 0 o 1; un campo de 3 bits contiene valores de 0 a 7. Al almacenar 9 en mode se conservan los tres bits menos significativos y se almacena 1. Esto pierde información, por lo que debes validar un modo antes de almacenarlo cuando los valores mayores indican un error.

Un campo de bits no tiene una ubicación cuya dirección pueda obtenerse por separado, por lo que &flags.mode no es válido para una variable llamada flags. Su orden de asignación y su distribución dependen de la implementación. No uses una declaración de campo de bits como garantía portable de una distribución exacta de archivo o dispositivo. Un ancho especificado determina el rango de valores del campo, no la distribución de cada byte a su alrededor.

Una lista simplemente enlazada almacena cada elemento en un nodo reservado por separado. Cada nodo contiene su valor y la dirección del nodo siguiente. El puntero al inicio de la lista apunta al primer nodo; NULL marca tanto una lista vacía como el final de una cadena.

Define el enlace e inserta al inicio

#include <stdbool.h>
#include <stdlib.h>
typedef struct node {
    int number;
    struct node *next;
} node;

bool prepend(node **head, int value) {
    node *n = malloc(sizeof *n);
    if (n == NULL) return false;
    n->number = value;
    n->next = *head;
    *head = n;
    return true;
}

Empieza con node *list = NULL;. Llama a prepend(&list, value) y gestiona un resultado falso. La función recibe la dirección del puntero al inicio de la función llamadora. Por tanto, *head designa el puntero que debe cambiar. Recibir solo node *head y asignar un valor a ese puntero local dejaría sin cambios el puntero al inicio de la función llamadora.

El orden de las asignaciones finales conserva la lista anterior. Primero conecta el nodo nuevo con el inicio anterior; después sustituye el inicio. Invertir esas sentencias establece n->next en el propio n y hace perder la cadena anterior. Para las llegadas 1, 2 y 3, las inserciones sucesivas al inicio producen 1, después 2 → 1 y después 3 → 2 → 1 → NULL. La inserción al inicio invierte el orden de llegada.

Recorre sin mover el puntero propietario

#include <stdio.h>
void print_list(const node *head) {
    for (const node *p = head; p != NULL; p = p->next)
        printf("%d ", p->number);
}

El puntero de recorrido p avanza mientras head sigue disponible. El ejemplo muestra «3 2 1 » con un espacio final. Para una lista vacía, el cuerpo del bucle se ejecuta cero veces. No hay índice de array: cada paso lee un enlace para encontrar el nodo siguiente. Los bloques reservados pueden estar dispersos por la memoria, e insertar un nodo no mueve los nodos existentes.

Añade al final

bool append(node **head, int value) {
    node *n = malloc(sizeof *n);
    if (n == NULL) return false;
    *n = (node){.number = value, .next = NULL};
    node **link = head;
    while (*link != NULL) link = &(*link)->next;
    *link = n;
    return true;
}

link empieza en el puntero al inicio de la función llamadora. Después pasa a la dirección de cada miembro next hasta que designa el enlace nulo final. Asignar ahí también funciona para una lista vacía. Sin un puntero guardado al final, cada inserción al final debe seguir primero la cadena existente hasta su extremo. Una función también puede devolver un nuevo puntero al inicio, siempre que la función llamadora lo guarde y gestione el fallo de reserva sin perder la lista anterior.

Libera los nodos en un orden seguro

void clear_list(node **head) {
    while (*head != NULL) {
        node *old = *head;
        *head = old->next;
        free(old);
    }
}

Lee el sucesor mientras old aún existe, mueve el puntero al inicio y después libera el nodo antiguo. Tras el bucle, el puntero al inicio de la función llamadora es NULL. Leer old->next después de liberar old es un uso después de la liberación aunque la memoria parezca no haber cambiado. Un comprobador de memoria puede ayudar a detectar lecturas inválidas y bloques de memoria olvidados; la liberación de recursos también debe ejecutarse si falla una operación posterior.

La búsqueda en una lista sigue un enlace a la vez. La inserción y la eliminación necesitan algo más: la dirección del enlace que debe cambiar. Ese enlace puede ser el puntero al inicio o un miembro next dentro de un nodo anterior.

Busca por valor

Con el tipo node, que tiene los miembros number y next:

node *find(node *head, int value) {
    for (node *p = head; p != NULL; p = p->next)
        if (p->number == value) return p;
    return NULL;
}

Una coincidencia devuelve la dirección del propio nodo. Si el valor no está presente, devuelve NULL. Llegar al nodo número 1000 requiere seguir 999 enlaces desde el inicio, incluso cuando conoces su posición de antemano.

Mantén un puntero al enlace que cambiará

Un node ** puede apuntar al puntero al inicio o al campo next de un nodo. Llámalo link: *link es el nodo al que se llega actualmente mediante ese enlace. Avanzar con link = &(*link)->next cambia el enlace que examinas; no modifica la lista.

bool insert_sorted(node **head, int value) {
    node **link = head;
    while (*link != NULL && (*link)->number < value)
        link = &(*link)->next;
    node *n = malloc(sizeof *n);
    if (n == NULL) return false;
    n->number = value;
    n->next = *link;
    *link = n;
    return true;
}

Incluye <stdbool.h> y <stdlib.h>. La lista de entrada ya debe estar en orden ascendente. Detente antes del primer valor que no sea menor que el nuevo, de modo que los duplicados se sitúen antes de los valores iguales. El lado izquierdo de && comprueba si es NULL antes de que el lado derecho desreferencie el nodo. Intercambiar esas pruebas desreferenciaría un puntero nulo al llegar al final.

Para las inserciones 5, 2, 8 y 4, la lista final es 2 → 4 → 5 → 8. Al insertar 4 en 2 → 5 → 8, link pasa del puntero al inicio a 2.next. El nuevo nodo apunta a 5 y 2.next se redirige al nuevo nodo. Si el nuevo elemento es el menor, link sigue designando el puntero al inicio. Al final, designa el enlace nulo final.

Desenlaza antes de liberar

bool remove_first(node **head, int value) {
    node **link = head;
    while (*link != NULL && (*link)->number != value)
        link = &(*link)->next;
    if (*link == NULL) return false;
    node *old = *link;
    *link = old->next;
    free(old);
    return true;
}

El bucle encuentra el enlace entrante. Guardar su destino como old mantiene el nodo disponible mientras *link se cambia para que apunte a su sucesor. Solo entonces se libera el nodo eliminado. Eliminar 5 de 2 → 4 → 5 → 8 da 2 → 4 → 8. Eliminar después 2 cambia el puntero al inicio y deja 4 → 8. Si el valor está ausente, la función devuelve falso sin modificar la lista.

Una versión con dos punteros mantiene prev y cur. Cuando prev es nulo, la coincidencia es el primer nodo y debe cambiarse el puntero al inicio; en otro caso, actualiza prev->next. Olvidar el caso del primer nodo deja un puntero a memoria liberada. La versión con la dirección del enlace gestiona ambos casos mediante la misma asignación.

Comprueba una entrada vacía, una lista de un nodo, coincidencias en el primer y el último nodo y un valor ausente. Para cada cambio, identifica el enlace entrante, el nodo afectado y su sucesor antes de escribir una asignación. Ningún nodo que deba conservarse debería quedar inaccesible, y ningún enlace debería apuntar a un nodo liberado.

La pregunta útil es qué operaciones realiza tu programa. Los arrays y las listas pueden contener los mismos valores, pero acceden a ellos y los mueven de forma diferente.

Compara las operaciones

Una lista no hace que encontrar una posición sea gratuito. La inserción después de un nodo del que ya tienes un puntero es directa, pero la eliminación también necesita el predecesor o el enlace que apunta al nodo. Si solo se dispone de la dirección del nodo, una lista simplemente enlazada generalmente requiere un recorrido desde el inicio para encontrar ese enlace entrante.

El almacenamiento también importa. En una plataforma típica de 64 bits, un nodo con un int de 4 bytes y un puntero de 8 bytes ocupa 16 bytes después del relleno. Para 1000 enteros, los nodos usan 16 000 bytes más los datos de gestión de las reservas; un array contiguo de enteros usa 4000 bytes. Recorrer el array suele ser más rápido porque los valores próximos se almacenan juntos.

Mantén juntos los metadatos de la lista

typedef struct {
    node *head;
    node *tail;
    size_t count;
} list_t;

Inicializa una estructura contenedora con list_t list = {0};. Las reglas de su estado vacío son head == NULL, tail == NULL y count == 0. Cada inserción o eliminación que tenga éxito debe actualizar el contador además de los enlaces. Un fallo de reserva no modifica ninguno de ellos.

Con un puntero al final, añadir un nodo después de comprobar la reserva requiere estas asignaciones:

n->next = NULL;
if (list.tail == NULL) list.head = n;
else list.tail->next = n;
list.tail = n;
++list.count;

Aquí n es un nodo inicializado. Para el primer nodo, los punteros al inicio y al final pasan a ser iguales. Eliminar el último nodo exige mover el puntero al final hacia atrás; en una lista simplemente enlazada esto requiere el predecesor. Eliminar el único nodo establece ambos extremos en NULL y el contador en cero.

Enlaza en ambas direcciones

typedef struct dnode {
    int value;
    struct dnode *prev, *next;
} dnode;
typedef struct {
    dnode *head, *tail;
} dlist;

void unlink_node(dlist *list, dnode *d) {
    if (d->prev != NULL) d->prev->next = d->next;
    else list->head = d->next;
    if (d->next != NULL) d->next->prev = d->prev;
    else list->tail = d->prev;
    free(d);
}

Esta función recibe un nodo existente que pertenece a la lista. Los enlaces de ambos vecinos se actualizan antes de liberarlo. En los extremos se cambia el puntero al inicio o al final en lugar del enlace de un vecino ausente. Una lista doblemente enlazada puede recorrerse hacia atrás y permite eliminar un nodo del que se tiene un puntero sin buscar su predecesor, a costa de otro puntero por nodo y más enlaces que mantener.

Libera los datos que posee el nodo antes de liberarlo

Un word_node puede ser propietario tanto del bloque del nodo como de un bloque para una cadena mediante word. Guarda next, llama a free(n->word), después a free(n) y avanza al sucesor guardado. Liberar solo el nodo provoca una fuga de la cadena. Leer n->word después de liberar el nodo no es válido. La propiedad indica qué código debe liberar cada bloque reservado, incluso cuando varios punteros permiten acceder a él.

Una pila elimina primero el elemento añadido más recientemente: último en entrar, primero en salir (LIFO). Sus operaciones definen un tipo abstracto de datos independientemente de que los valores se almacenen en un array o en nodos enlazados. push añade en la cima, pop elimina el elemento de la cima y peek lo lee sin eliminarlo.

Usa un array y un contador

#include <stdbool.h>
#define STACK_CAP 100
typedef struct {
    int items[STACK_CAP];
    int top;
} stack;

bool push(stack *s, int value) {
    if (s->top == STACK_CAP) return false;
    s->items[s->top++] = value;
    return true;
}
bool pop(stack *s, int *out) {
    if (s->top == 0) return false;
    *out = s->items[--s->top];
    return true;
}

Inicializa con stack s = {0};. Aquí top es el número de elementos almacenados, por lo que el índice ocupado de la cima es top - 1. Una inserción que tiene éxito escribe en la siguiente posición libre e incrementa el contador. Una extracción que tiene éxito primero reduce el contador y después lee ese índice. La función llamadora proporciona un puntero out válido y comprueba el resultado antes de usar su valor.

Apilar 4, 7 y 1 y después extraer dos veces devuelve 1 y 7, y deja 4. Sin una comprobación de capacidad, insertar en una pila llena escribe en items[STACK_CAP] después del final. Sin la comprobación de pila vacía, el top con signo baja de 0 a −1 y la extracción lee items[-1]. Ambos accesos tienen comportamiento indefinido.

Usa el inicio de una lista como cima

Una pila enlazada inserta al inicio un nodo cuya reserva se ha comprobado. La extracción elimina el primer nodo:

bool pop_linked(node **top, int *out) {
    if (*top == NULL) return false;
    node *old = *top;
    *out = old->number;
    *top = old->next;
    free(old);
    return true;
}

node tiene un number entero y un puntero next. Una pila enlazada no tiene la capacidad fija de un array, pero una inserción puede fallar si falla la reserva. Sigue necesitando comprobaciones de pila vacía y la liberación de los nodos que queden al final.

Comprueba delimitadores anidados

Recorre la entrada de izquierda a derecha. Apila cada paréntesis, corchete o llave de apertura. Para cada delimitador de cierre, extrae uno y comprueba que los tipos coincidan. Un delimitador de cierre sin uno de apertura falla de inmediato. Termina comprobando que la pila esté vacía: los delimitadores de apertura restantes también indican una falta de correspondencia.

El texto «( [ ] { } )» está equilibrado. En «( ]», el delimitador de cierre no corresponde al de apertura extraído. En «( ( )», queda un delimitador de apertura después del recorrido. Un simple recuento de delimitadores de apertura y cierre no detectaría un anidamiento incorrecto como «( [ ) ]».

Evalúa expresiones posfijas

Apila los números a medida que llegan. Para un operador binario, extrae primero el operando derecho y después el izquierdo, calcula left operator right y apila el resultado. Para «3 4 + 2 *», + combina 3 y 4 para obtener 7, después * combina 7 y 2 para obtener 14. Para «9 4 -», extrae 4 como operando derecho y 9 como izquierdo, lo que produce 5. Invertirlos produce −5. Rechaza los casos con operandos insuficientes y exige un único resultado final; la división también necesita un operando derecho distinto de cero.

Las llamadas a funciones tienen tiempos de vida organizados como una pila: una función llamada retorna antes de que continúe la función llamadora. Cada llamada activa necesita un marco, por lo que una recursión muy profunda puede agotar la pila de llamadas incluso cuando las reservas en el montículo tienen éxito.

Una cola elimina primero el elemento más antiguo: primero en entrar, primero en salir (FIFO). Encolar añade al final; desencolar elimina del inicio. Después de encolar A, B y C, las dos siguientes extracciones devuelven A y B. Esto se adapta al trabajo que debe procesarse en orden de llegada.

Mantén ambos extremos de una cola enlazada

Con nodos que tienen los miembros number y next, e incluyendo <stdbool.h> y <stdlib.h>:

typedef struct { node *head, *tail; } queue;

bool enqueue(queue *q, int value) {
    node *n = malloc(sizeof *n);
    if (n == NULL) return false;
    *n = (node){.number = value, .next = NULL};
    if (q->tail == NULL) q->head = n;
    else q->tail->next = n;
    q->tail = n;
    return true;
}
bool dequeue(queue *q, int *out) {
    if (q->head == NULL) return false;
    node *old = q->head;
    *out = old->number;
    q->head = old->next;
    if (q->head == NULL) q->tail = NULL;
    free(old);
    return true;
}

Inicializa con queue q = {0};. Encolar establece el enlace del antiguo nodo final antes de mover el puntero al final. Para el primer nodo, también establece el puntero al inicio. Desencolar mueve el puntero al inicio hacia delante. Cuando eso elimina el único nodo, el puntero al final también debe pasar a ser NULL. De lo contrario, la siguiente inserción escribe mediante un puntero al final colgante. Ninguna de las dos operaciones necesita recorrer la lista.

Reutiliza un array fijo como anillo

Una cola en un array simple que siempre elimina del índice 0 debe desplazar los valores restantes. Un búfer circular mantiene, en cambio, un índice del inicio y un contador de elementos:

#define CAP 4
typedef struct {
    char items[CAP];
    unsigned head, count;
} ring;

bool ring_put(ring *q, char value) {
    if (q->count == CAP) return false;
    q->items[(q->head + q->count) % CAP] = value;
    ++q->count;
    return true;
}
bool ring_get(ring *q, char *out) {
    if (q->count == 0) return false;
    *out = q->items[q->head];
    q->head = (q->head + 1) % CAP;
    --q->count;
    return true;
}

Inicializa un anillo con {0}. head siempre identifica el elemento inicial cuando la cola no está vacía. El siguiente índice de inserción es el inicio más el número de elementos, con vuelta al principio mediante % CAP. Lee el elemento inicial antes de mover head. El contador distingue entre vacío y lleno sin renunciar a una posición.

Sigue la vuelta al principio

Encola A, B y C en las posiciones 0, 1 y 2. Desencola A: el inicio pasa a ser 1 y el contador pasa a ser 2. D entra en la posición 3; E entra en la posición 0. El array físico contiene ahora E, B, C, D, pero el orden lógico de extracción es B, C, D, E. El anillo está lleno porque el contador es 4, aunque el inicio esté en el índice 1.

Otro diseño mantiene el índice del inicio y el índice de la siguiente posición libre al final sin un contador. En ese diseño, índices iguales podrían significar vacío o lleno, por lo que una política habitual deja una posición sin usar. Vacío es head == tail; lleno es (tail + 1) % CAP == head. No mezcles esa política con las reglas de capacidad de la versión basada en un contador. Las colas también permiten visitar árboles nivel por nivel al mantener los nodos que esperan su turno.

Un árbol binario da a cada nodo como máximo dos hijos, llamados izquierdo y derecho. La raíz es el nodo superior. Una hoja no tiene hijos y un nodo, junto con todos sus descendientes, es un subárbol. Un hijo ausente y un árbol vacío se representan mediante NULL.

Representa las ramas

typedef struct tnode {
    int key;
    struct tnode *left;
    struct tnode *right;
} tnode;

Cada puntero a un hijo conduce a la raíz de otro árbol. Por tanto, la misma definición describe una hoja, un árbol grande con ramas o una cadena larga. La altura cuenta las aristas del camino más largo desde la raíz hasta una hoja: una raíz sola tiene altura 0. Usa −1 para un árbol vacío, de modo que los dos subárboles vacíos de una hoja den naturalmente altura 0. Contar niveles daría uno más.

Aplica la regla a subárboles completos

Un árbol binario de búsqueda, o BST, ordena las claves. Para cada nodo, todas las claves de su subárbol izquierdo son menores y todas las de su subárbol derecho son mayores. Almacena cada clave una sola vez. Esta condición incluye a los descendientes lejanos. Una raíz 50 con hijo izquierdo 30 y un hijo derecho 60 bajo ese 30 no es válida: 60 sigue estando en el subárbol izquierdo de 50.

Inserta 50, 30, 70, 20, 40, 60 y 80 en un BST vacío. La raíz es 50; 30 y 70 son sus hijos. Los hijos de 30 son 20 y 40, y los de 70 son 60 y 80. Cada elección de rama conserva los límites heredados de los antepasados.

Elige una rama en cada paso

#include <stddef.h>
tnode *search(tnode *t, int key) {
    while (t != NULL) {
        if (key == t->key) return t;
        if (key < t->key) t = t->left;
        else t = t->right;
    }
    return NULL;
}

Buscar 60 en el ejemplo visita 50, va a la derecha hasta 70 y después a la izquierda hasta 60: tres nodos. Buscar 65 sigue el mismo camino y después intenta acceder al hijo derecho de 60. Ese hijo es NULL, por lo que 65 está ausente. No necesitas examinar el subárbol izquierdo de 50 porque todas sus claves son menores que 50.

La forma recursiva gestiona primero t == NULL y una clave coincidente, y después busca en el hijo seleccionado. La comprobación del subárbol vacío es el caso base. Sin ella, una búsqueda fallida acaba desreferenciando un puntero nulo. La versión con bucle se detiene en el mismo límite sin añadir llamadas recursivas.

Usa la forma para explicar el trabajo

Un árbol perfectamente equilibrado con 20 niveles contiene 1 048 575 claves y una búsqueda visita como máximo 20 nodos. En cambio, insertar las claves ya ordenadas 10, 20, 30, 40, 50 crea una cadena hacia la derecha. Su altura es 4 y encontrar 50 visita los cinco nodos. La regla de ordenación de un BST por sí sola no mantiene el árbol bajo. Los árboles autoequilibrados, como los árboles AVL, reorganizan las ramas para controlar la altura.

Para encontrar un mínimo, sigue los hijos izquierdos hasta que el siguiente enlace izquierdo sea NULL. Para encontrar un máximo, sigue los hijos derechos. En el ejemplo de siete nodos estas claves son 20 y 80. Las mismas elecciones de dirección funcionan en la raíz de cualquier subárbol porque la regla de ordenación también se aplica allí.

Las funciones sobre árboles trabajan sobre un subárbol y conectan su resultado con el padre. Mantén explícito el caso del subárbol vacío y distingue las operaciones que modifican enlaces de las que solo visitan nodos.

Inserta mediante el enlace al subárbol

Con tnode que contiene key, left y right, incluye <stdbool.h> y <stdlib.h>:

bool insert(tnode **link, int key) {
    if (*link == NULL) {
        tnode *n = malloc(sizeof *n);
        if (n == NULL) return false;
        *n = (tnode){.key = key, .left = NULL, .right = NULL};
        *link = n;
        return true;
    }
    if (key < (*link)->key) return insert(&(*link)->left, key);
    if (key > (*link)->key) return insert(&(*link)->right, key);
    return true;
}

Llama con insert(&root, key) y comprueba su resultado. Una clave existente deja el árbol sin cambios y se considera un éxito. La dirección del enlace permite que la inserción actualice la raíz de la función llamadora o un puntero a un hijo. En una interfaz que devuelve la raíz, guarda cada resultado: t->left = insert(t->left, key) y root = insert(root, key). Ignorar un bloque reservado devuelto cuando el subárbol original estaba vacío deja ese nodo sin enlazar y provoca una fuga.

Elige cuándo visitar la raíz

Para las inserciones 50, 30, 70, 20, 40, 60, 80, la salida en inorden es «20 30 40 50 60 70 80». El preorden da «50 30 20 40 70 60 80»; el postorden da «20 40 30 60 80 70 50».

void free_tree(tnode *t) {
    if (t == NULL) return;
    free_tree(t->left);
    free_tree(t->right);
    free(t);
}

Después de free_tree(root), establece root = NULL en el código propietario. La función libera primero los hijos para poder leer sus direcciones desde el padre, que aún existe. El tamaño es cero para un subárbol vacío y, en otro caso, uno más los tamaños de ambos hijos. La altura es −1 para un árbol vacío y, en otro caso, uno más la mayor altura de los hijos. El ejemplo tiene tamaño 7 y altura 2.

Elimina sin romper el orden

Una hoja pasa a ser NULL. Un nodo con un hijo se sustituye por ese hijo. Para dos hijos, copia la clave menor del subárbol derecho en el nodo y después elimina ese sucesor de su posición original:

tnode *erase(tnode *t, int key) {
    if (t == NULL) return NULL;
    if (key < t->key) t->left = erase(t->left, key);
    else if (key > t->key) t->right = erase(t->right, key);
    else {
        if (t->left == NULL || t->right == NULL) {
            tnode *child = t->left != NULL ? t->left : t->right;
            free(t);
            return child;
        }
        tnode *s = t->right;
        while (s->left != NULL) s = s->left;
        t->key = s->key;
        t->right = erase(t->right, s->key);
    }
    return t;
}

Llama como root = erase(root, key). Eliminar 50 del ejemplo coloca 60 en la raíz y elimina el antiguo nodo 60. La salida en inorden pasa a ser «20 30 40 60 70 80»; en preorden pasa a ser «60 30 20 40 70 80». Un sucesor puede tener un hijo derecho, por lo que su eliminación debe volver a conectar ese hijo.

Para claves de palabras, usa el signo de strcmp, no la igualdad de punteros, y reserva un bloque propio para cada palabra de la que el árbol sea propietario. Libera la palabra antes que su nodo. La eliminación de registros de este tipo con dos hijos también necesita un plan de propiedad para la palabra trasladada y cualquier valor asociado; copiar un puntero propietario y después liberar la palabra de su nodo original dejaría una clave colgante.

Una tabla de dispersión elige una ubicación inicial a partir de una clave. Una función de dispersión produce un número; calcular el resto de dividir ese número entre un número positivo de cubetas da un índice. El encadenamiento separado mantiene una lista enlazada en cada cubeta, por lo que la búsqueda recorre la cadena seleccionada.

Separa la dispersión de la igualdad

Una función de dispersión útil es determinista, rápida de calcular y distribuye las claves esperadas entre las cubetas. Las claves iguales deben producir valores de dispersión iguales. Las claves diferentes aún pueden compartir un índice: esto es una colisión, y toda tabla debe gestionarla. Cuando hay más claves posibles que cubetas, algunas colisiones son inevitables.

Para palabras que empiezan por una letra en un sistema compatible con ASCII, toupper((unsigned char)word[0]) - 'A' asigna 26 cubetas de letras; «Luigi» empieza en la cubeta 11. Muchas palabras inglesas empiezan por «s» y pocas por «x», por lo que esta regla puede dejar cadenas muy desiguales. La conversión explícita de tipo es necesaria porque las funciones de <ctype.h> requieren un valor de carácter sin signo o EOF. Valida la letra inicial y el supuesto sobre el conjunto de caracteres antes de usar esta regla de indexación.

Una función de dispersión basada en la suma de caracteres también tiene debilidades. Con códigos ASCII y diez cubetas, «cat» suma 99 + 97 + 116 = 312 y llega a la cubeta 2; «dog» suma 314 y llega a la cubeta 4. «act» también suma 312. La suma pierde el orden de las letras, por lo que todas sus reorganizaciones colisionan.

Incorpora el orden de los caracteres al valor de dispersión

unsigned long hash_word(const char *word) {
    unsigned long h = 5381;
    const unsigned char *p = (const unsigned char *)word;
    while (*p != '\0') {
        h = h * 33 + *p;
        ++p;
    }
    return h;
}

Este patrón djb2 usa aritmética sin signo, cuyo desbordamiento se reduce modularmente de forma definida. El desbordamiento con signo tendría comportamiento indefinido. Para las cadenas ASCII «cat» y «act», los valores son 193 488 125 y 193 486 013. Calcula el índice con hash_word(word) % N, donde N es el número positivo de cubetas. El orden de las letras cambia estos valores de dispersión, aunque calcular el resto aún puede producir una colisión.

Si una tabla trata «Cat» y «cat» como iguales, tanto la función de dispersión como la comparación deben usar la misma regla para las mayúsculas y minúsculas. Ignorarlas solo durante la comparación puede enviar claves iguales a cubetas distintas, donde la búsqueda no las comparará. Un resto negativo de un valor de dispersión con signo tampoco es adecuado como índice de array.

Elige una estrategia para las colisiones

El encadenamiento separado almacena cada colisión en la lista enlazada de una cubeta. La búsqueda compara claves hasta encontrar una coincidencia o llegar al final. El direccionamiento abierto almacena las entradas en el propio array. Con sondeo lineal, una colisión lleva a probar la posición siguiente y a volver al principio al llegar al final. La búsqueda sigue la misma secuencia de sondeo, por lo que puede examinar varias posiciones del array.

Reconstruye los índices cuando la tabla crece

El factor de carga es el número de claves almacenadas dividido entre el número de cubetas. Doce claves en ocho cubetas dan 1,5 entradas por cubeta de media. Dieciséis cubetas reducen esa media a 0,75. Esta media no garantiza que todas las cadenas sean cortas; una función de dispersión deficiente puede colocar todas las claves juntas.

Un índice de cubeta depende del número de cubetas. Después de reservar e inicializar un array de cubetas más grande, vuelve a calcular el índice de cada clave almacenada para el nuevo número de cubetas y enlázala allí. Copiar los antiguos punteros al inicio en las nuevas cubetas con los mismos números deja las claves en lugares donde la nueva búsqueda no las buscará. Una tabla con encadenamiento puede contener más entradas que cubetas; el direccionamiento abierto necesita posiciones sin usar para las nuevas entradas y para un sondeo fiable.

Una tabla con encadenamiento combina un array, enlaces de lista, comparación de cadenas y propiedad de la memoria. Cada entrada es propietaria de su clave copiada. El array de cubetas es propietario de las cadenas y cada cadena termina en NULL.

Inicializa cubetas y busca texto

#include <stdbool.h>
#include <limits.h>
#include <stdlib.h>
#include <string.h>
#define N 26
typedef struct entry {
    char *key;
    int count;
    struct entry *next;
} entry;
static entry *table[N];

El almacenamiento estático empieza con punteros nulos en todas las cubetas. Un array local necesita, en cambio, un inicializador como entry *table[N] = {NULL};. Usa la función hash_word sin signo que empieza en 5381 e incorpora cada byte con el multiplicador 33.

entry *find_word(const char *key) {
    size_t i = hash_word(key) % N;
    for (entry *e = table[i]; e != NULL; e = e->next)
        if (strcmp(e->key, key) == 0) return e;
    return NULL;
}

strcmp compara texto. e->key == key comprobaría si los punteros designan la misma ubicación. Dos búferes separados pueden contener palabras iguales, por lo que la igualdad de punteros no sirve para buscar una palabra.

Cuenta una clave existente o instala una nueva

bool add_word(const char *key) {
    entry *e = find_word(key);
    if (e != NULL) {
        if (e->count == INT_MAX) return false;
        ++e->count;
        return true;
    }
    e = malloc(sizeof *e);
    if (e == NULL) return false;
    e->key = malloc(strlen(key) + 1);
    if (e->key == NULL) {
        free(e);
        return false;
    }
    strcpy(e->key, key);
    e->count = 1;
    size_t i = hash_word(key) % N;
    e->next = table[i];
    table[i] = e;
    return true;
}

La función llamadora proporciona una cadena terminada en nulo. La comprobación de INT_MAX informa de un fallo antes de que el contador desborde su almacenamiento int. El byte adicional de la reserva de la cadena contiene '\0'. Si falla la segunda reserva, libera la entrada que aún no está enlazada. El puntero al inicio de la cubeta solo cambia después de que ambas reservas y la inicialización tengan éxito.

Guardar e->key = key conservaría, en cambio, el espacio de almacenamiento de la función llamadora. Si la entrada reutiliza repetidamente un búfer, cada puntero guardado podría mostrar la palabra más reciente. Copiar el texto da a cada entrada un tiempo de vida independiente de ese búfer. strdup proporciona esa operación en POSIX y C23; la reserva explícita y strcpy funcionan en C17.

En un ejemplo con diez cubetas y una suma de caracteres, insertar «cat», «dog», «act» deja «act» → «cat» en la cubeta 2 y «dog» en la cubeta 4. Buscar «tac» recorre la cubeta 2, compara ambas palabras y llega a NULL. Una cubeta coincidente solo es una ubicación candidata, no una prueba de que haya una clave igual.

Libera los datos, los nodos y los punteros al inicio de las cubetas

void clear_table(void) {
    for (size_t i = 0; i < N; ++i) {
        entry *e = table[i];
        while (e != NULL) {
            entry *next = e->next;
            free(e->key);
            free(e);
            e = next;
        }
        table[i] = NULL;
    }
}

Guardar next y liberar la clave ocurre mientras la entrada aún existe. Restablecer cada cubeta permite reutilizarla. Las herramientas de comprobación de memoria ayudan a verificar las rutas ejecutadas; las rutas de fallo de reserva también necesitan liberar recursos. El orden de dispersión no es un orden clasificado. Para mostrar las claves alfabéticamente, recógelas para ordenarlas o almacénalas en un BST.

En el direccionamiento abierto, la eliminación necesita una marca de borrado para que la búsqueda continúe a través de una posición eliminada hasta las claves posteriores que colisionaron. Una posición realmente sin usar puede terminar una búsqueda fallida. Las secuencias de sondeo deben estar limitadas y la tabla debe ampliarse antes de que todas las posiciones estén ocupadas.