Download Estr-Dato

4. Estructuras de datos
Punteros, referencias
Listas enlazadas
Arboles
Estructuras de Datos
• Toda la información almacenada en términos simples
es una secuencia de caracteres (bytes) en donde se
encuentran las instrucciones y datos.
• Las estructuras de datos persiguen un
almacenamiento eficiente de la información en la
memoria del computador.
• las piezas básicas para la construcción de algoritmos
complejos, y permiten implementarlos de manera
eficiente.
Estructura de dato 1: Arreglo
• Secuencia de datos del mismo tipo
• Nace y muere con una cantidad de datos fija para
eficiencia en el acceso
– tipo[] nombre = new tipo[n_elem];
– int[] arreglo = new int[10];
• El nombre puede verse como puntero al primer
elemento: número de byte donde se encuentra
• Lugar del i-esimo elemento
– nombre * i * largo(tipo)
• ¿ Que ventajas permite esta organización ?
Punteros
• puntero : variable que almacena la dirección de
memoria de otra variable (indireccion)
• Si se imagina que la memoria del computador es
un gran arreglo de bytes, el puntero
correspondería a un índice del arreglo
• En algunos lenguajes (Ej. C) punteros pueden ser
declarados explícitamente
– Se puede realizar aritmética de punteros para mayor
eficiencia
– a cambio se "oscurece" el código del programa -> alta
probabilidad de cometer errores de programación
difíciles de detectar
• En Java no
Java: Variables de referencia
• variable de referencia, o referencia: almacena la
dirección de memoria en donde se ubica un objeto.
• Diferencia con puntero: una referencia sólo puede
apuntar a objetos residentes en memoria, esto excluye
los tipos primitivos.
• Esto implica que en Java toda variable que no sea de tipo
primitivo, es una referencia.
• Por ejemplo, Object aux=new Object();
• aux es una referencia a un objeto de la clase Object que
permite operar con él.
Estructura de dato 2: Lista Enlazada
• Una lista enlazada es una serie de nodos,
conectados entre sí a través de una referencia
• Los nodos de una lista enlazada se componen de
dos partes principales:
class NodoLista {
Object informacion;
NodoLista siguiente;
}
• siguiente almacena dirección del siguiente
elemento de la lista. Último elemento no tiene
siguiente, o la referencia siguiente del último
elemento es null (nula).
Ejemplo: Lista de strings
class NodoLista { String info; NodoLista sgte;
NodoLista(String x, NodoLista y) {
info = x; sgte = y;
}
NodoLista p = new NodoLista(“Pedro”,null),
q = new NodoLista(“Juan”,null),
r = new NodoLista(“Diego”, null);
p.Sgte = q; q.sgte = r;
//otra forma
NodoLista lista = new NodoLista(“Diego”, null);
Lista = new NodoLista(“Juan”, lista);
Lista = new NodoLista(“Pedro”,lista);
Recorriendo una Lista
Imprime el contenido de una lista cuyo comienzo se pasa
como parámetro a la función
void recorrido(NodoLista lista) {
NodoLista aux=lista;
while (aux!=null) {
System.out.println(aux.info);
aux=aux.sgte; }
}
Insertando elementos
Es necesario tener una referencia al elemento que
quedará antes que el que se quiere insertar
NodoLista aux=lista;
while (...) { aux=aux.sgte; }
NodoLista nuevo = new NodoLista(“Paula”,aux.sgte);
aux.sgte = nuevo;
– Para insertar al final basta que
aux quede apuntando al último
– Insertar al principio es caso especial
Eliminando elementos
Es necesario tener una referencia al elemento que
quedará antes que el que se quiere eliminar . Ej. Eliminar
nodo que contiene “Paula”. Eliminar al principio es caso
especial
if (lista.info.equals(“Paula”))
lista = lista.sig;
else {
NodoLista aux=lista;
while (aux.sgte != null) {
if (aux.sgte.info.equals(“Paula”)) {
aux.sgte = aux.sgte.sgte;
break;
}
}
}
Ejercicio: Invertir una lista
El último elemento de la lista sea el primero, el penúltimo el
segundo, etc..., modificando sólo las referencias y no el
contenido de los nodos. Invariante:
anterior
anterior
siguiente
siguiente
anterior
siguiente
Invertir una lista
El último elemento de la lista sea el primero, el penúltimo el
segundo, etc..., modificando sólo las referencias y no el
contenido de los nodos. Invariante:
anterior
lista
siguiente
void invertir(NodoLista lista) {
NodoLista siguiente=lista, anterior=null;
while(lista!=null) {
siguiente=lista.sgte;
lista.sgte=anterior;
anterior=lista; lista=siguiente;
}
}
Variación 1: Lista de doble enlace
• La implementación vista se conoce como lista de
enlace simple, y sólo puede recorrerse en un solo
sentido.
• En una lista de doble enlace se agrega una segunda
referencia al nodo previo, lo que permite recorrer la
lista en ambos sentidos,
• Generalmente se implementa con una referencia al
primer y otra referencia al último elemento.
Variación 2: Listas circulares
• Una lista circular es aquella en donde la referencia
siguiente del último nodo en vez de ser null apunta al
primer nodo de la lista. El concepto se aplica tanto a
listas de enlace simple como doblemente enlazadas.
Variación 3: Cabezas de lista
• En muchas aplicaciones que utilizan listas enlazadas
es útil contar con un nodo cabecera, que no contiene
información relevante, y su referencia siguiente
apunta al primer elemento de la lista.
• De esta manera siempre es posible definir un nodo
previo a cualquier nodo de la lista,
• Eliminar/agregar al principio no es caso particular
Todo Junto: cabeza, doble, circular
• Nodo cabecera en una lista de doble enlace
• Basta solo un puntero a la cabecera de la lista
• De esta forma la lista de doble enlace queda circular
de una manera natural.
¿Qué es un TDA ?
• Es un modelo matemático compuesto por una colección
de operaciones definidas sobre un conjunto de datos
• Provee de una interfaz con la cual es posible realizar las
operaciones permitidas, abstrayéndose de la manera en como
estén implementadas dichas operaciones
• Relación entre estructura de dato y TDA: Un mismo TDA puede
ser implementado utilizando distintas estructuras de datos y
proveer la misma funcionalidad
• Los Lenguajes de programación
orientados a objetos son consecuencia
de estas ideas
TDA Lista
• serie de N elementos E1, E2, ..., EN, ordenados
de manera consecutiva es decir, el elemento Ek
(que se denomina elemento k-ésimo) es previo
al elemento Ek+1
• Si la lista contiene 0 elementos se habla de una
lista vacía.
• Operaciones:
–
–
–
–
insertar un elemento en la posición k,
borrar el k-ésimo elemento,
buscar un elemento dentro de la lista y
preguntar si la lista esta vacía.
Definición de la interfaz de un TDA
• Define firma de las funciones (métodos) que realizarán esto
• Distintas clases implementarán esta interfaz usando diferentes
estructuras de datos, pero deben respetar la firma
• El usuario puede usar cualquiera de ellas indistintamente ya que
la sintaxis de las funciones será la misma
• Ejemplo para lista
interface Lista {
boolean estaVacia();
void insertar(Object x, Posicion k);
Posición buscar(Object x);
Object buscarK(Posición k);
void eliminar(Object x);
void eliminar(Posicion k);
}
Implementación
• Se podría pensar en dos posibilidades: con arreglos y con lista
enlazada
• Posición con arreglos sería entonces un entero (índice del lugar
del elemento).
• Con lista enlazada sería un puntero (índice a lugar en la memoria)
a0
a1
...
i
a0
a1
an-1
...
n
a1
an-1
Orden
• ¿ De qué orden son los métodos en una u otra implementación ?
Método
boolean estaVacia();
void insertar(Object x, Posicion k);
Posicion buscar(Object x);
Object buscarK(Posición k);
void eliminar(Object x);
void eliminar(Posicion k);
arreglo
L. enlazada
Eficiencia en una lista enlazada
• Se puede usar como posición la dirección en memoria del
elemento anterior
• Se requiere una cabeza de lista
• Al tener la posición, insertar y eliminar un elemento es O(1)
• Buscar el elemento es siempre O(n)
Un iterador de TDA’s
• Para muchos TDA’s es útil definir un iterador, es decir,
objeto que permita recorrer esta estructura
Ej
TDAx a = new TDAx();
//agregar elementos
. . .
Iterador b = new Iterador(a);
while (b.notEmpty())
print(b.next();
• La idea es que el iterador esconda también la impl.
• El iterador se define normalmente como una interfaz
• Mirar interfaz Iterator de Java
Un iterador de Lista con lista enlazada
class IteradorLista implements Iterador {
NodoLista actual;
}
public IteradorLista(Lista n) {
actual=n.primero;
}
poublic boolean notEmpty() {
return actual != null;
}
public Object next() {
Object aux = actual.info;
actual = actual.sig;
return aux;
}
Otra Estructura de Datos: árbol
• Colección de nodos organizados en forma recursiva:
• 0 nodos -> árbol esta vacío,
• Si no, un nodo denominado raíz, con 0 o más
referencias a otros árboles (subárboles)
• Raíces de los subárboles se llaman hijos de la raíz,
• Raíz se llama padre de las raíces de sus subárboles
Definiciones (1)
• Los nodos sin hijos se denominan hojas.
• Dos nodos que tienen el padre en común se
denominan hermanos.
• Un camino entre un nodo n1 y un nodo nk está
definido como la secuencia de nodos n1, n2, ..., nk tal
que ni es padre de ni+1, 1 <= i < k.
• El largo del camino es el número de referencias que
componen el camino, que para el ejemplo son k-1.
• El camino desde un nodo del árbol a sí mismo es de
largo 0.
• Existe un único camino desde la raíz hasta cualquier
otro nodo del árbol.
Definiciones (2)
• Un nodo n es ancestro de un nodo m si existe un
camino desde n a m;
• Un nodo n es descendiente de un nodo m si existe un
camino desde m a n.
• La profundidad del nodo nk es el largo del camino
entre la raíz del árbol y el nodo nk. (profundidad de la
raíz es siempre 0)
• La altura de un nodo nk es el máximo número de
nodos en un camino desde nk hasta alguna hoja.
(altura de toda hoja es 1)
• La altura de un árbol es igual a la altura de la raíz.
• La altura de un árbol vacío se define como 0.
Ejemplo
•
•
•
•
•
•
•
•
•
A es la raíz del árbol y es padre de B, C y D.
E y F son hermanos, puesto que ambos son hijos de B.
E, J, K, L, C, P, Q, H, N y O son las hojas del árbol.
El camino desde A a J (único) lo conforman los nodos A-B-F-J, largo = 3.
D es ancestro de P, y por lo tanto P es descendiente de D.
L no es descendiente de C, puesto que no existe un camino desde C a L.
La profundidad de C es 1, de F es 2 y de Q es 4.
La altura de C es 1, de F es 2 y de D es 4.
La altura del árbol es 5 (número de nodos en el camino entre la raíz A y la
hoja P o Q).
Arboles Binarios
• Un árbol binario es un árbol en donde cada nodo posee 2 referencias a
subárboles (ni más, ni menos). En general, dichas referencias se
denominan izquierda y derecha, y consecuentemente se define
el subárbol izquierdo y subárbol derecho del árbol.
class NodoArbolBinario {
Object información;
NodoArbolBinario izq;
NodoArbolBinario der;
}
Nodos internos y externos
• Los nodos en sí que conforman un árbol binario se denominan nodos
internos, y todas las referencias que son null se denominan nodos
externos.
Propiedades de los árboles binarios
• Propiedad 1:
• Si se define i = número de nodos internos, e = número de nodos externos,
entonces se tiene que: e = i+1
• Demostración: inducción sobre i (ejercicio).
Propiedades de los árboles binarios
• Propiedad 2:
• Sea n = número de nodos internos. Se define:
– In = suma del largo de los caminos desde la raíz a cada nodo interno
(largo de caminos internos).
– En = suma del largo de los caminos desde la raíz a cada nodo externo
(largo de caminos externos).
• Se tiene que: En = In+2n
• Demostración: inducción sobre n (ejercicio).
Propiedades de los árboles binarios
• Propiedad 3:
¿Cuántos árboles binarios distintos se pueden construir con n nodos internos?
n
bn
0
1
1
1
2
2
3
5
¿bn?
Por ejemplo: b4 = b0*b3 + b1*b2 + b2*b1 + b3*b0 = 5 + 2 + 2 + 5 = 14.
Este tipo de ecuaciones se puede resolver y la solución es la siguiente:
La serie de numeros que genera bn se conoce como números de Catalan.
Asintóticamente:
Ejemplo: árboles de expresiones
matemáticas
• En un árbol de expresiones las hojas corresponden a los operandos de la
expresión (variables o constantes), y los nodos restantes a operadores. Como
los operadores matemáticos son binarios, un árbol de expresiones resulta ser
un árbol binario.
• Un árbol de expresiones se puede evaluar de la siguiente forma:
• Si la raíz del árbol es una constante o una variable se retorna el valor de ésta.
• Si la raíz resulta ser un operador, entonces recursivamente se evalúan los
subárboles izquierdo y derecho, y se retorna el valor que resulta al operar los
valores obtenidos de las evaluaciones de los subárboles con el operador
respectivo.
Recorridos de árboles binarios
• Existen tres formas principales para recorrer un árbol binario en forma
recursiva. Estas son:
– Preorden: raíz - subárbol izquierdo - subárbol derecho.
– Inorden: subárbol izquierdo - raiz - subárbol derecho.
– Postorden: subárbol izquierdo - subárbol derecho - raíz.
• Por ejemplo, al recorrer el árbol de
expresiones anterior en pre-orden se obtiene:
– *+ab-cd
• Al recorrer el árbol en in-orden se obtiene:
– a+b*c–d
• Al recorrer el árbol en pos-torden se obtiene:
– ab+cd-*
• La expresión que se obtiene con el recorrido en postorden se conoce
como notación polaca.
Árboles generales
•
•
•
•
•
•
Los nodos tienen un número indeterminado de hijos.
La implementación: un nodo tiene dos referencias, una a su primer hijo y otra a su
hermano más cercano.
La raíz del árbol necesariamente tiene la referencia a su hermano como null.
Un árbol general puede representarse como un árbol binario, con la salvedad que el
hijo derecho de la raíz es siempre null.
la raíz tiene hermanos, lo que se conoce como bosque, entonces se tiene que el
conjunto de los bosques generales es isomorfo al conjunto de los árboles binarios.
Las propiedades vistas en árboles binarios se cumplen en árboles generales.