Estructuras de Datos Esenciales: De Grafos a Árboles de Búsqueda

Grafos y su Representación

Un grafo se define como un valor ordenado y se define como un valor de conjuntos finitos, los cuales se han visto de diferentes maneras. Una forma de representación de los grafos es mediante una matriz de adyacencia por listas, donde se asocia cada fila y cada columna del grafo, tomando los vértices de uno si existe la arista y cero si es el lado contrario.

Apuntadores y Gestión de Memoria

Apuntador: Guarda una dirección de memoria de una variable; se utiliza para apuntar indirectamente a un espacio de memoria. Representación técnica: & (dirección) y * (puntero).

Listas Enlazadas

Lista: En esta forma, los nodos se organizan de modo que cada uno apunta al siguiente, y el último no apunta a nada; es decir, el puntero del nodo siguiente vale NULL.

En las listas abiertas existe un nodo especial: el primero. Normalmente, diremos que nuestra lista es un puntero a ese primer nodo y llamaremos a ese nodo la cabeza de la lista. Eso es porque, mediante ese único puntero, podemos acceder a toda la lista.

Pilas (Stacks)

Pilas: Estructura de datos en la cual los elementos almacenados en la misma se agregan y se sacan del mismo lugar hasta el tope de la pila. Una pila es un tipo especial de lista abierta en la que solo se pueden insertar y eliminar nodos en uno de los extremos de la lista. Estas operaciones se conocen como "push" y "pop", respectivamente "empujar" y "tirar" (extraer). Además, las escrituras de datos siempre son inserciones de nodos, y las lecturas siempre eliminan el nodo leído.

Estas características implican un comportamiento de lista LIFO (Last In First Out), donde el último en entrar es el primero en salir.

• PUSH: Insertar elemento.
• POP: Leer y eliminar elemento.

Operaciones Comunes en Pilas

P_CREAR, P_VACIAR, P_VACIA, P_AGREGAR, P_SACAR

Colas (Queues)

Colas: Una cola es un tipo especial de lista abierta en la que solo se pueden insertar nodos en uno de los extremos de la lista y solo se pueden eliminar nodos en el otro. Además, como sucede con las pilas, las escrituras de datos siempre son inserciones de nodos, y las lecturas siempre eliminan el nodo leído.

Este tipo de lista es conocido como lista FIFO (First In First Out), donde el primero en entrar es el primero en salir.

Colas Circulares

Colas circulares: Una lista circular es una lista lineal en la que el último nodo apunta al primero. Las listas circulares evitan excepciones en las operaciones que se realicen sobre ellas. No existen casos especiales: cada nodo siempre tiene uno anterior y uno siguiente. En algunas listas circulares se añade un nodo especial de cabecera; de ese modo se evita la única excepción posible, la de que la lista esté vacía.

Listas Doblemente Ligadas

Listas doblemente ligadas: Una lista doblemente enlazada es una lista lineal en la que cada nodo tiene dos enlaces: uno al nodo siguiente y otro al anterior.

Las listas doblemente enlazadas no necesitan un nodo especial para acceder a ellas; pueden recorrerse en ambos sentidos a partir de cualquier nodo. Esto es porque, a partir de cualquier nodo, siempre es posible alcanzar cualquier nodo de la lista hasta que se llega a uno de los extremos.

Estructuras de Árbol

Árbol: Un árbol es una estructura no lineal en la que cada nodo puede apuntar a uno o varios nodos.

También se suele dar una definición recursiva: un árbol es una estructura compuesta por un dato y varios árboles.

Árbol de Búsqueda Binaria

Árbol (búsqueda): Se trata de árboles de orden 2 en los que se cumple que, para cada nodo, el valor de la clave de la raíz del subárbol izquierdo es menor que el valor de la clave del nodo, y que el valor de la clave raíz del subárbol derecho es mayor que el valor de la clave del nodo.