Site hosted by Angelfire.com: Build your free website today!

Sequentielle Suche


Eine sequentielle Suche vergleicht, wie der Name schon sagt jedes Element eines Feldes der Reihe nach mit dem gesuchten Wert. Man kann dieses Verfahren auf unsortierte Felder und Listen anwenden.
Die Laufzeit im durchschnittlichen Fall beträgt O(N/2), da im Mittel das gesuchte Element genau in der Feldmitte liegt und alle Elemente bis dorthin geprüft werden müssen. Der ungünstigste Fall tritt auf, wenn der gesuchte Schlüssel nicht im Feld vorhanden ist, da für diese Erkenntnis das gesamte Array durchlaufen werden muss und hat damit O(N+1).
Bei der folgenden Implementierung wird das Feld von hinten her durchsucht, da es effizienter ist, mit einem Markereintrag zu arbeiten, als bei jedem Vergleich noch zusätzlich zu überprüfen, ob das Feldende erreicht ist.

Implementierung mit einem Feld 
dataType cm_SequentielleSuche(itemType wert) {
     int i = N+1;
     feld[0].key = wert;
     feld[0].daten = keineDaten;
     while(wert != feld[--i].key) ;
     return feld[x].daten;
}

Implementierung mit einer verketteten Liste 
dataType cm_SequentielleListenSuche(itemType wert) {
     node *t = head;
     z->key = wert;
     z->daten = keineDaten;
     while(wert != t->key) t=t->next;
     return t->daten;
}


   Computer    Programmieren (incl. C++ Kurs)    Algorithmen    Bücher    

Zeitschriften    Heavy Metal    Mountainbiking    Meine Katze    

Über mich und die Site    Links    Downloads    Gästebuch    HP mit Umfrage