Concepto de datos estructurado
Un dato estructurado es aquel que organiza información en un formato definido, facilitando su almacenamiento, procesamiento y recuperación. A diferencia de los datos simples, los estructurados permiten agrupar varios valores relacionados, manteniendo una relación lógica entre ellos. Ejemplos: arreglos, listas, pilas, colas y árboles.
Tipos de datos estructurados
Los tipos de datos estructurados se dividen principalmente en:
- Estáticos: Su tamaño se define antes de ejecutar el programa y permanece fijo durante toda la ejecución.
- Dinámicos: Su tamaño y forma pueden variar durante la ejecución del programa, permitiendo mayor flexibilidad en el manejo de la memoria.
Estáticos
- Simples: Son estructuras que almacenan un único valor a la vez, como enteros, caracteres, booleanos o reales. Representan los bloques básicos de construcción de los programas.
- Compuestos: Son estructuras que permiten almacenar múltiples valores bajo un mismo identificador, generalmente del mismo tipo. Ejemplos: arreglos, vectores y registros.
Dinámicos
- Pilas (Stacks): Estructura lineal que sigue la política LIFO (Last In, First Out), en la que el último elemento que entra es el primero en salir. Ejemplo: el manejo del botón “Deshacer” en editores de texto.
- Colas (Queues): Estructura lineal que sigue la política FIFO (First In, First Out), en la que el primer elemento en entrar es el primero en salir. Ejemplo: el orden de espera en una fila.
- Listas (Linked Lists): Conjunto de nodos enlazados dinámicamente mediante punteros. Cada nodo contiene un valor y una referencia al siguiente nodo, lo que permite crecer o reducir su tamaño en ejecución.
- Árbol (Tree): Estructura jerárquica compuesta por nodos conectados. El nodo inicial se llama raíz, y a partir de él se generan ramas y hojas. Se utilizan en búsquedas, jerarquías y organización de datos.
Estructuras de datos contiguas
Son aquellas en las que los elementos se almacenan en posiciones de memoria consecutivas. Esto permite un acceso directo mediante índices, pero su tamaño es fijo y no se puede modificar durante la ejecución. Ejemplos: arreglos, vectores y matrices.
Cadenas (Strings)
Una cadena es una secuencia de caracteres almacenados de forma contigua en memoria. Se utiliza para representar texto como palabras, frases o símbolos. Generalmente terminan con un carácter especial (como \0 en C) que indica el final de la cadena.
Arreglos (Arrays)
Un arreglo es una estructura de datos contigua que almacena múltiples elementos del mismo tipo bajo un mismo nombre. Cada elemento se accede mediante un índice que indica su posición.
Vectores
Un vector es un tipo de arreglo unidimensional que contiene elementos homogéneos almacenados en posiciones consecutivas. Se consideran la forma más simple de los arreglos.
Operaciones en arreglos y vectores
Las operaciones más comunes son:
- Recorrido: acceder a cada elemento.
- Búsqueda: localizar un valor específico.
- Inserción: añadir un valor en una posición determinada.
- Eliminación: borrar un valor de una posición.
- Actualización: modificar el valor de un elemento existente.
Matrices
Una matriz es un arreglo bidimensional que organiza datos en filas y columnas. Son útiles para representar tablas, imágenes o relaciones numéricas.
Operaciones en matrices
Entre las más comunes:
- Suma y resta: entre matrices de igual dimensión.
- Multiplicación: por un escalar o entre matrices compatibles.
- Transposición: intercambiar filas por columnas.
- Recorrido: visitar cada elemento en filas y columnas.
Arreglos multidimensionales
Son arreglos con más de dos dimensiones. Ejemplo: un arreglo tridimensional puede usarse para representar un cubo de datos. Se utilizan en aplicaciones científicas, gráficas y simulaciones.
Arreglos heterogéneos (Registros)
Son estructuras que permiten agrupar datos de diferentes tipos bajo un mismo identificador. Ejemplo: un registro de “Alumno” puede contener nombre (cadena), edad (entero) y promedio (real).
Definición de punteros
Un puntero es una variable que almacena la dirección de memoria de otra variable. En lugar de guardar un valor directo, guarda la referencia hacia donde se encuentra el dato.
Uso de punteros
Los punteros se utilizan para:
- Crear estructuras dinámicas (listas, pilas, colas, árboles).
- Optimizar el uso de memoria.
- Manipular arreglos y cadenas directamente.
- Pasar datos por referencia en funciones.
PSeInt
Es un software educativo que facilita la enseñanza de lógica de programación. Permite escribir algoritmos en pseudocódigo y ejecutarlos para comprender su funcionamiento antes de implementarlos en un lenguaje real.
Listas
Una lista es una estructura de datos lineal dinámica que permite almacenar un conjunto de elementos en un orden específico. A diferencia de los arreglos, el tamaño de la lista no es fijo y puede crecer o reducirse durante la ejecución de un programa.
Listas enlazadas
Una lista enlazada es una colección de nodos, donde cada nodo contiene dos partes:
- Dato: el valor o información que se quiere almacenar.
- Enlace (puntero): una referencia al siguiente nodo de la lista.
Las listas enlazadas permiten una gestión flexible de memoria, ya que los nodos pueden almacenarse en posiciones no contiguas en la memoria.
Creación de una lista
La creación de una lista enlazada implica reservar memoria para el primer nodo (conocido como nodo cabeza o head) y asignar un valor al campo de datos. A partir de este nodo, pueden añadirse nuevos nodos enlazados al anterior, formando la estructura completa.
Procesamiento
El procesamiento de una lista se refiere a la ejecución de operaciones sobre ella, como ordenar, contar elementos, modificar valores, buscar elementos o realizar cálculos con los datos almacenados.
Recorrido de lista
Recorrer una lista enlazada significa visitar cada nodo en orden desde el primero hasta el último. Se utiliza un puntero auxiliar que va avanzando de nodo en nodo siguiendo los enlaces hasta encontrar un valor nulo (NULL), que indica el final de la lista.
Búsqueda en una lista
La búsqueda consiste en localizar un elemento dentro de la lista. Esto se hace recorriendo nodo por nodo y comparando el valor almacenado con el que se desea encontrar.
Inserción de un elemento
Insertar en una lista implica crear un nuevo nodo y enlazarlo correctamente. Puede hacerse en distintas posiciones:
- Al inicio.
- Al final.
- En una posición intermedia específica.
Eliminación de un elemento
Eliminar un nodo de una lista requiere modificar los enlaces de los nodos adyacentes para excluir el nodo a borrar, y liberar la memoria que este ocupaba. Al igual que en la inserción, puede hacerse al inicio, al final o en una posición intermedia.
Pilas
Una pila es una estructura de datos dinámica que sigue el principio LIFO (Last In, First Out), es decir, el último elemento en entrar es el primero en salir. Las pilas se utilizan en algoritmos de retroceso (backtracking), control de llamadas a funciones y deshacer operaciones en editores.
- Creación: Se inicia una pila vacía con un puntero o índice en la cima (top), que apunta al último elemento insertado.
- Procesamiento: Implica realizar operaciones básicas como push (inserción), pop (eliminación) y peek/top (consultar el elemento en la cima).
- Recorrido: Se recorren los elementos desde la cima hasta la base, mostrando o procesando cada dato en orden.
- Búsqueda de datos: Se verifica si un elemento está contenido en la pila, revisando desde la cima hacia abajo.
- Inserción de datos: Mediante la operación push, se agrega un nuevo elemento en la cima de la pila.
- Eliminación de datos: Con la operación pop, se elimina el elemento que se encuentra en la cima.
Colas
Una cola es una estructura de datos dinámica que sigue el principio FIFO (First In, First Out), es decir, el primer elemento en entrar es el primero en salir. Se usan en sistemas de atención, planificación de procesos en sistemas operativos y transmisión de datos.
- Procesamiento de colas: Implica realizar operaciones como enqueue (inserción al final de la cola), dequeue (eliminación al frente de la cola), y la visualización de sus elementos en orden de llegada.
Concepto de árbol binario
Un árbol binario es una estructura de datos jerárquica en la que cada nodo puede tener como máximo dos hijos, conocidos como hijo izquierdo e hijo derecho. Se utiliza para representar relaciones jerárquicas, facilitar búsquedas, ordenar datos y optimizar operaciones de acceso.
Partes de un árbol binario
- Nodo: unidad fundamental que contiene un valor o dato.
- Raíz: primer nodo del árbol, desde donde comienza la estructura.
- Subárbol izquierdo: conjunto de nodos que cuelgan del hijo izquierdo de un nodo.
- Subárbol derecho: conjunto de nodos que cuelgan del hijo derecho de un nodo.
- Hojas: nodos sin hijos.
- Altura: número de niveles desde la raíz hasta la hoja más lejana.
Creación de un árbol binario
Crear un árbol binario implica definir un nodo raíz y luego agregar sus hijos de forma que cada nodo pueda tener como máximo dos conexiones. Puede implementarse de manera:
- Estática: utilizando arreglos.
- Dinámica: con estructuras enlazadas mediante punteros.
Recorrido de un árbol binario
El recorrido de un árbol consiste en visitar todos los nodos siguiendo un orden específico:
- Pre-Orden: se procesa primero la raíz, luego el subárbol izquierdo y después el derecho.
- In-Orden: se procesa primero el subárbol izquierdo, luego la raíz y finalmente el subárbol derecho.
- Post-Orden: se procesan primero los subárboles (izquierdo y derecho) y al final la raíz.
Árbol binario de búsqueda (ABB)
Un árbol binario de búsqueda (Binary Search Tree, BST) es un árbol binario en el que cada nodo cumple la condición de orden:
- Todo nodo en el subárbol izquierdo tiene un valor menor al del nodo padre.
- Todo nodo en el subárbol derecho tiene un valor mayor al del nodo padre.
Esto permite realizar búsquedas, inserciones y eliminaciones de forma más eficiente.
Creación de un árbol binario de búsqueda
Se crea insertando nodos de manera que respeten las reglas de orden:
- El primer valor insertado se convierte en la raíz.
- Si el valor a insertar es menor que el nodo actual, se coloca en el subárbol izquierdo.
- Si es mayor, se coloca en el subárbol derecho.
- Este proceso se repite recursivamente hasta ubicar el nodo en la posición correcta.