Wir wollen die Zeichen eines vom Benutzer einzugebenden Strings in sortierter Reihenfolge ausgeben. (Diese Aufgabenstellung mag zunächst künstlich erscheinen; sie wird uns aber in Abschnitt 2.3.5 als grundlegender Baustein eines bestimmten Verfahrens zur Gruppierung von Strings wieder begegnen.) Dazu verwenden wir einen einfachen Sortieralgorithmus: Im ersten Schritt suchen wir nach dem „kleinsten“ Zeichen, d. h. dem Zeichen, das in der lexikographischen Reihenfolge aller Zeichen als erstes kommt^[7], und vertauschen es mit dem ersten Zeichen (das die Nummer 0 hat). Im zweiten Schritt suchen wir in dem Restfeld (man beachte hier das Wort „Feld“!), das an Position 1 beginnt, nach dem kleinsten Zeichen (also dem zweitkleinsten insgesamt), und tauschen es mit dem Zeichen an Position 1. Im dritten Schritt suchen wir usw. Allgemein suchen wir im i-ten Schritt im Restfeld, das an der Position i-1 beginnt, nach dem kleinsten Zeichen und vertauschen es mit dem Zeichen an Position i-1. Bei insgesamt n Zeichen stehen dann nach insgesamt n Schritten (Iterationen) die Zeichen in der richtigen Reihenfolge.^[8] (Es genügen sogar n-1 Iterationen, denn das letzte Restfeld, das aus nur einem Zeichen besteht, ist schon korrekt sortiert.) Dieses Sortierverfahren heißt Sortieren durch Minimumsuche.

Beim Sortieren ist es also wichtig, auf die einzelnen Zeichen über ihre Nummer (genannt Index) zugreifen und sie vertauschen zu können. Die Datenstruktur der Wahl hierfür ist das Feld (engl. array). Wir lesen also einen String ein und speichern seine einzelnen Zeichen als Elemente eines Arrays ab, sortieren dann das Array nach dem skizzierten Verfahren und schreiben zum Schluss die Zeichen in sortierter Reihenfolge wieder in den String zurück. Dazu benutzen wir die LEDA-Klasse array.

#include <LEDA/array.h>
#include <LEDA/string.h>
#include <LEDA/misc.h>
#include <iostream>

using leda::array;
using leda::string;
using std::cout;

int main() 
{
  string s;

  s = leda::read_string("Please enter a string: ");

  int n = s.length();

  array<char> A(n);

  // copy chars into array
  for(int i = 0; i < n; i++)
    A[i] =  s[i];

  // sort array
  for(int i = 0; i < n-1 ; i++) {
    char min = A[i]; // minimal element seen so far
    int min_pos = i; // memorize its position
    // search for min starting from position i+1
    for(int j = i + 1; j < n; j++) 
      if(A[j] < min) {
        min = A[j];
        min_pos = j;
      }
    // swap elements at positions i and min_pos
    A[min_pos] = A[i];
    A[i] = min;
  }

  // copy chars back into string, overwriting old ordering
  for(int i = 0; i < n; i++)
    s[i] =  A[i];

  cout << s << "\n";
}

Ein Beispiellauf des Programms ist folgender:

Please enter a string: Jumping Jack Flash
  FJJaacghiklmnpsu

Die LEDA-Klasse array ist unser erstes Beispiel für einen Containertyp. Das ist eine Datenstruktur, in der Ansammlungen von (gleichartigen) Objekten verwaltet werden können. Die Objekte werden in diesem Zusammenhang auch als Elemente bezeichnet. Der Typ der Elemente eines Arrays ist ein Typparameter, der bei der Deklaration des Arrays angegeben werden muss. In unserem Beispiel speichern wir einzelne Zeichen in dem Array A ab; das Array ist also vom Typ array<char>. Abbildung 2.1 zeigt ein Array mit den Zeichen des Beispiellaufes.

Abbildung 2.1. Ein Array von Zeichen

Dieses Array besteht aus n=18 Zeichen. Der Index des ersten Zeichens ist 0, der des letzten 17.

Die Anzahl der Elemente, die ein Array speichern soll, kann bei der Definition angegeben werden. Im Gegensatz zu gewöhnlichen C++-Arrays muss diese Anzahl aber nicht zur Kompilationszeit bekannt sein; sie kann durchaus variabel sein, wie obige Definition

array<char> A(n);

