Tutorium Algorithmen und Datenstrukturen 2
Übungsblatt 3: Einfache Suchverfahren
Aufgabe 3-1 *
Implementieren Sie einen sequentiellen Suchalgorithmus in einer Methode. Die Methode soll als Parameter eine Liste vom Typ java.util.LinkedList und einen Wert vom Typ String übergeben bekommen; dieser Wert ist in dieser Liste zu suchen. Zurückgegeben werden soll die Position der Fundstelle in der Liste (als Wert vom Typ int).
Verwenden Sie einen naïven Algorithmus entsprechend Ihren Aufzeichnungen der Vorlesung „Algorithmen und Datenstrukturen 1.“
Aufgabe 3-2 *
Ändern Sie in Ihrer Lösung von Aufgabe 3-1 das Iterations-Idiom wie folgt: Ersetzen Sie
for (int i = 0; i < n; i++) { …
durch
for (Iterator i = liste.iterator(); i.hasNext(); Object item = i.next()) { …
Aufgabe 3-3
Vergleichen Sie die Ausführungsgeschwindigkeiten der Lösungen zu den Aufgaben 3-1 und 3-2.
- Begründen Sie den Unterschied!
- Geben Sie die Zeitkomplexität beider Varianten in der Groß-O-Notation an.
Zusatzaufgabe 3-4 *
Implementieren Sie einen sequentiellen Suchalgorithmus in einer Methode. Die Methode soll als Parameter einen Array vom Typ int[] und einen Wert vom Typ int übergeben bekommen; dieser Wert ist in diesem Array zu suchen. Zurückgegeben werden soll der Array-Index der Fundstelle.
$Id: HEADER.html,v 1.2 2008/05/21 01:41:10 aj3 Exp $
Name Last modified Size Description
Parent Directory -
HEADER.html 2023-10-11 10:00 2.0K
KeyNotFoundException.java 2023-10-11 10:00 346