Zeiger und Felder, dynamische Speiche

Grundlagen der Programmiersprache C für
Studierende der Naturwissenschaften
Teil 5: Zeiger und Felder, dynamische Speicherverwaltung
Patrick Schön
Abteilung für Angewandte Mathematik
Vorlesung vom 18. Mai 2015
Wiederholung Teil 4 – Funktionen
Funktionen sind Unterprogramme, die einzelne, abgegrenzte
Aufgaben erfüllen. C-Programme bestehen in der Regel aus einer
Vielzahl von relativ kleinen Funktionen.
Bei Funktionen werden unterschieden:
Deklaration vereinbart lediglich Rückgabetyp, Namen und die
Parameterliste einer Funktion,
Definition legt die Anweisungen fest, die bei Funktionsaufruf
ausgeführt werden.
Bevor eine Funktion das erste Mal verwendet werden darf, muss sie
vereinbart werden. Dies geschieht entweder durch eine Deklaration
oder eine Definition.
Wiederholung Teil 4 – Call by value
Parameter werden stets in Kopie an eine Funktion übergeben.
Zuweisungen an Parameter innerhalb einer Funktion haben keine
Auswirkung auf die übergebenen Variablen!
Beispiel:
void swap(int a, int b)
{
int c = a;
a = b;
b = c;
}
/* wrong */
int main(void)
{
int a = 1, b = 2;
swap(a, b); /* a, b unchanged */
return 0;
}
Gliederung
Ein sequentielles Speichermodell
Felder
Zeiger
Dynamische Speicherverwaltung
Zeiger, Felder und Adressarithmetik∗
Gliederung
Ein sequentielles Speichermodell
Felder
Zeiger
Dynamische Speicherverwaltung
Zeiger, Felder und Adressarithmetik∗
Größe von Variablen
Wir wissen, dass in Variablen Werte abgespeichert werden können:
int a = 1;
double x = 2.;
Mit dem sizeof-Operator können wir die Speichergröße in Byte
eines Typs oder eines Objekts ermitteln:
sizeof(int)
sizeof(x)
/* size is 4 byte */
/* size is 8 byte */
Ein vereinfachtes Speichermodell
Vereinfachend stellen wir uns die Speicherorganisation eines
Rechners wie folgt vor:
I
Der Speicher besteht aus einer zusammenhängenden Reihe von
Bytes, die fortlaufend nummeriert sind:
a
120
a
121
122
123
124
I
Die Nummer einer Speicherzelle nennen wir ihre Adresse. Über
ihre Adresse lässt sich jede Speicherzelle eindeutig identifizieren
und anspringen.
I
Jedes Speicherobjekt in C (z. B. Variablen, Funktionen) belegt
Platz im Speicher. Damit hat jedes Objekt auch eine Adresse.
Gliederung
Ein sequentielles Speichermodell
Felder
Zeiger
Dynamische Speicherverwaltung
Zeiger, Felder und Adressarithmetik∗
Felder
Für jeden Datentyp in C kann ein Feld angelegt werden, man spricht
auch von einem abgeleiteten Typ.
Ein Feld (engl. array) besteht aus einer festen Anzahl von Elementen
gleichen Typs, die konsekutiv im Speicher liegen:
a[0] a[1] a[2]
120
124
128
132
136
Die Feldelemente werden unter dem gemeinsamen Namen des Felds
und ihrer Position innerhalb des Felds angesprochen.
Definition von Feldern
Syntax:
typename identifier[const_integer];
→ Die strikt positive Integer-Konstante const_integer gibt die
Länge des Feldes an.
→ Das Feld besteht aus einer Folge von Feldelementen, die alle
vom Typ typename sind.
Beispiele:
int a[3];
double x[5];
/* integer array of size 3 */
/* double array of size 5 */
Initialisierung von Feldern
Mit der Definition kann ein Feld durch Angabe einiger oder aller
Elemente initialisiert werden:
int a[3] = {0, 1, 2};
double x[5] = {3, 2};
Im zweiten Fall werden nur die ersten beiden Elemente des Feldes
mit den angegebenen Werten belegt.
Auf die Angabe der Feldlänge kann verzichtet werden, wenn
sämtliche Feldelemente angegeben werden:
int a[] = {0, 1, 2};
/* array a has 3 elements */
Zugriff auf Feldelemente
Auf die einzelnen Elemente eines Felds wird über einen Index
zugegriffen:
int a[3];
a[0], a[1], a[2];
/* access all entries */
In C beginnen Indizierungen immer mit dem Wert 0. Der letzte gültige
Index eines Felds der Länge N ist dann N − 1.
Achtung: Der Zugriff auch auf ungültige Indizes ist nicht beschränkt.
int a[3];
a[99]; /* invalid index */
Solche Bereichsüberschreitungen führen zu undefiniertem
Programmverhalten!
Iteration über Feldelemente
Über die Einträge eines Felds kann man z. B. in einer for-Schleife
iterieren:
int a[3];
int i;
for(i = 0; i < 3; ++i)
a[i] = i;
Auch bei der Iteration darf man nicht über ungültige Indizes laufen!
for(i = 0; i < 99; ++i)
a[i] = i;
/* wrong, but will compile */
Felder als Funktionsargument
Felder können als Argumente an Funktionen übergeben werden.
double norm(double x[5]);
{
double norm2 = 0.;
int i;
for(i = 0; i < 5; ++i)
norm2 += x[i]*x[i];
return sqrt(norm2);
}
Die Feldlänge muss nicht explizit angegeben werden und könnte als
weiterer Parameter übergeben werden:
double norm2 (double x[], int len);
Achtung: Dies verallgemeinert sich nicht auf mehrdimensionale
Felder (s. u.)!
Mehrdimensionale Felder I
Mehrdimensionale Felder (etwa zum Abspeichern voll besetzter
Matrizen) erhält man durch Angabe weiterer Indizes:
int b[4][3][2];
double H[3][3];
Die Elemente eines mehrdimensionalen Felds sind mehrfach
indiziert:
/* initialize Hilbert matrix of size 3 */
int i, j;
for(i = 0; i < 3; ++i)
for(j = 0; j < 3; ++j)
H[i][j] = 1./(1 + i + j);
Mehrdimensionale Felder II
Auch mehrdimensionale Felder können an Funktionen übergeben
werden.
Beispiele:
void printMatrix(double M[3][3]);
void printMatrix(double M[][3], int rows);
Nicht erlaubt ist die folgende, naheliegende „Verallgemeinerung“:
/* results in compiler error! */
void printMatrix(double M[][], int rows, int cols);
Bei mehrdimensionalen Feldern darf nur die Anzahl von Elementen
im ersten Argument ausgelassen werden.
Speichergröße und Anordnung von Feldern
Der Speicherbedarf eines Feldes ergibt sich aus Anzahl und Typ
seiner Elemente:
int a[3];
double x[2][2];
printf("%zu\n", sizeof(a)); /*12=3*sizeof(int)*/
printf("%zu\n", sizeof(x)); /*32=2*2*sizeof(double)*/
Die Elemente eines mehrdimensionalen Felds liegen konsekutiv im
Speicher. Die Position des Elements
x[row][col]
berechnet sich nach der Formel
2*row + col.
Felder dynamischer Größe
Bislang haben wir nur Felder konstanter Größe angelegt:
double H[3][3];
/* constant number of rows+columns */
Erst mit dem neuesten C-Standard (C11) sind Felder dynamischer
Größe erlaubt:
void printHilbertMatrix(int n)
{
double H[n][n];
/* ... */
}
Eine abwärtskompatible Alternative besteht in der Verwendung von
Zeigern und den Funktionen zur dynamischen Speicherverwaltung (s.
u.).
Gliederung
Ein sequentielles Speichermodell
Felder
Zeiger
Dynamische Speicherverwaltung
Zeiger, Felder und Adressarithmetik∗
Zeiger
Zeiger (engl. pointer) gehören zu den wichtigsten Sprachmitteln in C.
Ein Zeiger speichert die Adresse eines Datenobjekts, er „zeigt“ oder
„verweist“ auf ein anderes Objekt.
p=264
p
120
p
124
a
264
Über einen Zeiger hat man Zugriff auf das verwiesene Objekt. Das
gilt auch für Kopien: Die Kopie eines Zeigers enthält dieselbe
Adresse und verweist auf dasselbe Objekt!
Definition von Zeigern I
Für jeden Typ typename erhalten wir einen neuen (abgeleiteten)
Datentyp „Zeiger auf typename“:
typename *
Ein Zeiger ist eine Variable von einem Zeigertyp. Der Typ typename
gibt an, auf welchen Typ ein Zeiger verweist.
Syntax:
typename *identifier;
Beispiele:
int *p;
double *q;
/* pointer to int */
/* pointer to double */
Definition von Zeigern II
Bei der Vereinbarung von Zeigern sind Leerzeichen zwischen
Typname, dem Asterisk * und dem Namen des Zeigers nicht
signifikant. Die folgenden Definitionen sind also äquivalent:
int *p;
int* p;
int * p;
Achtung: Sollen mehrere Zeigervariablen gleichen Typs auf einmal
vereinbart werden, muss jede einzeln als Zeiger ausgezeichnet
werden:
int *p, *q;
int *p, q;
/* p, q are pointers to int */
/* q is integer variable */
Der Adressoperator &
Sei x ein Objekt beliebigen Typs. Der folgende Ausdruck liefert die
Adresse von x:
&x
/* value corresponds to address of x */
Ist x vom Typ typename, so ist &x vom Typ typename *.
Der unäre Operator & heißt Adressoperator. Er kann ausschließlich
auf Variablen, Feldelemente oder Funktionen angewendet werden.
Beispiel:
int a, *p;
p = &a; /* types match */
double x, *q;
q = &x;
Zuweisung von Zeigern
Mit Hilfe des Adressoperators können wir Zeiger initialisieren:
int a;
int *p = &a;
double x;
double *q = &x
Der Adressoperator kann nie auf der linken Seite einer Zuweisung
stehen:
&a = p;
/* error */
Zeiger können auch kopiert werden:
double x, *u, *v;
u = &x;
v = u;
Null-Zeiger
Neben der Adresse eines Objekts kann ein Zeiger einen anderen,
ausgezeichneten Wert annehmen, den Wert Null:
int *p = 0;
Dieser Wert ist insofern ausgezeichnet, als dass man ihn abprüfen
kann. Der Ausdruck
(int) p /* evaluates to zero, iff p == 0 */
hat den Wert 0 oder 1. Hat der Ausdruck den Wert 0, verweist der
Zeiger p nicht auf ein gültiges Objekt.
Dies kann man in Ausdrücken oder Anweisungen verwenden:
if(!p)
printf("p is zero pointer");
Der Inhaltsoperator *
Der unäre Operator * heißt Inhaltsoperator. Er kann nur auf Zeiger
angewandt werden.
Syntax:
*(pointer)
Ist ein Zeiger p vom Typ typename *, so ist der Typ von *p gleich
typename.
Beispiel:
int a, b, *p;
p = &a;
b = *p; /* types match */
Dereferenzieren von Zeigern
Verweist ein Zeiger auf ein anderes Objekt, kann man seinen
Speicherort über den Inhaltsoperator erreichen. Man spricht dann
vom Dereferenzieren des Zeigers.
Beispiel:
int a = 1, b, *p;
p = &a;
b = *p; /* b = 1 */
Wichtig: Da man über einen Zeiger Zugriff auf den Speicher
bekommt, ändern Zuweisungen den Wert des verwiesenen Objekts:
Beispiel:
int a = 1, *p;
p = &a;
*p = 1; /* a = 1 */
Uninitialisierte Zeiger I
Der häufigste Fehler im Zusammenhang mit Zeigern besteht im
Dereferenzieren ungültiger Zeiger.
Es ist verboten, einen uninitalisierten Zeiger oder einen Nullzeiger zu
dereferenzieren.
Beispiel:
double *p, *q = 0; /* p not initialized! */
*p; /* fatal, dereferencing unitialized pointer */
*q; /* fatal, dereferencing zero pointer */
Beides führt in der Regel zum sofortigen Programmabsturz. Es sind
allerdings auch schlimmere Konsequenzen denkbar. Der Compiler
kann solche Fehler im allgemeinen nicht erkennen.
Uninitialisierte Zeiger II
Im Zusammenhang mit uninitialisierten Zeigern kommt dem
Null-Zeiger besonerdere Bedeutung zu.
Solange ein Zeiger nicht auf ein gültiges Speicherobjekt verweist,
sollte er unbedingt mit dem Wert 0 initialisiert werden.
double *p = 0;
Vor dem Dereferenzieren eines Zeigers sollte dann stets auf Null
geprüft werden. In der Datei assert.h gibt es dazu das schöne
Makro:
assert(p);
*p;
/* assert that p != 0 */
Ist p ein Null-Zeiger, bricht das Programm mit einer Fehlermeldung
ab. Bei höheren Optimierungseinstellungen des Compilers wird das
Makro deaktiviert.
Zeiger auf void
Zeiger vom Datentyp void * können ein Speicheradresse
beinhalten:
int a;
void *p = (void *)&a;
Jeder Zeiger kann in einen Zeiger vom Typ void * gecastet werden.
Ein Zeiger vom Typ void * kann nicht dereferenziert werden:
int b = *p;
/* error */
Der Compiler kann nicht wissen, wie die Daten unter der in p
gespeicherten Adresse interpretiert werden sollen!
Ein void-Zeiger muss erst in einen spezifizierten Zeigertypen
gecastet werden, ehe er dereferenziert werden kann:
int *q = (int *)p;
Die symbolische Konstante NULL
Ein void-Zeiger kann mit Null initialisiert werden:
void *p = 0;
Statt der Integer-Null wird bisweilen die symbolische Konstante NULL
verwendet:
double *p = NULL;
Die symbolische Konstante ist in der Regel gleichbedeutend mit
(void *) 0
und wird in der Datei stdio.h definiert.
Zeiger auf Funktionen I
Nicht nur Variablen, auch Funktionen haben eine Adresse, und man
kann Zeiger auf Funktionen vereinbaren!
Betrachten wir die folgende Funktion:
double power(double x, int n);
Der Adressoperator kann auch auf Funktionen angewandt werden:
&power
/* returns address of power */
Die Verwendung des Adressoperators ist optional, auch der Name
einer Funktion alleine liefert bereits die Adresse der Funktion:
power
/* returns address of power */
Zeiger auf Funktionen II
Ein Zeiger auf die Funktion power wird nun wie folgt vereinbart:
double (*fp)(double, int) = &power;
double (*fp)(double, int) = power;
Die Deklaration des Zeigers enthält wiederum alle Informationen über
das Objekt, auf das er verweist!
Um eine Funktion über einen Zeiger aufzurufen, kann auf die Angabe
des Inhaltsoperators verzichtet werden. Die folgenden
Funktionsaufrufe sind alle äquivalent:
double x = (*fp)(2., 2);
double x = (fp)(2., 2);
double x = fp(2., 2);
/ * x = 4 */
/ * x = 4 */
/ * x = 4 */
Call by reference I
Eine Funktion erhält bei ihrem Aufruf Kopien der Argumente (call by
value).
Das gilt auch für den Fall, dass Zeiger an eine Funktion übergeben
werden:
void swap(int *a, int *b);
int main(void)
{
int a = 1, b = 2;
swap(&a, &b);
return 0;
}
Jede Kopie eines Zeigers verweist aber auf die gleiche
Speicheradresse. Wird diese beschrieben, ändert sich der Zustand
der dort abgelegten Variable.
Programmbeispiel Variablentausch
Quelltext
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
void swap ( int *p, int *q )
{
int temp;
temp = *p;
*p = *q;
*q = temp;
}
int main ( void )
{
int a = 1, b = 2 ;
int *p = &a, *q = &b;
printf( "a = %d, b = %d\n", a, b );
swap( p, q );
printf( "a = %d, b = %d\n", a, b );
return 0;
}
/* a = 1, b = 2 */
/* a = 2, b = 1 */
Call by reference II
Felder werden stets per Referenz (nicht als Kopie) an Funktionen
übergeben:
void initialize(double x[], int len)
{
int i;
for(i = 0; i < len; ++i)
x[i] = 0.;
}
int main(void)
{
double x[3];
initialize(double x[3]);
return 0;
}
/ * x = 0 */
Die obige Funktion ändert tatsächlich die in x gespeicherten Werte.
Gliederung
Ein sequentielles Speichermodell
Felder
Zeiger
Dynamische Speicherverwaltung
Zeiger, Felder und Adressarithmetik∗
Matrizen
Ein Feld
double A[2][3] = {{4.,2.,1.}, {-1.,2.,1.}};
entspricht einer dicht besetzten Matrix:
4 2 1
.
−1 2 1
Für jeden möglichen Eintrag wird Speicher reserviert:
printf("sizeof(A) = %zu\n",
sizeof(A)/sizeof(double)); /* prints 6 */
Nicht jede Matrix ist voll besetzt. Entsprechend sollten wir weniger
Speicher verbrauchen.
Dreiecksmatrizen
Eine untere Dreicksmatrix ist eine quadratische Matrix der Form:


∗
∗ ∗



 ..

..
.

.


∗

∗
∗ ∗ ... ∗ ∗
Alle Werte oberhalb der Diagonalen sind gleich Null.
Die Nullen brauchen nicht abgespeichert zu werden. Der
Speicheraufwand für eine Dreicksmatrix der Dimension n beträgt
dann noch
n(n + 1)
≤ n2 .
2
Dynamische Speicherverwaltung
Soll Speicher auf Anfrage angelegt, freigegeben oder angepasst
werden, spricht man von dynamischer Speicherverwaltung.
Die C-Standardbibliothek enthält eine Reihe von Funktionen zur
dynamischen Speicherverwaltung.
Auf den folgenden Folien beschäftigen wir uns mit den Fragen:
I
Wie legen wir neuen Speicher an oder passen eine Größe an?
I
Was müssen wir dabei beachten?
I
Wie verwenden wir neue Speicherblöcke?
Funktionen zur Speicherverwaltung
Die folgenden Methoden zur dynamischen Speicherverwaltung sind
in der Datei stdlib.h enthalten:
/* allocate memory */
void *malloc(size_t size);
/* allocate and initialize memory */
void *calloc(size_t number, size_t size);
/* deallocate memory */
void free (void *ptr);
/* try to resize memory at given address */
void *realloc (void *ptr, size_t size);
Anfordern von Speicher I
Die Funktion malloc (von engl. allocate memory) kann einen
Speicherblock beliebiger Länge anfordern:
void *malloc(size_t size);
Dabei gibt size die Größe des benötigten Speichers in Byte an.
Der Datentyp size_t ist ganzzahlig, vorzeichenlos und für die
Größenangaben von Datentypen und -objekten vorgesehen (z. B. als
Rückgabetyp von sizeof).
Anfordern von Speicher II
Angenommen, es soll Speicher für n Integerwerte angelegt werden.
Eine Integer-Zahl belegt in der Regel 4 Byte. Diese Zahl ist aber vom
System abhängig und kann variieren.
Wieviel Speicher für einen Datentyp benötigt wird, sagt der Operator
sizeof:
size_t single = sizeof(int);
Die richtige Menge Speicher fordern wir also an mit:
void *p = malloc(n*sizeof(int));
Analog lässt sich die benötigte Speichergröße für Daten vom Typ
float, double, etc. ermitteln.
Rückgabewert von malloc
Der Rückgabewert von
void *malloc(size_t size);
ist ein Zeiger vom Typ void *.
Semantik:
I
Konnte der angeforderte Speicher erfolgreich angelegt werden,
zeigt der Rückgabewert auf den Anfang des neuen
Speicherblocks.
I
Konnte der Speicher nicht angelegt werden, hat der Zeiger den
Wert Null, sprich der Zeiger ist ungültig.
Beispiel:
size_t size = 4;
void *p = malloc(size);
if(!p)
printf("error");
Rückgabetyp
Der Rückgabetyp von malloc ist void *. Dieser Typ enthält bloße
Speicheradressen ohne weitere Typspezifikation.
Der Aufrufer weiß, für welchen Datentyp Speicher reserviert wurde.
Der Rückgabewert wird nachträglich explizit oder implizit konvertiert:
int *p = (int*) malloc(n*sizeof(int));
So wird vereinbart, dass p auf einen Block von Integer-Zahlen zeigt.
Bemerkung: Die Adresse von p entspricht der des ersten Elements
im Block (s. u.):
*p == &p[0]
Zugriff auf dynamisch erzeugten Speicher
Mit malloc (oder calloc, s. u.) angelegter Speicher ist
zusammenhängend (wie bei Feldern).
Auf die Elemente des erzeugten Speicherblocks wird (wieder wie bei
Feldern) über den Operator [] und einen Index zugegriffen.
Beispiel:
int i, size = 4;
int *p = (int*) malloc(size*sizeof(int));
assert(p); /* remember to include assert.h */
for(i = 0; i < size; ++i)
p[i] = 0;
Freigeben von Speicher
Dynamisch angelegter Speicher bleibt solange reserviert, bis er
explizit freigegeben wird und damit für eine neue Verwendung zur
Verfügung steht.
Die Funktion
void free(void *ptr);
gibt den Speicherbereich, auf den ptr zeigt und der über malloc
(oder calloc) angelegt wurde, wieder frei.
Zu beachten ist unbedingt, dass. . .
I
auf freigegebenen Speicher nicht mehr zugegriffen werden darf
I
und Speicher nicht zweimal freigegeben werden darf!
Beispiel zum Freigeben von Speicher
Im folgenden Beispiel wird zunächst sichergestellt, dass nur ein
erfolgreich angelegter Speicherblock freigegeben wird:
double *vector = (double*) malloc(3*sizeof(double));
if(vector)
{
free(vector);
vector = 0; /* good practice: invalidate pointer */
}
Am Ende ist vector gleich Null, d. h. ein ungültiger Zeiger. Damit ist
für den weiteren Programmverlauf klar, dass vector nicht
dereferenziert werden darf.
Speicherlecks
Ein Speicherblock ist nur solange erreichbar, wie seine Adresse
bekannt ist. Im folgenden Beispiel geht 1 MB Speicher verloren:
int *p = (int*) malloc(262144*sizeof(int));
p = 0;
Einmal verlorener Speicher kann weder erreicht noch freigegeben
werden. Der Speicherblock bleibt für die gesamte Laufzeit des
Programms reserviert und steht dem eigenen Programm (und
anderen Prozessen) nicht mehr zur Verfügung.
Dieser Fehler heißt Speicherleck (engl. memory leak). Der Compiler
kann solche Fehler i. a. nicht finden.
Speicher anlegen bei gleichzeitiger Initialisierung
Die Funktion
void *calloc(size_t num, size_t size);
alloziiert einen zusammenhängenden Speicherbereich von num
Elementen der Größe size:
Semantik:
I
Wie bei malloc zeigt der Rückgabewert auf das erste Element
des neuen Speicherblocks, falls dieser erfolgreich angelegt
werden konnte. Andernfalls ist der Rückgabewert gleich Null.
I
Im Unterscheid zu malloc wird jedes Bit mit Null initialisiert.
Beispiel:
int *p = (int*) calloc(3, sizeof(int));
Speicher vergößern oder verkleinern
Mit der Funktion
void *realloc(void *ptr, size_t size);
wird die Größe des Speicherblocks, auf den ptr zeigt, angepasst.
Das zweite Argument size gibt dabei die neue Größe des
Speicherblocks an.
Die Funktion darf den Inhalt des Speicherblocks, auf den ptr zeigt,
an eine andere Stelle verschieben. In diesem Fall wird die Adresse
der neuen Speicherstelle zurückgegeben.
Das Verhalten von realloc ist auch für die Sonderfälle ptr = 0
oder size = 0 definiert. Dazu verweisen wir auf geeignete
Nachschlagewerke zur Standardbibliothek.
Dynamisches Anlegen von Matrizen
I
In vielen numerischen Anwendungen tauchen Matrizen oder
ähnliche Datenstrukturen auf.
Nicht immer ist es sinnvoll oder möglich, Matrizen in Feldern zu
speichern.
I
Auf den folgende Folien geben wir häufig verwendete
Code-Fragmente (Pattern) an, die zeigen, wie Speicher für
Matrizen angelegt und freigegeben werden kann.
Für die anzulegenden Matrizen verwenden wir Doppelzeiger:
double **A;
Zugriff auf die Elemente der Matrix geht dann so:
A[i][j]
I
/* access (i,j)-th element */
Komplette Programmbeispiele finden Sie diesmal auf der
Homepage!
Pattern I (Verschachteltes Alloziieren)
Es ist möglich, Speicher für jede Zeile der Matrix alloziieren:
in i;
double **A;
A = (double **) malloc(rows*sizeof(double *));
/* allocate memory for each row separately */
for(i = 0; i < rows; ++i)
A[i] = (double *) malloc(cols*sizeof(double));
Für jeden Aufruf von malloc muss abschließend free aufgerufen
werden:
for(i = 0; i < rows; ++i)
free(A[i]);
free(A);
Fehlerbehandlung
Der Rückgabewert von malloc zur Behandlung von Ausnahmen
wird im obigen Beispiel ignoriert: konnte der angeforderte Speicher
nicht angelegt werden, ist der Rückgabewert der Funktion gleich Null.
A = (double **) malloc(rows*sizeof(double *));
if(A != 0)
/* continue with allocation */
else
/* on error */
Im obigen Pattern wird malloc gleich mehrfach aufgerufen. Tritt ein
Fehler erst beim zweiten, dritten, usw. Aufruf auf, ist bereits Speicher
alloziiert worden, der wieder freigegeben werden muss (s. nächste
Seite).
Pattern II (Fehlerbehandlung beim Alloziieren)
int i, j;
double **A;
A = (double **) malloc(rows*sizeof(double *));
assert(A);
for(i = 0; i < rows; ++i)
{
A[i] = (double *) malloc(cols*sizeof(double));
/* on error: free previously allocated memory */
if(!A[i])
{
for(j = 0; j < i; ++j)
free(A[j]);
free(A);
return 1;
}
}
Konsekutiven Speicher anlegen
Gegenüber klassischen Feldern hat die obige Technik einen Nachteil:
I
Die Matrixeinträge werden im allgemeinen nicht konsekutiv im
Speicher liegen.
I
Für die Implementierung von Algorithmen (schnelle
Matrix-Vektor-Multiplikationen o. ä.) ist das allerdings
wünschenswert.
Das abschließende Beispiel zeigt, wie eine Matrix in zwei Schritten
initialisiert wird:
I
Zuerst wird ein einziger zusammenhängender Speicherblock für
die gesamte Matrix angelegt
I
Anschließend betten wir die Matrix in den Speicherblock ein.
Pattern III (Konsekutiver Speicher)
/* allocate memory first */
buffer = (double *) malloc(size*sizeof(double));
assert(buffer);
/* initialize A */
A = (double **) malloc(rows*sizeof(double *));
assert(A);
for(i = 0; i < rows; ++i)
A[i] = &buffer[i*rows] ;
/* free storage */
free(A);
free(buffer);
Gliederung
Ein sequentielles Speichermodell
Felder
Zeiger
Dynamische Speicherverwaltung
Zeiger, Felder und Adressarithmetik∗
Adressarithmetik mit ganzen Zahlen
In geringem Umfang sind arithmetische Operationen auf Zeigern
erlaubt:
I
Subtraktion von Zeigern
I
Addition/Subtraktion mit ganzen Zahlen
I
Vergleiche von Zeigern.
Einzelne Algorithmen lassen sich effizienter unter Verwendung von
Adressarithmetik implementieren (s. z. B. Blatt 6, Aufgabe 2).
Subtrahieren von Zeigern
Zeiger, die in einem einheitlichen Speicherbereich liegen, können
subtrahiert werden:
int a[3];
int *p = a[0], *q = a[2];
p - q;
Ergebnis die Anzahl von Feldelementen zwischen den beiden
Speicherpositionen.
Der Ausruck
p - q
ist vom Typ ptrdiff_t (engl. pointer difference type):
ptrdiff_t distance = p - q;
Dieser Typ ist in der Datei stddef.h definiert.
Adressarithmetik mit ganzen Zahlen
Ganze Zahlen können zu addiert oder von Zeigern abgezogen
werden:
p+1, p+2, ..., p+d
Resultat ist ein Zeiger q auf ein Objekt gleichen Typs, so dass
q - p == d.
Das lässt sich graphisch veranschaulichen:
p
p+1 p+2
a:
120
124
264
Feldnamen
Mit der Definition
int a[3];
wird ein Feld von drei Integer-Werten vereinbart.
Der Name des Felds
a
ist ein Ausdruck vom Typ int *. Sein Wert entspricht der Adresse
des ersten Elements von a:
a == &a[0]
Die folgenden Zuweisungen sind daher identisch:
int *p = &a[0];
int *p = a;
Adressarithmetik und Feldelemente
Ist int a[3] ein Feld ein Feld, so ist der Zugriff auf das i-te Element
a[i]
äquivalent zu
*(a+i)
Wendet man auf beide Ausdrücke den Adressoperator & an, erhält
man die Äquivalenz der folgenden beiden Ausdrücke:
a+i == &a[i]
Unterschiede von Zeigern und Feldern
Ein Zeiger ist eine Variable, deren Wert sich (durch Zuweisungen,
Inkrement-Operatoren, etc.) ändern kann:
int a[3];
int *p = a;
++p; /* p points to a[0] */
Ein Feldname ist keine Variable. Ausdrücke wie
a = p
oder
++a
sind daher nicht erlaubt.
Autoren
Autoren die an diesem Skript mitgewirkt haben:
I
2011–2014 : Christoph Gersbacher
I
2014–2015 : Patrick Schön
This work is licensed under a Creative Commons
Attribution-ShareAlike 4.0 International (CC
BY-SA 4.0) License.
http://creativecommons.org/
licenses/by-sa/4.0/legalcode

Download Report