mit variablem n zeigt. Wie wir gleich sehen werden, kann sie sogar ganz ausgelassen werden, da LEDA-Arrays zur Laufzeit auf jede beliebige Größe gebracht werden können.

Auf die einzelnen Elemente des Arrays kann wie in C++ und anderen Sprachen durch den Subskript-Operator [] zugegriffen werden. A[0] bezeichnet dabei das erste Element des Arrays; genauer gesagt liefert [] eine Referenz auf dieses Element zurück. Dadurch kann der Wert eines Elementes ausgelesen oder neu gesetzt werden:

A[0] = 'P'; 

macht aus dem Jumping Jack Flash den Pumping Jack Flash.

Zum Einlesen des Strings haben wir hier die Funktion read_string() benutzt, die wie andere nützliche kleine Funktionen in der Header-Datei misc.h deklariert ist. Sie gibt eine Eingabeaufforderung aus und liefert den vom Benutzer eingegebenen String zurück.

Wir können nun sagen: Für diese Sortiererei hätten wir doch eigentlich gar kein Array gebraucht, auf die einzelnen Zeichen des Strings können wir doch ebenfalls durch den Operator [] zugreifen! Wir könnten folglich gleich im String selbst sortieren, ohne den Umweg über ein Array. Das ist richtig, und ein erfahrener LEDA-Programmierer würde auch niemals ein Sortierverfahren selbst schreiben, denn alle nur erdenklichen effizienten Sortieralgorithmen sind selbstverständlich schon in LEDA eingebaut. Wir hätten uns das Sortieren durch die Array-Methode

A.sort(); 

auch einfacher machen können. Dazu müssen wir die Zeichen vom String in ein Array kopieren, das Array sortieren, und die Zeichen wieder in den String zurückschreiben:

#include <LEDA/array.h>
#include <LEDA/string.h>
#include <iostream>

using leda::array;
using leda::string;
using std::cout;

int main() 
{
  string s;

  cout << "Please enter a string: ";

  s.read_line();

  int n = s.length();

  array<char> A(n);

  for(int i = 0; i < n; i++)
    A[i] =  s[i];

  A.sort();

  for(int i = 0; i < n; i++)
    s[i] =  A[i];

  cout << s << "\n";
}

Hier lesen wir den String über die String-Methode read_line() ein. Die Array-Methode sort() sortiert die Elemente eines Array gemäß deren linearer Ordnung. Mehr zu linearen Ordnungen und wie ein Typ zu einem linear geordneten Typ gemacht werden kann, werden wir in Abschnitt 2.8.3 sehen. Der Typ char jedenfalls besitzt schon eine von LEDA vordefinierte lineare Ordnung.

Im Gegensatz zu C++-Arrays dürfen LEDA-Arrays jedes beliebige ganzzahlige Intervall als Indexmenge haben. Die Indizes müssen also nicht bei 0 beginnen, und insbesondere dürfen auch negative Indizes vorkommen. Abbildung 2.2 verdeutlicht dies.

Abbildung 2.2. Ein LEDA-Array mit negativen Indizes

Bei der Definition werden die Elemente nicht initialisiert. low() bzw. high() liefern den kleinsten bzw. größten Index des Arrays.

Der kleinste und der größte Index sind bei der Definition anzugeben, also etwa

array<char> A(-5, 5);

Alternativ dazu kann ein Array auch durch

array<char> A;

angelegt, und seine Größe erst zu einem späteren Zeitpunkt durch resize() festgelegt werden.

Die Klasse array besitzt noch weitere nützliche Methoden, die wir hier kurz vorstellen wollen.

Die Methode

A.init(x);

setzt alle Elemente eines Arrays auf den Wert x.

	Wichtig
	Es ist nicht so, dass schon bei der Definition eines Arrays die Elemente auf einen definierten Anfangswert gesetzt würden, etwa 0. Das wäre vielleicht ganz praktisch, aber dann könnten Arrays nicht mehr in konstanter Zeit angelegt werden. (Was „konstante Zeit“ bedeutet, werden wir in Abschnitt 2.2.3 erfahren.)

Die Methode

A.print();

gibt das gesamte Array auf die Standardausgabe aus und bietet somit eine bequeme Möglichkeit der Kontrollausgabe.

Ein Aufruf von

A.permute();

bringt die Elemente des Arrays A in eine zufällige Reihenfolge.

Besonders interessant ist die Methode

A.resize(new_low, new_high);

