Am Tag 8, »Zeiger«, wurden Ihnen bereits die Grundlagen der Programmierung mit Zeigern, die einen ganz wichtigen Teil von C ausmachen, vorgestellt. Heute werden wir dieses Wissen vertiefen und einige fortgeschrittene Techniken zum Umgang mit Zeigern ansprechen, die Ihnen größere Flexibilität bei der Gestaltung Ihrer Programme gestatten. Heute lernen Sie -
Wie Sie am Tag 8 erfahren haben, ist ein Zeiger eine numerische Variable, deren Wert die Adresse einer anderen Variablen ist. Zur Deklaration eines Zeigers verwendet man den Indirektionsoperator (*). Beispielsweise deklariert die folgende Zeile:
int *zgr;
einen Zeiger namens zgr, der auf eine Variable vom Typ int verweist. Mit Hilfe des
Adressoperators (&) können Sie den Zeiger danach auf eine bestimmte Variable des
entsprechenden Typs richten. Unter der Voraussetzung, dass x als eine Variable vom
Typ int deklariert wurde, weist die Anweisung
zgr = &x;
dem Zeiger zgr die Adresse von x zu, so dass zgr danach auf x zeigt. Wiederum unter
Verwendung des Indirektionsoperators können Sie über den Zeiger auf die Variable,
auf die der Zeiger verweist, zugreifen. Die beiden folgenden Anweisungen weisen x
den Wert 12 zu:
x = 12;
*zgr = 12;
Da ein Zeiger selbst auch eine numerische Variable ist, wird er im Arbeitsspeicher des Computers unter einer bestimmten Adresse abgespeichert. Folglich ist es möglich, einen Zeiger auf einen Zeiger zu erzeugen, also eine Variable, deren Wert die Adresse eines Zeigers ist. So geht´s:
int x = 12; /* x ist eine int-Variable. */
int *zgr = &x; /* zgr ist ein Zeiger auf x. */
int **zgr_auf_zgr = &zgr; /* zgr_auf_zgr ist ein Zeiger auf einen */
/* Zeiger auf int. */
Beachten Sie die Deklaration des doppelten Indirektionsoperators (**) bei der Deklaration eines Zeigers auf einen Zeiger. Der doppelte Indirektionsoperator kommt auch zum Einsatz, wenn man einen Zeiger auf einen Zeiger verwendet, um auf eine Variable zuzugreifen. Die folgende Anweisung
**zgr_auf_zgr = 12;
weist somit der Variablen x den Wert 12 zu und die Anweisung
printf("%d", **zgr_auf_zgr);
gibt den Wert von x auf den Bildschirm aus. Wenn Sie versehentlich nur einen
einzigen Indirektionsoperator verwenden, kommt es zu Fehlern. Die Anweisung
*zgr_auf_zgr = 12;
weist zgr den Wert 12 zu, das heißt, zgr verweist danach auf die Speicheradresse 12
und das, was auch immer unter dieser Adresse abgelegt ist. Dies ist natürlich ein
grober Fehler.
Deklaration und Verwendung eines Zeigers auf einen Zeiger bezeichnet man auch als mehrfache Indirektion. Abbildung 14.1 verdeutlicht die Beziehung zwischen Variable, Zeiger und Zeiger auf Zeiger. Für die mehrfache Indirektion gibt es im Übrigen keine Grenze - Sie können ohne Probleme einen Zeiger auf einen Zeiger auf einen Zeiger und so fort deklarieren, doch gibt es nur wenige Einsatzbereiche, wo es lohnt, über zwei Ebenen hinauszugehen. Zudem wirkt die mit jeder Ebene zunehmende Komplexität wie eine Einladung, Fehler zu machen.
Abbildung 14.1: Ein Zeiger auf einen Zeiger.
Wie setzt man Zeiger auf Zeiger sinnvoll ein? Am häufigsten werden Zeiger auf Zeiger in Zusammenhang mit Arrays von Zeigern eingesetzt. Mit Arrays von Zeigern werden wir uns noch weiter hinten in diesem Kapitel beschäftigen. In Listing 17.5 aus dem Kapitel zu Tag 17, »Die Bibliothek der C-Funktionen«, finden Sie ein Beispiel für den Einsatz der mehrfachen Indirektion.
Am Tag 7, »Numerische Arrays«, wurde bereits auf das besondere Verhältnis zwischen Zeigern und Arrays hingewiesen. Dort haben wir auch schon festgestellt, dass der Name eines Arrays ohne nachfolgende Klammern gleichbedeutend mit einem Zeiger auf das erste Element des Arrays ist. Aus diesem Grund ist es für den Zugriff auf bestimmte Array-Typen einfacher, die Zeigernotation zu verwenden. Die Beispiele aus Kapitel 7 beschränkten sich allerdings noch auf eindimensionale Arrays. Wie sieht es mit den mehrdimensionalen Arrays aus?
Mehrdimensionale Arrays werden, wie Sie bereits wissen, mit einem eigenen
Klammernpaar für jede Dimension deklariert. So deklariert beispielsweise die folgende
Anweisung ein zweidimensionales Array, das acht Variablen vom Typ int enthält:
int multi[2][4];
Zweidimensionale Arrays kann man sich als eine Struktur aus Zeilen und Spalten
vorstellen - in unserem Beispiel also zwei Zeilen und vier Spalten. Es gibt aber noch
eine andere Möglichkeit, sich mehrdimensionale Arrays vorzustellen, und diese ist
näher an der Art und Weise, wie C die Arrays organisiert. Betrachten Sie multi
einfach als ein Array mit zwei Elementen, wobei jedes Element aus einem Array von
vier Integer-Werten besteht.
Sollte Ihnen dies nicht ganz klar sein, betrachten Sie Abbildung 14.2, in der die Array- Deklaration in ihre Bestandteile zerlegt wurde.
Abbildung 14.2: Bestandteile der Deklaration eines mehrdimensionalen Arrays.
Die einzelnen Teile der Deklaration sind wie folgt zu interpretieren:
multi.
multi enthält zwei Elemente.
int.
Eine Deklaration eines mehrdimensionalen Arrays liest man, indem man beim Array- Namen beginnt und von dort Klammer für Klammer nach rechts vorrückt. Nachdem das letzte Klammernpaar (die letzte Dimension) gelesen wurde, springt man zum Anfang der Deklaration, um den zugrunde liegenden Datentyp des Arrays zu ermitteln.
Gemäß dem Array-von-Arrays-Schema kann man sich ein mehrdimensionales Array wie in Abbildung 14.3 vorstellen.
Abbildung 14.3: Ein zweidimensionales Array kann man sich als Array von Arrays vorstellen.
Kommen wir noch einmal zurück auf die Verwendung von Array-Namen als Zeiger
(schließlich geht es in diesem Kapitel ja um Zeiger). Wie im Falle der eindimensionalen
Arrays gilt auch für die mehrdimensionalen Arrays, dass der Name des Arrays auf das
erste Element des Arrays verweist. Für unser obiges Beispiel bedeutet dies, dass multi
ein Zeiger auf das erste Element des als int multi[2][4] deklarierten
zweidimensionalen Arrays ist. Was aber genau ist das erste Element von multi?
Vielleicht wird es Sie verwundern, aber es ist nicht die int-Variable multi[0][0].
Denken Sie daran, dass multi ein Array von Arrays ist. Das erste Element ist daher
multi[0] - ein Array von vier int-Variablen (und eines der zwei untergeordneten
Arrays aus multi).
Wenn aber multi[0] ein Array ist, stellt sich die Frage, ob multi[0] selbst wieder auf
etwas verweist? Und tatsächlich, multi[0] zeigt auf das erste Element, multi[0][0].
Vielleicht verwundert es Sie, dass multi[0] ein Zeiger sein soll. Denken Sie daran,
dass der Name eines Arrays ohne Klammern ein Zeiger auf das erste Array-Element
darstellt. Der Ausdruck multi[0] ist der Name des Arrays multi[0][0] ohne das letzte
Klammernpaar und damit ein Zeiger.
Sorgen Sie sich nicht, wenn Sie jetzt ein bisschen verwirrt sind. Das Thema ist nicht einfach zu durchschauen. Vielleicht helfen Ihnen die folgenden Regeln, die für alle n-dimensionalen Arrays gelten:
Die Anwendung dieser Regeln auf das obige Beispiel ergibt, dass multi und multi[0]
als Zeiger interpretiert werden, während multi[0][0] zu Array-Daten ausgewertet wird.
Schauen wir uns jetzt einmal an, worauf alle diese Zeiger verweisen. Listing 14.1 deklariert ein zweidimensionales Array, wie wir es von den obigen Ausführungen her kennen, und gibt die Werte der zugehörigen Zeiger auf den Bildschirm aus. Auch die Adresse des ersten Array-Elements wird ausgegeben.
Listing 14.1: Beziehung zwischen mehrdimensionalen Arrays und Zeigern.
1: /* Beispiel für Zeiger und mehrdimensionale Arrays. */
2:
3: #include <stdio.h>
4:
5: int multi[2][4];
6:
7: int main(void)
8: {
9: printf("multi = %lu\n", (unsigned long)multi);
10: printf("multi[0] = %lu\n", (unsigned long)multi[0]);
11: printf("&multi[0][0] = %lu\n",
12: (unsigned long)&multi[0][0]);
13: return(0);
14: }
multi = 134518272
multi[0] = 134518272
&multi[0][0] = 134518272
Auf Ihrem System wird als Wert vermutlich nicht 134518272 angezeigt werden, aber es
werden auf jeden Fall alle drei Werte gleich sein. Die Adresse des Arrays multi ist die
gleiche wie die Adresse des Arrays multi[0], und beide Adressen sind wiederum
identisch mit der Adresse des ersten Integer-Werts im Array, zu multi[0][0].
Wenn aber alle drei Zeiger den gleichen Wert haben, gibt es dann überhaupt aus Sicht eines Programms einen verwertbaren Unterschied zwischen den Zeigern? Denken Sie zurück an Tag 8, wo ausgeführt wurde, dass der Compiler weiß, worauf ein Zeiger verweist. Um ganz genau zu sein: der Compiler kennt die Größe der Elemente, auf die ein Zeiger verweist.
Wie groß sind die Elemente, die wir verwendet haben? Listing 14.2 verwendet den
sizeof()-Operator, um die Größe der Elemente in Byte auszugeben.
Listing 14.2: Die Größe der Elemente bestimmen.
1: /* Größe der Elemente eines mehrdimensionalen Arrays. */
2:
3: #include <stdio.h>
4:
5: int multi[2][4];
6:
7: int main(void)
8: {
9: printf("Die Größe von multi = %u\n", sizeof(multi));
10: printf("Die Größe von multi[0] = %u\n", sizeof(multi[0]));
11: printf("Die Größe von multi[0][0] = %u\n", sizeof(multi[0][0]));
12: return(0);
13: }
Die Ausgabe dieses Programms (auf einer Linux-Maschine mit 4-Byte-Integern) sieht wie folgt aus:
Die Größe von multi = 32
Die Größe von multi[0] = 16
Die Größe von multi[0][0] = 4
Denken Sie daran, dass der Datentyp int unter Linux und auf einem Rechner mit
Intel-kompatiblem Prozessor vier Byte belegt. Auf Linux-Maschinen mit DEC/
Compaq-Alpha-Prozessor oder irgendeinem anderen 64-Bit-Prozessor wird die
Ausgabe vermutlich etwas anders aussehen.
Wie kann man diese Größenangaben erklären? Das Array multi enthält zwei Arrays,
die jedes aus vier Integern bestehen. Jeder Integer belegt im Speicher vier Byte. Für
insgesamt acht Integer mit je vier Byte kommt man auf eine Gesamtgröße von 32
Byte.
multi[0] ist ein Array mit vier Integern. Jeder Integer belegt 4 Byte, so dass eine
Größenangabe von 16 Byte für multi[0] einen Sinn ergibt.
multi[0][0] schließlich ist ein Integer, so dass seine Größe natürlich 4 Byte beträgt.
Was bedeuten diese Größen für die Zeigerarithmetik, die an Tag 8 besprochen wurde? Der Compiler kennt die Größe des Objekts, auf das verwiesen wird, und die Zeigerarithmetik berücksichtigt diese Größe. Wenn Sie einen Zeiger inkrementieren, wird der Wert des Zeigers um den Betrag erhöht, der den Zeiger auf das nächste Element richtet - unabhängig davon, auf welche Art von Element der Zeiger verweist. Mit anderen Worten, der Zeiger wird um die Größe der Objekte, auf die er verweist, inkrementiert.
Was bedeutet dies für unser Beispiel. multi ist ein Zeiger auf ein 4-elementiges
Integer-Array mit einer Größe von 16 Byte. Wenn Sie multi inkrementieren, sollte
sein Wert um 16 (die Größe eines 4-elementigen Integer-Arrays) erhöht werden.
Wenn multi auf multi[0] verweist, sollte demnach (multi + 1) auf multi[1] zeigen.
Listing 14.3 testet diese Theorie für uns.
Listing 14.3: Zeigerarithmetik mit mehrdimensionalen Arrays.
1: /* Wendet die Zeigerarithmetik auf Zeiger an, die auf */
2: /* mehrdimensionale Arrays verweisen. */
3:
4: #include <stdio.h>
5:
6: int multi[2][4];
7:
8: int main(void)
9: {
10: printf("Wert von (multi) = %lu\n",
11: (unsigned long)multi);
12: printf("Wert von (multi + 1) = %lu\n",
13: (unsigned long)(multi+1));
14: printf("Adresse von multi[1] = %lu\n",
15: (unsigned long)&multi[1]);
16: return(0);
17: }
Wert von (multi) = 134518304
Wert von (multi + 1) = 134518320
Adresse von multi[1] = 134518320
Die genauen Werte werden auf Ihrem System anders aussehen, aber die Relation wird
die gleiche sein. Wenn der Zeiger multi um 1 inkrementiert wird, erhöht sich sein
Wert (auf einem 32-Bit-System) um 16 und der Zeiger weist auf das nächste Element
im Array, multi[1].
Sie haben nun gesehen, dass multi ein Zeiger auf multi[0] ist. Sie haben auch
gesehen, dass multi[0] ebenfalls ein Zeiger ist (auf multi[0][0]). multi ist folglich ein
Zeiger auf einen Zeiger. Um über den Ausdruck multi auf einzelne Array-Daten
zuzugreifen, muss man sich daher der doppelten Indirektion bedienen. Um
beispielsweise den Wert von multi[0][0] auszugeben, könnten Sie jede der drei
folgenden Anweisungen verwenden:
printf("%d", multi[0][0]);
printf("%d", *multi[0]);
printf("%d", **multi);
Die gleichen Betrachtungen gelten auch für drei oder mehrere Dimensionen. So ist ein dreidimensionales Array nichts anderes als ein Array, dessen Elemente zweidimensionale Arrays sind; jedes dieser Elemente ist wiederum ein Array von eindimensionalen Arrays.
Das Thema mehrdimensionale Arrays und Zeiger ist zweifelsohne etwas verwirrend.
Wenn Sie mit mehrdimensionalen Arrays arbeiten, behalten Sie folgende Regel im
Hinterkopf: Die Elemente eines Arrays mit n Dimensionen sind selbst Arrays mit n-1
Dimensionen. Wenn n gleich 1 ist, sind die Elemente des Arrays Variablen des
Datentyps, der bei der Deklaration des Arrays angegeben wurde.
Bis jetzt hatten wir es nur mit Array-Namen zu tun, die Zeigerkonstanten darstellen,
deren Wert nicht geändert werden kann. Wie würde man eine Zeigervariable
deklarieren, die auf ein Element eines mehrdimensionalen Arrays verweist? Wir
führen zu diesem Zwecke das obige Beispiel mit dem Array multi fort.
int multi[2][4];
Um eine Zeigervariable zgr zu deklarieren, die auf ein Element von multi verweisen
kann (also auf ein vierelementiges Integer-Array zeigt), schreiben Sie
int (*zgr)[4];
Der nächste Schritt besteht darin, zgr auf das erste Element in multi zu richten:
zgr = multi;
Vielleicht fragen Sie sich, wozu die runden Klammern in der Zeigerdeklaration nötig
sind. Die eckigen Klammern ([ ]) haben eine höhere Priorität als das Sternchen *.
Wenn Sie schreiben
int *zgr[4];
deklarieren Sie ein Array von vier Zeigern auf den Typ int. Man kann zwar Arrays
von Zeigern deklarieren und verwenden, doch ist dies nicht das, worum es uns hier
geht.
Was kann man mit Zeigern auf Elemente von mehrdimensionalen Arrays anfangen? Wie für die eindimensionalen Arrays gilt, dass man zur Übergabe von Arrays an Funktionen Zeiger benötigt. Listing 14.4 stellt Ihnen zwei Methoden vor, wie man mehrdimensionale Arrays an Funktionen übergeben kann.
Listing 14.4: Übergabe eines mehrdimensionalen Arrays an eine Funktion.
1: /* Demonstriert die Übergabe eines Zeigers auf ein */
2: /* mehrdimensionales Array an eine Funktion. */
3:
4: #include <stdio.h>
5:
6: void printarray_1(int (*zgr)[4]);
7: void printarray_2(int (*zgr)[4], int n);
8:
9: int main(void)
10: {
11: int multi[3][4] = { { 1, 2, 3, 4 },
12: { 5, 6, 7, 8 },
13: { 9, 10, 11, 12 } };
14:
15: /* zgr ist ein Zeiger auf ein Array von 4 Integern. */
16:
17: int (*zgr)[4], count;
18:
19: /* Richte zgr auf das erste Element von multi. */
20:
21: zgr = multi;
22:
23: /* Mit jedem Schleifendurchlauf wird zgr inkrementiert und auf */
24: /* das nächste Element (das nächste 4-Element-Integer-Array) */
25: /* von multi gerichtet */
26: for (count = 0; count < 3; count++)
27: printarray_1(zgr++);
28:
29: puts("\n\nEingabetaste drücken...");
30: getchar();
31: printarray_2(multi, 3);
32: printf("\n");
33: return(0);
34: }
35:
36: void printarray_1(int (*zgr)[4])
37: {
38: /* Gibt die Elemente eines einzelnen 4-elementigen Integer-Arrays */
39: /* aus. p ist ein Zeiger auf int. Um p die Adresse in zgr */
40: /* zuzuweisen, ist eine Typumwandlung nötig */
41:
42: int *p, count;
43: p = (int *)zgr;
44:
45: for (count = 0; count < 4; count++)
46: printf("\n%d", *p++);
47: }
48:
49: void printarray_2(int (*zgr)[4], int n)
50: {
51: /* Gibt die Elemente eines n x 4-elementigen Integer-Arrays aus */
52:
53: int *p, count;
54: p = (int *)zgr;
55:
56: for (count = 0; count < (4 * n); count++)
57: printf("\n%d", *p++);
58: }
1
2
3
4
5
6
7
8
9
10
11
12
Eingabetaste drücken...
1
2
3
4
5
6
7
8
9
10
11
12
In den Zeilen 11 bis 13 wird ein Array von Integern, multi[3][4], deklariert und
initialisiert. Die Zeilen 6 und 7 enthalten die Prototypen für die Funktionen
printarray_1() and printarray_2(), die zum Ausgeben der Daten aus dem Array
verwendet werden.
Die Funktion printarray_1() erwartet nur ein einziges Argument, einen Zeiger auf ein
Array von vier Integern. Diese Funktion gibt alle vier Elemente des Arrays aus. Wenn
main() in Zeile 27 die Funktion printarray_1() das erste Mal aufruft, übergibt sie
einen Zeiger auf das erste Element (das erste 4-Element-Integer-Array) von multi.
Danach wird die Funktion noch zweimal aufgerufen, wobei der Zeiger jedes Mal zuvor
inkrementiert wurde, so dass er auf das zweite und danach auf das dritte Element von
multi zeigt. Nach Abarbeitung der drei Aufrufe werden die zwölf Integer aus multi auf
den Bildschirm ausgegeben.
Die zweite Funktion, printarray_2(), verfolgt einen anderen Ansatz. Die Funktion
übernimmt ebenfalls einen Zeiger auf ein Array von vier Integern. Zusätzlich erwartet
die Funktion jedoch noch eine Integer-Variable, die die Anzahl der Elemente (die
Anzahl der Arrays von vier Integern) des mehrdimensionalen Arrays angibt. Ein
einziger Aufruf von printarray_2(), Zeile 31, gibt den gesamten Inhalt von multi auf
den Bildschirm aus.
Beide Funktionen bedienen sich der Zeigernotation, um die einzelnen Integer im
Array durchzugehen. Die Syntax (int *)zgr, die in beiden Funktionen Verwendung
findet (Zeilen 43 und 54) sind vielleicht nicht ganz klar. Der Ausdruck (int *) ist eine
Typumwandlung, die den Datentyp der Variablen vorübergehend vom deklarierten
Datentyp in einen anderen Datentyp umwandelt. Für die Zuweisung des Wertes von
zgr an p ist die Typumwandlung unabdingbar, da beide Zeiger unterschiedliche Typen
haben (p ist ein Zeiger auf den Typ int, während zgr ein Zeiger auf ein Array von vier
Integern ist). C erlaubt keine Zuweisungen zwischen Zeigern, die unterschiedlichen
Datentypen angehören. Die Typumwandlung teilt dem Compiler mit: »Für die aktuelle
Anweisung behandle den Zeiger zgr so, als ob es sich um einen Zeiger auf int
handele.« Am Tag 18, »Vom Umgang mit dem Speicher«, werden wir uns noch
eingehender mit den Typumwandlungen beschäftigen.
Am Tag 7 haben Sie erfahren, dass ein Array ein zusammenhängender Block von Datenspeicherstellen ist, die dem gleichen Datentyp angehören und über denselben Namen angesprochen werden. Da Zeiger ebenfalls zu den Datentypen von C gehören, können Sie auch Arrays von Zeigern deklarieren und verwenden. Arrays von Zeigern stellen eine leistungsfähige und in bestimmten Situationen sehr nützliche Konstruktion dar.
Am häufigsten werden Arrays von Zeigern zusammen mit Strings eingesetzt. Ein String
ist, wie Sie am Tag 9, »Zeichen und Strings«, gelernt haben, eine Folge von Zeichen, die
im Speicher abgelegt sind. Der Beginn eines Strings wird durch einen Zeiger auf das
erste Zeichen (einen Zeiger vom Typ char) angezeigt. Das Ende des Strings wird durch
ein Nullzeichen markiert. Indem Sie ein Array von Zeigern auf char deklarieren und
initialisieren, können Sie auf elegante Weise eine große Anzahl von Strings verwalten
und manipulieren. Jedes Element in dem Array zeigt auf einen anderen String, und
durch Iteration über das Array können Sie auf die einzelnen Strings zugreifen.
Ich denke, dies ist ein günstiger Zeitpunkt, um noch einmal aufzufrischen, was Sie am
Tag 9 über String-Allokation und -Initialisierung gelernt haben. Eine Möglichkeit,
Speicher für einen String zu reservieren und diesen zu initialisieren, besteht darin, ein
Array vom Typ char zu deklarieren:
char meldung[] = "Dies ist eine Meldung.";
Die andere Möglichkeit besteht darin, einen Zeiger auf char zu deklarieren:
char *meldung = "Dies ist eine Meldung.";
Beide Deklarationen sind äquivalent. In beiden Fällen reserviert der Compiler
Speicher, der groß genug ist, den String mit seinem abschließenden Nullzeichen
aufzunehmen. Der Bezeichner meldung weist jeweils auf den Beginn des Strings. Wie
sieht es mit den folgenden zwei Deklarationen aus?
char meldung1[20];
char *meldung2;
Die erste Zeile deklariert ein Array vom Typ char, das 20 Zeichen lang ist; meldung1
stellt einen Zeiger auf die erste Position im Array dar. Beachten Sie, dass der Speicher
für das Array zwar reserviert, nicht aber initialisiert ist. Der Inhalt des Arrays ist
unbestimmt. Die zweite Zeile deklariert meldung2, einen Zeiger auf char. Diese
Anweisung reserviert keinen Speicher - abgesehen von dem Speicher für den Zeiger.
Wenn Sie einen String erzeugen wollen, auf dessen Beginn meldung2 zeigen soll,
müssen Sie zuerst Speicher für den String reservieren. Am Tag 9 haben Sie gelernt,
wie man sich zu diesem Zweck der Speicherallokationsfunktion malloc() bedient.
Denken Sie daran, dass für jeden String Speicher allokiert werden muss: entweder zur
Kompilierzeit in Form einer Deklaration oder zur Laufzeit mittels malloc() oder einer
anderen Speicherallokationsfunktion.
Nach diesem kurzen Rückblick wollen wir uns anschauen, wie man ein Array von
Zeigern deklariert. Die folgende Anweisung deklariert ein Array von zehn Zeigern auf
char:
char *meldung[10];
Jedes Element im Array meldung[] ist ein individueller Zeiger auf char. Wie Sie
sicherlich schon vermuten, können Sie die Deklaration mit der Initialisierung und
Speicherallokation der Strings kombinieren:
char *meldung[10] = { "eins", "zwei", "drei" };
Diese Deklaration bewirkt Folgendes:
meldung wird allokiert. Die Elemente von
meldung sind Zeiger auf char.
meldung[0] wird auf das erste Zeichen im String "eins" gerichtet. meldung[1] weist
auf das erste Zeichen im String "zwei" und meldung[2] weist auf das erste Zeichen
im String "drei".
Abbildung 14.4 veranschaulicht den Zusammenhang zwischen dem Array von
Zeigern und den Strings. Die Array-Elemente von meldung[3] bis meldung[9] sind in
diesem Beispiel nicht initialisiert und weisen folglich auf nichts Bestimmtes.
Abbildung 14.4: Ein Array von Zeigern auf char.
Schauen Sie sich nun Listing 14.5 an, das ein Beispiel für die Verwendung eines Arrays von Zeigern enthält.
Listing 14.5: Ein Array von Zeigern auf char initialisieren und verwenden.
1: /* Ein Array von Zeigern auf char initialisieren. */
2:
3: #include <stdio.h>
4:
5: int main(void)
6: {
7: char *meldung[6] = { "Vor", "vier", "Generationen",
8: "begannen", "unsere", "Vorväter" };
9: int count;
10:
11: for (count = 0; count < 6; count++)
12: printf("%s ", meldung[count]);
13: printf("\n");
14: return(0);
15: }
Vor vier Generationen begannen unsere Vorväter
Das Programm deklariert ein Array von sechs Zeigern auf char und initialisiert diese
so, dass sie auf sechs Strings verweisen (Zeilen 7 und 8). Danach werden in den Zeilen
11 und 12 die einzelnen Elemente des Arrays mit Hilfe einer for-Schleife auf den
Bildschirm ausgegeben.
Bereits dieses kleine Programm macht deutlich, dass die Arbeit mit einem Array von Zeigern einfacher ist als die Manipulation einzelner Strings. Noch deutlicher tritt der Vorteil in komplexeren Programmen zutage - wie zum Beispiel dem Programm aus Listing 14.7. Wie Sie in diesem Programm sehen werden, wird der Vorteil noch größer, wenn Funktionen ins Spiel kommen, denn es ist viel einfacher, ein Array von Zeigern an eine Funktion zu übergeben als einzelne Strings. Man kann dies auch demonstrieren, indem man das Programm aus Listing 14.5 so umschreibt, dass es zur Ausgabe der Strings eine Funktion verwendet. Das umgeschriebene Programm steht in Listing 14.6.
Listing 14.6: Ein Array von Zeigern an eine Funktion übergeben.
1: /* Ein Array von Zeigern an eine Funktion übergeben. */
2:
3: #include <stdio.h>
4:
5: void strings_ausgeben(char *p[], int n);
6:
7: int main(void)
8: {
9: char *meldung[6] = { "Vor", "vier", "Generationen",
10: "begannen", "unsere", "Vorväter" };
11:
12: strings_ausgeben(meldung, 6);
13: printf ("\n");
14: return(0);
15: }
16:
17: void strings_ausgeben(char *p[], int n)
18: {
19: int count;
20:
21: for (count = 0; count < n; count++)
22: printf("%s ", p[count]);
23: }
Vor vier Generationen begannen unsere Vorväter
Die Funktion strings_ausgeben() übernimmt zwei Argumente (siehe Zeile 17). Das
erste Argument ist ein Array von Zeigern auf char, das zweite ist die Anzahl der
Elemente im Array. Die Funktion strings_ausgeben() ist daher geeignet, Strings, auf
die die Zeiger eines beliebigen Arrays von Zeigern auf char verweisen, auszugeben.
Vielleicht erinnern Sie sich, dass ich Ihnen weiter oben im Abschnitt »Zeiger auf Zeiger« ein Beispiel versprochen habe. Sie haben das Beispiel gerade gesehen! Listing 14.6 deklariert ein Array von Zeigern. Der Name dieses Arrays ist ein Zeiger auf das erste Element des Arrays. Wenn Sie das Array an eine Funktion übergeben, übergeben Sie einen Zeiger (den Array-Namen) auf einen Zeiger (das erste Array- Element).
Es ist an der Zeit, dass wir ein komplexeres Beispiel angehen. Listing 14.7 verwendet
viele der Programmiertechniken, die Sie bereits kennen gelernt haben - unter
anderem auch Arrays von Zeigern. Das Programm liest ganze Zeilen von der Tastatur
ein. Während des Einlesens wird für jede eingegebene Zeile Speicher allokiert. Für die
Verwaltung der Zeilen wird ein Array von Zeigern auf char eingesetzt. Durch Eingabe
einer Leerzeile signalisieren Sie dem Programm, dass die Eingabe beendet ist,
woraufhin das Programm die Strings alphabetisch sortiert und auf den Bildschirm
ausgibt.
Wenn Sie Programme wie dieses neu erstellen, sollten Sie bei der Planung einen Ansatz verfolgen, der der strukturierten Programmierung Rechnung trägt. Legen Sie als Erstes eine Liste der Aufgaben an, die das Programm erledigen soll:
Diese Liste legt es nahe, dass das Programm zumindest drei Funktionen enthalten
sollte: eine zum Einlesen der Zeilen, eine zum Sortieren der Zeilen und eine zum
Ausgeben der Zeilen. Danach planen Sie jede der Funktionen für sich. Was muss die
Eingabefunktion, wir nennen sie zeilen_einlesen(), tun?
Wenden wir uns nun der zweiten Funktion zu, die für das Sortieren der Zeilen
verantwortlich sein soll. Nennen wir sie sortieren(). (Originell, nicht wahr?) Das in
dieser Funktion verwendete Sortierverfahren ist ebenso einfach wie primitiv.
Aufeinander folgende Strings werden verglichen und vertauscht, wenn der zweite
String kleiner als der erste String ist. Streng genommen werden allerdings nicht
benachbarte Strings verglichen, sondern Strings, deren Zeiger im Array
nebeneinander abgelegt sind und ausgetauscht werden - wo erforderlich -, und zwar
ebenfalls die Zeiger auf die Strings und nicht die Strings selbst.
Um sicherzustellen, dass das Array vollständig sortiert wird, müssen Sie das Array von Anfang bis zum Ende durchgehen und bei jedem Durchgang alle benachbarten String- Paare vergleichen und gegebenenfalls vertauschen. Für ein Array von n Elementen bedeutet dies, dass das Array n-1 Male durchlaufen werden muss. Warum ist dies notwendig?
Bei jedem Durchlaufen des Arrays kann ein gegebenes Element bestenfalls um eine Position verschoben werden. Was bedeutet dies für einen String, der an einer falschen Position steht? Nehmen wir an, der String, der an der ersten Position stehen sollte, ist im unsortierten Array auf der letzten Position abgespeichert. Beim ersten Durchlaufen des Arrays rückt der String auf die vorletzte Position, beim zweiten Durchgang rückt er um eine weitere Position nach vorne und so weiter. Insgesamt werden n-1 Durchgänge benötigt, um den String an die erste Position zu verschieben.
Das hier vorgestellte Sortierverfahren ist äußerst ineffizient und unelegant. Es ist allerdings einfach zu implementieren und zu verstehen, und für die kurze Liste, die in dem Beispielprogramm zu sortieren ist, ist das Verfahren absolut ausreichend.
Die letzte Funktion gibt die sortierten Zeilen auf den Bildschirm aus. Im Grunde haben wir diese Funktion bereits in Listing 14.6 aufgesetzt. Für die Verwendung in Listing 14.7 bedarf es nur geringfügiger Anpassungen.
Listing 14.7: Programm, das Textzeilen von der Tastatur einliest, diese alphabetisch sortiert und die sortierte Liste ausgibt.
1: /* Liest Strings von der Tastatur ein, sortiert diese */
2: /* und gibt sie auf den Bildschirm aus. */
3: #include <stdlib.h>
4: #include <stdio.h>
5: #include <string.h>
6:
7: #define MAXZEILEN 25
8:
9: int zeilen_einlesen(char *zeilen[]);
10: void sortieren(char *p[], int n);
11: void strings_ausgeben(char *p[], int n);
12:
13: char *zeilen[MAXZEILEN];
14:
15: int main(void)
16: {
17: int anzahl_zeilen;
18:
19: /* Lese die Zeilen von der Tastatur ein. */
20:
21: anzahl_zeilen = zeilen_einlesen(zeilen);
22:
23: if ( anzahl_zeilen < 0 )
24: {
25: puts("Fehler bei Speicherreservierung");
26: exit(-1);
27: }
28:
29: sortieren(zeilen, anzahl_zeilen);
30: strings_ausgeben(zeilen, anzahl_zeilen);
31: return(0);
32: }
33:
34: int zeilen_einlesen(char *zeilen[])
35:{
36: int n = 0, slen;
37: char puffer[80]; /* Temporärer Speicher für die Zeilen. */
38:
39: puts("Geben Sie einzelne Zeilen ein; Leerzeile zum Beenden.");
40:
41: while ((n < MAXZEILEN) && (fgets(puffer,80,stdin) != 0))
42: {
43: slen = strlen (puffer);
44: if (slen < 2)
45: break;
46: puffer [slen-1] = 0;
47: if ((zeilen[n] = (char *)malloc(strlen(puffer)+1)) == NULL)
48: return -1;
49: strcpy( zeilen[n++], puffer );
50: }
51: return n;
52:
53: } /* Ende von zeilen_einlesen() */
54:
55: void sortieren(char *p[], int n)
56: {
57: int a, b;
58: char *x;
59:
60: for (a = 1; a < n; a++)
61: {
62: for (b = 0; b < n-1; b++)
63: {
64: if (strcmp(p[b], p[b+1]) > 0)
65: {
66: x = p[b];
67: p[b] = p[b+1];
68: p[b+1] = x;
69: }
70: }
71: }
72: }
73:
74: void strings_ausgeben(char *p[], int n)
75: {
76: int count;
77:
78: for (count = 0; count < n; count++)
79: printf("%s\n", p[count]);
80: }
Geben Sie einzelne Zeilen ein; Leerzeile zum Beenden.
Hund
Apfel
Zoo
Programm
Mut
Apfel
Hund
Mut
Programm
Zoo
Es lohnt sich, bestimmte Details des Programms gründlicher zu untersuchen. Das
Programm verwendet etliche neue Bibliotheksfunktionen zur Bearbeitung der Strings,
die hier nur kurz erklärt werden. Am Tag 16, »Stringmanipulation«, werde ich auf
diese Funktionen näher eingehen. Damit die Funktionen im Programm verwendet
werden können, muss die Header-Datei string.h eingebunden werden.
In der Funktion zeilen_einlesen() wird die Eingabe von der while-Anweisung in Zeile
41 kontrolliert:
while ((n < MAXZEILEN) && (fgets(puffer,80,stdin) != 0))
Die Bedingung, die von while getestet wird, besteht aus zwei Teilen. Der erste Teil,
n < MAXZEILEN, stellt sicher, dass die maximale Anzahl an einzulesenden Zeilen noch
nicht erreicht wurde. Der zweite Teil, fgets(puffer,80,stdin) != 0, ruft die
Bibliotheksfunktion fgets() auf, um eine einzelne Zeile von der Tastatur in puffer
einzulesen, und stellt sicher, dass kein End-of-File- oder irgendein anderer Fehler
aufgetreten ist. Von Tag 9 her wissen Sie, dass fgets() die von der Tastatur
eingelesene Zeile, einschließlich des Neue-Zeile-Zeichens, zurückliefert. In Zeile 43
liefert die Bibliotheksfunktion strlen() (aus string.h) die Länge des Strings zurück
(ohne das abschließende Nullzeichen) und weist diesen Wert der Variablen slen zu.
Die Variable slen wird in Zeile 44 kontrolliert. Wenn die Länge des Strings kleiner als
2 ist (also nur aus einer Leerzeile besteht), verlässt das Programm mit Hilfe von break
die while-Schleife (Zeile 45). In Zeile 46 wird das Neue-Zeile-Zeichen am Stringende
mit dem Nullzeichen überschrieben. Denken Sie daran, dass Array-Indizes mit 0
beginnen, so dass der Index des letzten Zeichens length-1 lautet.
Wenn eine der beiden Testbedingungen der while-Schleife als unwahr ausgewertet
wird oder die Länge des Eingabestrings kleiner als 2 wird, bricht die Schleife ab und
die Programmausführung springt zu dem aufrufenden Programm zurück - mit der
Anzahl der eingegebenen Zeilen als Rückgabewert der Funktion. Andernfalls wird die
if-Anweisung aus Zeile 47 ausgeführt:
if ((zeilen[n] = (char *)malloc(strlen(puffer)+1)) == NULL)
Diese Anweisung ruft malloc() auf, um Speicher für den gerade eingegebenen String
zu reservieren. Die Funktion strlen() liefert die Länge des an sie übergebenen Strings
zurück. Dieser Wert wird um 1 inkrementiert, so dass malloc() Speicher für den
String plus dem abschließenden Nullzeichen reserviert. Der Ausdruck (char *) direkt
vor malloc() ist eine Typumwandlung, die den Datentyp des von malloc()
zurückgelieferten Zeigers in einen Zeiger auf char zurückliefert (mehr zu
Typumwandlungen an Tag 18).
Die Bibliotheksfunktion malloc() liefert, wie Sie sich vielleicht erinnern, einen Zeiger
zurück. Die Anweisung speichert den Wert des Zeigers, der von malloc()
zurückgeliefert wird, in dem nächsten freien Element des Zeiger-Arrays. Wenn
malloc() den Wert NULL zurückliefert, sorgt die if-Bedingung dafür, dass die
Programmausführung mit dem Rückgabewert -1 an das aufrufende Programm
zurückgeht. Der Code in main() prüft den Rückgabewert von zeilen_einlesen() und
stellt fest, ob ein Wert kleiner Null zurückgeliefert wurde. Falls ja, wird in den Zeilen
23 bis 27 eine Fehlermeldung bezüglich der missglückten Speicherreservierung
ausgegeben und das Programm beendet.
Wenn die Speicherallokation erfolgreich war, ruft das Programm in Zeile 48 die
Funktion strcpy() auf, um den String aus dem temporären Speicher puffer in den
gerade mit malloc() reservierten Speicher zu kopieren. Danach beginnt ein neuer
Schleifendurchgang, und eine weitere Eingabezeile wird eingelesen.
Wenn die Programmausführung von zeilen_einlesen() nach main() zurückkehrt,
sind folgende Aufgaben erledigt (immer vorausgesetzt, dass bei der Speicherallokation
kein Fehler aufgetreten ist):
zeilen[] enthält Zeiger auf die eingelesenen Strings. Die Reihenfolge
der Zeiger in dem Array entspricht der Reihenfolge, in der die Strings eingelesen
wurden.
anzahl_zeilen
festgehalten.
Jetzt kommen wir zum Sortieren. Denken Sie daran, dass wir dazu nicht die Strings
selbst, sondern nur die Zeiger aus dem Array zeilen[] umordnen. Schauen Sie sich
den Code der Funktion sortieren() an. Er enthält zwei ineinander geschachtelte for-
Schleifen (Zeilen 60 bis 71). Die äußere Schleife wird anzahl_zeilen - 1 Male
ausgeführt. Jedes Mal, wenn die äußere Schleife ausgeführt wird, durchläuft die innere
Schleife das Zeiger-Array und vergleicht für alle n von 0 bis anzahl_zeilen - 1 den n-
ten String mit dem n+1-ten String. Den eigentlichen Vergleich führt die
Bibliotheksfunktion strcmp() aus (Zeile 64), der die Zeiger auf die beiden Strings
übergeben werden. Die Funktion strcmp() liefert einen der folgenden Werte zurück:
Wenn strcmp() einen Wert größer Null zurückliefert, bedeutet dies für unser
Programm, dass der erste String größer als der zweite ist und die Strings (d.h. die
Zeiger auf die Strings) vertauscht werden müssen. Dazu wird die temporäre Variable x
benötigt (Zeilen 66 bis 68).
Wenn die Programmausführung aus sortieren()zurückkehrt, sind die Zeiger in
zeilen[] in die gewünschte Reihenfolge gebracht: Der Zeiger auf den »kleinsten«
Strings ist in zeilen[0] abgelegt, der Zeiger auf den »nächstkleineren« String steht in
zeilen[1] und so weiter. Nehmen wir beispielsweise an, Sie hätten die folgenden fünf
Zeilen eingegeben:
Hund
Apfel
Zoo
Programm
Mut
Abbildung 14.5 veranschaulicht die Situation vor dem Aufruf von sortieren(). Wie
das Array nach dem Aufruf von sortieren() aussieht, können Sie Abbildung 14.6
entnehmen.
Abbildung 14.5: Vor dem Sortieren sind die Zeiger in der gleichen Reihenfolge im Array abgelegt, in der die Strings eingegeben wurden.
Abbildung 14.6: Nach dem Sortieren sind die Zeiger nach der alphabetischen Reihenfolge der Strings angeordnet.
Zu guter Letzt ruft das Programm die Funktion strings_ausgeben() auf, die die Liste
der sortierten Strings auf dem Bildschirm anzeigt. Diese Funktion dürfte Ihnen noch
von dem vorangegangenen Beispiel vertraut sein.
Das Programm aus Listings 14.7 ist das komplexeste Programm, dem Sie bisher in diesem Buch begegnet sind. Es nutzt viele der C-Programmiertechniken, die wir in den zurückliegenden Tagen behandelt haben. Mit Hilfe der obigen Erläuterungen sollten Sie in der Lage sein, dem Programmablauf zu folgen und die einzelnen Schritte zu verstehen. Sollten Sie auf Code-Abschnitte stoßen, die Ihnen unverständlich sind, lesen Sie bitte noch einmal die Passagen im Buch, an denen die betreffenden Techniken erklärt werden.
Zeiger auf Funktionen stellen eine weitere Möglichkeit dar, wie man Funktionen aufrufen kann. »Stopp!«, werden Sie sagen. »Wie kann es Zeiger auf Funktionen geben? Zeiger enthalten doch Adressen, in denen Variablen abgespeichert sind.«
Ja und nein. Es ist richtig, dass Zeiger Adressen beinhalten, doch muss dies nicht notwendigerweise die Adresse einer Variablen sein. Wenn ein Programm ausgeführt wird, wird der Code der Funktionen in den Speicher geladen. Dadurch wird jeder Funktion eine Startadresse zugeordnet, an der ihr Code beginnt. Ein Zeiger auf eine Funktion enthält eine solche Startadresse einer Funktion - den Eintrittspunkt der Funktion, mit dem ihre Ausführung beginnt.
Wofür braucht man Zeiger auf Funktionen? Wie schon erwähnt, bieten Zeiger auf Funktionen mehr Möglichkeiten, Funktionen aufzurufen. Zeiger auf Funktionen ermöglichen einem Programm, zwischen mehreren Funktionen auszuwählen und sich für die Funktion zu entscheiden, die unter den gegebenen Umständen am geeignetsten ist.
Wie für alle Variablen in C gilt auch für Zeiger auf Funktionen, dass man sie vor der Verwendung deklarieren muss. Die allgemeine Syntax einer solchen Deklaration sieht wie folgt aus:
typ (*zgr_auf_funk)(parameter_liste);
Obige Anweisung deklariert zgr_auf_funk als Zeiger auf eine Funktion die den
Rückgabetyp typ hat und der die Parameter aus parameter_liste übergeben werden.
Schauen wir uns einige konkrete Beispiele an:
int (*funk1)(int x);
void (*funk2)(double y, double z);
char (*funk3)(char *p[]);
void (*funk4)();
Die erste Zeile deklariert funk1 als Zeiger auf eine Funktion, die ein Argument vom
Typ int übernimmt und einen Wert vom Typ int zurückliefert. Die zweite Zeile
deklariert funk2 als Zeiger auf eine Funktion, die zwei double-Argumente übernimmt
und void als Rückgabetyp hat (also keinen Wert zurückliefert). Die dritte Zeile
deklariert funk3 als Zeiger auf eine Funktion, die ein Array von Zeigern auf char als
Argument übernimmt und einen Wert vom Typ char zurückliefert. Die letzte Zeile
deklariert funk4 als Zeiger auf eine Funktion, die kein Argument übernimmt und void
als Rückgabetyp hat.
Wozu sind die Klammern um den Zeigernamen? Warum kann man das erste Beispiel nicht einfach wie folgt schreiben:
int *funk1(int x);
Der Grund für die Klammern ist die relativ niedrige Priorität des Indirektionsoperators *.
Die Priorität des Indirektionsoperators liegt noch unter der Priorität der Klammern für
die Parameterliste. Obige Deklaration ohne Klammern um den Zeigernamen
deklariert daher funk1 als eine Funktion, die einen Zeiger auf int zurückliefert. (Zu
Funktionen, die einen Zeiger zurückliefern, kommen wir noch weiter unten in dieser
Lektion.) Wenn Sie einen Zeiger auf eine Funktion deklarieren, vergessen Sie also
nicht, den Zeigernamen und den Indirektionsoperator in Klammern zu setzen, oder
Sie handeln sich eine Menge Ärger ein.
Es genügt nicht, einen Zeiger auf eine Funktion zu deklarieren, man muss den Zeiger auch initialisieren, damit er auf etwas verweist. Dieses »Etwas« ist natürlich eine Funktion. Für Funktionen, auf die verwiesen wird, gelten keine besonderen Regeln. Wichtig ist nur, dass Rückgabetyp und Parameterliste der Funktion mit dem Rückgabetyp und der Parameterliste aus der Zeigerdeklaration übereinstimmen. Der folgende Code deklariert und definiert eine Funktion und einen Zeiger auf diese Funktion:
float quadrat(float x); /* Der Funktionsprototyp. */
float (*p)(float x); /* Die Zeigerdeklaration. */
float quadrat(float x) /* Die Funktionsdefinition. */
{
return x * x;
}
Da die Funktion quadrat() und der Zeiger p die gleichen Parameter und
Rückgabetypen haben, können Sie p so initialisieren, dass er auf quadrat zeigt:
p = quadrat;
Danach können Sie die Funktion über den Zeiger aufrufen:
antwort = p(x);
So einfach ist das. Für ein echtes Beispiel kompilieren Sie Listing 14.8 und führen es aus. Das Programm deklariert und initialisiert einen Zeiger auf eine Funktion. Die Funktion wird zweimal aufgerufen, einmal über den Funktionsnamen und beim zweiten Mal über den Zeiger. Beide Aufrufe führen zu demselben Ergebnis.
Listing 14.8: Eine Funktion über einen Funktionszeiger aufrufen.
1: /* Beispiel für Deklaration und Einsatz eines Funktionszeigers.*/
2:
3: #include <stdio.h>
4:
5: /* Der Funktionsprototyp. */
6:
7: double quadrat(double x);
8:
9: /* Die Zeigerdeklaration. */
10:
11: double (*p)(double x);
12:
13: int main(void)
14: {
15: /* p wird mit quadrat initialisiert. */
16:
17: p = quadrat;
18:
19: /* quadrat() wird auf zwei Wegen aufgerufen. */
20: printf("%f %f\n", quadrat(6.6), p(6.6));
21: return(0);
22: }
23:
24: double quadrat(double x)
25: {
26: return x * x;
27: }
43.560000 43.560000
Zeile 7 deklariert die Funktion quadrat(), und Zeile 11 deklariert den Zeiger p auf eine
Funktion mit einem double-Argument und einem double-Rückgabetyp, in
Übereinstimmung mit der Deklaration von quadrat(). Zeile 17 richtet den Zeiger p auf
quadrat, wobei weder für quadrat noch für p Klammern angegeben werden. Zeile 20
gibt die Rückgabewerte der Aufrufe quadrat() und p() aus.
Ein Funktionsname ohne Klammern ist ein Zeiger auf die Funktion (klingt nach dem gleichen Konzept, das wir von den Arrays her kennen, nicht wahr?). Welchen Nutzen bringt es, einen Zeiger auf eine Funktion zu deklarieren und zu verwenden? Der Funktionsname ist eine Zeigerkonstante, die nicht geändert werden kann (wieder die Parallele zu den Arrays). Der Wert einer Zeigervariablen kann dagegen sehr wohl geändert werden. Insbesondere kann die Zeigervariable bei Bedarf auf verschiedene Funktionen gerichtet werden.
Listing 14.9 ruft eine Funktion auf, der ein Integer-Argument übergeben wird. In Abhängigkeit von dem Wert dieses Arguments, richtet die Funktion einen Zeiger auf eine von drei Funktionen und nutzt dann den Zeiger um die betreffende Funktion aufzurufen. Jede der Funktionen gibt eine spezifische Meldung auf den Bildschirm aus.
Listing 14.9: Mit Hilfe eines Funktionszeigers je nach Programmablauf unterschiedliche Funktionen aufrufen.
1: /* Über einen Zeiger verschiedene Funktionen aufrufen. */
2:
3: #include <stdio.h>
4:
5: /* Die Funktionsprototypen. */
6:
7: void funk1(int x);
8: void eins(void);
9: void zwei(void);
10: void andere(void);
11:
12: int main(void)
13: {
14: int a;
15:
16: for (;;)
17: {
18: puts("\nGeben Sie einen Wert (1 - 10) ein, 0 zum Verlassen: ");
19: scanf("%d", &a);
20:
21: if (a == 0)
22: break;
23: funk1(a);
24: }
25: return(0);
26: }
27:
28: void funk1(int x)
29: {
30: /* Der Funktionszeiger. */
31:
32: void (*zgr)(void);
33:
34: if (x == 1)
35: zgr = eins;
36: else if (x == 2)
37: zgr = zwei;
38: else
39: zgr = andere;
40:
41: zgr();
42: }
43:
44: void eins(void)
45: {
46: puts("Sie haben 1 eingegeben.");
47: }
48:
49: void zwei(void)
50: {
51: puts("Sie haben 2 eingegeben.");
52: }
53:
54: void andere(void)
55: {
56: puts("Sie haben einen anderen Wert als 1 oder 2 eingegeben.");
57: }
Geben Sie einen Wert (1 - 10) ein, 0 zum Verlassen:
2
Sie haben 2 eingegeben.
Geben Sie einen Wert (1 - 10) ein, 0 zum Verlassen:
9
Sie haben einen anderen Wert als 1 oder 2 eingegeben.
Geben Sie einen Wert (1 - 10) ein, 0 zum Verlassen:
0
Dieses Programm enthält eine Endlosschleife, die in Zeile 16 beginnt und so lange
ausgeführt wird, bis ein Wert von 0 eingegeben wird. Eingaben ungleich Null werden
an die Funktion funk1() übergeben. Schauen Sie sich Zeile 32 an. Dort wird
innerhalb von funk1() ein Zeiger zgr auf eine Funktion deklariert. Weil zgr innerhalb
der Funktion deklariert wurde, ist er lokal zu funk1() - was sinnvoll ist, da der Zeiger
von anderen Teilen des Programms nicht benötigt wird. In den Zeilen 34 bis 39 weist
die Funktion funk1() dem Zeiger zgr in Abhängigkeit von dem eingegebenen Wert
eine passende Funktion zu. In Zeile 41 erfolgt ein Aufruf von zgr(), wodurch die
betreffende Funktion ausgeführt wird.
Dieses Programm dient natürlich nur der Veranschaulichung. Man hätte das gleiche Ergebnis problemlos auch ohne Funktionszeiger erreichen können.
Schauen wir uns noch einen weiteren Weg an, wie man mit Hilfe von Zeigern verschiedene Funktionen aufrufen kann: Wir übergeben den Zeiger als Argument an eine Funktion. Listing 14.10 ist eine Überarbeitung von Listing 14.9.
Listing 14.10: Einen Zeiger als Argument an eine Funktion übergeben.
1: /* Einen Zeiger als Argument an eine Funktion übergeben. */
2:
3: #include <stdio.h>
4:
5: /* Der Funktionsprototyp. Die Funktion funk1() übernimmt */
6: /* als Argument einen Zeiger auf eine Funktion, die keine */
7: /* Argumente und keinen Rückgabewert hat. */
8:
9: void funk1(void (*p)(void));
10: void eins(void);
11: void zwei(void);
12: void andere(void);
13:
14: int main(void)
15: {
16: /* Der Funktionszeiger. */
18: void (*zgr)(void);
19: int a;
20:
21: for (;;)
22: {
23: puts("\nGeben Sie einen Wert (1 - 10) ein, 0 zum Verlassen: ");
24: scanf("%d", &a);
25:
26: if (a == 0)
27: break;
28: else if (a == 1)
29: zgr = eins;
30: else if (a == 2)
31: zgr = zwei;
32: else
33: zgr = andere;
34: funk1(zgr);
35: }
36: return(0);
37: }
38:
39: void funk1(void (*p)(void))
40: {
41: p();
42: }
43:
44: void eins(void)
45: {
46: puts("Sie haben 1 eingegeben.");
47: }
48:
49: void zwei(void)
50: {
51: puts("Sie haben 2 eingegeben.");
52: }
53:
54: void andere(void)
55: {
56: puts("Sie haben einen anderen Wert als 1 oder 2 eingegeben.");
57: }
Geben Sie einen Wert (1 - 10) ein, 0 zum Verlassen:
2
Sie haben 2 eingegeben.
Geben Sie einen Wert (1 - 10) ein, 0 zum Verlassen:
11
Sie haben einen anderen Wert als 1 oder 2 eingegeben.
Geben Sie einen Wert (1 - 10) ein, 0 zum Verlassen:
0
Beachten Sie die Unterschiede zwischen Listing 14.9 und Listing 14.10. Die
Deklaration des Funktionszeigers wurde nach main() (Zeile 18) verschoben, wo Sie
gebraucht wird. Jetzt ist der Code in main(), der den Zeiger in Abhängigkeit von der
Benutzereingabe (Zeilen 26 bis 33) mit der korrekten Funktion initialisiert. Dann
übergibt main() den initialisierten Zeiger an funk1(). Die Funktion funk1() dient in
Listing 14.10 keinem besonderen Zweck, alles was sie tut, ist die Funktion aufzurufen,
auf die zgr verweist. Dieses Programm dient wiederum nur der Veranschaulichung,
doch die gleichen Techniken können auch in echten Programmen, wie dem
nachfolgenden Beispiel, angewendet werden.
Eine typische Situation, in der man auf Funktionszeiger zurückgreift, ist das Sortieren von Daten. Manchmal möchte man verschiedene Sortierregeln anwenden. Beispielsweise könnten Sie einmal in alphabetischer und ein anderes Mal in umgekehrter alphabetischer Reihenfolge sortieren wollen. Mit Hilfe von Zeigern auf Funktionen können Sie Ihr Programm stets die gewünschte Sortierfunktion aufrufen lassen. In der Praxis werden allerdings üblicherweise keine unterschiedlichen Sortierfunktionen, sondern unterschiedliche Vergleichsfunktionen aufgerufen.
Blättern Sie zurück zu Listing 14.7. In der Funktion sortieren() dieses Programms
wurde die Sortierreihenfolge von dem Rückgabewert der Bibliotheksfunktion strcmp()
bestimmt, die dem Programm mitteilt, ob ein bestimmter String kleiner oder größer
als ein anderer String ist. Wie wäre es, wenn Sie zwei Vergleichsfunktionen schreiben
würden - eine die in alphabetischer Reihenfolge (von A bis Z) und eine die in
umgekehrter alphabetischer Reihenfolge (von Z bis A) sortiert. Das Programm könnte
dann den Anwender entscheiden lassen, in welcher Reihenfolge dieser sortieren
möchte, und mit Hilfe eines Funktionszeigers die zugehörige Vergleichsfunktion
aufrufen. Listing 14.11 erweitert Listing 14.7 um diese Möglichkeit.
Listing 14.11: Mit Funktionszeigern die Sortierreihenfolge steuern.
1: /* Liest Strings von der Tastatur ein, sortiert diese */
2: /* in aufsteigender oder absteigender Reihenfolge */
3: /* und gibt sie auf den Bildschirm aus. */
4: #include <stdlib.h>
5: #include <stdio.h>
6: #include <string.h>
7:
8: #define MAXZEILEN 25
9:
10: int zeilen_einlesen(char *zeilen[]);
11: void sortieren(char *p[], int n, int sort_typ);
12: void strings_ausgeben(char *p[], int n);
13: int alpha(char *p1, char *p2);
14: int umgekehrt(char *p1, char *p2);
15:
16: char *zeilen[MAXZEILEN];
17:
18: int main(void)
19: {
20: int anzahl_zeilen, sort_typ;
21:
22: /* Lies die Zeilen von der Tastatur ein. */
23:
24: anzahl_zeilen = zeilen_einlesen(zeilen);
25:
26: if ( anzahl_zeilen < 0 )
27: {
28: puts("Fehler bei Speicherreservierung");
29: exit(-1);
30: }
31:
32: puts("0 für umgekehrte oder 1 für alphabet. Sortierung :" );
33: scanf("%d", &sort_typ);
34:
35: sortieren(zeilen, anzahl_zeilen, sort_typ);
36: strings_ausgeben(zeilen, anzahl_zeilen);
37: return(0);
38: }
39:
40: int zeilen_einlesen(char *zeilen[])
41: {
42: int n = 0;
43: char puffer[80]; /* Temporärer Speicher für die Zeilen. */
44:
45: puts("Geben Sie einzelne Zeilen ein; Leerzeile zum Beenden.");
46:
47: while (n < MAXZEILEN && fgets(puffer,80,stdin) != 0 &&
puffer[0] != '\n')
48: {
49: if ((zeilen[n] = (char *)malloc(strlen(puffer)+1)) == NULL)
50: return -1;
51: strcpy( zeilen[n++], puffer );
52: }
53: return n;
54:
55: } /* Ende von zeilen_einlesen() */
56:
57: void sortieren(char *p[], int n, int sort_typ)
58: {
59: int a, b;
60: char *x;
61:
62: /* Der Funktionszeiger. */
63:
64: int (*vergleiche)(char *s1, char *s2);
65:
66: /* Initialisiere den Funktionszeiger in Abh. von sort_typ */
67: /* mit der zugehörigen Vergleichsfunktion. */
68:
69: vergleiche = (sort_typ) ? umgekehrt : alpha;
70:
71: for (a = 1; a < n; a++)
72: {
73: for (b = 0; b < n-1; b++)
74: {
75: if (vergleiche(p[b], p[b+1]) > 0)
76: {
77: x = p[b];
78: p[b] = p[b+1];
79: p[b+1] = x;
80: }
81: }
82: }
83: } /* Ende von sortieren() */
84:
85: void strings_ausgeben(char *p[], int n)
86: {
87: int count;
88:
89: for (count = 0; count < n; count++)
90: printf("%s", p[count]);
91: }
92:
93: int alpha(char *p1, char *p2)
94: /* Alphabetischer Vergleich. */
95: {
96: return(strcmp(p2, p1));
97: }
98:
99: int umgekehrt(char *p1, char *p2)
100: /* Umgekehrter alphabetischer Vergleich. */
101: {
102: return(strcmp(p1, p2));
103: }
Geben Sie einzelne Zeilen ein; Leerzeile zum Beenden.
Rosen sind rot
Veilchen sind blau
C gibt's schon lange,
Aber nur grau in grau!
0 für umgekehrte oder 1 für alphabet. Sortierung:
0
Veilchen sind blau
Rosen sind rot
C gibt's schon lange,
Aber nur grau in grau!
Die Zeilen 32 und 33 von main() fordern den Anwender auf, die gewünschte
Sortierreihenfolge anzugeben. Der eingegebene Wert wird in sort_typ abgespeichert.
Weiter unten wird dieser Wert zusammen mit den eingegebenen Zeilen und der
Zeilenanzahl an die Funktion sortieren() übergeben. Die sortieren()-Funktion
wurde in einigen Punkten geändert. In Zeile 64 wird ein Zeiger namens vergleiche
auf eine Funktion eingerichtet, die zwei Zeiger auf char (sprich zwei Strings) als
Argumente übernimmt. In Zeile 69 wird vergleiche auf eine der beiden neu
hinzugekommenen Funktionen gesetzt. Auf welche Funktion vergleiche gesetzt wird,
hängt von dem Wert in sort_typ ab. Die beiden neuen Funktionen heißen alpha()
und umgekehrt(). Die Funktion alpha() verwendet die Bibliotheksfunktion strcmp() in
der gleichen Weise, wie dies auch schon in Listing 14.7 der Fall war. Die Funktion
umgekehrt() vertauscht die Argumente zu strcmp(), so dass eine umgekehrte
Sortierung entsteht.
In den vorangehenden Tagen haben Sie etliche Funktionen aus der C- Standardbibliothek kennen gelernt, die einen Zeiger als Rückgabewert zurückliefern. Selbstverständlich können Sie auch Ihre eigenen Funktionen mit Zeigern als Rückgabewerte aufsetzen. Wie zu erwarten, wird dabei in der Funktionsdeklaration und der Funktions-definition der Indirektionsoperator (*) verwendet. Die allgemeine Form der Deklaration lautet:
typ *funk(parameter_liste);
Diese Anweisung deklariert eine Funktion funk(), die einen Zeiger auf typ
zurückliefert. Hier zwei konkrete Beispiele:
double *funk1(parameter_liste);
struct adresse *funk2(parameter_liste);
Die erste Zeile deklariert eine Funktion, die einen Zeiger auf den Typ double
zurückliefert. Die zweite Zeile deklariert eine Funktion, die einen Zeiger auf den Typ
adresse zurückliefert (adresse ist in diesem Fall eine benutzerdefinierte Struktur).
Verwechseln Sie nicht die Funktionen, die einen Zeiger zurückliefern, mit den Zeigern auf Funktionen. Wenn Sie in der Deklaration ein zusätzliches Klammernpaar setzen, deklarieren Sie einen Zeiger auf eine Funktion - wie in dem folgenden Beispiel:
double (*funk)(...); /* Zeiger auf Funktion, die double zurückgibt. */
double *funk(...); /* Funktion, die Zeiger auf double zurückgibt. */
Nachdem wir uns mit der Deklarationssyntax vertraut gemacht haben, stellt sich die Frage, wie man Funktionen, die Zeiger zurückliefern, verwendet? Es gibt keine speziellen Regeln für diese Funktionen - sie werden wie alle anderen Funktionen eingesetzt, ihr Rückgabewert wird einer Variablen passenden Typs (in diesem Fall einem Zeiger) zugewiesen. Da der Funktionsaufruf einem C-Ausdruck entspricht, kann er überall eingesetzt werden, wo Sie auch einen Zeiger des entsprechenden Typs verwenden würden.
Listing 14.12 zeigt ein einfaches Beispiel: eine Funktion, die zwei Argumente
übernimmt und bestimmt, welches Argument größer ist. Das Listing realisiert dies auf
zwei verschiedene Arten: Eine Funktion liefert einen int-Wert zurück, die andere
Funktion liefert einen Zeiger auf int zurück.
Listing 14.12: Zeiger aus Funktionen zurückliefern.
1: /* Funktion, die einen Zeiger zurückliefert. */
2:
3: #include <stdio.h>
4:
5: int groesser1(int x, int y);
6: int *groesser2(int *x, int *y);
7:
8: int main(void)
9: {
10: int a, b, bigger1, *bigger2;
11:
12: printf("Geben Sie zwei Integer-Werte ein: ");
13: scanf("%d %d", &a, &b);
14:
15: bigger1 = groesser1(a, b);
16: printf("Der größere Wert ist %d.\n", bigger1);
17: bigger2 = groesser2(&a, &b);
18: printf("Der größere Wert ist %d.\n", *bigger2);
19: return(0);
20: }
21:
22: int groesser1(int x, int y)
23: {
24: if (y > x)
25: return y;
26: return x;
27: }
28:
29: int *groesser2(int *x, int *y)
30: {
31: if (*y > *x)
32: return y;
33:
34: return x;
35: }
Geben Sie zwei Integer-Werte ein: 1111 3000
Der größere Wert ist 3000.
Der größere Wert ist 3000.
Dieses Programm ist nicht schwer nachzuvollziehen. Die Zeilen 5 und 6 enthalten die
Prototypen für die beiden Funktionen. Die erste, groesser1(), übernimmt zwei int-
Variablen und liefert einen int-Wert zurück. Die zweite, groesser2(), übernimmt zwei
Zeiger auf int-Variablen und liefert einen Zeiger auf int zurück. Die main()-Funktion,
Zeilen 8 bis 20, folgt dem üblichen Schema. Zeile 10 deklariert vier Variablen. a und b
nehmen die Werte auf, die verglichen werden sollen. bigger1 und bigger2 nehmen die
Rückgabewerte der Funktionen groesser1() and groesser2() auf. Beachten Sie, dass
bigger2 ein Zeiger auf int ist, während es sich bei bigger1 um eine einfache int-
Variable handelt.
Zeile 15 ruft groesser1() mit den beiden int-Argumenten a und b auf. Der von der
Funktion zurückgelieferte Wert wird bigger1 zugewiesen und in Zeile 16 ausgegeben.
Zeile 17 ruft groesser2() mit den Adressen der beiden int-Variablen auf. Der von der
Funktion zurückgelieferte Zeiger wird bigger2, also einem Zeiger, zugewiesen. In der
darauf folgenden Zeile wird dieser Wert dereferenziert und ausgegeben.
Die beiden Vergleichsfunktionen sind sich sehr ähnlich. Beide vergleichen die
übergebenen Werte und liefern den größeren zurück. Der Unterschied zwischen
beiden Funktionen ist, dass groesser2() mit Zeigern arbeitet und groesser1() nicht.
Beachten Sie, dass groesser2() den Dereferenzierungsoperator im Vergleich aber
nicht in den return-Anweisungen in den Zeilen 32 und 34 verwendet.
Häufig hat man, wie in Listing 14.12, die Wahl, ob man eine Funktion schreibt, die einen Wert oder einen Zeiger zurückliefert. Für welche Option man sich entscheidet, hängt von den Bedürfnissen des Programms ab - hauptsächlich davon, wie man den Rückgabewert weiter verwenden möchte.
Eine verkettete Liste ist eine effiziente Methode zur Datenspeicherung, die sich in C leicht implementieren lässt. Warum behandeln wir die verketteten Listen zusammen mit den Zeigern? Weil, wie Sie schon bald sehen werden, Zeiger für die Implementierung von verketteten Listen unabdingbar sind.
Es gibt verschiedene Arten von verketteten Listen: einfach verkettete Listen, doppelt verkettete Listen und binäre Bäume. Jede dieser Formen ist für bestimmte Aufgaben der Datenspeicherung besonders geeignet. Allen gemeinsam ist, dass die Verkettung der Datenelemente durch Informationen hergestellt wird, die in den Datenelementen selbst - in Form von Zeigern - abgelegt sind. Dies ist ein gänzlich anderes Konzept, als wir es beispielsweise von Arrays kennen, wo die Verknüpfung der Datenelemente durch das Speicherlayout des Arrays festgelegt wird. Der folgende Abschnitt beschreibt die grundlegendste Form der verketteten Liste: die einfach verkettete Liste (die ich im Folgenden einfach als verkettete Liste bezeichnen werde).
Die Elemente einer verketteten Liste werden in Strukturen gekapselt. (Was Strukturen sind, haben Sie bereits am Tag 10, »Strukturen«, gelernt.) Die Struktur definiert die Datenelemente, die zum Abspeichern der jeweiligen Daten benötigt werden. Was für Datenelemente das sind, hängt von den Bedürfnissen des jeweiligen Programms ab. Darüber hinaus gibt es noch ein weiteres Datenelement - einen Zeiger. Dieser Zeiger stellt die Verbindung zwischen den Elementen der verketteten Liste her. Schauen wir uns ein einfaches Beispiel an:
struct person {
char name[20];
struct person *next; // Zeiger auf nächstes Element
};
Dieser Code definiert eine Struktur namens person. Zur Aufnahme der Daten enthält
person ein 20-elementiges Array von Zeichen. In der Realität würden Sie für die
Verwaltung so einfacher Daten keine verkettete Liste verwenden, aber für ein
einführendes Beispiel ist es gut, die Struktur einfach zu halten. Zusätzlich enthält die
Struktur person noch einen Zeiger auf den Typ person - also einen Zeiger auf eine
andere Struktur des gleichen Typs. Dies bedeutet, dass Strukturen vom Typ person
nicht nur Daten aufnehmen, sondern auch auf eine andere person-Struktur verweisen
können. Abbildung 14.7 zeigt, wie man Strukturen auf diese Weise zu einer Liste
verketten kann.
Abbildung 14.7: Verknüpfungen in einer verketteten Liste.
Beachten Sie, dass in Abbildung 14.7 jede person-Struktur auf die jeweils
nachfolgende person-Struktur verweist. Die letzte person-Struktur zeigt auf nichts. Das
letzte Element einer verketteten Liste ist dadurch gekennzeichnet, dass seinem
Zeigerelement der Wert NULL zugewiesen wurde.
Die Strukturen, aus denen verkettete Listen aufgebaut werden, bezeichnet man als Elemente, Links oder Knoten der verketteten Liste.
Wie der letzte Knoten einer verketteten Liste identifiziert wird, haben Sie nun
gesehen. Wie sieht es aber mit dem ersten Knoten aus? Dieser wird durch einen
speziellen Zeiger (keine Struktur) identifiziert, den so genannten Head1-Zeiger. Der
Head-Zeiger verweist immer auf das erste Elemente der verketteten Liste. Das erste
Element enthält einen Zeiger auf das zweite Elemente, das zweite Element enthält
einen Zeiger auf das dritte Element und so weiter bis Sie auf ein Element treffen,
dessen Zeiger NULL ist. Wenn die Liste leer ist (keine Verknüpfungen enthält), wird der
Head-Zeiger auf NULL gesetzt. Abbildung 14.8 zeigt den Head-Zeiger vor dem
Anlegen der Liste und nach dem Einfügen des ersten Elements.
Abbildung 14.8: Der Head-Zeiger einer verketteten Liste.
Der Head-Zeiger ist ein Zeiger auf das erste Element einer verketteten Liste. Er wird manchmal auch als Top- oder Wurzelzeiger (root) bezeichnet.
Mit verketteten Listen zu programmieren, bedeutet, Elemente (oder Knoten) einzufügen, zu löschen und zu bearbeiten. Das Bearbeiten von Elementen stellt keine besondere Herausforderung dar, wohl aber das Einfügen und Löschen von Elementen. Wie ich bereits dargelegt habe, sind die Elemente einer Liste durch Zeiger miteinander verbunden. Ein Großteil der Arbeit beim Einfügen und Löschen von Elementen besteht aus der Manipulation dieser Zeiger. Wie diese Manipulationen im Einzelnen aussehen, hängt davon ab, ob die Elemente am Anfang, in der Mitte oder am Ende der Liste eingefügt werden.
Etwas weiter unten in diesem Kapitel finden Sie ein einfaches
Demonstrationsprogramm und ein etwas komplizierteres, praxisorientiertes
Programm. Bevor wir in die unvermeidbaren Details dieser Programme abtauchen,
sollten wir uns vorab noch mit einigen der wichtigsten Aufgaben bei der
Programmierung mit verketteten Listen vertraut machen. Dazu verwenden wir
weiterhin die Struktur person, die weiter oben eingeführt wurde.
Bevor Sie darangehen, eine verkettete Liste aufzubauen, müssen Sie eine
Datenstruktur für die Liste definieren und den Head-Zeiger deklarieren. Da die Liste
zu Anfang leer ist, sollte der Head-Zeiger mit NULL initialisiert werden. Ein weiterer
Zeiger auf den Strukturtyp der Liste wird zum Einfügen von Daten benötigt. (Unter
Umständen benötigt man mehr als einen Zeiger; dazu später mehr.) Hier der
zugehörige Code:
struct person {
char name[20];
struct person *next;
};
struct person *neu;
struct person *head;
head = NULL;
Wenn der Head-Zeiger NULL ist, ist die Liste leer und das neue Element wird das
einzige Element der Liste sein. Wenn der Head-Zeiger nicht NULL ist, enthält die Liste
bereits eines oder mehrere Elemente. Die Vorgehensweise zum Einfügen eines neuen
Elements am Anfang der Liste ist in beiden Fällen jedoch die gleiche:
malloc() zur
Speicherreservierung nutzen können.
next-Zeiger des neuen Elements auf den aktuellen Wert des Head-
Zeigers. Der aktuelle Wert ist NULL, wenn die Liste leer ist; andernfalls ist es die
Adresse des Elements, das augenblicklich noch an erster Stelle steht.
Der zugehörige Code sieht wie folgt aus;
neu = (person*)malloc(sizeof(struct person));
neu->next = head;
head = neu;
Beachten Sie die Typumwandlung für malloc(), die den Rückgabewert in den
gewünschten Typ, einen Zeiger auf die Datenstruktur person, konvertiert. Denken Sie
auch daran, dass der Wert von head in der zweiten Zeile für leere Listen NULL ist.
Es ist wichtig, die korrekte Reihenfolge bei der Umordnung der Zeiger einzuhalten. Wenn Sie zuerst den Head-Zeiger umbiegen, verlieren Sie die Verbindung zur Liste.
Abbildung 14.9 verdeutlicht das Einfügen eines neuen Elements in eine leere Liste, Abbildung 14.10 illustriert das Einfügen eines neuen Elements in eine bestehende Liste.
Abbildung 14.9: Einfügen eines neuen Elements in eine bestehende Liste.
Abbildung 14.10: Einfügen eines neuen Elements in eine leere Liste.
Beachten Sie, dass mit Hilfe von malloc() Speicher für das neue Element reserviert
wird. Grundsätzlich reserviert man für jedes neu einzufügende Element Speicher,
gerade so viel, wie für das Element benötigt wird. Statt malloc() hätte man auch die
Funktion calloc() verwenden können, die den Speicherplatz für das neue Element
nicht nur reserviert, sondern auch initialisiert.
In dem obigen Code-Fragment wurde darauf verzichtet, anhand des Rückgabewerts von
malloc()zu überprüfen, ob die Speicherreservierung erfolgreich war. In einem echten Programm sollten Sie die Rückgabewerte der Speicherreservierungsfunktionen stets überprüfen.
Wenn möglich, sollten Sie Zeiger bei der Deklaration stets mit dem Wert
Nullinitialisieren. Lassen Sie keine Zeiger uninitialisiert, sonst laufen Sie Gefahr, sich unnötigen Ärger einzuhandeln.
Um ein Element am Ende einer verketteten Liste einzufügen, muss man - beginnend mit dem Head-Zeiger - die ganze Liste durchgehen, bis man beim letzten Element ankommt. Ist das Element gefunden, geht man wie folgt vor:
malloc() zur
Speicherreservierung nutzen können.
next-Zeiger des letzten Elements auf das neue Element (dessen
Adresse von malloc() zurückgeliefert wurde).
next-Zeiger des neuen Elements auf NULL, um anzuzeigen, dass
dieses Element das letzte Element in der Liste ist.
person *aktuell;
...
aktuell = head;
while (aktuell->next != NULL)
aktuell = aktuell->next;
neu = (person*)malloc(sizeof(struct person));
aktuell->next = neu;
neu->next = NULL;
Abbildung 14.11 illustriert das Einfügen eines neuen Elements am Ende einer verketteten Liste.
Abbildung 14.11: Einfügen eines neuen Elements am Ende einer Liste.
Wenn Sie häufiger mit verketteten Listen arbeiten, werden Sie feststellen, dass die meisten Einfügeoperationen irgendwo in der Mitte der Liste stattfinden. Wo genau ein neues Element dabei einzufügen ist, hängt von der Organisation der Liste ab - beispielsweise wenn die Liste nach einem oder mehreren Datenelementen sortiert ist. Sie müssen also zuerst die Position in der Liste bestimmen, wo das neue Element hingehört, und dann das Element einfügen. Im Einzelnen schließt dies folgende Schritte ein:
malloc() zur
Speicherreservierung nutzen können.
next-Zeiger des Marker-Elements auf das neue Element (dessen
Adresse von malloc() zurückgeliefert wurde).
next-Zeiger des neuen Elements auf das Element, auf das bisher
das Marker-Element verwiesen hat.
Als Code könnte das wie folgt aussehen:
person *marker;
/* Hier steht der Code, der den Marker auf die gewünschte
Einfügeposition setzt. */
...
neu = (person*)malloc(sizeof(PERSON));
neu->next = marker->next;
marker->next = neu;
Abbildung 14.12 veranschaulicht diese Operation.
Abbildung 14.12: Einfügen eines neuen Elements in der Mitte einer Liste.
Um ein Element aus einer verketteten Liste zu löschen, muss man lediglich die entsprechenden Zeiger umsetzen. Welche Zeiger dabei wie umzusetzen sind, hängt davon ab, wo das zu löschende Element lokalisiert ist:
next-Zeiger des vorletzten
Elements auf NULL.
next-Zeiger des
vorangehenden Elements auf das Element hinter dem zu löschenden Element
setzt.
Zusätzlich sollte der Speicher des Elements, das aus der Liste gelöscht wurde, wieder
freigegeben werden, damit das Programm keinen Speicher belegt, den es nicht
benötigt (ansonsten spricht man von einem Speicherleck). Das Freigeben des
Speichers erfolgt mit Hilfe der Funktion free(). Der folgende Code zeigt, wie das
erste Element einer verketteten Liste gelöscht wird:
free(head);
head = head->next;
Dieser Code löscht das letzte Element aus einer Liste mit zwei oder mehr Elementen:
person *aktuell1, *aktuell2;
aktuell1 = head;
aktuell2= aktuell1->next;
while (aktuell2->next != NULL)
{
aktuell1 = aktuell2;
aktuell2= aktuell1->next;
}
free(aktuell1->next);
aktuell1->next = NULL;
if (head == aktuell1)
head = NULL;
Der folgende Code schließlich löscht ein Element aus der Mitte einer Liste:
person *aktuell1, *aktuell2;
/* Hier steht Code, der aktuell1 auf das Element direkt */
/* vor dem zu löschenden Element richtet. */
aktuell2 = aktuell1->next;
free(aktuell1->next);
aktuell1->next = aktuell2->next;
Listing 14.13 veranschaulicht Einsatz und Verwendung verketteter Listen. Das Programm dient ausschließlich Demonstrationszwecken; es akzeptiert keine Benutzereingaben und hat keinen praktischen Nutzen - aber es führt Ihnen den Code vor, der für die Implementierung der wichtigsten Listenoperationen benötigt wird. Im Einzelnen macht das Programm Folgendes:
Listing 14.13: Grundlegende Operationen verketteter Listen.
1: /* Veranschaulicht den grundlegenden Einsatz */
2: /* verketteter Listen. */
3:
4: #include <stdlib.h>
5: #include <stdio.h>
6: #include <string.h>
7:
8: /* Die Struktur für die Listendaten. */
9: struct daten {
10: char name[20];
11: struct daten *next;
12: };
13:
14: /* Definiere typedefs für die Struktur und die darauf */
15: /* gerichteten Zeiger. */
16: typedef struct daten PERSON;
17: typedef PERSON *LINK;
18:
19: int main(void)
20: {
21: /* Zeiger für Head, neues und aktuelles Element. */
22: LINK head = NULL;
23: LINK neu = NULL;
24: LINK aktuell = NULL;
25:
26: /* Erstes Listenelement einfügen. Wir gehen nicht davon */
27: /* aus, dass die Liste leer ist, obwohl dies in */
28: /* diesem Demoprogramm der Fall ist. */
29:
30: neu = (LINK)malloc(sizeof(PERSON));
31: neu->next = head;
32: head = neu;
33: strcpy(neu->name, "Abigail");
34:
35: /* Element am Ende der Liste anhängen. Wir gehen davon aus, */
36: /* dass die Liste mindestens ein Element enthält. */
37:
38: aktuell = head;
39: while (aktuell->next != NULL)
40: {
41: aktuell = aktuell->next;
42: }
43:
44: neu = (LINK)malloc(sizeof(PERSON));
45: aktuell->next = neu;
46: neu->next = NULL;
47: strcpy(neu->name, "Katharina");
48:
49: /* Ein neues Element an der zweiten Position einfügen. */
50: neu = (LINK)malloc(sizeof(PERSON));
51: neu->next = head->next;
52: head->next = neu;
53: strcpy(neu->name, "Beatrice");
54:
55: /* Alle Datenelemente der Reihe nach ausgeben. */
56: aktuell = head;
57: while (aktuell != NULL)
58: {
59: printf("%s\n", aktuell->name);
60: aktuell = aktuell->next;
61: }
62:
63: printf("\n");
64: return(0);
65: }
Abigail
Beatrice
Katharina
Einen Großteil des Codes werden Sie sicherlich schon selbst entschlüsseln können.
Die Zeilen 9 bis 12 deklarieren die Datenstruktur für die Liste. Die Zeilen 16 und 17
definieren die typedefs für die Datenstruktur und für einen Zeiger auf die
Datenstruktur. An sich wäre dies nicht notwendig, aber es vereinfacht das Aufsetzen
des Codes, da man danach statt struct daten einfach PERSON und statt struct daten*
einfach LINK schreiben kann.
In den Zeilen 22 bis 24 werden ein Head-Zeiger und einige weitere Zeiger deklariert,
die für die Bearbeitung der Liste benötigt werden. Alle diese Zeiger werden mit NULL
initialisiert.
Die Zeilen 30 bis 33 fügen am Kopf der Liste einen neuen Knoten ein. Zeile 30
reserviert Speicher für die neue Datenstruktur. Ich möchte Sie noch einmal darauf
aufmerksam machen, dass wir hier einfach davon ausgehen, dass die
Speicherreservierung mit malloc() erfolgreich war - etwas, das Sie in echten
Programmen niemals tun sollten.
Zeile 31 richtet den next-Zeiger der neuen Struktur auf die Adresse, auf die der Head-
Zeiger verweist. Warum weist man dem Zeiger nicht einfach NULL zu? Weil dies nur
gut geht, wenn man weiß, dass die Liste leer ist. So wie der Code im Listing aufgesetzt
ist, funktioniert er auch dann, wenn die Liste bereits Elemente enthält. Das neue erste
Element weist danach auf das Element, das zuvor das erste in der Liste war - ganz so,
wie wir es haben wollten.
Zeile 32 richtet den Head-Zeiger auf das neue Element, und Zeile 33 speichert Daten in dem Element.
Das Hinzufügen eines Elements am Ende der Liste ist etwas komplizierter. In diesem
Beispiel wissen wir zwar, dass die Liste nur ein Element enthält, doch davon kann
man in echten Programmen nicht ausgehen. Es ist daher unumgänglich, die Liste
Element für Element durchzugehen - so lange, bis das letzte Element (gekennzeichnet
durch den auf NULL weisenden next-Zeiger) gefunden ist. Dann können Sie sicher sein,
sich am Ende der Liste zu befinden. Die Zeilen 38 bis 42 erledigen dies für uns.
Nachdem das letzte Element gefunden wurde, müssen wir nur noch Speicher für die
neue Datenstruktur reservieren, das alte letzte Listenelement auf diesen richten und
den next-Zeiger des neuen Elements auf NULL setzen, um anzuzeigen, dass dieses
Element jetzt das letzte Element der Liste ist. Dies geschieht in den Zeilen 44 bis 47.
Beachten Sie, dass der Rückgabewert von malloc() in den Typ LINK umgewandelt
wird. (An Tag 18 erfahren Sie mehr über Typumwandlungen.)
Die nächste Aufgabe besteht darin, ein Element in der Mitte der Liste einzufügen - in
diesem Fall an der zweiten Position. Nachdem Speicher für eine zweite Datenstruktur
allokiert wurde (Zeile 50), wird der next-Zeiger des neuen Elements auf das Element
gesetzt, das früher das zweite Element in der Liste bildete und jetzt das dritte Element
ist (Zeile 51). Danach wird der next-Zeiger des ersten Elements auf das neue Element
gerichtet (Zeile 52).
Zum Schluss gibt das Programm die Daten aller Elemente der verketteten Liste aus,
wozu man die Liste einfach Element für Element durchgeht. Begonnen wird mit dem
Element, auf das der Head-Zeiger verweist. Das letzte Element ist erreicht, wenn man
auf den NULL-Zeiger stößt. Der zugehörige Code steht in den Zeilen 56 bis 61.
Nachdem Sie jetzt wissen, wie man Elemente in Listen einfügt, ist es an der Zeit, sich anzuschauen, wie Listen in der Praxis eingesetzt werden. Listing 14.14 enthält ein etwas umfangreicheres Programm, das eine verkettete Liste zum Abspeichern einer Liste von fünf Zeichen verwendet. Diese Zeichen werden im Arbeitsspeicher in Form einer verketteten Liste abgelegt. Statt Zeichen hätte man genauso gut Namen, Adressen oder irgendwelche andere Daten nehmen können. Um aber das Beispiel so einfach wie möglich zu halten, habe ich mich für einzelne Zeichen entschieden.
Was dieses Programm kompliziert macht, ist der Umstand, dass die Elemente beim Einfügen sortiert werden. Dies ist aber auch genau das, was das Programm so wertvoll und interessant macht. Je nach ihrem Wert werden die Elemente am Anfang, am Ende oder irgendwo in der Mitte der Liste eingefügt, so dass die Liste stets sortiert bleibt. Würden Sie ein Programm schreiben, dass die Elemente einfach an das Ende der Liste anhängt, wäre die Programmlogik wesentlich einfacher; das Programm wäre aber auch nicht so nützlich.
Listing 14.14: Implementierung einer verketteten Liste von Zeichen.
1: /*=============================================================*
2: * Programm: list1414.c *
3: * Buch: C Programmierung für Linux in 21 Tagen *
4: * Zweck: Implementierung einer verketteten Liste *
5: *=============================================================*/
6: #include <stdio.h>
7: #include <stdlib.h>
8:
9: #ifndef NULL
10: #define NULL 0
11: #endif
12:
13: /* Datenstruktur der Liste */
14: struct list
15: {
16: int ch; /* Verwende int zum Aufnehmen der Zeichen. */
17: struct list *next_el; /* Zeiger auf nächstes Listenelement. */
18: };
19:
20: /* typedefs für Struktur und Zeiger. */
21: typedef struct list LIST;
22: typedef LIST *LISTZGR;
23:
24: /* Funktionsprototypen. */
25: LISTZGR in_Liste_einfuegen( int, LISTZGR );
26: void Liste_ausgeben(LISTZGR);
27: void Listenspeicher_freigeben(LISTZGR);
28:
29: int main( void )
30: {
31: LISTZGR first = NULL; /* Head-Zeiger */
32: int i = 0;
33: int ch;
34: char trash[256]; /* um stdin-Puffer zu leeren. */
35:
36: while ( i++ < 5 ) /* Liste aus 5 Elementen aufbauen */
37: {
38: ch = 0;
39: printf("\nGeben Sie Zeichen %d ein, ", i);
40:
41: do
42: {
43: printf("\nMuss zwischen a und z liegen: ");
44: ch = getc(stdin); /* nächstes Zeichen einlesen */
45: fgets(trash,256,stdin); /* Müll aus stdin löschen */
46: } while( (ch < 'a' || ch > 'z') && (ch < 'A' || ch > 'Z'));
47:
48: first = in_Liste_einfuegen( ch, first );
49: }
50:
51: Liste_ausgeben( first ); /* Ganze Liste ausgeben */
52: Listenspeicher_freigeben( first ); /* Speicher freigeben */
53: return(0);
54: }
55:
56: /*========================================================*
57: * Funktion : in_Liste_einfuegen()
58: * Zweck : Fügt ein neues Element in die Liste ein
59: * Parameter : int ch = abzuspeicherndes Zeichen
60: * LISTZGR first = Adresse des urspr. Head-Zeigers
61: * Rückgabe : Adresse des Head-Zeigers (first)
62: *========================================================*/
63:
64: LISTZGR in_Liste_einfuegen( int ch, LISTZGR first )
65: {
66: LISTZGR new_el = NULL; /* Adresse des neuen Elements */
67: LISTZGR tmp_el = NULL; /* temporäres Element */
68: LISTZGR prev_el = NULL; /* Adresse des vorangehenden Elements */
69:
70: /* Speicher reservieren. */
71: new_el = (LISTZGR)malloc(sizeof(LIST));
72: if (new_el == NULL) /* Speicherallokation misslungen */
73: {
74: printf("\nSpeicherallokation fehlgeschlagen!\n");
75: exit(1);
76: }
77:
78: /* Links für neues Element setzen */
79: new_el->ch = ch;
80: new_el->next_el = NULL;
81:
82: if (first == NULL) /* Erstes Element in Liste einfügen */
83: {
84: first = new_el;
85: new_el->next_el = NULL; /* zur Sicherheit */
86: }
87: else /* nicht das erste Element */
88: {
89: /* vor dem ersten Element einfügen? */
90: if ( new_el->ch < first->ch)
91: {
92: new_el->next_el = first;
93: first = new_el;
94: }
95: else /* in Mitte oder am Ende einfügen? */
96: {
97: tmp_el = first->next_el;
98: prev_el = first;
99:
100: /* wo wird das Element eingefügt? */
101:
102: if ( tmp_el == NULL )
103: {
104: /* zweites Element am Ende einfügen */
105: prev_el->next_el = new_el;
106: }
107: else
108: {
109: /* in der Mitte einfügen? */
110: while (( tmp_el->next_el != NULL))
111: {
112: if( new_el->ch < tmp_el->ch )
113: {
114: new_el->next_el = tmp_el;
115: if (new_el->next_el != prev_el->next_el)
116: {
117: printf("FEHLER");
118: getc(stdin);
119: exit(0);
120: }
121: prev_el->next_el = new_el;
122: break; /* Element ist eingefügt; while beenden*/
123: }
124: else
125: {
126: tmp_el = tmp_el->next_el;
127: prev_el = prev_el->next_el;
128: }
129: }
130:
131: /* am Ende einfügen? */
132: if (tmp_el->next_el == NULL)
133: {
134: if (new_el->ch < tmp_el->ch ) /* vor Ende */
135: {
136: new_el->next_el = tmp_el;
137: prev_el->next_el = new_el;
138: }
139: else /* am Ende */
140: {
141: tmp_el->next_el = new_el;
142: new_el->next_el = NULL; /* zur Sicherheit */
143: }
144: }
145: }
146: }
147: }
148: return(first);
149: }
150:
151: /*========================================================*
152: * Funktion: Liste_ausgeben
153: * Zweck : Informationen über Zustand der Liste ausgeben
154: *========================================================*/
155:
156: void Liste_ausgeben( LISTZGR first )
157: {
158: LISTZGR akt_zgr;
159: int counter = 1;
160:
161: printf("\n\nElement-Adr Position Daten Nachfolger\n");
162: printf("=========== ======== ===== ===========\n");
163:
164: akt_zgr = first;
165: while (akt_zgr != NULL )
166: {
167: printf(" %X ", akt_zgr );
168: printf(" %2i %c", counter++, akt_zgr->ch);
169: printf(" %X \n",akt_zgr->next_el);
170: akt_zgr = akt_zgr->next_el;
171: }
172: }
173:
174: /*========================================================*
175: * Funktion: Listenspeicher_freigeben
176: * Zweck : Gibt den für die Liste reservierten Speicher frei
177: *========================================================*/
178:
179: void Listenspeicher_freigeben(LISTZGR first)
180: {
181: LISTZGR akt_zgr, next_el;
182: akt_zgr = first; /* Am Anfang starten */
183:
184: while (akt_zgr != NULL) /* Bis zum Listenende */
185: {
186: next_el = akt_zgr->next_el; /* Adresse des nächsten Elementes */
187: free(akt_zgr); /* Aktuelles Elem freigeben */
188: akt_zgr = next_el; /* Neues aktuelles Element */
189: }
190: }
Geben Sie Zeichen 1 ein,
Muss zwischen a und z liegen: q
Geben Sie Zeichen 2 ein,
Muss zwischen a und z liegen: b
Geben Sie Zeichen 3 ein,
Muss zwischen a und z liegen: z
Geben Sie Zeichen 4 ein,
Muss zwischen a und z liegen: c
Geben Sie Zeichen 5 ein,
Muss zwischen a und z liegen: a
Element-Adr Position Daten Nachfolger
=========== ======== ===== ===========
0x8049ae8 1 a 0x8049b18
0x8049b18 2 b 0x8049af8
0x8049af8 3 c 0x8049b08
0x8049b08 4 q 0x8049b28
0x8049b28 5 z 0
Auf Ihrem Bildschirm werden wahrscheinlich andere
Adresswerte angezeigt.
Dieses Programm demonstriert, wie man ein Element in eine verkettete Liste einfügt. Das Listing ist nicht einfach zu verstehen. Wenn Sie den Code langsam durchgehen, werden Sie jedoch feststellen, dass das Programm letztlich eine Kombination aus den drei Einfügeoperationen darstellt, die wir bereits weiter oben diskutiert haben. Man kann es zum Einfügen am Beginn, in der Mitte und am Ende einer verketteten Liste verwenden. Des Weiteren werden in diesem Listing auch die Spezialfälle zum Einfügen des ersten und zweiten Elements behandelt.
Der einfachste Weg, sich mit diesem Listing vertraut zu machen, besteht darin, das Programm Zeile für Zeile im DDD-Debugger auszuführen und dazu die nachfolgende Analyse zu lesen. Wenn Sie die Ausführung des Programms verfolgen, werden Sie das Listing besser verstehen. Mit Hilfe des Befehls View/Data Window können Sie sich eine grafische Präsentation Ihrer verketteten Liste anzeigen lassen (siehe Abbildung 14.13).
Etliche Abschnitte am Anfang von Listing 14.14 sollten Ihnen vertraut oder zumindest
leicht zu verstehen sein. In den Zeilen 9 bis 11 wird überprüft, ob der Wert NULL
bereits definiert ist. Wenn nicht, wird er in Zeile 10 als 0 definiert. Die Zeilen 14 bis
22 definieren die Struktur für die verkettete Liste und die Typen, die die weitere
Arbeit mit der Struktur und den Zeigern vereinfachen sollen.
Abbildung 14.13: DDD mit dem first-Zeiger und einer zweielementigen verketteten Liste im Datenfenster.
Die Vorgänge in der main()-Funktion sollten leicht nachzuvollziehen sein. In Zeile 31
wird ein Head-Zeiger namens first deklariert und mit NULL initialisiert. Denken Sie
daran, Zeiger niemals uninitialisiert zu lassen. Die Zeilen 36 bis 49 enthalten eine
while-Schleife, mit der fünf Buchstaben über die Tastatur eingelesen werden.
Innerhalb dieser äußeren while-Schleife, die fünfmal wiederholt wird, stellt eine
do...while-Konstruktion sicher, dass es sich bei den eingegebenen Zeichen um
Buchstaben handelt. In der Bedingung dieser Schleife hätte man auch die Funktion
isalpha() verwenden können.
Wurde ein Buchstabe erfolgreich eingelesen, wird die Funktion in_Liste_einfuegen()
aufgerufen, der die einzufügenden Daten und der Zeiger auf den Anfang der Liste
übergeben werden.
Die main()-Funktion endet mit den Aufrufen der Funktionen Liste_ausgeben()zum
Ausgeben der Listendaten und Listenspeicher_freigeben()zum Freigeben des
Speichers, der für die Listenelemente reserviert wurde. Beide Funktionen sind ähnlich
aufgebaut. Beide beginnen am Anfang der Liste (Head-Zeiger first) und wandern mit
Hilfe einer while-Schleife und dem next_zgr-Wert von einem Element zum nächsten.
Wenn next_zgr gleich NULL ist, ist das Ende der verketteten Liste erreicht, und die
Funktion wird beendet.
Die wichtigste (und komplizierteste) Funktion in diesem Listing ist unzweifelhaft die
Funktion in_Liste_einfuegen(), die in den Zeilen 56 bis 149 definiert ist. Die Zeilen
66 bis 68 deklarieren drei Zeiger, die auf die verschiedenen Elemente verweisen. Der
Zeiger new_el verweist auf das Element, das neu eingefügt werden soll. Der Zeiger
tmp_el wird auf das aktuelle Element gesetzt, das gerade bearbeitet wird. Gibt es mehr
als ein Element in der Liste, wird der Zeiger prev_el verwendet, um auf das zuvor
besuchte Element zu verweisen.
Zeile 71 reserviert Speicher für das Element, das neu hinzugefügt werden soll. Dem
Zeiger new_el wird der von malloc() zurückgelieferte Wert zugewiesen. Falls der
angeforderte Speicher nicht reserviert werden kann, wird in den Zeilen 74 und 75
eine Fehlermeldung ausgegeben und das Programm beendet. Kann der Speicher
erfolgreich reserviert werden, wird das Programm fortgesetzt.
Zeile 79 speichert die Daten in der Struktur. In unserem Beispielprogramm bedeutet
dies, dass der Buchstabe, der dem ch-Parameter der Funktion übergeben wurde, an
das Zeichenfeld (new_el->ch) des neuen Listenelements übergeben wird. In
komplexeren Programmen würden wahrscheinlich mehrere Datenfelder gesetzt. Zeile
80 setzt den new_el-Zeiger des neuen Elements auf NULL, damit der Zeiger nicht auf
irgendeine zufällige Adresse weist.
In Zeile 82 beginnt der Code zum Einfügen eines Elements. Als Erstes wird überprüft,
ob es bereits Elemente in der Liste gibt. Wenn das einzufügende Element das erste
Element in der Liste sein wird (was dadurch angezeigt wird, dass der Head-Zeiger
first auf NULL weist), wird der Head-Zeiger einfach auf die gleiche Adresse wie der
new_el-Zeiger gesetzt, und wir sind fertig.
Ist das einzufügende Element nicht das erste Element, wird die Funktion mit dem else
in Zeile 87 fortgesetzt. In Zeile 90 wird geprüft, ob das neue Element am Kopf der
Liste einzufügen ist. Wie Sie sich sicherlich erinnern werden, ist dies einer der drei
Fälle zum Einfügen von Listenelementen. Wenn das Element tatsächlich am Anfang
der Liste einzufügen ist, wird der next_el-Zeiger des neuen Elements auf das Element
gesetzt, das bis dato das erste (englisch first) Element in der Liste war (Zeile 92).
Danach wird in Zeile 93 der Head-Zeiger first auf das neue Element gesetzt. Auf
diese Weise wird das neue Element am Anfang der Liste eingefügt.
Wenn das einzufügende Element nicht das erste Element ist, das in eine leere Liste
eingefügt wird, und es nicht am Anfang einer bestehenden Liste einzufügen ist, muss
es irgendwo in der Mitte oder am Ende der Liste eingefügt werden. In den Zeilen 97
und 98 werden die weiter oben deklarierten Zeiger tmp_el und prev_el eingerichtet.
Dem Zeiger tmp_el wird die Adresse des zweiten Elements in der Liste und dem Zeiger
prev_el die Adresse des ersten Elements in der Liste zugewiesen.
Als Nächstes müssen wir den Sonderfall abfangen, dass es in der Liste nur ein
Element gibt. Beachten Sie, dass in diesem Falle tmp_el gleich NULL ist. Dies liegt
daran, dass tmp_el der Wert des next_el-Zeigers des ersten Elements zugewiesen
wird, der - da es nur ein Element gibt - gleich NULL ist. Zeile 102 fängt diesen Fall ab.
Wenn tmp_el gleich NULL ist, wissen wir, dass es das zweite Element ist, das eingefügt
wird. Da wir weiterhin wissen, dass das Element nicht vor dem ersten Element
kommt, muss es am Ende der Liste eingefügt werden. Um dies zu erreichen, brauchen
wir nur prev_el->next_el auf das neue Element zu richten.
Wenn der Zeiger tmp_el ungleich NULL ist, wissen wir, dass es bereits mindestens zwei
Elemente in der Liste gibt. Die while-Anweisung in den Zeilen 110 bis 129 iteriert
über den Rest der Elemente, um festzustellen, wo das neue Element einzufügen ist. In
Zeile 112 wird überprüft, ob das Datenelement des neuen Elements kleiner als das
Datenelement des atuellen Elements ist, auf das der Zeiger tmp_el gerade verweist. Ist
dies der Fall, wissen wir, dass wir das neue Element hier einfügen müssen. Sind die
neuen Daten größer als die Daten des aktuellen Elements, müssen wir zum nächsten
Element in der Liste weitergehen. Die Zeilen 126 und 127 setzen die Zeiger tmp_el
und next_el auf das nächste Element.
Wenn das einzufügende Zeichen kleiner ist als das Zeichen im aktuellen Element, wird
das neue Element an der entsprechenden Stelle in der Mitte der Liste eingefügt. Wie
dies geht, wurde bereits weiter vorne im Kapitel dargestellt und ist in den Zeilen 114
bis 122 implementiert. In Zeile 114 wird dem next-Zeiger des neuen Elements die
Adresse des aktuellen Elements (tmp_el) zugewiesen. Zeile 121 richtet den next-Zeiger
des vorangehenden Elements auf das neue Element. Danach sind wir fertig. Im Listing
wird die while-Schleife mit Hilfe einer break-Anweisung verlassen.
Die Zeilen 115 bis 120 enthalten Debug-Code, der zu Lehrzwecken im Listing belassen wurde. Sie können diese Zeilen entfernen; solange das Programm aber korrekt arbeitet, wird der Code sowieso nicht ausgeführt. Nachdem der
next-Zeiger des neuen Elements auf den aktuellen Zeiger gesetzt wurde, sollte der Zeiger gleich demnext-Zeiger des vorangehenden Listenelements sein, das ebenfalls auf das aktuelle Element verweist. Wenn die beiden Zeiger nicht gleich sind, ist irgendetwas falsch gelaufen!
Der bis hierher beschriebene Code fügt neue Elemente in der Mitte der Liste ein.
Wenn das Ende der Liste erreicht wird, endet die while-Schleife aus den Zeilen 110
bis 129, ohne dass das Element eingefügt wurde. Die Zeilen 132 bis 144 sorgen
dafür, dass das Element am Ende der Liste eingefügt wird.
Wenn das letzte Element in der Liste erreicht ist, ist tmp_el->next_el gleich NULL. Zeile
132 prüft diese Bedingung. In Zeile 134 wird ermittelt, ob das neue Element vor oder
nach dem letzten Element eingefügt werden soll. Gehört das Element hinter das letzte
Element, wird der next_el-Zeiger des letzten Elements auf das neue Element gerichtet
(Zeile 141) und der next-Zeiger des neuen Elements auf NULL gesetzt (Zeile 142).
Verkettete Listen sind nicht unbedingt einfach zu verstehen und zu implementieren. Sie stellen aber, und ich denke, dies hat Listing 14.14 demonstriert, einen ausgezeichneten Weg dar, Daten in sortierter Ordnung zu speichern. Da es relativ einfach ist, neue Elemente in eine verkettete Liste einzufügen, ist der Code, der dafür sorgt, dass die Elemente einer Liste in sortierter Reihenfolge bleiben, ein gutes Stück einfacher als vergleichbarer Code für Arrays oder andere Datenstrukturen. Das Listing könnte ohne große Mühe zum sortierten Verwalten von Namen, Telefonnummern oder anderen Daten umgeschrieben werden. Auch die Sortierreihenfolge kann ohne großen Aufwand von der aufsteigenden Sortierung (A bis Z) in eine absteigende Sortierung (Z bis A) umgewandelt werden
Die heutige Lektion hat Ihnen verschiedene fortgeschrittene Einsatzbereiche für Zeiger vorgestellt. Wie Sie mittlerweile sicherlich gemerkt haben, stellen die Zeiger ein ganz zentrales Konzept der Sprache C dar. Tatsächlich gibt es nur wenige echte C-Programme, die ohne Zeiger geschrieben sind. Sie haben gesehen, wie Sie Zeiger auf Zeiger verwenden und wie man Arrays von Zeigern sinnvoll für die Verwaltung von Strings einsetzt. Sie haben auch gesehen, wie in C mehrdimensionale Arrays als Arrays von Arrays behandelt werden und wie man auf solche Arrays über Zeiger zugreift. Sie haben gelernt, wie man Zeiger auf Funktionen deklariert und verwendet - eine wichtige und flexible Programmiertechnik. Schließlich haben Sie noch erfahren, wie man verkettete Listen implementiert - eine leistungsfähige und flexible Form der Datenspeicherung.
Insgesamt war das heute eine lange Lektion. Einige der behandelten Themen waren recht kompliziert, dafür aber zweifelsohne auch sehr interessant. Mit der heutigen Lektion haben wir uns in einige der ausgefeilteren Möglichkeiten der Sprache C vertieft. Die Leistungsfähigkeit und die Flexibilität, die aus diesen Möglichkeiten entspringen, sind einer der Hauptgründe dafür, dass C eine so populäre Sprache ist.
Frage:
Über wie viele Ebenen kann man Zeiger auf Zeiger richten?
Antwort:
Der GNU-C-Compiler erlegt Ihnen bezüglich der Tiefe Ihrer
Zeigerkonstruktionen keinerlei Beschränkungen auf. In der Praxis hat es aber
üblicherweise keinen Sinn, über drei Ebenen (Zeiger auf Zeiger auf Zeiger)
hinauszugehen. Die meisten Programmierer nutzen selten mehr als zwei
Ebenen.
Frage:
Gibt es einen Unterschied zwischen einem Zeiger auf einen String und einen
Zeiger auf ein Array von Zeichen?
Antwort:
Grundsätzlich gibt es keinen Unterschied: Strings sind letztlich nichts anderes
als eine Folge (ein Array) von Zeichen. Unterschiede gibt es allerdings in der
Handhabung. Für Zeiger auf char wird bei der Deklaration kein Speicher
reserviert.
Frage:
Muss man die am heutigen Tag vorgestellten Konzepte nutzen, wenn man von C
profitieren will?
Antwort:
Sie können mit C programmieren, ohne je irgendwelche der fortgeschrittenen
Zeigerkonzepte anzuwenden. Sie verzichten damit aber auf eine der
besonderen Stärken, die Ihnen C bietet. Mit Hilfe der heute vorgestellten
Zeigeroperationen sollten Sie in der Lage sein, praktisch jede gestellte
Programmieraufgabe schnell und effizient zu lösen.
Frage:
Gibt es noch weitere sinnvolle Einsatzbereiche für Zeiger auf Funktionen?
Antwort:
Ja. Zeiger auf Funktionen werden auch zur Realisierung von Menüs
verwendet. In Abhängigkeit von dem Wert, den das Menü zurückliefert, setzt
man einen Zeiger auf die zugehörige Funktion, die als Reaktion auf die
Menüauswahl aufgerufen werden soll.
Frage:
Welches sind die beiden wichtigsten Vorteile der verketteten Listen?
Antwort:
Ein Vorteil liegt in der Größe der Liste, die zur Laufzeit des Programms
wachsen und schrumpfen kann und nicht beim Aufsetzen des Codes vom
Programmierer festgelegt werden muss. Ein zweiter Vorteil ist, dass man
verkettete Listen ohne große Mühe sortiert anlegen kann. Da Elemente an
beliebigen Positionen in die Liste eingefügt oder aus der Liste gelöscht
werden können, ist es zudem einfach, die Sortierung beim Einfügen zu
erhalten.
Der Workshop enthält Quizfragen, die Ihnen helfen sollen, Ihr Wissen zu festigen, sowie Übungen, die Sie anregen sollen, das Gelernte umzusetzen und eigene Erfahrungen zu sammeln. Die Lösungen zu den Fragen und den Übungen finden Sie in Anhang C.
float deklariert. Deklarieren und
initialisieren Sie einen Zeiger, der auf die Variable verweist. Deklarieren und
initialisieren Sie einen Zeiger auf diesen Zeiger.
x einen Wert von 100 zuzuweisen.
Kann man dazu die folgende Anweisung verwenden?
*ppx = 100;
int array[2][3][4];
array[0][0]?
array[0][0] == &array[0][0][0];
array[0][1] == array[0][0][1];
array[0][1] == &array[0][1][0];
char übernimmt und void zurückliefert.
char
zurückliefert und ein Array von Zeigern auf char als Argument übernimmt.
char *zgr(char *x[]);
void-Zeiger, der inkrementiert wird, erhöht?
NULL ist?
int *var1;
int var2;
int **var3;
int a[3][12];
int (*b)[12];
int *c[12];
char *z[10];
char *y(int feld);
char (*x)(int feld);
float zurückliefert.
char.
int x[3][12];
int *zgr[12];
zgr = x;
Für die nachfolgenden Übungen 6 und 7 gibt es keine Antworten, da jeweils viele korrekte Lösungen denkbar sind.
double-Variablen zehn
Zahlenwerte vom Anwender abfragt, diese sortiert und dann auf den Bildschirm
ausgibt (Hinweis: siehe Listing 14.7).
zahlen auf, die drei Integer-
Argumente übernimmt. Die Integer sollen in Form von Verweisen (Zeigern)
übergeben werden.
zahlen aus Übung 9 mit den drei Integern
int1, int2 und int3 aufgerufen wird
void quadrieren(void *nbr)
{
*nbr *= *nbr;
}
Wegen der vielen denkbaren Lösungen gibt es zu den nachfolgenden Übungen keine Lösungen.
first anzeigen zu lassen, markieren Sie den
Variablennamen und klicken ihn mit der rechten Maustaste an. In dem
erscheinenden Kontextmenü klicken Sie auf Display first. Experimentieren Sie
ein wenig mit dieser Option des DDD-Debuggers. Sie ist sehr nützlich, um sich
mit den Operationen verketteter Listen vertraut zu machen oder
Implementierungen verketteter Listen zu debuggen.
