Listensuche

aus www.iwiki.de, der freien Wissensdatenbank

Die Listensuche ist eines der wichtigsten und fundamentalsten Operationen in Computer Systemen. Beispiele beinhalten die Suche nach Schlüsselwörtern in Nachschlagewerke, Namen in Symboltabellen oder komplexe Informationen in Datenbanken. In diesem Kapitel werden die Elementaroperationen der Suche behandelt.

Inhaltsverzeichnis 1 Definition 2 Links 3 Quelle 4 Weblinks

Definition

Listensuche ist der Prozess des Auffindens eines oder mehreren Listenelementen mit einem bestimmten Kriterium, dies nennt man Suchschlüssel.

Der Prozess ist erfolgreich, wenn der Suchschlüssel ein übereinstimmendes Element in der Liste findet und somit seine Lage in der Liste bekannt geben kann.

Definition: mittlere Suchlänge

L_s = mittlere Suchlänge

n = Anzahl der Elemente

c_i = Anzahl von Schlüsselparameter

p_i = Wahrscheinlichkeit der Suche nach dem i'ten Element

Wenn die Wahrscheinlichkeit nicht bekannt ist wird das arithmetische Mittel verwendet P_i : 1/n für alle i

Links

• Liste
• Datentyp Liste
• Blocksuche

Quelle

• Bernd Breutmann: Data and Algorithms. An Introductory Course, 2001 Carl Hanser Verlag München, ISBN 3-446-21591-3

Weblinks

• Lineare Suche
  
• Binäre Suche