Sie legt die Größe eines Arrays neu fest; dabei sind der neue kleinste und größte Index anzugeben. „Alte“ Elemente werden dabei automatisch in das neue Array kopiert und neu hinzugekommene Elemente werden auf 0 bzw. auf den Default-Wert des Elementtyps gesetzt.

Die Methoden

A.low();
A.high();

liefern den kleinsten bzw. größten Index eines Arrays, und

A.size();

liefert die Anzahl der Elemente von A. Diese Methoden sind vor allem dann sehr nützlich, wenn aufgrund eines resize() die Größe und die Endindizes nicht mehr bekannt sind.

Zum schnellen Suchen von Elementen gibt es die Methode

A.binary_search(x);

die ein Element mit dem Wert x in Zeit O(log n) findet, wenn das Array n Elemente enthält. Vorbedingung der Binärsuche ist, dass das Array sortiert ist; s. hierzu auch Übung 3. Ist es dies nicht, kann es vorher mittels sort() sortiert werden. binary_search() liefert den Index des zu suchenden Elementes zurück.

Gibt es in dem Array mehrere Elemente mit dem Wert x, so stehen diese in einer Teilfolge nebeneinander. binary_search() liefert dann irgendeinen Index dieser Folge zurück. Dagegen führt die Methode

A.binary_locate(x);

ebenfalls eine schnelle Binärsuche durch, liefert jedoch den maximalen Index einer Teilfolge gleicher Werte zurück.

	Warnung
	In der derzeitigen Version 6.2 von LEDA ist binary_locate() fehlerhaft und sollte nicht verwendet werden.

In A mehrfach vorkommende Elemente können mit

A.unique();

entfernt werden. Vorbedingung ist auch hier, dass das Array sortiert ist. Diese Methode kopiert jeden im Array vorkommenden Wert einmal an den Anfang und liefert den Index des letzten dieser (nun eindeutigen) Werte zurück. Das ursprüngliche Array wird also zerstört, weil Elemente am Anfang überschrieben, aber nicht nach hinten kopiert werden! (Es gehen dabei Elemente verloren!)

Einem erfahrenen Programmierer sagt ein kleines Programm mehr als tausend Worte, und daher wollen wir durch ein kleines, für sich gesehen völlig sinnloses Progrämmchen den Gebrauch dieser Methoden skizzieren:

#include <LEDA/array.h>
#include <iostream>

using leda::array;
using std::cout;
using std::endl;

int main() 
{
  array<int> A(-5,5);

  A.init(0);
  A.print(); cout << endl;

  for(int i = A.low(); i <= A.high(); i++)
    A[i] = i;
  A.print(); cout << endl;

  A.permute();
  A.print(); cout << endl;
  
  A.sort();
  A.print(); cout << endl;

  A.resize(0,15);
  A.print(); cout << endl;

  cout << "A contains " << A.size() << " elements.\n";

  for(int i = A.low(); i <= A.high(); i++)
    A[i] /= 2;
  A.print(); cout << endl;
 
  A.sort();
  A.print(); cout << endl;

  int pos1 = A.binary_search(0);
  int pos2 = A.binary_locate(0);
  cout << "pos1 = " << pos1 << "   " << "pos2 = " << pos2 <<endl;

  int h = A.unique();
  cout << "The unique elements of A are: ";
  for(int i = A.low(); i <= h; i++) 
    cout << A[i] << " ";
  cout << endl;

  cout << "The rest of A is now: ";
  for(int i = h+1; i <= A.high(); i++) 
    cout << A[i] << " ";
  cout << endl;
}

Die sensationelle Ausgabe des Programms ist

  0 0 0 0 0 0 0 0 0 0 0
 -5 -4 -3 -2 -1 0 1 2 3 4 5
 4 5 2 -2 -5 1 -4 3 -1 0 -3
 -5 -4 -3 -2 -1 0 1 2 3 4 5
 0 1 2 3 4 5 0 0 0 0 0 0 0 0 0 0
A contains 16 elements.
 0 0 1 1 2 2 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0 0 1 1 2 2
pos1 = 7   pos2 = 7
The unique elements of A are: 0 1 2
The rest of A is now: 0 0 0 0 0 0 0 0 0 1 1 2 2

	Anmerkung
	Man beachte, dass print() immer zuerst ein Leerzeichen ausgibt. Dies ist ein Fehler, der ab der Version 4.5 von LEDA behoben sein wird.

Einer der Hauptvorteile von LEDA-Arrays gegenüber gewöhnlichen C++-Arrays liegt in der Möglichkeit, ihre Größe durch resize() dynamisch anzupassen. Abbildung 2.3 verdeutlicht, was in obigem Programm bei Aufruf der Methode resize() geschieht: Der Indexbereich des Arrays ändert sich vom Intervall [-5..5] auf das Intervall [0..15]. Die Elemente, die in der Schnittmenge der beiden Indexmengen liegen (also die Elemente mit den Indizes 0 bis 5) werden übernommen, die neu hinzugekommenen Elemente werden auf 0 initialisiert.

Abbildung 2.3. Die Funktion resize() von Arrays

Eine schöne Anwendung von resize() findet sich in der effizienten Berechnung der Binomialkoeffizienten (n,k). Damit wird die Anzahl der k-elementigen Teilmengen einer n-elementigen Menge bezeichnet. So gibt es z. B. beim Lotto (49,6) Möglichkeiten, 6 Kugeln aus einer Trommel von insgesamt 49 Kugeln zu ziehen. Das sind insgesamt 13.983.816 Möglichkeiten. Daher liegt die Wahrscheinlichkeit, einen Sechser im Lotto zu erzielen (wenn man nur einen Tipp pro Schein ausfüllt), bei 1/13.983.816. Anders ausgedrückt muss man im Durchschnitt 13.938.816/52 = 268.054,15 Jahre Lotto spielen, um wirklich reich zu werden. Da ist es besser, wir lernen anständig LEDA und machen dann als LEDA-Experte Kohle!

Bekanntlich treten die Binomialkoeffizienten als Zahlen im Pascal'schen Dreieck auf, s. Abbildung 2.4. In jeder Zeile im Dreieck sind die beiden äußeren Zahlen 1, die inneren Zahlen ergeben sich als die Summe der beiden darüber stehenden Zahlen in der Vorgängerzeile. In Formeln ausgedrückt:

Abbildung 2.4. Das Pascal'sche Dreieck

Das folgende Programm berechnet 10 Zeilen des Pascal'schen Dreiecks. Wir verwenden dabei ein temporäres Array, um die jeweils neue Zeile aus der alten zu berechnen. Dieses wird in jeder Iteration durch einen Aufruf von resize() um 1 Element größer. A.low() und B.low() bleiben hier natürlich immer auf 0 stehen, nur der Wert von high() wächst in jeder Iteration.

#include <LEDA/array.h>
#include <iostream>

using leda::array;
using std::cout;

int main()
{
  array<int> A(0,1);
  A[0] = A[1] = 1;

  A.print();
  cout << "\n";

  array<int> B;

  for(int n = 0; n <= 10 ; n++) {

    B.resize(A.low(), A.high() + 1);

    B[0] = B[B.high()] = 1;
    for(int k = 1; k < B.high(); k++)
      B[k] = A[k-1] + A[k];

    B.print();
    cout << "\n";

    A = B;
  }
}

Die Ausgabe des Programms ist

 1 1
 1 2 1
 1 3 3 1
 1 4 6 4 1
 1 5 10 10 5 1
 1 6 15 20 15 6 1
 1 7 21 35 35 21 7 1
 1 8 28 56 70 56 28 8 1
 1 9 36 84 126 126 84 36 9 1
 1 10 45 120 210 252 210 120 45 10 1
 1 11 55 165 330 462 462 330 165 55 11 1
 1 12 66 220 495 792 924 792 495 220 66 12 1

Das Array B wird hier in jeder Iteration um 1 Element größer. Es dient als temporäres Array, um die jeweils nächste Zeile aus der Vorgängerzeile zu berechnen.

Was genau geschieht bei obiger Zuweisung A = B? Was könnte geschehen? Als erfahrene Programmierer fallen uns sofort zwei Möglichkeiten ein: Die Elemente könnten komponenentweise (d. h. elementweise) von B nach A kopiert werden, oder B und A könnten nun auf dasselbe Objekt, d. h. denselben Speicherbereich „zeigen“. Wie geht LEDA hier vor? Und was erst geschieht, wenn die Arrays komplexere Typen als int speichern? (Wie wir eigene Typen als Parameter von Containern spezifizieren können, werden wir in Abschnitt 2.3.5 sehen.) Werden diese dann bitweise kopiert, oder werden nur Referenzen weitergegeben? Was also geschieht genau? Um diese wichtigen Fragen zu klären, müssen wir uns mit dem Typen- und Kopierkonzept von LEDA auseinandersetzen.

