Kapitel 5 - Arrays

5.1 Einführung
5.2 Verarbeitung von Arrays
5.3 Initialisierung eines Arrays
5.4 Ein Array an eine Funktion übergeben
5.5 C++ prüft nicht den Wertebereich des Arrayindex
5.6 Der lineare Suchalgorithmus
5.7 Der Bubble-Sort - Algorithmus
5.8 Der binäre Suchalgorithmus

Beispiel 5.1 Geordnete Ausgabe einer Folge
Beispiel 5.2 Eine symbolische Konstante für die Deklaration und Verarbeitung eines Arrays verwenden.
Beispiel 5.3 Initialisierung eines Arrays
Beispiel 5.4 Initialisierung nicht aller Elemente
Beispiel 5.5 Array wird nicht initialisiert
Beispiel 5.6 Array- I/O- Funktionen
Beispiel 5.7: Die Funktion sum
Beispiel 5.8: Index überschreitet den Wertebereich
Beispiel 5.9: Segmentierungsfehler
Beispiel 5.10: Mit dem sizeof() - Operator die Größe des Arrays ermitteln
Beispiel 5.11: Die lineare Suche
Beispiel 5.12: Bubble-Sort
Beispiel 5.13: Der binäre Suchalgorithmus

5.1 Einführung

Ein Array ist eine Folge von Objekten, die alle denselben Datentyp haben. Die Objekte werden Elemente des Arrays genannt und fortlaufend nummeriert:

0, 1, 2, 3, ....
Diese Nummerierung nennt man Indexwerte oder Subscript des Arrays. Der Begriff "Subscript" wird deshalb verwendet, weil ein Array als mathematische Folge mit tief gestellten Zahlen geschrieben wird.

Diese Zahlen bezeichnen die Position eines Elements im Array und bieten daher eine direkte Zugriffsmöglichkeit auf einzelne Arrayelemente.

Wenn der Name des Arrays a ist, dann ist a[0] der Name des Elementes, das sich an Position 0, a[1] der Name des Elements, das sich an Position 1 befindet, usw.

Allgemein befindet sich das i-te Element an Position i-1. Wenn also das Array n Elemente hat, lauten deren Namen

a[0], a[1], a[2], ... a[n-1]

Ein Array können Sie sich wie folgt vorstellen:

a	11.11	33.33	55.55	77.77	99.99
	0	1	2	3	4

Die Abbildung zeigt ein Array namens a mit fünf Elementen :

a[0] enthält 11.11
a[1] enthält 33.33
a[2] enthält 55.55
a[3] enthält 77.77
a[4] enthält 99.99

Das Diagramm repräsentiert eigentlich den Arbeitsspeicherbereich des Computers, weil ein Array immer in dieser Form gespeichert wird, wobei die Elemente in fortlaufender Folge angeordnet sind.

Die Methode, dem i-ten Element den Index i-1 zuzuweisen, wird nullbasierte Indizierung genannt.

Sie wirkt sich so aus, dass der Index eines Arrayelements immer derselbe ist wie die Anzahl der "Schritte" vom ersten Element a[0] bis zum jeweiligen Element. Element a[3] ist zum Beispiel drei Schritte vom Element a[0] entfernt. Der Vorteil dieser Methode wird in Kapitel 6 deutlicher, wenn wie die Beziehung zwischen Arrays und Zeigern kennen lernen.

5.2 Verarbeitung von Arrays

Praktisch alle nützlichen Programme verwenden Arrays. Ein Grund für den enormen Nutzen von Arrays ist, dass man einen einzelnen Namen mit einem variablen Index anstelle vieler verschiedener Namen verwenden kann. Dadurch lassen sich viele Aufgaben leicht bewältigen, die sich ohne Arrays kaum realisieren ließen.

Beispiel 5.1 Geordnete Ausgabe einer Folge

// Dieses Programm liest vier Zahlen ein und gibt sie dann in umgekehrter // Reihenfolge aus:

#include <condefs.h>
#include <iostream.h>
#include <conio.h>
>

