Suchverfahren (4)


Unser allgemeines Suchschema liefert eine elegante Lösung für ein klassisches Problem, das traditionell in einer Weise angegangen wird, welche die Verwendung von Sprüngen oder des Abbruchs einer Schleife nahelegt; wir kommen hier bequem ohne sie aus. Es handelt sich um das Suchen in einer rechteckigen Matrix:
TYPE Zeilen = 1 .. zmax;
     Spalten = 1 .. smax;
     Daten = RECORD wert: atom;
                    key: keytype;
             END;
VAR a: ARRAY [Zeilen, Spalten] OF Daten;

PROCEDURE suche(k: keytype; VAR found: BOOLEAN;
                VAR z: Zeilen; VAR s: Spalten);
VAR Zustand: (suchen, ja, nein);
BEGIN Zustand := suchen; z := 1; s := 1;
      WHILE Zustand = suchen 
      DO IF a[z,s].key = k then Zustand := ja;
         ELSIF s < smax THEN s := s + 1;
         ELSIF z < zmax THEN z := z + 1; s := 1;
         ELSE Zustand := nein;
         END;
      END;
      found := Zustand = ja;
END suche;
Traditionell wird dies mit zwei geschachtelten Schleifen und jeweils vorzeitigem Aussprung programmiert; unsere Lösung finden wir klarer, und sie ist mindestens ebenso effizient.
PROCEDURE suche(k: keytype; VAR found: BOOLEAN;
                VAR z: Zeilen; VAR s: Spalten);
BEGIN found := FALSE;
      FOR z := 1 TO zmax 
      DO FOR s := 1 TO smax 
         DO IF a[z,s].key = k THEN found := TRUE; EXIT;
            END;
         END; IF found THEN EXIT END;
      END;
END suche;
In manchen Sprachen kann man mit EXIT auch mehrere geschachtelte Schleifen verlassen; dann fällt der zweite Aussprung weg.

Abgesehen vom Programmieren auf Maschinenebene, wo die höheren Konstrukte fehlen, ist uns kein Beispiel (mehr) bekannt, in denen explizite Sprünge von Vorteil wären.


zurück | Inhalt | Index | vor | Vorlesung

Klaus Lagally, 22. Februar 2000, 19:36