Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


3. Elementare Datenstrukturen



Felder

Die vielleicht grundlegendste Datenstruktur ist das Feld, welches in Pascal und den meisten anderen Programmiersprachen als ein Grundelement definiert ist. Ein Feld ist eine feste Anzahl von einzelnen Daten, welche zusammenhängend gespeichert werden und über einen Index zugänglich sind. Wir bezeichnen das i-te Element eines Felds a mit a[i]. Der Programmierer ist dafür verantwortlich, daß etwas sinnvoll in einer Feldposition a[i] gespeichert wird, bevor darauf Bezug genommen wird; die Vernachlässigung dieser Forderung ist einer der häufigsten Programmierfehler.

Ein einfaches Beispiel für die Verwendung eines Feldes wird durch das folgende Programm gegeben, welches alle Primzahlen ausgibt, die kleiner als 1000 sind. Das zur Anwendung kommende Verfahren, das aus dem 3. Jahrhundert v. Chr. datiert, wird »Sieb des Eratosthenes« genannt:

    program primes(input,output); 
    const N=1000;
    var a: array[1..N] of boolean;
        i,j: integer; 
    begin
    a[1]:=false; for i:=2 to N do a[i]:=true;
    for i:=2 to N div 2 do
      for j:=2 to N div i do a[i*j]:=false;
    for i:=1 to N do
      if a[i] then write(i:4); 
    end.

Dieses Programm verwendet ein Feld, das aus dem einfachsten Typ von Elementen besteht, sogenannten logischen bzw. booleschen Werten. Das Ziel des Programmes besteht darin, dem Element a[i] den Wert true (wahr) zuzuweisen, falls i eine Primzahl ist, und andernfalls den Wert false (falsch). Dies wird erreicht, indem für jedes i alle Elemente des Felds, die einem beliebigen Vielfachen von i entsprechen, auf falsch gesetzt werden, da eine Zahl, die ein Vielfaches einer anderen Zahl ist, keine Primzahl sein kann. Danach wird das Feld nochmals durchgegangen, wobei die Primzahlen ausgegeben werden. (Das Programm kann etwas effizienter gestaltet werden, indem vor der for-Schleife, die die j Werte durchläuft, der Test if a[i] then eingefügt wird. Falls i nämlich keine Primzahl ist, müssen die Elemente des Feldes, die seinen sämtlichen Vielfachen entsprechen, bereits markiert worden sein.) Zu beachten ist, daß das Feld zuerst »initialisiert« wird. Dadurch wird angegeben, daß es keine Zahlen gibt, von denen bekannt ist, daß sie keine Primzahlen sind. Der Algorithmus setzt dann diejenigen Feldelemente auf false, die Indizes entsprechen, die als Nicht-Primzahlen bekannt sind.

Das Sieb des Eratosthenes ist ein typisches Beispiel eines Algorithmus, der die Tatsache ausnutzt, daß jedes Element eines Feldes leicht angesprochen werden kann. Weiterhin realisiert der Algorithmus einen sequentiellen Zugriff auf die Elemente des Feldes. In vielen Anwendungen ist eine sequentielle Anordnung wesentlich; in anderen Fällen wird eine sequentielle Anordnung genutzt, weil sie ebenso gut ist wie jede andere. Das Hauptmerkmal von Feldern besteht jedoch darin, daß, falls der Index bekannt ist, ein Zugriff auf jedes Element in konstanter Zeit möglich ist.

Die Größe des Feldes muß im voraus bekannt sein; in Pascal zum Zeitpunkt der Kompilierung. Um das obige Programm für einen anderen Wert von N ablaufen zu lassen, muß die Konstante N geändert werden, wonach das Programm kompiliert und ausgeführt wird. In manchen Programmierumgebungen ist es möglich, die Größe eines Feldes zum Zeitpunkt der Ausführung festzulegen (so daß man zum Beispiel einen Anwender den Wert von N eingeben lassen könnte und dann die Primzahlen ausgeben würde, die kleiner als N sind, ohne Speicherplatz dafür zu verschwenden, daß man ein Feld so groß definiert wie den größten Wert, den der Anwender eingeben darf), doch trotzdem bleibt es eine wesentliche Eigenschaft von Feldern, daß ihre Größe feststeht und bekannt sein muß, bevor sie verwendet werden.

Felder sind insofern grundlegende Datenstrukturen, als sie in einem direkten Zusammenhang zu Speichersystemen in praktisch allen Computern stehen. Um in der Maschinensprache den Inhalt eines Wortes aus dem Speicher zu bestimmen, geben wir eine Adresse an. Demnach könnten wir uns den gesamten Speicher eines Computers als ein Feld vorstellen, wobei die Speicheradressen den Feldindizes entsprechen. Die meisten Compiler übersetzen Programme, in denen Felder auftreten, in recht effiziente Programme in Maschinensprache, die direkt auf den Speicher zugreifen.

Ein weiteres gebräuchliches Verfahren zur Strukturierung von Information besteht in der Verwendung einer zweidimensionalen Tabelle von Zahlen, die in Zeilen und Spalten angeordnet sind. Zum Beispiel könnte eine Noten-Tabelle der Studenten eines Faches eine Zeile für jeden Studenten und eine Spalte für jede Arbeit, für die Noten erteilt wurde, besitzen. Auf einem Computer würde eine solche Tabelle als ein zweidimensionales Feld mit zwei Indizes dargestellt, einem für die Zeile und einem für die Spalte. Algorithmen, die mit solchen Strukturen operieren, sind sehr einfach: Um beispielsweise den Notendurchschnitt für eine Arbeit zu berechnen, bilden wir die Summe der Elemente einer Spalte und dividieren sie durch die Anzahl der Zeilen; um den Notendurchschnitt eines bestimmten Studenten zu ermitteln, addieren wir die Elemente einer Zeile und dividieren durch die Anzahl der Spalten. Zweidimensionale Felder werden bei Anwendungen dieser Art sehr oft benutzt. Darüber hinaus ist es auf einem Computer oft zweckmäßig und recht einfach, mehr als zwei Dimensionen zu verwenden: Ein Hochschullehrer könnte zum Beispiel einen dritten Index verwenden, um Tabellen der Noten von Studenten für eine Reihe aufeinanderfolgender Jahre zu führen.

Weiterhin besteht eine direkte Entsprechung zwischen Feldern und Vektoren (der mathematische Begriff für indizierte Listen von Objekten). In ähnlicher Weise entsprechen zweidimensionale Felder Matrizen. Algorithmen zur Behandlung dieser mathematischen Objekte werden wir in den Kapiteln 36 und 37 untersuchen.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]