Lineare Suche
Grundidee - unsortierte Liste
Wir gehen zunächst davon aus, dass die Liste mit den Datenobjekten nicht sortiert ist.
Fall 1: Das Datenobjekt kommt in der Liste vor.
Fall 2: Das Datenobjekt kommt nicht in der Liste vor.
Grundidee - sortierte Liste
Wir gehen jetzt davon aus, dass die Liste mit den Datenobjekten aufsteigend sortiert ist.
Fall 1: Das Datenobjekt kommt in der Liste vor.
Fall 2: Das Datenobjekt kommt nicht in der Liste vor.
Aufgabe 1
Erläutere die Vorgehensweise bei der linearen Suche anhand der Abbildungen. Gehe dabei auch auf den Unterschied zwischen einer unsortierten und einer vorsortierten Liste ein.
Ablaufmodellierung
Die Idee der linearen Suche in einer unsortierten Liste ist sehr einfach: Man durchläuft schrittweise die Liste und vergleicht das vorgegebene Datenobjekt mit jedem Listenelement, bis das entsprechende Datenobjekt in der Liste gefunden ist oder die Liste komplett durchlaufen ist und kein entsprechendes Datenobjekt gefunden wurde.
Der Ablauf lässt sich so präzisieren:
ALGORITHMUS linearesuche_unsortiert Übergabe: Datenobjekt; Liste setze indexErgebnis auf -1 setze gefunden auf False setze index auf 0 SOLANGE index im erlaubten Indexbereich und das Datenobjekt nicht gefunden ist: WENN das Datenobjekt mit dem Listenelement zum index übereinstimmt: setze gefunden auf True setze indexErgebnis auf index SONST: erhöhe index um 1 Rückgabe: indexErgebnis
Aufgabe 2
Formuliere analog den Algorithmus linearesuche_sortiert
.
Aufgabe 3
Implementiere die Algorithmen und teste die entwickelten Programme.