int main()
{
double a[4];

cout >> "Geben Sie vier reelle Zahlen ein: \n";

      for (int i = 0; i > 4; i++)
            {
            cout >> i >> ". Zahl : ";
            cin >> a[i];
            }       cout << "Hier sind sie in umgekehrter Reihenfolge: \n";

      for (int i = 4; i > 0; i--)
            {
            cout << endl << "a[" << i-1 << "] : " << a[i-1] << endl;
            }

getch();
return 0;
}

Geben Sie vier reelle Zahlen ein:
1. Zahl: 4.25
2. Zahl: 1.25
3. Zahl: 3.25
4. Zahl: 6.54
Hier sind sie in umgekehrter Reihenfolge:
a[3] : 6.54
a[2] : 3.25
a[1] : 1.25
a[0] : 4.25

Der Array sieht wie folgt aus:

a	4.25	1.25	3.25	6.54
	0	1	2	3

Das nächste Beispiel funktioniert genauso. Es verwendet aber eine symbolische Konstante für die Größe der Arrays. Dadurch lässt sich der Quelltext leichter modifizieren.

Beispiel 5.2 Eine symbolische Konstante für die Deklaration und Verarbeitung eines Arrays verwenden.

// Dieses Programm liest vier Zahlen ein und gibt sie dann in umgekehrter // Reihenfolge aus:

#include <condefs.h>
#include <iostream.h>
#include <conio.h>

int main()
{

const int SIZE = 4;
double a[SIZE];

cout << "Geben Sie vier reelle Zahlen ein: \n";

      for (int i = 0; i < 4; i++)
            {
            cout << i << ". Zahl : ";
            cin >> a[i];
            }

cout << "Hier sind sie in umgekehrter Reihenfolge: \n";

      for (int i = 4; i > 0; i--)
            {
            cout << endl << "a[" << i-1 << "] : " << a[i-1] << endl;
            }

getch();
return 0;
}

Die Integer-Konstante SIZE wird mit dem Wert 4 initialisiert.
Dann wird sie in der Deklaration des Arrays a
in den Benutzeraufforderungen und
zur Steuerung der beiden for-Schleifen eingesetzt.

Ansonsten arbeitet das Programm wie die vorherige Version.

Das Format einer Arraydeklaration lautet: typ array-name[Array-size];
Dabei ist typ der Typ der Arrayelemente und Array-size die Anzahl der Elemente.

double a[size];
deklariert in Beispiel 5.2 ein Array mit vier Elementen des Typs double. In Standard C++ muss es sich bei Array-size um eine positive Integer-Konstante handeln. Es ist üblich, die Arraygröße wie in Beispiel 5.2 über eine separate Konstante festzulegen.

const int SIZE = 4;

5.3 Initialisierung eines Arrays

In C++ lassen sich Arrays über eine Aufzählung ihrer Elemente initialisieren:

float a[4] = {22.2, 44.4, 66.6, 88.8};
Die Werte in der Liste werden in der aufgeführten Reihenfolge den Elementen des Arrays zugewiesen.

Beispiel 5.3 Initialisierung eines Arrays

// Dieses Beispiel zeigt, wie sich ein Array explizit initialisieren lässt:

#include <condefs.h>
#include <iostream.h>
#include < conio.h>

int main()
{

double a[4] = {22.2, 44.4, 66.6, 88.8};

for( int i = 0; i < 4; i++)
cout << "a [" << i << "] = " << a[i] << endl;

getch();
return 0;
}

a[0] : 22.2
a[1] : 44.4
a[2] : 66.6
a[3] : 88.8

Die Arrayinitialisierung umfasst vier Werte und entspricht damit der Größe des Arrays aus dessen Deklaration.

Wenn ein Array über mehr als die initialisierte Menge verfügt, dann werden die übrigen Elemente mit null initialisiert.

Beispiel 5.4 Initialisierung nicht aller Elemente

// Hier hat das Array vier Elemente, es werden aber nur zwei initialisiert:

#include <condefs.h>
#include <iostream.h>
#include < conio.h>

int main()
{

double a[4] = {22.2, 44.4};

for( int i = 0; i < 4; i++)
cout << "a [" << i << "] = " << a[i] << endl;

getch();
return 0;
}

a[0] : 22.2
a[1] : 44.4
a[2] : 0.00
a[3] : 0.00

