|
Folien
Übungen
Programme
Bilder
 Zurück
|
Multimedia-Ergänzungen zum Buch: Algorithmen und Datenstrukturen, Kapitel 3: Suchen
|
|
|
|
Das Suchen in Datenmengen ist eine der wichtigsten und
grundlegendsten Operationen, die man mit Computern ausführen
können möchte. Man denke an das Suchen nach einem
Stichwort in einem Wörterbuch oder einer Enzyklopädie,
die Suche nach einer Telefonnummer in einem Telefonverzeichnis,
nach einem Namen in einer Symboltabelle, nach einer Kontonummer,
Personalnummer, usw. Wir setzen in diesem Kapitel durchweg voraus,
daß die Information, nach der wir suchen, durch einen
Schlüssel eindeutig identifizierbar ist.
Meistens nehmen wir der Einfachheit halber an, daß die Schlüssel
positive ganze Zahlen sind, wie etwa Kontonummern,
Personalnummern, Auftragsnummern.
Wir wollen in diesem Kapitel nur elementare Suchverfahren
behandeln; das sind Verfahren, die, wie allgemeine Sortierverfahren,
nur Vergleichsoperationen zwischen Schlüsseln
ausführen. Arithmetische Operationen, die es erlauben, aus dem
Suchschlüssel direkt die Speicheradresse zu berechnen, werden in
diesem Kapitel ebensowenig behandelt wie besondere Datenstrukturen,
die das Suchen und Wiederfinden gespeicherter Daten besonders
unterstützen. Wir beschränken uns in diesem Kapitel im
wesentlichen auf die Diskussion der wichtigsten elementaren Verfahren
zum Suchen in linearen Listen, die sequentiell oder verkettet
gespeichert sind. Arithmetische Verfahren zur direkten Bestimmung der
Speicheradresse aus einem gegebenen Schlüssel werden
ausführlich im Kapitel über Hashing behandelt. Ebenso werden
die wichtigsten die Suche unterstützenden Baumstrukturen in einem
eigenen Kapitel behandelt. Daß eine vorhandene Sortierung beim
Suchen hilft, weiß jeder aus alltäglicher Erfahrung. Wir
werden den möglichen Gewinn auch quantitativ abschätzen.
|
|
Bei Fragen zu dem Inhalt des Buches senden Sie bitte eine Email an ad-buch@informatik.uni-freiburg.de.
|
|