Conceptos básicos de estructuras de datos
Antes de aprender formalmente las distintas estructuras de datos, es necesario dominar la clasificación de las estructuras de datos, el concepto de tipo de dato abstracto y repasar los conocimientos clave del lenguaje C estrechamente relacionados con las estructuras de datos.
Clasificación de las estructuras de datos
Las estructuras de datos se pueden clasificar desde dos dimensiones: estructura lógica y método de almacenamiento. Comprender estas dos formas de clasificación ayuda a determinar rápidamente qué tipo de estructura de datos se debe elegir al enfrentar un problema concreto.
La figura anterior muestra el sistema completo de clasificación de las estructuras de datos; a continuación se explica cada uno.
Clasificación por estructura lógica
La estructura lógica describe las relaciones abstractas entre los elementos de datos y no involucra la forma real en que los datos se almacenan en la memoria.
| Tipo | Relación entre elementos | Ejemplo típico | Escenario de aplicación |
|---|---|---|---|
| Estructura lineal | Relación uno a uno de precedencia | Arreglos, listas enlazadas, pilas, colas | Los datos tienen un orden secuencial evidente, como una lista de tareas pendientes o el historial de navegación. |
| Estructura de árbol | Relación jerárquica de uno a muchos | Árbol binario, BST, montículo (heap) | Los datos tienen una pertenencia jerárquica, como los directorios de un sistema de archivos o la estructura organizativa. |
| Estructura de grafo | Relación en red de muchos a muchos | Grafo dirigido, grafo no dirigido, grafo ponderado | Las relaciones entre los datos son complejas, como en las redes sociales o la navegación por mapas. |
Clasificación por método de almacenamiento
El método de almacenamiento describe la forma real en que se organizan los datos en la memoria.
| Tipo | Características | Ejemplo típico | Compensación (trade-off) |
|---|---|---|---|
| Almacenamiento secuencial | Los elementos se almacenan de manera sucesiva en un espacio de memoria contiguo. | Arreglos, pilas/colas implementadas con arreglos | Acceso rápido (O(1)), pero inserción y eliminación lentas y tamaño fijo. |
| Almacenamiento enlazado | Los elementos pueden almacenarse de forma dispersa y se conectan mediante punteros. | Listas enlazadas, árboles, grafos (lista de adyacencia) | Inserción y eliminación rápidas, pero no admite acceso aleatorio y tiene gasto adicional de punteros. |
| Almacenamiento por índice | Se crea una tabla de índices adicional para localizar los datos. | Tabla hash (indexada mediante una función hash) | La búsqueda es extremadamente rápida, pero se necesita espacio adicional para almacenar la estructura de índice. |
La misma estructura lógica se puede implementar con diferentes métodos de almacenamiento. Por ejemplo, una pila (lógicamente una estructura lineal) puede implementarse tanto con un arreglo (almacenamiento secuencial) como con una lista enlazada (almacenamiento enlazado). La elección del método de implementación depende de los distintos requisitos de velocidad de acceso, eficiencia de inserción/eliminación y uso de memoria del escenario de aplicación concreto.
Tipo de dato abstracto (ADT)
Tipo de dato abstracto (Abstract Data Type, abreviado ADT)Es un concepto central en el aprendizaje de las estructuras de datos.
Se refiere a la descripción abstracta de un conjunto de datos y de un conjunto de operaciones definidas sobre esos datos; solo se preocupa por «qué hace», no por «cómo lo hace».
Tomemos la «pila» como ejemplo para entender el ADT:
| Nivel ADT (qué hace) | Nivel de implementación (cómo lo hace) |
|---|---|
| Definir operaciones: push (apilar), pop (desapilar), peek (ver el tope de la pila) | Implementar con un arreglo: mantener un arreglo + puntero top |
| Definir comportamiento: último en entrar, primero en salir (LIFO) | Implementar con una lista enlazada: usar la cabeza de la lista como tope de la pila |
| Establecer la restricción: solo se puede operar desde un extremo | Ambas implementaciones cumplen la definición de ADT, pero sus características de rendimiento son diferentes. |
Esta idea de «separación entre interfaz e implementación» es la piedra angular del diseño modular en la ingeniería de software moderna.
Cuando usas una pila, solo necesitas saber cómo usar operaciones como push y pop; no necesitas preocuparte por si la capa inferior está implementada con un arreglo o una lista enlazada: este es precisamente el valor del ADT.
Repaso de conceptos básicos del lenguaje C
Antes de aprender estructuras de datos, es necesario dominar los siguientes tres conocimientos clave del lenguaje C, que están presentes en casi todos los capítulos de este tutorial.
Puntero (Pointer)
El puntero es una de las características más importantes y flexibles del lenguaje C. Almacena la dirección de memoria de otra variable; a través de él se puede acceder y manipular indirectamente la variable objetivo.
Ejemplo
int main() {
int num = 42; /* variable entera ordinaria */
int *ptr = # /* ptr es un puntero a int, almacena la dirección de num */
printf("valor de num: %d\n", num); /* salida: 42 */
printf("dirección de num: %p\n", &num); /* salida: 0x16d2f2f38 (dirección de ejemplo) */
printf("dirección almacenada en ptr: %p\n", ptr); /* salida: igual que arriba */
printf("valor desreferenciado de *ptr: %d\n", *ptr); /* salida: 42, * es el operador de desreferencia */
*ptr = 100; /* modificar el valor de num a través del puntero */
printf("después de modificar, num = %d\n", num); /* salida: 100 */
return 0;
}
Usos principales de los punteros en las estructuras de datos:
| Uso | Ejemplo |
|---|---|
| Construir conexiones dinámicas entre nodos | En el nodo de la lista enlazada,nextpunteros; en el nodo del árbol,left/rightpunteros. |
| Acceso indirecto y modificación de datos | Hacer que la función modifique el valor de una variable externa a través de un parámetro de puntero |
| Gestión dinámica de memoria | mallocDevuelve la dirección inicial de la memoria asignada; debe recibirse con un puntero. |
| Evitar la copia de grandes cantidades de datos | Al pasar una estructura grande a una función, es más eficiente pasar un puntero que pasar el valor. |
Lo que más confunde a los principiantes es
*y&el uso de * y &: al declarar, *int *pindica que p es un tipo puntero; al usarlo, **pindica desreferencia (obtener el valor);&x& indica obtener la dirección. Estos son dos operadores completamente distintos; comprender esta diferencia es la premisa para usar bien los punteros.
Estructura (struct)
La estructura permite combinar múltiples datos de diferentes tipos en un tipo personalizado; es la unidad básica para construir estructuras de datos compuestas como nodos de listas enlazadas y nodos de árboles.
Ejemplo
#include <string.h> /* archivo de cabecera donde se encuentra la función strcpy */
/* definir la estructura del nodo de la lista enlazada */
struct Node {
int data; /* campo de datos: almacena los datos reales */
struct Node* next; /* campo de puntero: apunta al siguiente nodo */
};
/* definir la estructura de información del estudiante */
struct Student {
int id; /* número de estudiante */
char name[50]; /* nombre, arreglo de caracteres */
float score; /* calificación */
};
int main() {
/* crear un nodo */
struct Node node1;
node1.data = 10;
node1.next = NULL; /* NULL indica que no hay un nodo siguiente */
printf("node1.data = %d\n", node1.data); /* salida: 10 */
/* crear un registro de estudiante */
struct Student stu;
stu.id = 1001;
strcpy(stu.name, "EJEMPLO"); /* strcpy: copia la cadena al arreglo de caracteres */
stu.score = 95.5;
printf("número de estudiante: %d, nombre: %s, calificación: %.1f\n",
stu.id, stu.name, stu.score);
/* salida: número de estudiante: 1001, nombre: EJEMPLO, calificación: 95.5 */
return 0;
}
La estructura combinada con punteros puede implementar estructuras de datos dinámicas flexibles. Por ejemplo, la estructura autorreferencial del nodo de una lista enlazada (struct Node* nextque apunta al siguiente nodo del mismo tipo) es precisamente la base de implementación de la lista enlazada.
Asignación dinámica de memoria
La asignación dinámica de memoria permite al programa solicitar y liberar memoria del montón (heap) según sea necesario en tiempo de ejecución; es la clave para construir estructuras de datos de tamaño variable (como listas enlazadas y árboles).
El lenguaje C proporciona cuatro funciones fundamentales:
| Función | Descripción | Ejemplo |
|---|---|---|
| malloc | Asigna memoria del número de bytes especificado; el contenido no está inicializado. | int* p = malloc(10 * sizeof(int)); |
| calloc | Asigna memoria y la inicializa a cero. | int* p = calloc(10, sizeof(int)); |
| realloc | Ajusta el tamaño de la memoria ya asignada. | p = realloc(p, 20 * sizeof(int)); |
| free | Libera la memoria asignada y la devuelve al sistema. | free(p); |
Ejemplo
#include <stdlib.h> /* archivo de cabecera donde se encuentran malloc y free */
int main() {
int n = 5;
/* malloc: asigna espacio contiguo para n int en el montón (heap) */
int* arr = (int*)malloc(n * sizeof(int));
/* comprobar si la asignación fue exitosa; malloc devuelve NULL si falla */
if (arr == NULL) {
printf("¡Error al asignar memoria!\n");
return 1; /* salida anómala */
}
/* usar la memoria asignada dinámicamente como un arreglo normal */
for (int i = 0; i < n; i++) {
arr[i] = (i + 1) * 10; /* asignación: 10, 20, 30, 40, 50 */
}
printf("contenido del arreglo dinámico: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n"); /* Salida: Contenido del arreglo dinámico: 10 20 30 40 50 */
free(arr); /* Liberar memoria, evitar fugas de memoria */
arr = NULL; /* Buen hábito: establecer el puntero a NULL, evitar punteros salvajes */
return 0;
}
Otras extensionesEl lenguaje C no recupera automáticamente la memoria asignada dinámicamente. Cada vez
malloc(ocalloc) debe tener el correspondientefree, de lo contrario provocará fugas de memoria. En proyectos reales, las fugas de memoria agotan gradualmente los recursos del sistema y, finalmente, provocan el colapso del programa. Este es uno de los errores más comunes que cometen los principiantes del lenguaje C.