Kurs:Algorithmen und Datenstrukturen/Vorlesung/Suche Einleitung
Einleitung Suchen Bearbeiten
In diesem Kapitel geben wir einen Überblick über das Thema Suchen. Suchprobleme sind eine der häufigsten Probleme in der Informatik. Man kann in sortierten Folgen suchen, Zeichenketten im Text suchen, Dokumente in Textkorpora suchen, oder allgemeine Lösungen von Problemräumen, wie der Spielbaumsuche oder der Plansuche, suchen. Hier behandeln wir zunächst die Suche in sortierten Folgen.
Motivation Bearbeiten
Beim Suchen wiederholt man häufig sehr nützliche Beispielalgorithmen, oder lernt diese sogar neu kennen. Außerdem dient es der Vorbereitung der theoretischen Betrachtungen zur Komplexität von Algorithmen. Des Weiteren dient es der informellen Diskussion von Entwurfsentscheidungen.
Suchen in sortierten Folgen Bearbeiten
- Annahme:
- Die Folge F ist ein Feld mit numerischen Werten. Dazu ist die Folge sortiert, das heißt, wenn i<j, dann ist F[i]<F[j]. Auf das i-te Element hat man Zugriff über F[i]. Es wird nur der Suchschlüssel berücksichtigt.
Ein Beispiel ist ein Telefonbuch, in dem wir nach Namen suchen möchten. Doch wie repräsentiert man diese Daten?
Einschub lineare Datenstrukturen Bearbeiten
Definition Bearbeiten
Eine lineare Datenstruktur L ist eine Sequenz . Die lineare Datenstruktur ordnet Elemente (entweder primitive Datentypen oder komplexere Datenstrukturen) in einer linearen Anordnung an.
Beispiel Bearbeiten
Zahlenfolgen
| 5 | 4 | 6 | 1 | 3 | 2 |
Strings
| L | I | N | E | A | R |
Atomare Operationen Bearbeiten
Zu den Operationen gehören Lesen mit
- get(i): Element an Position i lesen
- first(): erstes Element lesen
- last(): letztes Element lesen
- next(e): Element nach Element e lesen
und Schreiben mit
- set(i,e): Element an Position i auf e setzen
- add(i,e): Element e an Position i einfügen
- del(i): Element an Position i löschen
Arrays und Listen Bearbeiten
Es gibt zwei Möglichkeiten lineare Datenstrukturen zu realisieren. Entweder Arrays oder (verlinkte) Listen. Arrays belegen einen zusammenhängenden Bereich im Speicher. Elemente einer verlinkten Liste können beliebig verteilt sein. Ob zur Realisierung einer linearen Datenstruktur ein Array oder eine Liste verwendet wird, hängt von der Anwendung ab. Arrays werden meist für statische Datenstrukturen verwendet, d.h. wenn die Länge des Arrays nicht verändert wird. Listen werden meist für dynamische Datenstrukturen verwendet, d.h. wenn die Länge variabel ist. Zu den positiven Eigenschaften von Arrays zählen der schneller Zugriff auf Einzelelemente durch den Index. Zu den negativen Eigenschaften von Arrays zählen das sehr aufwändige Einfügen der Elemente. Zu den positiven Eigenschaften von Listen zählen die relativ effiziente Manipulation, zu den negativen Eigenschaften der ineffiziente Direktzugriff.
Einfache verlinkte Liste von Zahlen in Java Bearbeiten
public class IntegerList {
private class IntegerListElement{
int value;
IntegerListElement next;
}
IntegerListElement first;
int size = 0;
private IntegerListElement getElement(int i){
if(i+1 > size)
throw new IllegalArgumentException();
int idx = 0;
IntegerListElement current = first;
while(idx != i){
current = current.next;
idx ++;
}
return current;
}
public int get(int i){
return this.getElement(i).value;
}
public int add(int pos, int val){
IntegerListElement newElem = new IntegerListElement();
newElem.value = val;
if(pos > 0){
IntegerListElement e = this.getElement(pos‐1);
newElem.next = e.next;
e.next = newElem;
}else{
newElem.next = this.first;
this.first = newElem;
}
Suchen und Sortieren Bearbeiten
Suchen und Sortieren sind voneinander abhängige Operationen. Dabei gibt es zwei Ansätze: Wenn Elemente nie sortiert sind, dann ist die Suche sehr aufwändig. Wenn die Elemente sortiert sind, wird die Suche erleichtert, jedoch kann das Sortieren an sich sehr aufwändig sein. Wenn Elemente hinzugefügt oder gelöscht werden ist diese Problematik noch sichtbarer. Nur ein unsortiertes Element macht die Suche aufwändig, doch bei jeder Einfügung oder Löschung zu sortieren ist ebenfalls sehr aufwändig. Spezielle dynamische Datenstrukturen erlauben eine automatische und effiziente Sortierung bei Einfügung oder Löschung. lol ist alles falsch ich bin ncool und ihr seid alle behindert
Lineare Datenstruktur in Java Bearbeiten
- Arrays:
- int[] arr = new int[10];
- arr[1] = 4;
- Listen:
- List<Integer> myList = new LinkedList<Integer>();
- myList.add(5);
- Neben LinkedList unterstützt Java eine Reihe weiterer Listenimplementierungen mit unterschiedlichen Vor- und Nachteilen
- Schnittstelle List<Type> beinhaltet die gemeinsamen Methoden
Suche Bearbeiten
- Problembeschreibung
- Die Eingabe ist eine Folge F mit n Elementen von Zahlen und Suchelementen k. Die Ausgabe ist eine erfolgreiche oder nicht erfolgreiche Suche. Erfolgreich ist sie, wenn der Index p ist. Eventuell muss man festlegen, was bei Mehrfachvorkommen passiert. Normalerweise gilt dann das erste Vorkommen. Ist die Suche nicht erfolgreich, dann ist die Ausgabe -1.
- Merkmale der Suche
- Es gibt immer einen Suchschlüssel für Suchelemente, z.B. Zahlen. Außerdem ist eine Suche immer erfolgreich oder erfolglos. Die Suche basiert auf Vergleichsoperationen und die Daten sind zunächst als Feld, bzw. Array, oder Liste dargestellt.
Literatur Bearbeiten
Da die Vorlesungsinhalte auf dem Buch Algorithmen und Datenstrukturen: Eine Einführung mit Java von Gunter Saake und Kai-Uwe Sattler aufbauen, empfiehlt sich dieses Buch um das hier vorgestellte Wissen zu vertiefen. Die auf dieser Seite behandelten Inhalte sind in Kapitel 5 zu finden.
