PROGRAMACIÓN II Datos compuestos enlazados

LISTAS
Una lista es una colección de elementos homogéneos, con una relación lineal que los
vincula. Esto significa que cada elemento, menos el primero, tiene un único
predecesor y cada elemento, menos el último, tiene un sucesor en la lista. El orden
de vinculación de los elementos de la lista afecta a su función de acceso
Definición: Una lista dinámica es un conjunto de tipo homogéneo, donde los mismos
no ocupan posiciones secuenciales o contiguas de memoria, es decir, los elementos o
componentes de una lista pueden aparecer físicamente dispersos en la memoria, si
bien mantienen un orden lógico interno
PUNTEROS
Como los elementos que conforman una lista no están en posiciones consecutivas de
memoria, para poder trabajar con ellos se necesita direccionarlos. Por eso, cada elemento de
la lista contiene un indicador, que apunta al próximo elemento de la misma. Es decir, se
requiere un nuevo tipo: el tipo puntero.
Se debe recordar que las diversas posiciones de almacenamiento de la memoria de una
máquina se identifican mediante direcciones numéricas; si se conoce la dirección de un dato
se lo puede ubicar directamente. Así después de almacenar un dato en la celda de memoria,
se puede almacenar la dirección de ese dato en otra; luego, si se quiere recuperar el dato y se
tiene acceso a la celda que contiene, se puede consultar el dato de dicha dirección.
Definición: Un puntero es un tipo de variable, en el cual se almacena la dirección de un dato
y permite manejar direcciones “apuntando” a un elemento determinado
Con la utilización adecuada de punteros, se puede considerar una lista como constituida por
elementos lógicamente adyacentes.
USO DE LISTAS
Para crear una lista utilizando punteros, se debe crear cada uno de sus nodos para luego
enlazarlos con algún criterio.
Para ello, necesitamos el espacio de memoria donde se va a almacenar la información y
una variable de tipo registro donde cargar los datos y la dirección de memoria de donde
se va almacenar.
Para saber donde está la primer entrada de una lista, se guarda en una celda de la
memoria la dirección de la primera entrada. Esta celda apunta al principio de la lista, y
suele llamarse puntero inicial. Si se quiere leer la lista, se comienza en la posición
indicada por este puntero y se halla el primer valor junto con el puntero a la siguiente
entrada. Y las acciones se repiten hasta el final de la lista.
El último elemento de la lista tiene un puntero nulo, indicando que no hay mas entradas
asociadas a la lista.
OPERACIONES CON LISTAS
Algunas de las operaciones más usuales con listas son:
Recorrido de la lista.
Acceso al n-ésimo elemento de la lista.
Intercalar un nuevo elemento en la lista.
Combinar dos listas, para formar una sola.
Localizar un elemento de la lista para conocer su posición dentro de ella.
Borrar un elemento de la lista.
LISTAS PARTICULARES
Listas Circulares
En lugar de almacenar un puntero nulo, en el último elemento, se guarda un puntero con la dirección del
primer elemento.
Ventajas:
Cada nodo de la lista circular es accesible desde cualquier otro nodo de ella.
Las operaciones de concatenación y división de las listas son más eficaces con listas circulares
Desventajas:
Al recorrerse, pueden generarse bucles infinitos, para evitarlo, se suele tener un nodo especial, llamado
cabecera, que tiene un valor especial que lo diferencie de los demás.
Listas doblemente enlazadas
Una lista doblemente enlazada, nos permite realizar el recorrido de la misma en ambas direcciones, ya que
se almacena tanto la dirección del nodo siguiente y del anterior
CARACTERÍSTICAS DE LAS
LISTAS
Una lista es una estructura lineal dinámica
Los datos no necesariamente residen en posiciones consecutivas de memoria
La mayor facilidad que brindan las listas es la unión dinámica de datos a través de
variables auxiliares de tipo puntero, que permiten un fácil intercalado o borrado de
información, sin un movimiento masivo de datos en la memoria
Cuando se trabaja con una estructura de datos con gran cantidad de información,
como un archivo, podemos crear listas con distintas secuencias de acceso a la
estructura por diferentes campos, y así, sin reordenar la información, organizarla por
diferentes criterios.
ÁRBOLES
La estructura conocida como árbol, nos permite organizar la información de forma
tal que podemos representar relaciones jerárquicas.
Los árboles nos permiten realizar operaciones muy variadas:
Es posible desarrollar algoritmos de búsqueda eficientes representando la secuencia
de pruebas de una búsqueda.
Pueden organizarse archivos en una computadora utilizando un árbol de directorios.
Es posible determinar quien es el ganador de un juego de estrategia representando las
posiciones permitidas en el juego mediante un árbol.
ÁRBOLES
Definición: Es una estructura de datos que satisface tres propiedades:
1. Cada elemento del árbol (nodo) se puede relacionar con 0 o más elementos, los
cuales se llaman hijos.
2. Si el árbol no está vacío, hay un único elemento el cual se llama raíz y que no
tiene padre (predecesor), es decir, no es hijo de ningún otro
3. Todo elemento del árbol posee un único padre y es un descendiente de la raíz
CARACTERÍSTICAS DE
ÁRBOLES
La raíz es el tope del árbol
Los árboles crecen hacia abajo
Cada elemento del árbol se denomina nodo y si los nodos no tienen hijos, se denominan hojas
Un camino en un árbol es una secuencia lineal de elementos, donde cada uno es el padre del
próximo item de la secuencia
Una rama en un árbol es un camino que se extiende desde la raíz hasta una hoja
Un subárbol de un árbol es un nodo con todos sus descendientes.
El nivel de un nodo en el árbol es el número de ítems que hay sobre un único camino que lo
une con la raíz
La altura de un árbol es el máximo entre los niveles de los nodos del árbol
ÁRBOL BINARIO
Definición: Un árbol donde cada nodo no tiene más de dos hijos se denomina árbol
binario.
Un árbol binario se dice que está ordenado cuando cada nodo del árbol es mayor que
los elementos de su subárbol izquierdo (el que tiene como raíz a su hijo izquierdo) y
menor o igual que los de su subárbol derecho (el que tiene como raíz a su hijo
derecho)
El elementos buscado se compara con la raíz y si es menor se repite el proceso
comparando contra el hijo izquierdo en caso contrario continuamos por la derecha.
El proceso termina cuando se encuentra el elementos o cuando se termina la rama.
REPRESENTACIÓN
Para el manejo de árboles se utiliza una estructura basada en punteros como se vio en
las listas.
En este caso se utilizan dos punteros por cada nodo, y sin embargo, al igual que
ocurría con las listas, los árboles son una estructura de datos dinámica, esto nos
permite insertar y borrar elementos dentro del árbol sin necesidad de mover otros
nodos.
Para realizar operaciones sobre árboles se requerirán algoritmos recursivos.
RECORRIDO DE ÁRBOLES
Para hacer recorrido de árboles tenemos deferentes maneras, las cuales están
clasificadas según el orden en el que se accede a los nodos del mismo:
Inorden: Primero el subárbol izquierdo in inorden, después la raíz, y por último, el
subárbol derecho en inorden
Preorden: Primero el nodo raíz, luego subárbol izquierdo en preorden, y por último,
el subárbol derecho en preorden
Postorden: Primero el subárbol izquierdo en postorden, luego el subárbol derecho en
postorden, y por último la raíz
EJEMPLOS DE RECORRIDOS
GRAFOS
Las estructuras de datos que vimos hasta ahora pueden reclasificarse según el tipo de
proceso que se realice con ellas como:
Estructuras lineales: aquellas donde los elementos están organizados en forma
secuencial con un sucesor y un predecesor, A esta clase pertenecen: pilas, colas,
arreglos y matrices, listas y todas las estructuras cuya recorrida es secuencial.
Estructuras no lineales: aquellas donde los elementos pueden tener más de un sucesor o
predecesor, en general acceden a sus elementos según un criterio determinado, es decir,
no secuencial. A esta clase pertenecen los árboles n-arios y en particular los árboles
binarios.
Existen algunas aplicaciones en las cuales es necesario representar una relación de
muchos a muchos, en estos casos es necesario utilizar una estructura de datos no lineal,
que llamaremos grafo
GRAFOS
Definición: un grafo G = (V,A) está formado por un conjunto de vértices V, y un conjunto de arcos A; cada arco se presenta mediante un
par (v,w), donde v y w pertenecen a V
Si el par está ordenado se dice que es un grafo dirigido. Los grafos dirigidos generalmente se llaman dígrafos
Se dice que el vertice w es adyacente a v si y solo si (v,w) pertenecen a A. En un grafo dirigido con arco (v,w) y, por consiguiente, (w,v),
es adyacente a v y viceversa.
Un camino en un grafo es una secuencia de vértices w1, w2,…,wn, tal que (wi, wi+1)pertenece a A para 1 <= i < n. La longitud de un
camino es la cantidad de arcos que contiene. Es posible obtener un camino que comience y termine en el mismo vértice. Si este camino
tiene longitud 1, es decir, el grafo tiene arcos de tipo (v,v), se dice que el grafo tiene un loop. En general se trabajará con grafos donde
esta última situación no ocurre.
Un grafo simple es aquel donde todos sus vértices son distintos. Solo el primero y el último pueden coincidir.
Un ciclo, en un grafo dirigido, es un camino de longitud mayor o igual que 1 donde el primer y el último vértice es el mismo; w 1 = wn .
Este ciclo se llamará ciclo simple si el camino es simple. En caso de grafos no dirigidos, es necesario que los arcos sean distintos. La idea
es que el camino u,v,u en un grafo dirigido no puede ser considerado un ciclo ya que se trata de un solo arco, (u,v). En un grafo dirigido
se trata de distintos arcos.
Un grafo es acíclico si no tiene ciclos
En algunas aplicaciones, los arcos tienen una tercera componente que es su peso o costo.
Un grafo no dirigido está conectado si para cualquier par de vértices existe un camino que los una. Un grafo con esta propiedad se dice
que está fuertemente conectado. Si un grafo dirigido no está fuertemente conectado, pero el grafo subyacente ( sin dirección en los arcos)
está conectado, se dice que es débilmente conectado.
REPRESENTACIÓN DE GRAFOS
Se consideran solo grafos dirigidos
Una manera siempre de representar un grafo es utilizar una matriz. Esta estructura es conocida como matriz de
adyacencia.
Para cada arco (u,v), se asigna M(u,v) :=1 ( como forma de indicar que el arco existe) y en caso contrario, el valor de
la matriz es 0, si els arco tiene un peso asociado, puede asignarse M(u,v) := peso y utilizar un valor centinela, muy
grande o muy chico para indicar que no existe arco.
Esta representación tiene el mérito de ser extremadamente siempre, sin embargo, el espacio necesario para guardarla
en memoria es proporcional a N2 , siendo N la cantidad de vértices. Nótese que el tamaño de memoria es
independiente de la cantidad de arcos. Esto puede redundar en un tamaño totalmente prohibitivo.
Una matriz de adyacencia es la representación adecuada en caso de tener un grafo denso, es decir, cuando la cantidad
de arcos se acerca a N2 pero en general, esto no se cumple
Cuando el grafo es esparcido, es decir que tiene pocos arcos, la mejor solución es usar una lista de adyacencia. En
esta representación, para cada vértice se mantiene una lista con todos sus adyacentes. Por lo tanto, el espacio
requerido será la suma total de arcos y el total de vértices.
La lista de adyacencia es la manera normalizada de representar un grafo. Los grafos no dirigidos pueden representarse
de la misma manera, solo que cada arco (u,v) aparecerá en dos listas, con lo cual, el espacio utilizado es el doble.
OPERACIONES CON GRAFOS
Las operaciones más comunes con grafos son:
Saber si existe un camino que una dos vértices dados.
Saber cual es el mejor camino, en general, utilizando arcos con un peso
BUSCAR UN CAMINO ENTRE
VÉRTICES DE UN GRAFO
Para saber si existe un camino que una dos vértices dados, se realiza una búsqueda exhaustiva. Lo que se
hace es tomar un vértice de partida, de éste, nos dirigimos hacia su adyacente a través de un arco, si es el
vértice que buscamos, termina el proceso, si no, se toma su adyacente, si ese siguiente vértice es el que se
buscaba, se termina el proceso, en caso contrario se sigue repitiendo el proceso.
Las posibles salidas del proceso son:
1. Se logra hallar el camino que una los dos vértices indicados.
2. Se llega a una vértice que no tiene arcos.
3. Se quedan genera un bucle infinito
No necesariamente ocurre el primer resultado, puede ocurrir que no exista un camino que una los dos
vértices, inclusive, puede existir un camino y que aún así se llegue a las opciones 2 o 3. Que se llegue al
resultado 2, no significa que no exista el camino.
En caso de llegar al resultado 2, debemos retroceder y usar otro arco evitando ingresar nuevamente al
mismo vértice
SOLUCIÓN USANDO UNA PILA
Una opción podría ser guardar la secuencia de ciudades en una pila. Cada vez que se
ingresa a un vértice, se la apila y cuando se quiere volver, se desapila.
El tope de la pila sería el vértice en el que se encuentra actualmente. La pila siempre
conserva el camino de origen al vértice actual, si es el buscado, indica el camino que se
siguió.
Las condiciones a considerar serían, que el vértice no tenga más arcos o que ya se
ingresó al vértice. Sería necesario desapilar cuando esto ocurre, y marcar los vértices
como ya ingresados.
La condición de fin del algoritmo sería:
1. Tener en el tope de la pila el vértice buscado
2. Que la pila quede vacía.
SOLUCIÓN UTILIZANDO UN
ALGORITMO RECURSIVO
A partir del vértice origen, se toma el primer adyacente que no se hubiese visitado, si
era el vértice de destino, el proceso termina, si no se sigue buscando a partir de él.
Este proceso se repite hasta que se encuentre el destino o hasta que se recorre todo el
grafo.
El uso de un algoritmo recursivo simplifica la implementación ya que no es
necesario utilizar una pila para recordar el camino andado. El proceso va “apilando”
en forma automática, de manera que al terminar, ya sea porque encontró el vértice
destino o porque no hay más vértices para visitar, retorna al contexto anterior,
produciendo el mismo efecto que el desapilado.
La recursividad no es una estructura alternativa, si no una manera de programar
mejor cierto tipo de algoritmos.