Diccionario Esencial de Estructuras de Datos y Conceptos de Programación

Conceptos Fundamentales de Estructuras de Datos

Estructura de Datos

Colección de datos cuya organización se caracteriza por las funciones de acceso que se usan para almacenar y acceder a elementos individuales de datos.

Clasificación de Estructuras de Datos

Clasificación por Persistencia

Estructuras Internas

Existen solo durante la ejecución de un programa o rutina. Ejemplos: variables, arreglos, listas, pilas, árboles.

Estructuras Externas

No pertenecen a un programa o rutina y persisten después de la ejecución. Ejemplos: Archivos, Bases de Datos (BD).

Clasificación por Tamaño

Estructuras Estáticas

Fijas en tamaño desde su definición hasta el término de la ejecución (variables, arreglos).

Estructuras Dinámicas

Pueden sufrir cambios en su especificación y utilización. Variables definidas por el usuario.

Clasificación por Relación entre Nodos

Estructuras Lineales

Cada nodo puede tener solo un nodo hijo (listas, pilas, colas).

Estructuras No Lineales

Cada nodo tiene o puede tener más de un hijo (árboles, grafos).

Estructuras Lineales Específicas

Variables

Son estáticas, ya que al declararse se reserva la cantidad de memoria para almacenar el tipo de dato. Si se intenta almacenar un dato más grande, se provoca un Overflow.

Arreglos (Arrays)

Pueden contener varios datos en sí mismos. Utilizan casillas continuas de memoria, por lo que se conoce la dirección de memoria donde se encuentra cada uno de los datos del arreglo.

Conceptos de Arreglos

Índice de Arreglo

Hace referencia a cada una de las casillas del arreglo. Su valor comienza en 0 y termina en el tamaño del arreglo.

Matriz

Arreglo de dos dimensiones que cuenta con filas y columnas.

Listas y Colas

Lista Circular

Estructura lineal donde el último nodo apunta al primero. Esto evita excepciones en las operaciones que se realizan sobre ellas, ya que cada nodo siempre tiene un anterior y un siguiente.

Lista Doblemente Enlazada

Estructura lineal donde cada nodo tiene dos enlaces: uno al nodo siguiente y uno al anterior. No necesitan un nodo especial para acceder a ellas.

Cola (Queue)

Solo se pueden insertar nodos en uno de los extremos y eliminar nodos en el otro (principio FIFO: First In, First Out).

Estructuras No Lineales: Árboles

Árbol

Estructura no lineal donde cada nodo puede apuntar a uno o varios nodos. Es inherentemente recursiva.

Terminología de Nodos en Árboles

• Nodo Hijo: Cualquier nodo apuntado por otro nodo del árbol.
• Nodo Padre: Nodo que apunta al nodo actual; es decir, el nodo que tiene hijos.
• Nodo Raíz: Nodo que no tiene padre.
• Nodo Hoja: Nodo que no tiene hijos.
• Nodo Rama: Nodo que tiene padre y tiene hijos.

Propiedades y Medidas de Árboles

Árbol Completo

Se cumple que todos los nodos internos tienen el total de hijos permitido o no tienen ningún hijo.

Orden

Número máximo de hijos que puede tener cada elemento del árbol.

Grado

El número de hijos que tiene el elemento con más hijos del árbol.

Nivel

Distancia a la raíz medida en nodos.

Altura

El nivel del nodo de mayor nivel.

Recorridos de Árboles

Preorden

El valor del nodo se procesa antes de recorrer las ramas.

Inorden

El valor del nodo se procesa después de recorrer la primera rama y antes de la última.

Postorden

El valor del nodo se procesa después de recorrer todas las ramas.

Tipos Especiales de Árboles

ABB

Árbol Binario de Búsqueda.

AVL

Árboles Binarios de Búsqueda Equilibrados.

Conceptos Adicionales

Puntero

Variable que almacena direcciones de memoria.