Suchverfahren (1)
Das Suchen nach einem Datenelement
mit einem gegebenen Suchschlüssel
wird üblicherweise von Fall zu Fall behandelt,
in Abhängigkeit von der Datenstruktur,
in der die Nutzdaten abgelegt und verwaltet werden.
Tatsächlich ist aber die dahinterstehende Grundlogik immer gleich;
Unterschiede bestehen nur in den Zugriffsarten auf die Daten
und in den darüber bekannten Informationen.
Wir behandeln hier das Suchproblem so allgemein wie möglich,
indem wir nur soviel Information verwenden,
wie wir unbedingt benötigen,
Unser Zugang ist notwendigerweise recht
abstrakt,
weil wir alles an konkreten Details weglassen,
was nicht zum Problem im engeren Sinne gehört;
dafür stehen uns die Einzelheiten auch nicht im Wege.
Um überhaupt suchen zu können, setzen wir voraus:
-
Datenelemente, die irgendwelche Nutzdaten tragen und über
einen Suchschlüssel von einem geeigneten linearen Typ
keytype identifiziert werden;
-
für jedes Datenelement gibt es eine geeignete Ortsangabe;
-
eine Datenstruktur, die die Datenelemente enthält, beschrieben
durch geeignete Beschreibungsgrößen;
-
ein Kriterium, ob die Datenstruktur leer ist;
-
eine Ortsangabe als Einstieg in eine nicht leere Datenstruktur,
die auf irgend ein Datenelement verweist.
Damit kann man die Suche als Pseudoprogramm bereits ausprogrammieren;
in dieser Form wird es allerdings noch kein Übersetzer akzeptieren.
Die nötigen Anpassungen sind im konkreten Fall offensichtlich.
PROCEDURE suche(k: keytype; d: Daten; VAR wo: Ort);
BEGIN IF leer(d) THEN wo := NIRGENDS
ELSE wo := Einstieg(d);
IF k <> key(wo)
THEN suche(k, Teilstruktur(d), wo)
END;
END;
END suche;
Teilstruktur(d) ist eine geeignete Teilmenge von d,
in der das Element zum Schlüssel k noch liegen kann.
Der Einstieg gehört sicher nicht dazu,
aber die Teilmenge kann durchaus wesentlich kleiner als der Rest sein,
je nachdem, wie viel man über den Aufbau der Datenstruktur weiß.
zurück |
Inhalt | Index |
vor |
Vorlesung
Klaus Lagally, 22. Februar 2000, 19:36