Actualizado el 12 de Julio del 2020 (Publicado el 17 de Junio del 2019)
1.514 visualizaciones desde el 17 de Junio del 2019
211,0 KB
35 paginas
Creado hace 9a (16/11/2015)
Algoritmos y Estructuras de Datos
Iteradores
Guillermo Román Díez
groman@fi.upm.es
Universidad Politécnica de Madrid
Curso 2015-2016
Guillermo Román, UPM
AED: Introducción
1/26
Iteradores
Es muy común tener que iterar linealmente sobre todos los
elementos de un TAD
Recordamos el código del método show
public static <E > void show ( PositionList <E > list ) {
if ( list == null ) return ;
Position <E > cursor = list . first () ;
while ( cursor != null ) {
System . out . println ( cursor . element () ) ;
cursor = list . next ( cursor ) ;
}
}
Poblemas de este código
Es específico para la lista de posiciones
El programador “cliente” es el responsable de iterar
adecuadamente
Guillermo Román, UPM
AED: Introducción
2/26
Iteradores
Se puede abstraer el cursor para tener código reutilizable para
otros TAD convirtiendo el cursor en un TAD llamado Iterador
Un objeto Iterador permite iterar linealmente sobre los
elementos de otro TAD
La iteración se realiza utilizando métodos del Iterador
No se usan métodos del TAD
Se puede reutilizar código para iterar otros TADs
public static <E > void show ( PositionList <E > list ) {
Iterator <E > it = list . i t e r a t o r () ;
while ( it . hasNext () ) {
System . out . println ( it . next () ) ;
}
}
// Nos da un i t e r a d o r
// ya i n i c i a l i z a d o
// B u c l e m i e n t r a s
// hay mas e l e m e n t o s
// C o g e m o s el e l e m e n t o
// y q u e d a el c u r s o r
// a v a n z a d o
Guillermo Román, UPM
AED: Introducción
3/26
Iterador
El método iterator devuelve un iterador inicializado en el
primer elemento de la estructura de datos
hasNext devuelve true mientras haya algún elemento
pendiente
next devuelve el elemento accesible desde el cursor
Deja el cursor avanzado (post-incremento)
Esto se conoce como un “efecto secundario” o “side effect”
Es análogo al recorrido de un array con post-incremento
int i = 0;
while ( i < arr . length ) {
System . out . println ( arr [ i ++]) ;
}
Guillermo Román, UPM
AED: Introducción
4/26
Ejemplo con otra estructura
Pregunta
¿cuáles serían los cambios sobre el método show para recorrer una
estructura de datos de tipo FIFO o LIFO?
public static <E > void show (PositionList <E > list ) {
Iterator <E > it = list . i ter ato r () ;
while ( it . hasNext () ) {
System . out . println ( it . next () ) ;
}
}
Guillermo Román, UPM
AED: Introducción
5/26
Ejemplo con otra estructura
Pregunta
¿cuáles serían los cambios sobre el método show para recorrer una
estructura de datos de tipo FIFO o LIFO?
public static <E > void show (FIFO <E > list ) {
Iterator <E > it = list . i ter ato r () ;
while ( it . hasNext () ) {
System . out . println ( it . next () ) ;
}
}
Guillermo Román, UPM
AED: Introducción
5/26
Ejemplo con otra estructura
Pregunta
¿cuáles serían los cambios sobre el método show para recorrer una
estructura de datos de tipo FIFO o LIFO?
public static <E > void show (FIFO <E > list ) {
Iterator <E > it = list . i ter ato r () ;
while ( it . hasNext () ) {
System . out . println ( it . next () ) ;
}
}
Ahora con un bucle for
for ( Iterator <E > it = list . i ter ato r () ; it . hasNext () ; ) {
System . out . println ( it . next () ) ;
}
Guillermo Román, UPM
AED: Introducción
5/26
Interfaces Iterator<T> e Iterable<T>
java.util.Iterator<E> declara todos los métodos que debe
implementar un objeto iterador
public i n t e r f a c e Iterator <E > {
public E next () ;
/* o b l i g a t o r i o */
public boolean hasNext () ; /* o b l i g a t o r i o */
public void remove () ;
/* p r o b l e m a t i c o */
}
java.util.Iterable<E> es la pieza que nos permitirá asociar
iteradores a un TAD
public i n t e r f a c e Iterable <E > {
public Iterator <E > i ter ato r () ;
}
Guillermo Román, UPM
AED: Introducción
6/26
Métodos Iterator
hasNext indica si el cursor referencia a un elemento (es
distinto de null)
NO debe entenderse como ¿hay siguiente cursor?
next guarda el elemento al que apunta el cursor, avanza el
cursor y devuelve el elemento guardado
NO debe interpretarse como dame el siguiente elemento
Puede dejar el cursor a null después de avanzar (si es el
último)
remove borra el elemento que devolvió next en su última
ejecución
Es necesario que previamente se haya ejecutado next
No es obligatorio implementarlo en la asignatura
Guillermo Román, UPM
AED: Introducción
7/26
Ejemplo Iterador
Iterator <E > = tad . i ter ato r () ;
{A , B }
↑
cursor
hasNext () dev uel ve true
next () avanza el cursor a B y d evu elv e A
Guillermo Román, UPM
AED: Introducción
8/26
Ejemplo Iterador
Iterator <E > = tad . i ter ato r () ;
{A , B }
↑
cursor
{A , B }
↑
cursor
hasNext () dev uel ve true
next () avanza el cursor a B y d evu elv e A
hasNext () dev uel ve true
next () avanza el cursor a null y d evu elv e B
Guillermo Román, UPM
AED: Introducción
8/26
Ejemplo Iterador
Iterator <E > = tad . i ter ato r () ;
hasNext () dev uel ve true
next () avanza el cursor a B y d evu elv e A
hasNext () dev uel ve true
next () avanza el cursor a null y d evu elv e B
hasNext () dev uel ve false
next ()
lanza N o S u c h E l e m e n t E x c e p t i o n
{A , B }
↑
cursor
{A , B }
↑
cursor
{A , B }
cursor
↓
null
Guillermo Román, UPM
AED: Introducción
8/26
Objeto Iterador
Si al crearse el iterador el TAD está vacío
hasNext devuelve false
next lanza NoSuchElementException
Si el TAD no está vacío
hasNext devuelve true
next avanza el cursor devolviendo el elemento actual
Si el cursor apunta a null
hasNext devuelve false
next lanza NoSuchElementException
Pregunta
¿es posible usar a la vez dos iteradores sobre el mismo TAD?
Guillermo Román, UPM
AED: Introducción
9/26
Método remove
Debe borrar del TAD el elemento devuelto por el último next
Si no ha habido next → IllegalStateException
while ( it . hasNext () ) {
it . next () ;
it . remove () ;
}
// c o r r e c t o
if (! it . hasNext () )
it . remove () ;
// Incorrecto , no hay e l e m e n t o s
if ( it . hasNext () )
it . remove () ;
// Incorrecto , no hay next previo
it . next () ;
it . remove () ;
// c o r r e c t o
// c o r r e c t o
Guillermo Román, UPM
AED: Introducción
10/26
Ejemplo: Décimo
Ejercicio
Método que devuelve el décimo elemento de una lista
Guillermo Román, UPM
AED: Introducción
11/26
Ejemplo: Décimo
Ejercicio
Método que devuelve el décimo elemento de una lista
public static <E > E tenth ( PositionList <E > list )
throws N o S u c h E l e m e n t E x c e p t i o n {
if ( list . size () < 10) {
throw new N o S u c h E l e m e n t E x c e p t i o n () ;
}
Iterator <E > it = list . i ter ato r () ;
for ( int i = 1; i < 10; i ++) {
it . next () ;
}
return it . next () ;
}
Guillermo Román, UPM
AED: Introducción
11/26
Ejemplo: Borra todos
Ejercicio
Método que borra todos los elementos de una lista
Guillermo Román, UPM
AED: Introducción
12/26
Ejemplo: Borra todos
Ejercicio
Método que borra todos los elementos de una lista
public <E > void d e l e t e A l l ( PositionList <E > list ) {
Iterator <E > it = list . i ter ato r () ;
while ( it . hasNext () ) {
it . next () ;
it . remove () ;
}
}
NOTA!!
Recordad que remove debe invocarse siempre después de next
Guillermo Román, UPM
AED: Introducción
12/26
Ejemplo: Suma
Ejercicio
Método que devuelve la suma de los elementos de una lista de enteros
Guillermo Román, UPM
AED: Introducción
13/26
Ejemplo: Suma
Ejercicio
Método que devuelve la suma de los elementos de una lista de enteros
public int s u m a E l e m s ( PositionList < Integer > list ) {
Iterator <E > it = list . i ter ato r () ;
int suma = 0;
while ( it . hasNext () )
suma += it . next () ; // A s u m i m o s != null
return suma ;
}
Guillermo Román, UPM
AED: Introducción
13/26
Ejemplo: Sublista
Ejercicio
Método que indica si una lista es sublista de otra
Guillermo Román, UPM
AED: Introducción
14/26
Ejemplo: Sublista
Ejercicio
Método que indica si una lista es sublista de otra
public static <E > boolean sublist ( PositionList <E > l1 ,
PositionList <E > l2 ) {
if ( l1 == null || l2 == null ) return false ;
if ( l1 == l2 ) return true ;
Iterator <E > it1 = l1 . i ter ato r () ;
boolean res = false ;
while ( it1 . hasNext () &&
( res = this . member ( it1 . next () , l2 ) ) )
;
return res ;
}
Guillermo Román, UPM
AED: Introducción
14/26
Ejemplo: Sublista
Ejercicio
Método que indica si dos listas son iguales
Guillermo Román, UPM
AED: Introducción
15/26
Ejemplo: Sublista
Ejercicio
Método que indica si dos listas son iguales
<E > boolean iguales ( PositionList <E > list1 ,
PositionList <E > list2 ) {
...
Iterator <E > it1 = list1 . i ter ato r () ;
Iterator <E > it2 = list2 . i ter ato r () ;
E e1 , e2 ;
boolean iguales = true ;
while ( it1 . hasNext () && iguales ) {
e1
e2
iguales = i g u a l e s E l e m ( e1 , e2 ) ;
= it1 . next () ;
= it2 . next () ;
}
return iguales ;
}
Guillermo Román, UPM
AED: Introducción
15/26
¿cómo y cuándo usar iteradores?
Los iteradores se usan para iterar sobre TADs que son
colecciones de elementos
No todos los TADs serán colecciones de elementos
Hay TADs que son colecciones de elementos pero dada su
naturaleza no son iterables
El problema debe requerir únicamente el acceso a elementos
(next)
No permite el acceso al nodo (sólo al elemento)
Sólo se puede borrar el último elemento devuelto por el
iterador (remove)
Guillermo Román, UPM
AED: Introducción
16/26
Implementación de Iteradores: Alternativas
El objeto iterador itera usando los métodos del interfaz del
TAD
El iterador puede usarse para iterar sobre objetos de cualquier
clase que implemente el interfaz
El iterador puede iterar sobre cualquier clase que implemente
’I’ si usa únicamente métodos de ’I’ para ”mover” el cursor.
El objeto mueve el cursor accedi
Comentarios de: Algoritmos y Estructuras de Datos (0)
No hay comentarios