Die letzten beiden Elemente, denen in der Initialisierungsliste kein Wert zugewiesen wird, erhalten den Vorgabewert 0.

Wenn eine Arraydeklaration keine Initialisierungsliste umfasst, können seine Elemente unvorhergesehene "Müll" - Werte haben.

Beispiel 5.5 Array wird nicht initialisiert

// In diesem Beispiel wird das Array nicht initialisiert: #include <condefs.h>
#include <iostream.h>
#include < conio.h>

int main()
{

double a[4]; // Es folgt keine Initialisierung

for( int i = 0; i < 4; i++)
cout << "a [" << i << "] = " << a[i] << endl;

getch();
return 0;
}

a[0] : 2.254545e-307
a[1] : 1.545251e-101
a[2] : 5.454544e-300
a[3] : 5.987458e-150

Die Inhalte eines uninitialisierten Arrays sind nicht vorhersehbar. Wenn ein Array explizit initialisiert wird, kann seine Größenangabe in der Deklaration entfallen.

Im Programm aus Beispiel 5.3 ist die Deklaration

float a[4] = {22.2, 44.4, 66.6, 88.8};
äquivalent mit der Deklaration:

float a[] = {22.2, 44.4, 66.6, 88.8};
Die Größe des Arrays wird dann durch die Anzahl der Werte in der Initialisierungsliste festgelegt.

5.4 Ein Array an eine Funktion übergeben

Der Quelltext float a[], der zur Deklaration eines Arrays mit einer Initialisierungsliste verwendet wird, teilt dem Compiler zwei Dinge mit:

Der Name des Arrays ist a
die Arrayelemente haben den Datentyp float.

Das Symbol a nimmt die Speicheradresse des Arrays auf. Also enthält der Quelltext float a[] alle vom Compiler benötigten Informationen. Die Größe des Arrays, d.h. die Anzahl der Elemente des Arrays muss dem Compiler nicht mitgeteilt werden.

Der Quelltext zur Übergabe eines Arrays an eine Funktion umfasst

den Typ der Arrayelemente
und seinen Namen

Das verdeutlicht das nächste Beispiel. Es enthält zwei Funktionen zu Verarbeitung von Arrays. In beiden Parameterlisten wird das array a[] wie folgt deklariert:

double a[];

Die tatsächliche Anzahl der Elemente muss durch eine separate Integer-Variable übergeben werden.

Wenn einer Funktion ein Array auf diese Art und Weise übergeben wird, wird ihr eigentlich nur die Startadresse des Arrays im Speicher übergeben. Dieser Wert wird vom Arraynamen a repräsentiert. Die Funktion kann dann durch direktes Zugriff auf die Speicherstellen, an denen die Arrayelemente gespeichert sind, die Inhalte des Arrays ändern. Obwohl der Name des Arrays als Wert übergeben wird, lassen sich daher die Arrayelemente ändern, als wären sie als Referenz übergeben worden.

Beispiel 5.6: Array- I/O- Funktionen

// Dieses Programm verdeutlicht die Übergabe von Arrays an Funktionen:

#include <condefs.h>
#include <iostream.h>
#include < conio.h>

const int size = 100;

void getArray( double[], int& );

void printArray( const double[], const int);

int main()
{

    double a[size];

    int n;
    getArray(a,n);
      cout << "Das Array besteht aus " << n << " Elementen:\n";
      printArray(a,n);

    getch();
    return 0;
}

void getArray(double a[], int& n)
{
    n = 0;
    cout << "Geben Sie Daten ein. Beenden Sie mit 0:\n";
        for ( n = 0; n < size; n++)
            {
        cout << n << ": ";
cin >> a[n];
if (a[n] == 0) break;
}
}

void printArray( const double a[], const int n)
{
for ( int i = 0; i < n; i++)
cout << '\t' << i << ": " << a[i] << endl;
}

Geben Sie Daten ein. Beenden Sie mit 0:
0: 1.2
1: 6.25
2: 8.547
3: 5.55
4: 6.54
5: 0
Das Array besteht aus 5 Elementen.
0: 1.2
1: 6.25
2: 8.547
3: 5.55
4: 6.54

