Software-Entwurfsmuster

Iterator

(mit Typ-Parameter)

 aufwärts

Ein Iterator ist ein Objekt, das eine bestimmte Daten­struktur sequenziell durchläuft (Bild 1). Mit jedem Aufruf seiner Methode next liefert der Iterator jeweils das nächst­folgende Element (bezeichnet als das Cursor-Objekt). Mithilfe der Methode hasNext stellt der Iterator fest, ob noch weitere Elemente vorhanden sind.

Bild 1: Durchlaufen einer Datenstruktur mit einem Iterator
Bild 1: Durchlaufen einer Datenstruktur mit einem Iterator

Array-Iterator

Der einfachste Iterator durchläuft ein Array. Der Datentyp des Arrays wird dem Iterator als Typ-Parameter übergeben, das Array selbst wird dem Iterator im Konstruktor als Parameter übergeben.

In einer Variablen i merkt sich der Iterator die Position des Cursor-Elements, also desjenigen Array-Elements, das als nächstes zurück­gegeben werden soll. Die Methode next gibt dieses Element zurück und erhöht i um 1. Die Methode hasNext ergibt den Wert true, solange i kleiner als die Länge des Arrays ist.

Es ist empfehlens­wert, die Schnitt­stelle java.util.Iterator zu verwenden. So ist der ArrayIterator überall einsetzbar, wo ein Iterator im Programm vorkommt. 1)

 

public class ArrayIterator<Type> implements Iterator<Type>
{
    private Type[] a;
    private int n, i;

    public ArrayIterator(Type[] a_)
    {
        a=a_;
        n=a.length;
        i=0;
    }

    public boolean hasNext()
    {
        return i<n;
    }

    public Type next()
    {
        return a[i++];
    }

    public void remove()
    {
        // nicht implementiert
    }

}    // end class ArrayIterator

 

Der Iterator wird typischer­weise wie folgt angewendet, z.B. um alle Elemente eines String-Arrays s auszugeben.

 

public class TestArrayIterator
{
    public static void main(String[] args)
    {
        String[] s=new String[3];
        s[0]="ene";
        s[1]="mene";
        s[2]="muh";
        Iterator<String> it=new ArrayIterator<String>(s);
        while (it.hasNext())
            System.out.print(it.next()+" ");
        System.out.println();
    }
}

 

Die Verwendung eines Iterators ist immer dann besonders elegant, wenn eine komplexere Daten­strukturen durchlaufen werden soll oder wenn der Durchlauf nach einem besonderen Muster vonstatten gehen soll. Beispiels­weise soll eine Matrix diagonalen­weise durchlaufen werden oder die Nachbarn eines Knotens in einem Graphen sollen durchlaufen werden.

Der Vorteil einer solchen Lösung mit einem Iterator besteht darin, dass der Iterator

ist. So muss nicht jedesmal neu überlegt, programmiert und getestet werden, wenn eine ent­sprechende Daten­struktur durchlaufen werden soll.

Iterator als Generator

Ein Iterator kann auch verwendet werden, um die Elemente einer bestimmten Menge oder Folge zu erzeugen. Beispiels­weise kann ein Iterator die Primfaktoren einer natürlichen Zahl erzeugen, die Permutationen einer Menge, oder die Zusammenhangs­komponenten eines Graphen.

Als weiteres Beispiel ist im Folgenden der Iterator ModIterator angegeben, der die Elemente von ganze Zahlenn, beginnend bei einem zufällig gewählten Element, erzeugt.

public class ModIterator implements Iterator<Integer>
{
    private int i, j, n;

    public ModIterator(int n_)
    {
        n=n_;
        i=0;
        j=(int)(Math.random()*n);    // Zufallszahl aus {0, ..., n-1}
    }

    public boolean hasNext()
    {
        return i<n;
    }

    public Integer next()
    {
        i++;
        return (i+j)%n;
    }

    public void remove()
    {
        // nicht implementiert
    }
}

 

Der ModIterator wird beispiels­weise wie folgt verwendet, um die Zahlen von 0 bis 9, beginnend bei einem zufälligen Anfangswert, zu erzeugen.

public class TestModIterator
{
    public static void main(String[] args)
    {
        int i;
        Iterator<Integer> it=new ModIterator(10);
        while (it.hasNext())
        {
            i=it.next();
            System.out.print(i+" ");
        }
        System.out.println();
    }
}

 

Aufgaben

Aufgabe 1:  Schreiben Sie einen Iterator, der eine m × n-Matrix mit Einträgen vom Typ Type zeilenweise durchläuft. Implementieren Sie den Konstruktor und die Methoden hasNext und next.

public class MatrixIterator<Type> implements Iterator<Type>
{
    // ...

    public MatrixIterator(Type[][] a)
    {
        // ...
    }

    public boolean hasNext()
    {
        // ...
    }

    public Type next()
    {
        // ...
    }
}

Testen Sie den Iterator mit einer Matrix vom Typ Double.


1)  Die Schnitt­stelle java.util.Iterator verlangt unsinniger­weise zusätzlich die Implementierung einer Methode remove (im Programm­beispiel nicht implementiert)

 

Weiter mit:  [Iterator ohne Typ-Parameter]   [Filteriterator]   oder   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©   Created: 05.11.2006   Updated: 03.03.2017
Valid HTML 4.01 Transitional

Hochschule Flensburg
Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik