5.1 Zeiger (pointer) 5.2 Arrays 5.4 Komplexe ... · Programmierkurs in C 5. Zeiger und komplexe...

Programmierkurs in C 5. Zeiger und komplexe Datenstrukturen

5 - 1 Wolfgang Effelsberg

5. Zeiger und komplexe Datenstrukturen

5.1 Zeiger (pointer)

5.2 Arrays

5.3 Zeichenketten (strings)

5.4 Komplexe Datenstrukturen (structs)



5.1 Zeiger (pointer)

Ein Zeiger (pointer) ist ein Verweis auf ein anderes Datenobjekt.

Beispiel: Ted

Null

Fred

Adam

Mary

Eva

Null Null Null

Null Null



Implementierung von Zeigern (1)

• Speicherzellen des Computers sind fortlaufend nummeriert

• Speicheradressen sind positive ganze Zahlen

• Ein Byte pro Speicherzelle

• Ein Zeiger in C ist die Speicheradresse des Objekts, auf das er verweist.

• Intern dargestellt als Zahl

• Zeigt auf das erste Byte des Objekts (z. B. double: 8 Bytes)

• Spezielle Adresse NULL für Zeiger, die auf nichts verweisen



Implementierung von Zeigern (2)

40 "Ted" adr("Fred")=80 adr ("Mary")=160

80 "Fred" adr("Adam")=100 NULL

100 "Adam" NULL NULL

160 "Mary" NULL adr("Eva")=180

180 "Eva" NULL NULL

Daten Zeiger



Zeiger-Syntax in ANSI C (1)

Deklaration:

Beispiel: int* a; int *b; float *c, *d; char *pointer, zeichen; Vorsicht: * muss vor jedem Bezeichner stehen. zeichen ist kein Zeiger:

Zeigerdeklaration

; * Typ Variable

,



Zeiger-Syntax in ANSI C (2)

Merke: • Der Typ des Datenelements, auf das gezeigt werden kann, ist aus der

Deklaration des Zeigertyps ersichtlich. • Zeiger vom Typ int*, der auf float zeigt, führt zu einer Warnung.

• Mit void * kann ein generischer Zeiger ohne Typ deklariert werden.

• void (engl. für „leer“) bedeutet in C „kein Datentyp“.

• void-Zeiger dürfen nicht zum Zugriff verwendet werden. Sie dienen nur als Platzhalter für Argumente in Funktionen.



Operationen auf Zeigern (1)

a) Wertzuweisung

Einem Zeiger kann der Wert eines anderen Zeigers zugewiesen werden.

Beispiel: int a; int *p1, *p2;

// Zuweisung von Adresse von a an Zeiger p1... (später)

...

...

p2 = p1; /* p2 zeigt nun auf dasselbe Objekt wie p1 */

...




b) Unärer Adressoperator &

• Einem Zeiger kann die Adresse eines Objekts zugewiesen werden.

• &c bedeutet: die Speicheradresse der Variablen c

Beispiel: int c; int *p = NULL; ... ...

p = &c;

/* p enthält nun die Adresse von c */

...

c p

c p




c) Unärer Inhaltsoperator *

Einem Objekt kann der Inhalt eines anderen Objektes zugewiesen werden, auf das ein Zeiger zeigt (de-referencing).

Beispiel: int c1=8, c2=6; int *p; ...

Zuweisen der Adresse von c1 an Zeiger p: p = &c1;

c1 = 8

c2 = 6

p

c1 = 8

c2 = 6

p




Zuweisen des Wertes, auf den p zeigt, an die Variable c2 c2 = *p;

Zuweisen eines Wertes an die Speicherstelle, auf die p zeigt *p = 5;

c1 = 5

c2 = 8

p

c1 = 8

c2 = 8

p




Merke: Die unären Inhalts- und Adressoperatoren * und & haben höheren Vorrang als die dyadischen arithmetischen Operatoren.

Beispiele: y = *p + 1 liest den Wert, auf den p zeigt, aus, erhöht ihn um 1 und weist das Ergebnis y zu

*p += 1 inkrementiert den Inhalt der Speicherstelle, auf die p zeigt, um 1

++*p ebenso (entspricht ++(*p))

(*p)++ ebenso

*p++ inkrementiert p (die Adresse). Bei gleichem Rang werden unäre Operatoren von rechts nach links ausgewertet. Ent- spricht *(p++).




d) Einrichten eines neuen Datenobjekts, auf das der Zeiger zeigt • Funktion malloc („memory allocate“) dient zum permanenten

Reservieren von Speicherplatz

• Größe (in Bytes) wird in Klammern angegeben

• Liefert die Anfangsadresse des allokierten Speicherbereichs als Pointer zurück.

• Die Adresse des Speicherbereichs wird in einem Zeiger gespeichert.

Beispiel int *p;

p = malloc(sizeof(int));

*p = 42;




Beispiel (erläutert): int *p,

p = malloc(sizeof(int));

Datenobjekt vom Typ int Kann nun eine Zahl speichern

p




Der unäre Operator sizeof wird dabei verwendet, um die Größe des zu allokierenden Speicherplatzes anzugeben. Wir erinnern uns: sizeof(Objekt) liefert die Größe des angegebenen Speicherobjekts (z. B. der Variablen) in Bytes. sizeof(Typname) liefert die Größe des angegebenen Typs in Bytes.




Zur Reservierung von Speicher für mehrere gleichartige Objekte am Stück gibt es eine spezielle Funktion: void * calloc(size_t nitems, size_t size)

calloc reserviert für nitems Objekte der Größe size Speicherplatz. Diese Funktion ist insbesondere für das dynamische Erzeugen eines Arrays interessant. Beispiel: Reserviere Speicherplatz für sieben ganze Zahlen hintereinander int *p = calloc(7, sizeof(int));




e) Löschen eines Datenobjekts, auf das ein Zeiger zeigt free(p);

• Der Speicherplatz für das Datenobjekt, auf das p zeigt, wird freigegeben. Der Wert von p ist anschließend undefiniert.

Normale Variablen existieren nur innerhalb des Anweisungsblocks, in dem sie definiert wurden. Sie werden am Ende des Blocks freigegeben (bei }).

Mit malloc erzeugte Objekte existieren dagegen, bis sie mit free gelöscht werden. Auch über Blockgrenzen hinweg!




f) Vergleich von Zeigern Alle Vergleichsoperatoren sind auch auf Zeigern möglich, aber nicht immer ist das Ergebnis sinnvoll.

Wenn die Zeiger p1 und p2 auf Elemente im gleichen linearen Adressraum zeigen, dann sind Vergleiche wie ==, !=, <, >, <=, >= sinnvoll. <, >, <=, >= sind insbesondere bei einem Array sinnvoll.

Beispiel: Seien p1 und p2 Zeiger auf Elemente eines Arrays (zum Beispiel mit calloc bereit gestellt).

p1 < p2 gilt, wenn p1 auf ein früheres Element im Vektor zeigt als p2.

Sind p1 und p2 jedoch nicht Elemente des gleichen Vektors, ist das Ergeb-nis nicht definiert/nicht vorhersagbar!




g) Arithmetik mit Zeigern

Addition und Subtraktion ganzzahliger Werte sind auf Zeigern erlaubt.

Beispiel: p += n setzt p auf die Adresse des n-ten Objektes nach dem Objekt, auf das p momentan zeigt (nicht n-tes Byte!) p++ setzt p auf die Adresse des nächsten Objektes p-- setzt p auf die Adresse des vorherigen Objektes (selten verwendet)

Merke: Alle anderen Operationen auf Zeigern sind verboten, wie Addition, Multi-plikation, Division oder Subtraktion zweier Zeiger, Bitoperationen oder Addition von Gleitpunktwerten auf Zeiger.




Beispiel für calloc und Arithmetik auf Zeigern

• Erzeugen von drei Gleitkommazahlen und Speichern von Werten

double* p = calloc(3, sizeof(double));

*p = 3.1415;

*(p+1) = 1.234;

p += 2;

*p = 5.4321; 3.1415 1.234 5.4321 p

nach Ausführung:

aufsteigende Adressen



"Verlieren" von Datenobjekten im Speicher (1)

Das Umsetzen eines Zeigers ohne "free" führt dazu, dass die Bezugsvari-able zwar noch existiert, aber nicht mehr adressiert werden kann. Der nicht freigegebene Speicherplatz bleibt auf Dauer blockiert!

Beispiel 1: int *p1, *p2;

.

.

.

p1 = malloc(sizeof(int));

*p1 = 17;


*p2 = 18;

p1 = p2;

17 p1

18 p2

unrettbar verloren



"Verlieren" von Datenobjekten im Speicher (2)

Beispiel 2: int *p1;

.

.

.


*p1 = 17;


Auch hier ist das Datenelement, das den Wert "17" enthält, nicht mehr auffindbar.



5.2 Arrays

• Ein Array ist ein Datenobjekt, das aus einer bestimmten Anzahl gleicher Teilobjekte besteht. Die Elemente werden über einen Index angespro-chen. Die Zählung beginnt bei 0.

Beispiel: int a[10];

definiert ein Array mit 10 Ganzzahlen mit den Namen a[0], ... a[9].

a:

a[0] a[1] a[9] .....



Arrays: Programmierhinweise

Hinweis 1: • Es ist gute Programmierpraxis, die Größe eines Arrays als Präprozessor-

Konstante zu definieren. Dann kann man sie später leichter ändern. #define ASIZE 10; // Definition einer Konstanten

…

int a[ASIZE];

for (i=0; i<ASIZE; i++)

a[i] = 0;

Hinweis 2: Ein Array-Bezeichner ist eine Konstante, nämlich die Anfangsadresse des Arrays (konstanter Zeiger). Auf ihm sind Zeigeroperationen nicht definiert. Jedoch kann ein anderer Zeiger auf ein Element des Arrays gesetzt werden.



Array-Syntax

Deklaration:

Beispiele: char name[20]; int lottozahlen[6];

Arraytyp

[ positive

Ganzzahl Typ Array- bezeichner ] ;

mehrdimensionaler Vektor



Array-Beispiel (1)

Beispiel:

Array kann als Serie von Werten deklariert und initialisiert werden. Die Größe des Arrays ergibt sich dann automatisch, die Größenangabe fällt weg. char name[ ] = {'E','f','f','e','l','s','b','e','r','g'};

implizite Größe: 10 Elemente.



Array-Beispiel (2)

• Deklaration eines Arrays mit 10 Elementen

• Belegung der Array-Elemente mit Werten 1, 1/2, 1/3, 1/4, 1/5

• Ausgabe des gesamten Arrays

double brueche[10];

for (int i=0; i<10; ++i)

brueche[i] = 1.0 / (i+1);

for (int i=0; i<10; ++i)

printf("%f ", brueche[i]);

printf("\n");



Unterschied zwischen Zeiger und Array (1)

int vektor[10];

int *zeiger = &vektor[0];

vektor

zeiger

0 9 .....



Unterschied zwischen Zeiger und Array (2)

Der Arrayname ist ein konstanter Zeiger auf die Adresse des ersten Ele-mentes. Damit sind folgende Zuweisungen erlaubt: zeiger = vektor; /* setzt zeiger auf &vektor[0] */

zeiger = vektor + i; /* setzt zeiger auf &vektor[i] */

Änderungen von vektor (konstanter Zeiger) sind jedoch verboten: vektor++;

vektor +=2;

vektor = zeiger; o. ä. SIND VERBOTEN!



Mehrdimensionaler Vektor

Beispiele int a[100]; /* 1-dimensionaler Vektor */ int b[3][5]; /* 2-dimensionaler Vektor */ int c[7][9][2]; /* 3-dimensionaler Vektor */

Elemente werden folgendermaßen angesprochen: b[1][2] /* Zeile 2, Spalte 3 der Matrix b */ (Erinnerung: das erste Element eines Arrays hat den Index 0, nicht 1!) Ein mehrdimensionales Array benötigt so viel zusammenhängenden Spei-cherplatz, wie sich aus dem Produkt der einzelnen Dimensionen ergibt (plus vier/acht Bytes für den Zeiger).



Array-Rechnungen

In C gilt: Arrays werden zeilenweise abgelegt (letzter Index läuft zuerst). Ausdrücke, die äquivalent zu b[i][j] sind:

*(b[i] + j)

(*(b+i))[j]

*((*(b+i)) + j)

*(&b[0][0] + 5*i + j)



5.3 Zeichenketten (strings)

Zeichenketten sind in C eindimensionale Vektoren vom Typ char, die mit einem speziellen Endezeichen (dem Null-Zeichen) versehen sind. char name[] = {'E','f','f','e','l','s','b','e','r','g','\0'};

(beachte: die implizite Größe des Vektors name ist 11!)

Abkürzungsschreibweise: char name[] = "Effelsberg";

Merke: •"a" mit Doppel-Anführungszeichen ist ein String, der mit dem Null-Zei-

chen beendet wird (Länge: 2). •'a' mit einfachen Anführungszeichen ist eine char-Konstante

(Länge:1). •'\0' belegt nur einen Speicherplatz vom Typ char (Sonderzeichen,

ESC-Zeichen) (Länge: 1).



Zeichenketten vs. Zeiger (1)

char *nachricht = "Go to prison";

/* Zeiger auf eine Zeichenkette */

'G' 'o' 't' ' ' 'o' ' ' 'p' 'r' 'i' 's' 'o' 'n' '\0'

nachricht

• Einzelne Zeichen sind in der Regel unveränderbar.

• Der Zeiger ist veränderbar.



Zeichenketten vs. Zeiger (2)

char zeichenkette[] = "Go to prison";

/* Array aus Zeichen */

• Inhalt veränderbar, auch die einzelnen Zeichen durch Direktzugriff

• Der Arraybezeichner ist ein konstanter Zeiger auf die Anfangsadresse des Arrays.

'G' 'o' 't' ' ' 'o' ' ' ‘p' 'r' 'i' 's' 'o' 'n' '\0'

zeichenkette:



Standard-String-Funktionen (1)

Beispiele aus <string.h>

int strcmp(char *s1, char *s2)

lexikographischer Vergleich von s1 und s2 (gibt 0 zurück, wenn s1 gleich s2) int strlen(char *s)

Gibt Länge der Zeichenkette s ohne die '\0' zurück. char *strcat(char *s1, char *s2)

Gibt s1 um s2 verlängert zurück (Konkatenation). s1 muss genügend Platz für die Aufnahme von s2 bereit stellen. char *strcpy(char *s1, char *s2)

Kopiert s2 nach s1. s1 muss genügend Platz für die Aufnahme von s2 be-reit stellen.



Standard-String-Funktionen (2)

char *strchr(char *s1, char c)

Gibt einen Zeiger auf das erste Vorkommen von c in s1 zurück. char *strstr( char *s1, char *s2)

Gibt einen Zeiger auf erste Kopie von s2 in s1 zurück.

Ausgabe von Zeichenketten printf("%s", nachricht);

Gibt die Zeichenkette nachricht auf dem Bildschirm aus.



5.4 Komplexe Datenstrukturen (structs)

Eine Struktur (struct) ist ein zusammengesetzter Datentyp. Er dient zur Konstruktion von Typen mit inhomogenen Komponenten (im Gegensatz zum Array).

• Nützlich zum Speichern verschiedenartiger Daten in einer Variablen

• Eine Person hat einen Namen (char*) und ein Alter (int)

• Ein Lebensmittel hat einen Namen (char*), einen Preis (float)

und ein Gewicht (float).

• Ein Quadrat in Mannheim besteht aus einem Buchstaben (char)

und einer Zahl (int).

• Deklaration eines structs gewöhnlich vor der main-Funktion



Beispiel für eine komplexe Datenstruktur

struct quadrat { int zahl; char buchstabe; };

• quadrat ist der der Name der Struktur

• quadrat ist jetzt ein Datentyp

• quadrat ist keine Variable! Definition einer Variablen q1 vom Typ quadrat: struct quadrat q1; Zugriff auf die Komponenten mit der Punkt-Notation: q1.zahl = 5; q1.buchstabe = 'A'; printf("%c%d", q1.buchstabe, q1.zahl);



Struct-Syntax (1)

Syntax der Deklaration:

Strukturdeklaration

{ Variable structure tag struct Komponente } ;

,

Komponente

Typ Typname ;

,



Struct-Syntax (2)

• Das structure tag dient als Abkürzung für den Teil der Vereinbarung in den geschweiften Klammern. Es definiert einen neuen Typ.

• Die Felder in einer Struktur heißen Komponenten (member fields). Sie können selbst wieder strukturierte Datentypen sein.

• Der Zugriff auf eine Komponente erfolgt mit der folgenden Syntax: • strukturvariablenname.komponentenname Der Komponentenname muss eindeutig sein.

Merke: Komponenten verschiedener Strukturen können denselben Namen haben. Dies ist aber in der Regel nur sinnvoll, wenn die Komponenten für sinn-verwandte Objekte stehen.



structs mit malloc

structs können temporär oder dauerhaft erzeugt werden.

• Temporär (nur gültig innerhalb des aktuellen Blocks)

• struct quadrat q1;

• Dauerhaft (existiert bis zum Löschen mit free)

• struct quadrat* q2;

• q2 = malloc(sizeof(struct quadrat));

• free(q2);

• Zugriff auf Komponenten mit (*q2).

(*q2).zahl = 3;



structs in Arrays

structs werden oft genutzt, um komplexere Datensätze zu speichern.

• Beispiel: eine Liste der Quadrate Mannheims

• Ein Array aus Quadraten ist handlicher als zwei Arrays (Buchstaben und Zahlen separat, zum Beispiel A 5).

struct quadrat mannheim[140];

// Jedes Element ist nun ein struct quadrat

mannheim[10].buchstabe = 'A';

mannheim[10].zahl = 5;



Schachtelung von Strukturen

structs können beliebig geschachtelt werden.

• Beispiel:

• Straße besteht aus Straßenname und Hausnummer.

• Adresse besteht aus Nachname und Straße.

struct adresse addr;

addr.str.name = "Hauptstrasse";

struct strasse { char* name; int nr; };

struct adresse { char* nachname; struct strasse str; };



Benutzerdefinierte Datenstrukturen (1)

• Zeiger werden häufig für die Definition eigener komplexer Datenstruk-turen eingesetzt.

Beispiel: verkettete Listen (linked lists) • Liste zum Speichern mehrerer Elemente des gleichen Typs

• Unterschied zu Arrays: die Größe der Liste ist veränderbar. • Die Anordnung der Elemente ist linear und geordnet.

• Für den Zeiger auf das erste Element wird häufig ein Anker (Listenkopf) eingerichtet.



Benutzerdefinierte Datenstrukturen (2)

/* Typdefinition */ struct element { int info; struct element *naechste_komponente; }; struct anker { struct element *anfang; int anzahl; }; /* Variablendefinition */ struct anker listenkopf; struct element *p;



Die verkettete Liste in C (1)

a) Erstes Element initialisieren p = malloc(sizeof(struct element));

(*p).info = 1; /* Das info-Feld wird durchgezaehlt */

(*p).naechste_komponente = NULL;

listenkopf.anfang = p;

listenkopf.anzahl = 1;

listenkopf

anfang:

anzahl: 1

info: 1

naechste_komponente: NULL




Merke:

• Operator "." hat eine stärkere Bindung (höhere Präzedenz) als "*“

Beim Ansprechen von Komponenten mittels Zeigern werden Klammern benötigt!

Diese Konstruktion kommt sehr oft vor, weshalb es eine Abkürzung dafür gibt:

(*p).info ist identisch zu p->info




b) Zweites Element mit Daten füllen p = malloc(sizeof(struct element));

p->naechste_komponente = listenkopf.anfang;

p->info = 2;

listenkopf.anfang = p;

listenkopf.anzahl++;

listenkopf

anfang:

anzahl: 2

info: 2

naechste_komponente naechste_komponente: NULL

info: 1




c) Drittes Element mit Daten füllen p = malloc(sizeof(struct element)); p->naechste_komponente = listenkopf.anfang; p->info = 3; listenkopf.anfang = p; listenkopf.anzahl++;

listenkopf

info: 2

naechste_komponente naechste_komponente: NULL

info: 1

anfang:

anzahl: 3

info: 3

naechste_komponente




d) Ausgabe der Listenelemente Zeiger p zeigt immer auf das aktuelle Element.

• Wird in jedem Schleifendurchlauf um eins nach vorne verschoben. • Die info-Komponente wird ausgegeben.

p = listenkopf.anfang;

while (p != NULL)

{

printf ("%d\n", p->info);

p = p->naechste_komponente;

}




e) Freigabe der Listenelemente p zeigt immer auf das zu löschende Element.

• Zeiger auf erstes Listenelement wird jeweils um eins nach vorne verschoben.

• Element, auf das p zeigt, wird gelöscht.

for (p = listenkopf.anfang; p != NULL; p = listenkopf.anfang)

{ listenkopf.anfang = p->naechste_komponente; free(p);

}




info: 2

naechste_komp

anfang: anzahl: x

info: 3 naechste_komp

p

info: 2

naechste_komp

anfang:

anzahl: x

info: 3

naechste_komp

vor erstem Schleifen- durchlauf:

nach erstem Durchlauf:



Zusammenfassung Verkettete Liste

• Zeiger ermöglichen Listen variabler Länge; belegt wird nur der wirklich benötigte Speicherplatz (anders als beim Array).

• Verkettete Listen sind sehr flexibel: Einfügen und Löschen ist an belie-biger Stelle möglich.

• Durch Restriktionen bzgl. der Einfüge- und Löschposition entsteht ein Kellerspeicher (stack) oder eine Warteschlange (queue).

stack queue

Date post:	22-Dec-2019
Category:	Documents
Upload:	others
View:	15 times
Download:	0 times

5.1 Zeiger (pointer) 5.2 Arrays 5.4 Komplexe ... · Programmierkurs in C 5. Zeiger und komplexe...

Documents