ALGORITMOS Y ESTRUCTURAS DE DATOS I – RESUMEN M2
ESTRUCTURA DE DATOS PILA
Estructura de datos: forma particular de organizar datos para que puedan ser utilizados de
manera eficiente.
Existen diferentes tipos de estructuras de datos y cada una de ella, por sus características, será
adecuada para resolver diferentes tipos de aplicaciones.
- Eficacia: capacidad de alcanzar un determinado objetivo
- Eficiencia: capacidad de alcanzar un objetivo utilizando la menor cantidad de recursos
posibles
Los recursos con los que cuenta una computadora son finitos (memoria, disco, capacidad de
procesamiento), por lo que se debe considerar este aspecto a la hora de diseñar y seleccionar
una estructura de datos.
Estructura de datos PILA: estructura lineal restrictiva de tipo LIFO (last in first out), esto indica
que el último elemento que ingresó a la pila debe ser el primero en salir.
- se pueden realizar inserciones de elementos siempre en primer lugar (por encima del
resto de los elementos, quedando el elemento en el tope o cima de la pila)
- se pueden realizar extracciones de elementos siempre en el primer lugar (el elemento
que esté en el tope o cima de la pila)
Una estructura de datos de tipo pila puede ser implementada a nivel de software en forma
estática o dinámica. Para una implementación estática, que define un tamaño al momento de
la creación de la estructura, utilizaremos un vector y para una implementación dinámica
utilizaremos una lista enlazada.
Una implementación estática con un vector genera un desperdicio de espacio en la memoria,
ya que, cuando se crea la pila, se reserva el espacio de memoria para toda la estructura,
aunque no esté ocupada. Por otra parte, su implementación es muy sencilla y se accede en un
tiempo constante a sus elementos.
Una implementación dinámica de una pila con una lista enlazada no desperdicia memoria,
dado a que los elementos se agregarán en forma dinámica y, por otra parte, como una pila solo
accede al elemento tope o cima, al ser el mismo el primer elemento de la lista, el acceso y la
inserción serán eficientes.
Si bien las operaciones más importantes sobre una pila son apilar y desapilar, existen otras
operaciones que se pueden realizar sobre una pila:
- Crear (crea pila vacia)
- Obtener tamaño (retorna el tamaño de la pila)
- Leer tope (lee el elemento en la cima de la pila sin eliminarlo)
- Vacia (indica si la pila esta vacia o no)
ALGORITMOS Y ESTRUCTURAS DE DATOS I – RESUMEN M2
ESTRUCTURA DE DATOS COLA
Estructura de datos: forma particular de organizar datos para que puedan ser utilizados de
manera eficiente (alcanzar el objetivo buscado, utilizando la menor cantidad de recursos
posibles).
Estructura de datos COLA: estructura lineal restrictiva de tipo FIFO (first in first out), esto
indica que el primer elemento que ingresó a la cola debe ser el primero en salir.
Principales características de la estructura de datos cola son:
- se pueden realizar inserciones de elementos siempre en último lugar (por detrás del
resto de los elementos), quedando el elemento en el fondo de la cola
- se pueden realizar extracciones de elementos siempre desde el primer lugar (el
elemento que esté en el primer lugar de la cola)
Con base en lo expuesto, en una estructura de datos cola, el dato al cual se tendrá acceso en
forma directa es al que está en el primer lugar de la cola y, para acceder a los otros datos,
necesariamente, deberán extraerse el resto de los elementos.
Una estructura de datos de tipo pila puede ser implementada a nivel de software en forma
estática o dinámica. Para una implementación estática, que define un tamaño al momento de
la creación de la estructura, utilizaremos un vector y para una implementación dinámica
utilizaremos una lista enlazada.
Una implementación estática con un vector genera un desperdicio de espacio en la memoria,
ya que, cuando se crea la cola, se reserva el espacio de memoria para toda la estructura,
aunque no esté ocupada. Por otra parte, su implementación es muy sencilla y se accede en un
tiempo constante a sus elementos.
Una implementación dinámica de una cola con una lista enlazada no desperdicia memoria,
dado a que los elementos se agregarán en forma dinámica, pero hay una particularidad,
porque deberemos tener referencias tanto del primer elemento de la cola como del último
elemento, para que las inserciones y extracciones sean eficientes.
Si bien las operaciones más importantes sobre una cola son encolar y desencolar, existen otras
operaciones que se pueden realizar sobre una estructura de tipo cola:
- crear: permite crear la cola vacía;
- obtener tamaño: retorna el tamaño de la cola;
- leer: lee el elemento que está en el primer lugar de la cola sin eliminarlo; y
- vacía: indica si la cola está vacía o no.
ALGORITMOS Y ESTRUCTURAS DE DATOS I – RESUMEN M2
ESTRUCTURA DE DATOS LISTA
Si bien existen muchas estructuras de datos, hay algunas estructuras que nos permiten
implementar otras estructuras, por ejemplo, las estructuras de datos pila y cola pueden ser
implementadas con una estructura de datos lista enlazada.
Estructura de datos LISTA ENLAZADA: Una lista lineal simplemente enlazada es una
estructura de datos dinámica compuesta por nodos enlazados linealmente, es decir, cada
nodo contiene datos y una referencia al siguiente elemento de la lista.
Podemos visualizar una lista como un conjunto de elementos que se enlazan uno con otro,
donde ese enlace se denomina referencia. Cuando la lista se crea, estará vacía y no
contendrá ningún elemento, con lo cual la lista tendrá una referencia a un valor nulo (null).
Cuando se agrega un nodo a la lista, se crea el nodo con el valor determinado y se modifican
sus referencias, por ejemplo, si creamos un elemento A, la lista referenciará al elemento A y
la referencia siguiente del elemento A será a NULL.
Cuando se agrega un nuevo nodo a la lista (por ejemplo, B), se crea el nodo con el valor
determinado y se modifican sus referencias. Si la inserción se hace como primer elemento
de la lista, la referencia al elemento siguiente de B será A.
Ahora bien, en una estructura de datos lista enlazada, no hay limitante en cuanto al método
de inserción de elementos. Este agregado podría ser realizado al inicio de la lista, al final de
lista o incluso podría ser insertado un elemento en una determinada posición.
De la misma forma que las inserciones en una lista pueden ser variadas, las extracciones de
elementos también lo son, es decir, podríamos extraer un elemento del principio de la lista,
del final de la lista o extraer un elemento de una posición determinada o un elemento
específico.
- Lista enlazada simple: Podemos definir a las listas enlazadas simples como las que
contienen una única referencia a un elemento “siguiente”, es decir que cada nodo de la
lista tendrá sus datos y una sola referencia o puntero.
Uno de los problemas que posee esta estructura es que no es factible acceder a un
elemento anterior. Supongamos que tenemos el abecedario ingresado en una lista
simple ordenada, donde cada nodo tiene una letra, comenzando desde la A hasta la Z,
y nos solicitan que hagamos una impresión por pantalla, pero en orden inverso.
Teniendo solo una referencia al elemento siguiente, deberíamos hacer un algoritmo
poco eficiente para resolver el problema, dado que deberíamos recorrer la lista hasta
el último elemento (Z) para imprimirlo y, luego, volver a recorrer la lista hasta el
anteúltimo elemento (Y) y así sucesivamente.
ALGORITMOS Y ESTRUCTURAS DE DATOS I – RESUMEN M2
ESTRUCTURA DE DATOS ARBOL
Los árboles pueden definirse de dos maneras: de forma recursiva o no recursiva. La definición
no recursiva es la técnica más directa, mientras que la formulación recursiva nos permitirá
escribir algoritmos simples para la manipulación de árboles.
Si analizamos un árbol de manera no recursiva, podemos definirlo como una estructura de
datos no lineal conformada por un conjunto finito, fijo o variable, de nodos y ramas. Las ramas
son aristas dirigidas que unen dos nodos.
- Nodo raíz → del cual se desprenden el resto de los nodos.
- Todo nodo, a excepción del nodo raíz, está conectado a otro nodo por una rama. Uno
de ellos es el nodo padre y, el otro, el nodo hijo. Esto significa que no hay nodos
sueltos.
- Se puede llegar a cada nodo por un camino único. La longitud de dicho camino es la
cantidad de ramas que hay que recorrer hasta llegar al nodo. La profundidad de un
nodo es la longitud del camino, desde el nodo raíz hasta dicho nodo.
- De cada nodo, descienden otros nodos del mismo tipo, a excepción de los últimos
nodos, los cuales no tienen descendencia y son nombrados como nodos hoja. Los
nodos que no son hoja, es decir, aquellos de los cuales se desprenden las ramas, se
llaman nodos de bifurcación o nodos rama.
- Se considera tamaño o grado de un nodo a la cantidad de descendientes (o cantidad
de ramas) que tiene, incluyéndose a sí mismo.
Si definimos a un árbol de manera recursiva, podemos decir que un árbol es un conjunto de
nodos y ramas tal que existe un nodo raíz y el resto de los nodos son un conjunto disjunto que
conforma subárboles de la raíz. De esta manera, se define a un árbol como un conjunto de
árboles.
Al indicar que los nodos son un conjunto disjunto, se quiere significar que los nodos que se
desprenden de la raíz y que conforman el subárbol derecho no pertenecen a los nodos del
subárbol izquierdo.
- un árbol puede estar vacío (no contener ningún nodo);
- un árbol puede tener solo un nodo raíz
- un árbol puede tener un conjunto de subárboles no vacíos.
Tipo de árboles y sus aplicaciones
Se puede encontrar una clasificación de los árboles en función de la cantidad de hijos que
tenga. Así, se pueden encontrar árboles binarios, es decir, aquellos de los cuales descienden
hasta dos hijos de cada nodo. Con el mismo razonamiento, se puede tener árboles ternarios
(hasta 3 hijos por nodo), árboles cuaternarios (hasta 4 hijos por nodo), etcétera.
Unas de las principales características de los árboles es que son muy eficientes en las
búsquedas de información, donde los árboles binarios tienen una gran importancia.
ALGORITMOS Y ESTRUCTURAS DE DATOS I – RESUMEN M2
Implementación de árboles binarios
Se puede definir a los árboles binarios de dos maneras. Por un lado, se puede decir que son
árboles en los que sus nodos tienen hasta dos hijos o se puede conceptualizar a un árbol
binario como un conjunto finito, fijo o variable de nodos, donde el nodo raíz consta de dos sub-
árboles binarios.
Árbol binario de búsqueda: se caracteriza por presentar una raíz que posee un valor mayor que
el de su hijo izquierdo y menor o igual que el de su hijo derecho. Esto nos permite afirmar que
cualquier nodo del árbol ubicado del lado izquierdo de este será menor que la raíz y, de la
misma manera, cualquier nodo del árbol ubicado del lado derecho de éste será mayor o igual.
