Prozedurale Programmierung - Kapitel 6 - Felder
Inhalte von Dr. E. Nadobnyh
Ein Feld (Array, Vektor) ist eine Zusammenfassung von mehreren Variablen (Feldvariablen, Elementen, Feldelementen, Komponenten, indizierten Variablen) desselben Datentyps unter einem gemeinsamen Namen.
Syntax der Definition des eindimensionalen Feldes: T a[N];
Legende:
T – Datentyp eines Feldelementes,
a - Feldname,
N - Anzahl der Variablen im Feld.
Bei der Definition wird ein zusammenhängender Speicherbereich für das ganze Feld reserviert. Die einzelnen Variablen sind in aufeinanderfolgenden Speicherplätzen abgelegt:
Achtung: Begriffsverwirrung bei Feldvariable vs. Feldname.
Index und indizierte Variable
Eine Variable des Feldes heißt indizierte Variable und hat den zusammengestellten Namen a[i]. Der Name besteht aus dem Feldnamen a und einem Index i.
Ein Index ist ein ganzzahliger Ausdruck. Die Indexgrenzen sind in C/C++ nicht frei wählbar. Die untere Grenze ist 0, die obere Grenze ist N-1.
Analogie: Erdgeschoß.
Ein Zugriff auf eine indizierte Variable erfolgt durch ihren Namen a[i].
Beispiel:
int a[2], b; // Definition
a[1] = 3; // schreibender Zugriff auf Variable a[1]
b = a[1]; // lesender Zugriff auf Variable a[1]
a[1] = 3; // schreibender Zugriff auf Variable a[1]
b = a[1]; // lesender Zugriff auf Variable a[1]
Verwendungszweck von Feldern
Die Arbeit mit einer größeren Anzahl von Variablen ist recht umständlich. Da jede Variable nur unter ihrem Namen angesprochen werden kann, ist es nicht möglich, sie alle in einer Schleife zu durchlaufen.
Diese Mängel lassen sich vermeiden, wenn die Variablen nicht einzeln, sondern gemeinsam als Feld definiert werden.
Die Felder-Verwendung ist flexibel, weil der Index ein beliebiger ganzzahliger Ausdruck sein kann, z.B.:
int a[4], i=1; a[1]=1; a[a[i]+2]=5;
⇒ Demo 1. Zweck
Besonderheiten der Feld-Syntax
1. Eine Feld-Definition hat sehr ähnliche Syntax mit einem Namen der indizierten Variable. Die Bedeutung kann nur durch den Kontext bestimmt werden.
Beispiel: Der Sprachkonstrukt a[n] kann als
a) ein Teil der Definition sein, z.B.:
const int n=4; int a[n]; oder
b) ein Variablenname sein, z.B.:
int n=1; a[n] =2;
2. Die Anzahl der Indizes wird als Dimension bezeichnet. Ein Feld mit einem Index ist eindimensional. Es gibt auch mehrdimensionale Felder.
Initialisierung
Ein Feld kann während der Definition mit Werten initialisiert werden. Eine Initialisierungsliste enthält in geschweiften Klammern mehrere durch Kommas getrennte Werte. Die Zuordnung von Werten erfolgt von links nach rechts.
Beispiel: int a[3] = {11, 22, 33};
Die Initialisierungsliste darf nicht größer sein als die Elementanzahl.
Falls die Liste kleiner als die Elementanzahl ist, werden die übrigen Feldelemente mit dem Wert 0 initialisiert.
Beispiel: int a[3] = {11, 22};
Ohne eine solche Liste werden die Elemente eines lokalen Feldes mit Zufallszahlen initialisiert.
Beispiel: int a[3];
Ein zu initialisierendes Feld kann auch ohne eine Elementanzahl definiert werden. Es enthält dann so viele Elemente, wie Ausdrücke in der Initialisierungsliste angegeben werden, z.B.:
int a[ ] = {11, 22+44, 33};
Es ist wichtig die Initialisierung von der Zuweisung zu unterscheiden:
1) Eine Initialisierung kann nur bei der Felddefinition auftreten.
2) Eine Zuweisung ändert eine schon vorhandene Variable, z.B.:
int a[3]; a[0]=11; a[1]=66; a[2]=33;
6.2. Verwendung von eindimensionalen Felder
Als Beispiele werden drei elementare Sortierverfahren behandelt:
1) Selectionsort (Sortieren durch Auswahl),
2) Insertionsort (Sortieren durch direktes Einfügen),
3) Bubblesort (Sortieren durch direktes Austauschen).
Selectionsort
Algorithmus für aufsteigendes Sortieren:
1. Teile ganzes Feld in zwei Feldteile:
- sortierten linken Feldteil (ursprünglich ist leer),
- unsortierten rechten Feldteil.
2. Finde das Minimum in unsortiertem Feldteil.
3. Tausche das Minimum gegen erstes Element in unsortiertem Feldteil.
Es gibt auch andere Variante des Verfahrens:
a) absteigendes Sortieren,
b) mit dem sortierten rechten Feldteil.
⇒ Demo 2. Select
Insertionsort
Algorithmus für aufsteigendes Sortieren:
1. Teile ganzes Feld in zwei Feldteile:
- sortierten linken Feldteil (ursprünglich ist leer) und
- unsortierten rechten Feldteil.
2. Rette erstes Element des unsortierten Feldteiles „e“.
3. Schiebe nach rechts alle große Elemente (größer als „e“) den sortierten Feldteil.
4. Schreibe gerettetes Element „e“ in die Lücke zwischen zwei sortierten Feldteilen.
⇒ Demo 3. Insert
Bubblesort
Algorithmus für aufsteigendes Sortieren:
1. Wandere das Feld von links nach rechts durch.
2. Tausche jedes Element mit seinem Nachbar, wenn die in falscher Reihenfolge stehen.
3. Widerhole dies so lange, bis das Feld sortiert ist.
Nach dem 1.Durchgang ist das größte Element an seiner endgültigen Position. Sortierter Feldteil ist rechts.
Analogie: Das Wandern des größten Elementes kann mit dem Aufsteigen von Luftblasen in einem Aquarium vergleichen.
Es gibt auch andere Variante des Verfahrens:
- absteigendes Sortieren,
- von rechts nach links durchwandern.
⇒ Demo 4. Bubble
6.3. Eindimensionale Felder. Details
Der Feldname ist keine Variable. Er stellt nicht das Feld als Ganzes dar, sondern nur die die Adresse des ersten Elements.
Nach dem Compilieren wird der Feldname durch die Adresse des ersten Elements ersetzt.
Beispiel:
int a[2]; cout<< a; //0x23ff48
Bei der Ausgabe der Adresse ist kein Adressoperator notwendig.
Es gibt keine Operatoren zur Verarbeitung eines ganzen Feldes. Deshalb kann ein Feld einem anderem nicht zugewiesen werden.
Beispiel:
int a[2], b[2];
a=b; //Fehler: L-Wert erwartet Hier links steht ein Adress-Literal.
Um ein ganzes Feld zu kopieren, müssen alle Elemente einzeln kopiert werden, z.B.:
for (int i=0; i<2; i++) a[i] = b[i];
Felder
Index-Kontrolle - Es gibt keine Index-Kontrolle in C.
Wenn dabei für ein mit N Elementen definiertes Feld ein Index angegeben wird, der nicht im Bereich der Grenzen 0..N–1 liegt, werden Speicherbereiche angesprochen, die nicht für das Feld reserviert sind.
6.4. Zeichenketten
Zeichenketten (Zeichenfolgen, C-Strings, C-Zeichenketten) sind eindimensionale Felder mit mehreren Besonderheiten.
1. Sie sind spezielle char-Felder. Der Datentyp eines Elementes ist char.
2. Als Zeichenkette müssen sie mit dem Symbol '\0' abgeschlossen sein.
3. Es gibt spezielle Zeichenkettenliterale (Stringliterale, Zeichenfolgenliterale).
Ein Zeichenkettenliteral entsteht aus der Zeichenfolge, indem man diese in Anführungszeichen einschließt. Das Zeichenkettenliteral "x" unterscheidet sich von dem Zeichenliteral 'x'.
- “x“ besteht aus zwei Zeichen: 'x' und '\0',
- 'x' definiert ein einzelnes Zeichen.
Initialisierung
Eine Initialisierung der Zeichenkette kann mit dem Zeichenkettenliteral oder mit der Initialisierungsliste stattfinden:
- char a[] = „abc“;
- char a[] = {‘a‘, ‘b‘, ‘c‘, ‘\0‘};
Diese Initialisierungen sind äquivalent.
Ein char-Feld, die eine Zeichenkette aufnehmen soll, muß wenigstens um eine Komponente länger sein, als die Zeichenkette lang ist.
- char a[3] = „abc“; //ohne ‘\0‘ gespeichert
- char b[4] = „abc“; //mit ‘\0‘ gespeichert
Zeichenkettenbearbeitung
In C selbst sind keine weiteren Sprachelemente zur Manipulation von Zeichenketten enthalten. Es existieren aber in der C-Standard-Bibliothek eine Reihe von Funktionen zur Zeichenkettenbearbeitung, z.B.:
strcat() Konkatenation zweier C-Strings,
strcmp() Vergleich zweier C-Strings,
strcpy() Kopieren eines C-Strings,
strlen() Ermittlung der Länge eines C-Strings.
Die entsprechenden Funktions-Deklarationen befinden ich in der Standard-Header-Datei <string.h>.
C-Zeichenketten kopieren
Wie andere char-Felder müssen die C-Zeichenketten elementweise kopiert werden. Die Funktion strcpy kopiert alle Bytes bis einschließlich des Nullbytes.
Beispiel:
char from[6] = „qwert“;
char to[10]; //to muss gross genug sein
//1.Variante: Schleife verwenden
int i=0;
while(from[i] != ‘\0‘) { to[i] = from[i]; i++; }
to[i]= ‘\0‘;
//2.Variante: Standard-Funktion verwenden
strcpy(to, from);
char to[10]; //to muss gross genug sein
//1.Variante: Schleife verwenden
int i=0;
while(from[i] != ‘\0‘) { to[i] = from[i]; i++; }
to[i]= ‘\0‘;
//2.Variante: Standard-Funktion verwenden
strcpy(to, from);
Strings in C++
Die C-Zeichenketten sind nicht mit den Strings (C++) zu verwechseln. Strings sind Objekte der Klasse string der C++Standardbibliothek. Standard-Header-Datei <string>. Strings sind verständlicher und komfortabler in der Anwendung. Beispielweise kann das Kopieren als eine Zuweisung programmiert werden:
#include <string.h>
#include <iostream> //enthält <string>
using namespace std;
int main()
{ char a[4]="abc", b[4];
strcpy (b, a); //<string.h>
string c("qwert"), d; //<string>
d=c; return 0;
}
#include <iostream> //enthält <string>
using namespace std;
int main()
{ char a[4]="abc", b[4];
strcpy (b, a); //<string.h>
string c("qwert"), d; //<string>
d=c; return 0;
}
6.5. Zweidimensionale Felder
1) Syntax der Definition eines zweidimensionalen Feldes:
Typ Feldname[N][M];
Ein zweidimensionales Feld kann als Tabelle oder Matrix dargestellt werden. Die linke Dimension N ist die Anzahl von Zeilen, M ist die Anzahl von Spalten.
Beispiel: int a[3][4];
| a[0][0] | a[0][1] | a[0][2] | a[0][3] |
| a[1][0] | a[1][1] | a[1][2] | a[1][3] |
| a[2][0] | a[2][1] | a[2][2] | a[2][3] |
2) Ein Zugriff auf eine indizierte Variable folgt durch ihren Name: Feldname[Index][Index].
Beispiel für den schreibenden Zugriff: a[2][1] = 5;
3) Durch die Verwendung zweidimensionaler Felder können viele mathematische Aufgaben bequemer programmiert werden.
Initialisierung
1.Eine Initialisierungsliste enthält in geschweiften Klammern mehrere Initialisierungslisten für die zweite Dimension durch Kommas getrennt, z.B.:
int a[2][3] = { {11, 22, 33},
{44, 55, 66} };
3. Falls die Liste kleiner als die Elementanzahl ist, werden die übrigen Feldelemente mit dem Wert 0 initialisiert, wenn sie einen fundamentalen Datentyp haben, z.B.:
int a[2][3] = { {11, 22}, // Die letzte Spalte wird
{44, 55} }; // mit 0 initialisiert.
int a[ ][3] = { {11, 22},
{44, 55} };
Beispiel. Matrixmultiplikation
Zwei Matrizen a[N][M] und b[M][N] werden multipliziert, indem die Produktsummenformel auf alle Paare aus einem Zeilenvektor
der ersten und einem Spaltenvektor der zweiten Matrix angewandt wird. Das Ergebnis ist die Matrix c[N][N].
Produktsummenformel
Programm:
const int N=2, M=3;
int a[N][M], b[M][N], c[N][N];
for (int i=0; i<N; i++)
{ for (int j=0; j<N; j++)
{ c[i][j] = 0;
for (int k=0; k<M; k++)
c[i][j] += a[i][k]*b[k][j];
}
}
int a[N][M], b[M][N], c[N][N];
for (int i=0; i<N; i++)
{ for (int j=0; j<N; j++)
{ c[i][j] = 0;
for (int k=0; k<M; k++)
c[i][j] += a[i][k]*b[k][j];
}
}
Feld von Feldern
1. Mehrdimensionale Felder werden als Feld von Feldern eingebaut und eindimensional gespeichert.
2. Ein zweidimensionales Feld a[N][M] ist ein eindimen-sionales Feld mit N Elementen (Zeilen), die selbst eindimensionale Felder mit M Elementen (Spalten) sind. Die Speicherung erfolgt immer so, daß sich der letzte Index am häufigsten ändert.
3. Mehrdimensionale Felder können wie eindimensionale initialisiert werden. Diese Initialisierungen sind äquivalent:
int a[2][3] = { {11, 22, 33}, {44, 55, 66} };
int a[2][3] = {11, 22, 33, 44, 55, 66};
Zweidimensionale Felder. Speicherabbildung
Beispiel: int matrix [2][3];
matrix [1][1] = 5;
CategoryProzeduraleProgrammierung
