Einleitung Suchen

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

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

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

Definition

Eine lineare Datenstruktur L ist eine Sequenz $L=(a_{1}...,a_{n})$ . Die lineare Datenstruktur ordnet Elemente (entweder primitive Datentypen oder komplexere Datenstrukturen) in einer linearen Anordnung an.

Beispiel

Zahlenfolgen

5	4	6	1	3	2

Strings

L	I	N	E	A	R

Atomare Operationen

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

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

public class IntegerList { 
  private class IntegerListElement{ 
   int value; 
   IntegerListElement next; 
  } 
 
  IntegerListElement ﬁrst; 
  int size = 0; 
     private IntegerListElement getElement(int i){ 
   if(i+1 > size)  
    throw new IllegalArgumentException(); 
   int idx = 0; 
   IntegerListElement current = ﬁrst; 
   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.ﬁrst; 
    this.ﬁrst = newElem; 
   }

Suchen und Sortieren

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

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

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

(0\leq p<n)

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

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.