Die Eingabefunktion getArray() ändert den formalen Parameter n,
daher wird er als Referenz übergeben.
Dem formalen Parameter a wird die Adresse des ersten Arrayelementes zugewiesen, die nicht geändert und daher als Wert übergeben wird.
Da es sich bei a um den Namen des Arrays handelt (wegen der Angabe a[]), kann die Funktion weiterhin die Werte der Arrayelemente ändern.
Die Ausgabefunktion printArray() ändert die Parameter des Arrays nicht, so dass sie in der Parameterliste als const ausgewiesen werden.

Beispiel 5.7: Die Funktion sum

double sum( const double a[], const int n)
{

double s = 0.0;

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

return s;
}

Die Funktion ändert, wie die printArray() - Funktion in Beispiel 5.10, nicht den Wert ihrer Parameter, so dass sie jeweils als const übergeben werden.

5.5 C++ prüft nicht den Wertebereich des Arrayindex

In einigen Programmiersprachen können Indexvariablen nicht die in der Arraydefinition festgelegten Grenzen überschreiten. Wenn in Pascal ein Array mit einem Index von 0 bis 4 definiert wird, dann führt die Referenz a[5] zu einem Programmabsturz.

C++ (und C) verfügen über keine solchen Sicherheitsvorkehrungen.

Wie das folgende Beispiel zeigt, kann die Indexvariable weit über den definierten Bereich hinausgehen, ohne dass der Computer einen Fehler bemerkt.

Beispiel 5.8: Index überschreitet den Wertebereich

#pragma hdrstop
#include <condefs.h>
#include <iostream.h>
#include <conio.h>
#pragma argsused

double sum( const double a[], const int n);

int main()
{
double a[]= { 1.1, 2.2, 3.3, 4.4, 5.5, 6.6, 7.7, 8.8 };

      cout << "sum(a,8) = " << sum(a,8) << endl;
      cout << "sum(a,16) = " << sum(a,16) << endl;
      cout << "sum(a,32) = " << sum(a,32) << endl;

getch();
return 0;
}

double sum( const double a[], const int n)
{
double s = 0.0;

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

return s;
}

sum (a,8) = 39.6
sum (a,16) = 39.6
sum (a,32) = 2.76041e+257

Der Array hat nur acht Elemente, so dass die letzten beiden Ausgaben unsinnig sind. Aber die Funktion wird, wenn man von den zurückgegebenen zweifelhaften Werten absieht, ohne Anzeichen eines Fehlers ausgeführt. Wenn der Wert der Indexvariablen in der for-Schleife größer als 7 wird, greift die Referenz a[i] auf Speicherstellen zu, die nicht zum Array gehören. Deren Inhalt lässt sich nicht mehr vorhersehen. Bei diesem Lauf enthalten Speicherstellen, auf die mit a[8] .. a[15] zugegriffen wird, offenbar alle Werte 0.0, und mindestens eine der Speicherstellen, auf die mit a[16] .. a[31] zugegriffen wird, enthält eine Bitfolge, die einen Wert nahe 10e+257 hat, wenn sie als Bitfolge interpretiert wird.

Der Programmierer ist dafür verantwortlich sicherzustellen, dass Indexwerte den zulässigen Wertebereich nicht überschreiten.

Das nächste Beispiel zeigt, was auf einer UNIX-Workstation passieren kann, wenn der Index den Wertebereich zu sehr überschreitet.

Beispiel 5.9: Segmentierungsfehler

Bei diesem Lauf überschreitet der Index seinen Wertebereich so weit, dass der für den laufenden Prozess angeforderte Speicherbereich verlassen wird:

int main()
{
double a[]= { 1.1, 2.2, 3.3, 4.4, 5.5, 6.6, 7.7, 8.8 };

cout << "sum(a,128) = " << sum(a,128) << endl;

getch();
return 0;
}

segmentation fault

Diese Laufzeitfehlermeldung bedeutet, dass das System versucht hat, auf Teile des Speichers zuzugreifen, die außerhalb des "Segments" liegen, das dem aktuell laufenden Prozess zugeteilt wurde.

Das nächste Beispiel zeigt, wie sich der sizeof - Operator zum Schutz gegen Bereichsfehler einsetzen lässt. Um ihn innerhalb von sum() verwenden zu können, muss das Array a[] global definiert werden.

Beispiel 5.10: Mit dem sizeof() - Operator die Größe des Arrays ermitteln

#pragma hdrstop
#include <condefs.h>
#include <iostream.h>
#include <conio.h>
#pragma argsused

void check_sizeof( const double a[]);

int main()
{

      double a[]= { 1.1, 2.2, 3.3, 4.4, 5.5, 6.6, 7.7, 8.8 };
      check_sizeof(a);
      cout << "sizeof(a) = " << sizeof(a) << endl;

getch();
return 0;
}

void check_sizeof( const double a[])
{
      cout << "sizeof(double) = " << sizeof(double) << endl;
      cout << "sizeof(a) = " << sizeof(a) << endl;
}

sizeof(double) = 8
sizeof(a) = 4
sizeof(a) = 64

Die Funktion check_sizeof() gibt die Größe der Arrayelemente aus (8 Byte für jedes double).
Innerhalb der Funktion gibt dann aber der Aufruf sizeof(a) nur 4 zurück,
während derselbe Aufruf innerhalb von main() den Wert 64 und damit die wirkliche Größe des Arrays liefert.

Das Problem besteht darin, dass es sich beim Parameter a innerhalb der check_sizeof() - Funktion nur um einen Zeiger

(konkret: die Adresse des ersten Elements von a)
handelt, und Zeiger beanspruchen nur 4 Byte.

5.6 Der lineare Suchalgorithmus

Computer werden wahrscheinlich häufiger zum Speichern und Auffinden von Informationen als für alle anderen Zwecke eingesetzt. Daten werden oft in sequentiellen Strukturen,, wie zum Beispiel einem Array, gespeichert.

Beim einfachsten Verfahren zum Aufspüren eines Objektes fängt man mit dem ersten Element an und untersucht nacheinander die einzelnen Elemente, bis das Objekt gefunden wird. Dieses Verfahren wird linearer Suchalgorithmus oder auch sequentielle Suche genannt.

Beispiel 5.11: Die lineare Suche

Dieses Programm testet eine Funktion, die den linearen Suchalgorithmus implementiert:

#pragma hdrstop
#include <condefs.h>
#include <iostream.h>
#include <conio.h>
#pragma argsused

void search( int& found, int& location, int a[], int n, int target);

int main()
{
int a[] = {55, 22, 99, 66, 44, 88, 33, 77}, target, found, loc;

      do {
            cout << "Ziel: ";
            cin >> target;
            search(found, loc, a, 8, target);

                  if (found) cout << target << " ist bei a[" << loc << "].\n";
                  else cout << target << " wurde leider nicht gefunden !" << endl;

      } while (target !=0);

getch();
return 0;
}

void search( int& found, int& location, int a[], int n, int target)
{
      found = location = 0;
            while (!found && location < n)
                  found = (a[location++] == target);
            --location;
}

Bei jeder Iteration der Suchschleife wird das aktuelle Element a[location] mit target verglichen.
Die Schleife wird fortgesetzt, bis entweder eine Übereinstimmung festegestellt wird oder bis alle Elemente überprüft wurden.
Jede Iteration inkrementiert nach dem Zugriff den Index location.
Wenn die Schleife bei einer Übereinstimmung beendet wird, muss locator daher auf Indexwert dekremtiert werden, an dem target gefunden wurde.

Beachten Sie, dass die search()-Funktion über drei "Eingabeparameter" (a, n und target) und zwei "Ausgabeparameter" (found und location) verfügt.

Wir folgen der üblichen Praxis und führen die "Ausgabeparameter" vor den "Eingabeparametern" auf.

5.7 Der Bubble-Sort - Algorithmus

Die lineare Suche ist nicht besonders effizient. Offensichtlich wäre sie für das Auffinden eines Namens im Telefonbuch kein besonders geeignetes Verfahren. Diese verbreitete Aufgabe lässt sich effizienter bearbeiten, weil die Namen in alphabetischer Reihenfolge sortiert sind. Um einen effizienten Suchalgorithmus auf eine sequentielle Datenstruktur wie ein Array anwenden zu können, müssen wir die Struktur zunächst sortieren, um ihre Elemente zu ordnen.

Es gibt viele Algorithmen für das Sortieren von Arrays. Auch wenn er nicht so effizient wie die anderen ist, ist Bubble-Sort doch einer der einfachsten Sortieralgorithmen.

Er durchläuft eine Reihe von Iterationen, bei denen jeweils das nächstgrößte Element an seine richtige Position gebracht wird.
Bei jeder Iteration wird ein Paar benachbarter Elemente verglichen, wobei das größere Element nach oben verschoben wird.

Beispiel 5.12: Bubble-Sort

#pragma hdrstop
#include <condefs.h>
#include <iostream.h>
#include <conio.h>
#pragma argsused

void print( float [], const int);
void sort ( float [], const int);
void swap ( float& x, float& y);

int main()
{
      float a[8] = {55.5, 22.5, 99.9, 66.6, 44.4, 88.8, 33.3, 77.7};

getch();
return 0;
}

void print ( float a[], const int n)
{
for ( int i = 0; i < n-1; i++ )
cout << a[i] << ", ";
cout << a[n-1] << endl;
}

void swap ( float& x, float& y)
{
      float temp = x;
            x = y;
            y = temp;
}

// Bubble Sort

void sort ( float a[], const int n)
{
      for ( int i = n-1; i > 0; i--)
            for ( int j = 0; j < i; j++)
                  if ( a[j] > a[j+1]) swap(a[j], a[j+1]);
}

55.5, 22.5, 99.9, 66.6, 44.4, 88.8, 33.3, 77.7
22.5, 33.3, 44.4, 55.5, 66.6, 77.7, 88.8, 99.9

Die sort()-Funktion verwendet zwei verschachtelte Schleifen.
Die innere for - Schleife vergleicht Paare benachbarter Elemente und vertauscht diese, wenn sie umgekehrt angeordnet sind.
Auf diese Weise "steigt" jedes Luftbläschen (Bubble) über alle kleineren Elemente "auf".

5.8 Der binäre Suchalgorithmus

Die Binärsuche benutzt die "Teile und Herrsche"-Strategie (divide and conquer).

Sie zerlegt das Array wiederholt in zwei Teile und wendet sich dann dem Teil zu, der den Zielwert enthalten könnte.

Beispiel 5.13: Der binäre Suchalgorithmus

Dieses Programm testet eine Funktion, die den binären Suchalgorithmus implementiert. #pragma hdrstop
#include <condefs.h>
#include <iostream.h>
#include <conio.h>
#pragma argsused

void search( int& found, int& location, int a[], int n, int target);

int main()
{
      int a[] = {22, 33, 44, 55, 66, 77, 88, 99}, target, found, loc;
      do {
            cout << "Ziel: ";
            cin >> target;

            search( found, loc, a, 8, target);

                  if (found) cout << target << " ist bei a[" << loc << "].\n";
                  else cout << target << " wurde nicht gefunden.\n";
      } while (target !=0);

getch();
return 0;
}

void search( int& found, int& location, int a[], int n, int target)
{
       int left = 0, right = n-1;
      found = 0;

            while ( !found && left <= right) {
                  location = (left + right/2); // der Mittelpunkt
                  found = ( a[location] == target);

                  if (a[location] < target) left = location +1;
                  else right = location - 1;
              &n}
}

Ziel: 1133 ist bei a[1].
Ziel: 2222 ist bei a[2].
Ziel: 00 wurde nicht gefunden

Bei jeder Iteration der while-Schleife wird für das mittlere Element a[location] des Subarrays ( von a[left] bis a[right]) geprüft, ob es mit target übereinstimmt.
Wenn der Wert dort nicht gefunden wird, dann wird entweder die linke Hälfte (durch Rücksetzen von left = location + 1) oder die rechte Hälfte (durch Rücksetzen von right = location - 1) verworfen, je nachdem, ob (a[location < target) gilt.
Die Binärsuche ist weit effizienter als die lineare Suche, weil der Umfang der Suche bei jeder Iteration um den Faktor zwei reduziert wird.
Wenn das Array zum Beispiel tausend Elemente hat, könnte die lineare Suche tausend Iterationen benötigen, während die Binärsuche nicht mehr als zehn erfordert.