Kapitel 6. Suchverfahren

25.05.01


Zum Starten hier klicken


Inhaltsverzeichnis

Kapitel 6. Suchverfahren

Sequentielle Suche

Binäre Suche

1. Falls Liste leer ist, endet die Suche erfolglos. Sonst: Betrachte Element der Liste an mittlerer Position m. 2. Falls K = Schlüsselwert dieses Elementes, dann ist das gesuchte Element gefunden .

Binäre Suche (2)

Kosten

Fibonacci-Suche

- Element an der Position i = F k-2 wird mit dem Schlüssel K verglichen

Sprungsuche

Einfache Sprungsuche

Optimale Sprungweite

Exponentielle Suche

Sind in der sortierten Liste nur positive, ganzzahlige Schlüssel ohne Duplikate gespeichert, wachsen Schlüsselwerte mindestens so stark wie die Indizes der Elemente.

Interpolationssuche

Sinnvoll, wenn der Schlüsselwert im betreffenden Bereich einigermaßen gleichverteilt ist

Anmerkungen zur Implementierung in C

Rekursive Definition eines Strukturtyps

Verwendung von typedef

Autor:Dietmar Saupe

E-Mail: der@informatik.uni-leipzig.de

Homepage: http://www.informatik.uni-leipzig.de/~der