Arrays von LEDA gehören zu den nicht-primitiven Typen, auch strukturierte Typen genannt; s. hierzu auch Abbildung A.1. Das bedeutet, dass sie Ansammlungen von Werten speichern; diese Ansammlungen weisen eine innere Struktur auf. Im Gegensatz dazu speichern primitive Typen, wie z. B. Strings, nur einzelne Werte aus einem bestimmten Wertebereich.^[9] Im Falle von Arrays ist diese innere Struktur einfach die lineare Abfolge der einzelnen Array-Elemente. Genauer gesagt, gehören Arrays zu den nicht-item-basierten strukturierten Typen, auch einfach strukturierte Typen genannt. (Was item-basierte strukturierte Typen sind, werden wir in Abschnitt 2.3.2 am Beispiel des Typs list erfahren.)

Wir hoffen, dass die Verwirrung an dieser Stelle nicht zu groß ist. Wir werden natürlich Beispiele für jeden Unterpunkt dieser Kategorisierung nacheinander kennen lernen. Vorerst müssen wir aber noch eine LEDA-Regel kennen lernen, die uns sagt, was denn nun bei einer Zuweisung A = B wirklich geschieht.

Es handelt sich hierbei um die Regel bzgl. der Kopie eines Wertes. Diese Regel besteht aus drei Teilregeln, die je nach Kategorie des Typs, von dem eine Kopie erzeugt wird, beschreiben, wie die Kopie angelegt wird. Wichtig ist hier zunächst Teil b der Regel, der für einfach-strukturierte Typen gilt. (Wie gerade erwähnt, sind Arrays von einfach strukturiertem Typ.) Dieser Teil b der Regel besagt, dass eine Kopie eines solchen Wertes, der ja eine Menge bzw. Folge darstellt, eine komponentenweise Kopie aller einzelnen Werte dieser Menge bzw. Folge ist.

Die einzelnen Werte des Arrays B sind vom Typ int, der als eingebauter Typ zu den primitiven Typen gezählt wird. Teil a der Regel besagt nun, dass eine Kopie eines solchen primitiven Wertes eine bitweise Kopie dieses Wertes selbst ist (in eine andere Speicherstelle geschrieben), so wie es auch die Sprache C++ vorsieht.

Wenn wir Teil a und b der Regel zusammen auf die Zuweisung A = B anwenden, so sehen wir, dass hier die einzelnen Werte komponentenweise und bitweise kopiert werden. Es ist also nicht so, dass A und B nach der Zuweisung auf denselben physikalischen Speicherbereich zeigen.

Ein Array kann aber auch Zeigertypen wie int* oder andere Typen wie string speichern. Solche Typen zählen gemäß der Regel ebenfalls zu den primitiven Typen. Es wird in diesem Falle also ebenfalls bitweise kopiert.

Es bleibt die Frage, was geschieht, wenn im Array B ein nicht-primitiver Typ gespeichert ist. Was geschieht dann beim Kopieren? Der einzige nicht-primitive Typ, den wir bisher kennen gelernt haben, ist array. Wenn wir nun also ein Array von Arrays, etwa ein array<array<int> >^[10] , kopieren, wie geht LEDA dann vor? In diesem Fall ist die Regel rekursiv anzuwenden: Die Gesamtstruktur wird bitweise kopiert, es werden nirgends Referenzen weitergegeben. Haben wir dagegen ein Array, in dem Werte eines item-basierten, strukturierten Typs wie etwa list gespeichert sind, also etwa ein array<list<int> >, so müssen wir zusätzlich Teil c anwenden; dazu kommen wir aber erst in Abschnitt 2.3.3.

Die Klasse array ist durch C++-Arrays implementiert.

Der Zugriff auf ein Element benötigt konstante Zeit. Die Methode sort() benutzt den Quicksort-Algorithmus zum Sortieren und benötigt bei n Elementen Zeit O(n·log(n)).

Werden in einem Array der Göße n Objekte vom Typ T gespeichert, so ist der Platzbedarf O(n·sizeof(T)).

Mehr über Arrays findet sich auf der entsprechenden Manualseite. Mehr zu den nützlichen Funktionen aus LEDA/misc.h werden wir in Abschnitt 2.11.5 erfahren.