Zum Inhalt springen

Notes 4

Entwurf aus dem letzten Wintersemester. Nach der Vorlesung aktualisieren wir diese Seite, in der Regel ein bis zwei Tage später. Was sich geändert hat, steht dann hier. Geänderte und neue Absätze haben links einen Strich.

Sie können diese Seite ausdrucken oder mit einem PDF-Drucker in ein PDF umwandeln, um Ihre eigenen Notizen hinzuzufügen.

Zu dieser Vorlesung gibt es Shorts, vor allem 4.1 (Hexadezimal), 4.2 (Pointer) und 4.3 (eigene Datentypen). Die Shorts 4.4 bis 4.6 gehören zu Vorlesung 4.5.

In dieser Vorlesung schauen Sie in den Speicher Ihres Rechners. Jede Variable liegt dort an einer bestimmten Stelle, und diese Stelle hat eine Nummer. Mit dieser Nummer kann ein Programm eine Variable erreichen, ohne ihren Namen zu kennen. Davon handeln drei Teile:

  • Speicher und Adressen. Wo liegt eine Variable, wie liest man ihre Adresse, wie kommt man über die Adresse an den Wert? Dazu kommen die Hexadezimalzahlen, in denen Adressen geschrieben werden, und eine Antwort auf die Frage, warum swap aus Vorlesung 3 nicht tauschen konnte.
  • Bilder. Ein Bild ist eine Tabelle aus Pixeln, ein Pixel besteht aus drei Bytes. Das brauchen Sie für Übung 5 (Filter).
  • Speicher anfordern und zurückgeben mit malloc und free, und was dabei schiefgehen kann.

Den Anfang machte Frage 1 der Montagsfragen. Die Funktion mittelwert braucht die Länge des Arrays als eigenen Parameter, mittelwert(noten, 4), weil das Array seine Länge nicht kennt. Warum das so ist, sehen Sie im Abschnitt Arrays übergeben ihre Adresse: Die Funktion bekommt gar nicht das Array, nur die Adresse, an der es beginnt.

Speicher: Adresse und Inhalt

  • Der Speicher Ihres Rechners ist eine lange Reihe von Bytes. Jedes Byte hat eine Nummer, seine Adresse, und einen Inhalt, seinen Wert. In Vorlesung 2 haben Sie Speicher als Kästchen gezeichnet; heute bekommen die Kästchen Nummern.

  • In der Vorlesung stand dafür ein Regal auf der Bühne, mit 15 Fächern, drei nebeneinander und fünf übereinander. Jedes Fach trägt eine Adresskarte, in jedem Fach steht eine Kiste, und in der Kiste liegt eine Karte mit dem Wert. Die Adressen laufen zeilenweise von links oben, von 0x00 bis 0x0E. Adressen und Werte sind hexadezimal geschrieben; was das heißt, steht im nächsten Abschnitt. In jeder Zelle steht erst die Adresse, dann der Wert:

    Adresse: WertAdresse: WertAdresse: Wert
    0x00: 030x01: CA0x02: 03
    0x03: 020x04: 050x05: 04
    0x06: B80x07: 580x08: 86
    0x09: 0D0x0A: 070x0B: 0A
    0x0C: 0B0x0D: 0C0x0E: AC
  • Adresse und Inhalt sind zwei verschiedene Dinge. Das Fach 0x0A enthält den Wert 07; das Fach 0x07 enthält 58. Wer nach „der 07“ fragt, muss sagen, ob er die Adresse 0x07 meint oder den Inhalt 07. Deshalb tragen Adressen das Präfix 0x.

  • Ein Wert kann selbst eine Adresse sein. Im Fach 0x0B liegt 0A. Liest man 0A als Adresse, kommt man zum Fach 0x0A, und dort liegt 07. Liest man auch das als Adresse, kommt man zum Fach 0x07 mit dem Wert 58. Ob 0A eine Zahl ist oder eine Adresse, sieht man der Kiste nicht an. In C sagt es der Typ der Variablen (Abschnitt Pointer).

  • Zwei Kisten können dieselbe Adresse enthalten. Im Regal enthalten 0x00 und 0x02 beide 03: Beide zeigen auf dieselbe Kiste, 0x03.

  • Die Adressen laufen einfach weiter. Das Regal war ein Ausschnitt aus dem Hörsaal, die ersten 15 Plätze von Reihe 1. Reihe 1 endet mit 0x11 ganz rechts, und 0x12 sitzt in Reihe 2 ganz links. Im Saal liegt zwischen beiden die ganze Breite des Mittelblocks; für den Speicher spielt das keine Rolle: 0x12 ist das Byte nach 0x11.

  • Mit einer Adresse kann man zwei Dinge tun. Man kann die Adresse ablesen, an der etwas liegt; in C schreibt man dafür &. Und man kann einer Adresse folgen und nachsehen, was dort liegt; dafür schreibt man *. In der Vorlesung stand dafür ein Schaumstoff-Finger: Er zeigt vom Fach, in dem die Adresse liegt, auf das Fach mit dieser Adresse.

Garbage Values („Müllwerte“)

  • In jeder Kiste liegt eine Karte, auch in denen, die niemand gefüllt hat. So ist es auch im Speicher: Ein Byte ist nie leer. Es enthält immer acht Bits, und die stehen auf dem, was zuletzt dort geschrieben wurde.
  • Im Hörsaal stand deshalb auf jedem Etikett ein Wert, auch auf denen an leeren Plätzen. Er war grau vorgedruckt: Müll von früher.
  • Für Ihre Programme heißt das: Eine Variable, der Sie noch keinen Wert gegeben haben, enthält trotzdem einen. Welchen, legt C nicht fest; es ist, was gerade an dieser Stelle stand. Solche Werte heißen Garbage Values (Müllwerte). Lesen Sie eine Variable nie, bevor Sie ihr einen Wert gegeben haben, also zum Beispiel int n = 0; statt nur int n;.
  • Dasselbe gilt für Speicher, den Sie sich später in dieser Vorlesung mit malloc holen: Auch dort steht zunächst Müll.

Warum schreibt man Speicheradressen mit dem Präfix 0x?

Antwort

0x sagt nur: Diese Zahl ist hexadezimal geschrieben. 0x10 ist 16, nicht zehn. Adressen schreibt man meist so, aber auch Werte wie 0xFF in einem Bild.

Welcher Operator liefert in C die Adresse einer Variablen?

Antwort

Der Operator &.

Wie liest man &n?

Antwort

„Die Adresse von n“.

Was bewirkt der Operator * vor einer Adresse?

Antwort

Er sucht die Stelle im Speicher auf, auf die die Adresse verweist.

Was sind Garbage-Werte?

Antwort

Alte Werte in einem Speicherblock, den man erhalten, aber nicht initialisiert hat.

Wie vermeidet man Garbage-Werte?

Antwort

Indem man den Speicher initialisiert, zum Beispiel mit Null.

Hexadezimal

  • Adressen und Werte schreibt man meist hexadezimal, im Stellenwertsystem mit der Basis 16. Es hat sechzehn Ziffern:

    0 1 2 3 4 5 6 7 8 9 a b c d e f

    a steht für 10, b für 11 und so weiter bis f für 15. Groß- und Kleinschreibung spielt keine Rolle.

  • Wie im Dezimalsystem ist jede Stelle eine Potenz der Basis, hier 1, 16, 256 und so weiter. Nach 09 kommt 0A, nach 0F kommt 10, und 10 ist hexadezimal die 16.

  • Zwei Hexadezimalziffern reichen genau für ein Byte. Die größte Zahl in einem Byte ist 255 (acht Einsen in Binärdarstellung), hexadezimal FF: 15 Sechzehner und 15 Einer, also 15⋅16+15=25515 \cdot 16 + 15 = 255. Deshalb stehen auf jedem Etikett im Hörsaal zwei Ziffern, und deshalb schreibt man Bytes so gern hexadezimal: Jede Ziffer steht für genau vier Bits.

  • Umrechnen ins Dezimale: Die linke Ziffer mal 16, plus die rechte. 0x64 ist 6⋅16+4=1006 \cdot 16 + 4 = 100, 0x1F ist 16+15=3116 + 15 = 31, 0xE5 ist 14⋅16+5=22914 \cdot 16 + 5 = 229. Der Mittelblock des Hörsaals hat 230 Plätze, 0x00 bis 0xE5; jede dieser Adressen passt in ein Byte.

  • Das Präfix 0x sagt, dass eine Zahl hexadezimal gemeint ist. 0x10 ist 16, 10 ist zehn.

  • Hexadezimalzahlen begegnen Ihnen auch bei Farben: #FF0000 ist volles Rot (mehr dazu im Abschnitt Bilder).

Wie viele Zählwerte (Ziffern) hat das Hexadezimalsystem?

Antwort

16: 0 bis 9 und a bis f. Daher auch der Name Base-16.

Für welchen Wert steht die Hexadezimalziffer F?

Antwort

Für 15.

Welche Dezimalzahl wird hexadezimal als 10 geschrieben?

Antwort

Die 16.

Welche Dezimalzahl ist hexadezimal FF?

Antwort

255, die höchste Zahl mit zwei Hexadezimalstellen.

Warum verwendet man das Hexadezimalsystem?

Antwort

Es kommt mit weniger Ziffern aus; Informationen lassen sich damit prägnanter darstellen.

Wie viele Hexadezimalziffern braucht man, um jeden möglichen Wert eines Bytes zu schreiben?

Antwort

Zwei. Jede Hexadezimalziffer steht für vier Bits, ein Byte hat acht. Die Werte reichen von 00 bis FF.

Welche Dezimalzahl ist 0x64?

Antwort

100: 6 Sechzehner und 4 Einer, also 96 plus 4.

Pointer: & und *

  • Im Hörsaal ist jeder Platz ein Byte. Nennen wir das Byte, auf dem Sie sitzen, c und lesen es als Zeichen, als char c. Dann ist c der Wert auf Ihrem Etikett und &c Ihre Adresse.

  • Liest man denselben Wert als Adresse, ist Ihr Platz ein Pointer (deutsch: Zeiger), in C char *p: eine Variable, deren Wert eine Adresse ist. p ist der Wert auf Ihrem Etikett, *p ist der Wert auf dem Etikett, auf das p zeigt, und &p ist Ihre eigene Adresse.

  • Ob ein Wert ein Zeichen ist oder eine Adresse, sagt allein der Typ. 5A ist als char der Buchstabe Z (im ASCII-Code ist Z die 90, hexadezimal 5A), als char * ist es die Adresse 0x5A, Reihe 5 im Mittelblock.

  • In der Vorlesung haben wir das an einzelnen Plätzen ausprobiert. Eine Person nannte &c (ihre Adresse) und c (ihren Wert). Dann haben wir den Wert als Adresse gelesen: Die Person auf dieser Adresse stand auf und las ihren Wert vor, *p. War der Platz leer, war der Speicher trotzdem da, mit einem Wert auf dem Etikett.

  • Liest man den Wert am Ziel noch einmal als Adresse, kommt man ein zweites Mal weiter, wie im Regal von 0x0B über 0x0A nach 0x07.

  • Dann haben wir über den Pointer geschrieben: *p = 'H';. Die Person am Ziel schrieb 48 auf ihr Etikett, denn H ist im ASCII-Code hexadezimal 48. Auf dem Platz von p änderte sich nichts: *p = … schreibt an das Ziel, nicht in den Pointer.

  • Danach hat der ganze Saal gleichzeitig dereferenziert: Jede und jeder hat den eigenen Wert als char *p gelesen und das Etikett an dieser Adresse aufgesucht. Bei etwa der Hälfte der Plätze zeigte der Wert ein bis drei Plätze daneben, nach links oder nach rechts. Drei Größen, die Sie auseinanderhalten müssen:

    AusdruckBedeutung im Hörsaal
    pder Wert auf Ihrem Etikett, gelesen als Adresse
    *pder Wert auf dem Etikett, auf das p zeigt
    &pdie Adresse Ihres eigenen Platzes
  • Manche Werte zeigten an einen leeren Platz. Das ist kein Problem: Der Speicher ist da, auch wenn niemand dort sitzt, und das Etikett hat einen Wert.

  • Manche Werte waren E6 oder größer. Diese Adressen gibt es im Mittelblock nicht, er endet bei 0xE5. Liest ein Programm an einer Adresse, die es gar nicht gibt oder die nicht zu ihm gehört, bricht das Betriebssystem es meist ab. Die Meldung dazu heißt Segmentation fault. Liegt die Adresse nur knapp daneben, merkt oft niemand etwas.

  • Auf einem Platz stand der Wert 00. Die Adresse 0 heißt in C NULL und steht für „zeigt nirgendwohin“. Im Hörsaal gab es zwar einen Platz 0x00, als Ziel eines Pointers gilt die 0 aber nicht: Wer 00 hatte, ging nirgendwohin. Mehr dazu bei malloc.

  • In der Vorlesung haben Sie das am Handy geprüft (live.inf.zone): erst gelesen, was bei *p steht, dann über *p geschrieben. Wer statt *p den eigenen Wert (p) oder die eigene Adresse (&p) eingibt, verwechselt genau die drei Größen aus der Tabelle oben. Wird ein Platz von mehreren Seiten überschrieben, zeigen mehrere Pointer auf dasselbe Byte.

Pointer am Rechner

  • Am Rechner sind Adressen größer und Variablen oft länger als ein Byte. Ein int belegt 4 Bytes (Vorlesung 2); seine Adresse ist die Adresse des ersten dieser Bytes.
#include <stdio.h>

int main(void)
{
    int n = 50;
    printf("%i\n", n);
}
  • C kennt zwei Operatoren für Adressen:
    • & liefert die Adresse von etwas, das im Speicher liegt. &n liest man „die Adresse von n“.
    • * geht zu der Stelle im Speicher, auf die eine Adresse zeigt.
  • Mit printf und dem Platzhalter %p geben Sie eine Adresse aus. Ein Pointer auf ein int hat den Typ int *: int *p = &n; legt eine Variable p an, deren Wert die Adresse von n ist.
#include <stdio.h>

int main(void)
{
    int n = 50;
    printf("%i\n", n);
    printf("%p\n", &n);

    int *p = &n;
    printf("%p\n", p);
    printf("%i\n", *p);
}
$ make adresse
$ ./adresse
50
0xffffc046fd1c
0xffffc046fd1c
50
  • Beide Adressen sind gleich, denn p enthält die Adresse von n. Die Ausgabe stammt vom Rechner in der Vorlesung. Ihre Adresse sieht anders aus und ändert sich bei jedem Lauf; im Codespace beginnen solche Adressen meist mit 0x7ff.

  • *p geht zu dieser Adresse und liest dort ein int: 50.

  • Der Stern hat zwei Bedeutungen, und das verwirrt am Anfang:

    • In einer Deklaration wie int *p sagt er, dass p ein Pointer ist, hier einer auf ein int.
    • In einem Ausdruck wie printf("%i\n", *p) heißt er: Geh zur Adresse in p. Das nennt man dereferenzieren.
  • Im Hörsaal passte jede Adresse in ein Byte, weil es nur 230 Plätze gab. Ihr Rechner hat Milliarden Bytes; dort ist eine Adresse, und damit ein Pointer, 8 Bytes groß.

  • Zwei Fehler, die beim Tippen leicht passieren. Fehlt das & bei int *p = &n;, schlägt der Compiler es selbst vor:

    adresse.c:9:10: error: incompatible integer to pointer conversion initializing 'int *' with an expression of type 'int'; take the address with & [-Wint-conversion]

    Fehlt der Stern bei printf("%i\n", *p);, passt der Platzhalter nicht zum Typ:

    adresse.c:11:20: error: format specifies type 'int' but the argument has type 'int *' [-Werror,-Wformat]

Was ist ein Pointer?

Antwort

Eine Variable, die eine Adresse enthält, also die Stelle eines Wertes im Speicher.

Was bedeutet int *p = &n;?

Antwort

p ist ein Pointer auf einen int und speichert die Adresse von n.

Was liefert *p, wenn p ein Pointer auf eine Ganzzahl ist?

Antwort

Die Ganzzahl an der Adresse, die in p gespeichert ist.

Wie viele Bytes belegt ein Pointer normalerweise?

Antwort

8 Bytes.

Mit welchem Platzhalter gibt printf eine Adresse aus?

Antwort

Mit %p.

Auf einem Etikett im Hörsaal steht der Wert 5A. Ist das ein Zeichen oder eine Adresse?

Antwort

Das sagt der Typ. Als char ist 5A der Buchstabe Z, als char * ist es die Adresse 0x5A.

Im Fach 0x34 liegt 33, im Fach 0x33 liegt 31, im Fach 0x31 liegt C3. Ein Pointer p enthält 0x34. Was ist *p?

Antwort

33: *p geht genau einen Schritt, zum Fach 0x34. Erst wer 33 noch einmal als Adresse liest, kommt zu 0x33.

Swap

  • Eine Funktion bekommt Kopien ihrer Argumente. Das haben Sie in Vorlesung 3 gesehen, als swap zwei Zahlen nicht tauschen konnte. Zur Erinnerung ein kleineres Beispiel:

    #include <stdio.h>
    
    void erhoehe(int a);
    
    int main(void)
    {
        int x = 1;
        erhoehe(x);
        printf("x ist %i\n", x);
    }
    
    void erhoehe(int a)
    {
        a++;
        printf("a ist %i\n", a);
    }
  • Das Programm gibt a ist 2 und dann x ist 1 aus. erhoehe erhöht seine Kopie a, nicht x.

  • Das printf in erhoehe steht dort mit Absicht: Ohne es bricht make ab, weil a einen Wert bekommt, den niemand mehr liest (error: parameter 'a' set but not used). Für die Frage wäre „Fehler“ dann die richtige Antwort gewesen.

#include <stdio.h>

void swap(int a, int b);

int main(void)
{
    int x = 1;
    int y = 2;
    printf("x ist %i, y ist %i\n", x, y);
    swap(x, y);
    printf("x ist %i, y ist %i\n", x, y);
}

// Soll x und y vertauschen
void swap(int a, int b)
{
    int tmp = a;
    a = b;
    b = tmp;
}
$ make swap
$ ./swap
x ist 1, y ist 2
x ist 1, y ist 2
  • swap vertauscht a und b, also seine Kopien. x und y in main bleiben, wie sie waren.
  • Damit swap an x und y von main herankommt, bekommt es nicht ihre Werte, sondern ihre Adressen. Die Parameter werden Pointer, int *a und int *b, und im Rumpf steht vor jedem Zugriff ein Stern:
// Vertauscht die Werte an den Adressen a und b
void swap(int *a, int *b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}
  • Ändert man nur swap und ruft weiter swap(x, y) auf, übersetzt das Programm nicht. Der Compiler meldet, dass ein int übergeben wird, wo ein int * erwartet wird, und schlägt gleich die Lösung vor:

    $ make swap
    swap.c:10:10: error: incompatible integer to pointer conversion passing 'int' to parameter of type 'int *'; take the address with & [-Wint-conversion]
       10 |     swap(x, y);
          |          ^
          |          &
  • main übergibt jetzt die Adressen von x und y:

#include <stdio.h>

void swap(int *a, int *b);

int main(void)
{
    int x = 1;
    int y = 2;
    printf("x ist %i, y ist %i\n", x, y);
    swap(&x, &y);
    printf("x ist %i, y ist %i\n", x, y);
}

// Vertauscht die Werte an den Adressen a und b
void swap(int *a, int *b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}
$ make swap
$ ./swap
x ist 1, y ist 2
x ist 2, y ist 1
  • Warum der Aufruf mit & tauscht, zeigten in der Vorlesung die Kartons aus Vorlesung 1 und 3: ein türkiser für main mit den Karten x und y, ein blauer für swap. Bisher kamen in den blauen Karton Karteikarten mit Kopien der Werte; was swap mit diesen Karten macht, erreicht main nie.

  • Diesmal bekommt der blaue Karton keine Kopien der Werte, sondern zwei Zettel mit Adressen: „Adresse von x“, „Adresse von y“. Folgt man einer solchen Adresse (*a), landet man im türkisen Karton, bei x selbst. Dort tauscht swap die Werte, mit tmp als Zwischenablage wie bisher:

    int tmp = *a;
    *a = *b;
    *b = tmp;
  • Die Kartons haben einen Namen: Jeder Funktionsaufruf bekommt einen eigenen Bereich im Speicher für seine Variablen, einen Frame. Die Frames liegen in einem Bereich des Speichers, der Stack heißt. Wenn eine Funktion endet, wird ihr Frame weggeräumt wie der blaue Karton. Mehr dazu in Vorlesung 4.5.

  • Die Regel: Soll eine Funktion eine Variable des Aufrufers ändern, bekommt sie deren Adresse. Auch dann bekommt sie eine Kopie, aber eine Kopie der Adresse, und die führt zum Original.

Was braucht man, um zwei Variablen zu vertauschen?

Antwort

Einen temporären Speicherplatz (tmp).

Warum tauscht swap(int a, int b) die Variablen x und y aus main nicht?

Antwort

Die Funktion erhält nur Kopien der Werte.

In welchem Speicherbereich liegen die Variablen, die Funktionen wie main oder swap nutzen?

Antwort

Auf dem Stack.

Wie heißt der eigene Speicherbereich, den main und swap jeweils auf dem Stack haben?

Antwort

Frame.

Was übergibt man an swap, damit die Funktion x und y in main tauschen kann?

Antwort

Die Adressen &x und &y. Genauer: Kopien dieser Adressen, über die swap die Originale erreicht.

main ruft swap(&x, &y) auf, die Funktion beginnt mit void swap(int *a, int *b). Was steht in a?

Antwort

Die Adresse von x, genauer: eine Kopie dieser Adresse. *a ist dann x selbst.

Arrays übergeben ihre Adresse

  • In Vorlesung 3 hat eine Funktion die Elemente eines Arrays vertauscht, ohne dass wir Adressen übergeben haben, und das Array in main war danach sortiert. Bei swap(x, y) mussten Sie dagegen & schreiben, damit sich etwas ändert. Was bekommt eine Funktion, wenn man ihr ein Array übergibt?

  • Das folgende Programm zeigt es. Es enthält die Funktion mittelwert aus den Montagsfragen und erhoehe von oben; beide geben aus, an welcher Adresse ihr Parameter liegt.

#include <stdio.h>

float mittelwert(int werte[], int n);
void erhoehe(int a);

int main(void)
{
    int noten[] = {2, 1, 3, 3};
    printf("noten in main:       %p\n", noten);
    printf("%.2f\n", mittelwert(noten, 4));

    int x = 1;
    printf("&x in main:          %p\n", &x);
    erhoehe(x);
    printf("x ist %i\n", x);
}

float mittelwert(int werte[], int n)
{
    printf("werte in mittelwert: %p\n", werte);
    float summe = 0;
    for (int i = 0; i < n; i++)
    {
        summe += werte[i];
    }
    return summe / n;
}

void erhoehe(int a)
{
    printf("&a in erhoehe:       %p\n", &a);
    a++;
}
  • printf mit %p und noten ohne & gibt eine Adresse aus. Der Name eines Arrays steht in C für die Adresse seines ersten Elements.
$ make original
$ ./original
noten in main:       0xffffc59f8f80
werte in mittelwert: 0xffffc59f8f80
2.25
&x in main:          0xffffc59f8f7c
&a in erhoehe:       0xffffc59f8f5c
x ist 1
  • noten in main und werte in mittelwert sind dieselbe Adresse. mittelwert arbeitet also auf denselben Bytes wie main. Bei x und a sind die Adressen verschieden: a ist eine Kopie, die woanders liegt. (Die Ausgabe stammt vom Rechner in der Vorlesung. Ihre Adressen sehen anders aus; es kommt nur darauf an, welche gleich sind.)

  • Die Zeile von mittelwert steht vor 2.25, weil printf in main den Mittelwert erst ausgeben kann, wenn mittelwert fertig ist.

  • Daraus folgt auch, warum die Länge eines Arrays als eigener Parameter mitmuss: Die Funktion bekommt nur die Adresse des ersten Elements. Wie viele Elemente danach kommen, steht nirgends.

  • Der Compiler weiß das. Schreibt man in mittelwert versehentlich int werte statt int werte[], nennt er noten selbst einen Pointer:

    original.c:10:33: error: incompatible pointer to integer conversion passing 'int[4]' to parameter of type 'int' [-Wint-conversion]
  • Die Regel: Ein Array übergibt immer seine Adresse. Die Funktion bekommt eine Kopie der Adresse, an der das Array beginnt, und arbeitet damit am Original. Deshalb konnte swap(int a[], int i, int j) in Vorlesung 3 im Array tauschen, und deshalb wird Ihre Funktion in Übung 5 das Bild verändern.

Übung: Wer ändert x?

Wählen Sie die Stufe, die Sie schaffen; alle drei sind gleich viel wert. Ohne Laptop, auf Papier. Gegeben sind drei Funktionen:

void f(int a)
{
    a = 0;
    printf("a in f: %i\n", a);
}

void g(int *a)
{
    *a = 0;
}

void h(int *a)
{
    int b = 0;
    a = &b;
    *a = 1;
}

In main steht jeweils vorher int x = 5;.

  1. Stufe 1: Welchen Wert hat x nach f(x);?
  2. Stufe 2: Welchen Wert hat x nach g(&x);?
  3. Stufe 3: Welchen Wert hat x nach h(&x);?
Lösung zu Stufe 1

5. f bekommt eine Kopie von x in a und setzt diese Kopie auf 0. x bleibt 5.

Lösung zu Stufe 2

0. g bekommt die Adresse von x. *a = 0 geht zu dieser Adresse und schreibt dort 0, also in x.

Lösung zu Stufe 3

5. Auch h bekommt die Adresse von x, aber als Kopie in a. a = &b überschreibt diese Kopie mit der Adresse von b; danach zeigt a nicht mehr auf x. *a = 1 schreibt deshalb in b. Auch der Zeiger ist eine Kopie. Häufiger Fehler: 1.

Als Programm (a2.c, x vor jedem Aufruf wieder 5):

$ make a2
$ ./a2
a in f:       0
x nach f(x):  5
x nach g(&x): 0
x nach h(&x): 5

Warum muss man einer Funktion die Länge eines Arrays als eigenen Parameter übergeben?

Antwort

Die Funktion bekommt nur die Adresse des ersten Elements. Wie viele Elemente danach kommen, weiß sie nicht.

Eine Funktion bekommt einen Pointer a und führt a = &b; aus. Ändert das den Pointer im Aufrufer?

Antwort

Nein. Auch ein Pointer wird als Kopie übergeben. Die Funktion lenkt nur ihre Kopie um.

Bilder: Pixel in einer Tabelle

  • Zoomt man in ein Foto immer weiter hinein, bleiben am Ende einfarbige Quadrate übrig, die Pixel. Ein Bild ist ein Raster aus Pixeln, Zeile für Zeile von oben nach unten, in jeder Zeile von links nach rechts.
  • Im einfachsten Fall ist ein Pixel entweder schwarz oder weiß. Dann reicht ein Bit je Pixel: 0 für Schwarz, 1 für Weiß, und das Bild ist eine Karte aus Bits.
  • Farbige Pixel bestehen aus drei Zahlen: wie viel Rot, Grün und Blau (RGB) darin steckt, je von 0 bis 255. In Bildbearbeitungsprogrammen stehen diese drei Werte oft hexadezimal hintereinander: #FF0000 ist volles Rot, kein Grün, kein Blau; #000000 ist Schwarz, #FFFFFF Weiß.

Ein Bild ist eine Tabelle

  • Ein Bild ist eine Tabelle aus Pixeln. In C ist das ein zweidimensionales Array: ein Array, dessen Elemente selbst Arrays sind, eins je Zeile. In Notes 2 stand dazu ein Beispiel:

    int tabelle[2][3] = {{1, 2, 3}, {4, 5, 6}};

    Das legt 2 Zeilen mit je 3 Spalten an. Der erste Index ist die Zeile, der zweite die Spalte, und beide beginnen bei 0: tabelle[1][2] ist die zweite Zeile, dritte Spalte, also 6; tabelle[0][0] steht oben links.

  • In Übung 5 heißt die Tabelle image, und image[i][j] ist das Pixel in Zeile i und Spalte j. Im Speicher liegen die Zeilen hintereinander, erst Zeile 0, dann Zeile 1 und so weiter, so wie die Adressen im Hörsaal Reihe für Reihe weiterlaufen.

  • Um jedes Pixel einmal anzufassen, braucht man zwei Schleifen ineinander: Die äußere geht die Zeilen durch, die innere die Spalten einer Zeile.

    for (int i = 0; i < height; i++)
    {
        for (int j = 0; j < width; j++)
        {
            // Pixel image[i][j]
        }
    }

    Bei einer Tabelle mit 2 Zeilen und 3 Spalten läuft der Rumpf der inneren Schleife 2⋅3=62 \cdot 3 = 6-mal, einmal je Pixel.

Ein Pixel ist ein struct

  • Ein Pixel besteht aus drei Bytes, je eines für Blau, Grün und Rot. Im Gerüst von Filter (Datei bmp.h) ist es als struct definiert:

    typedef uint8_t BYTE;
    
    typedef struct
    {
        BYTE rgbtBlue;
        BYTE rgbtGreen;
        BYTE rgbtRed;
    } RGBTRIPLE;
  • BYTE ist ein anderer Name für uint8_t, eine ganze Zahl aus genau 8 Bits ohne Vorzeichen, also von 0 bis 255 bzw. 0x00 bis 0xFF. Das ist das Byte, das auf jedem Etikett im Hörsaal stand.

  • Mehr als 255 passt nicht hinein. Weist man einem BYTE einen größeren Wert zu, bleibt nur der Rest beim Teilen durch 256: Aus 259 wird 3, aus einem fast weißen Pixel ein fast schwarzes. Wer rechnet und dabei über 255 kommen kann, muss das vorher abfangen.

  • Auf einen Farbwert greifen Sie mit der Punktschreibweise zu, wie bei people[0].name in Vorlesung 3: image[i][j].rgbtRed ist der Rotwert des Pixels in Zeile i, Spalte j. Drei Bytes FF, 00, 00 für Rot, Grün und Blau ergeben volles Rot.

  • Die Funktionen, die Sie in Übung 5 schreiben, haben alle diese Form:

    void grayscale(int height, int width, RGBTRIPLE image[height][width]);

    height und width sind die Zahl der Zeilen und Spalten, image das Bild. Die beiden Zahlen stehen vor image, weil die Größe des Arrays sie schon braucht. Die Funktion gibt nichts zurück (void), und trotzdem ist das Bild danach verändert. Wie das geht, zeigt der Abschnitt Arrays übergeben ihre Adresse.

Übung: Bild als Tabelle

Wählen Sie die Stufe, die Sie schaffen; alle drei sind gleich viel wert. Ohne Laptop, auf Papier. Ein Bild mit 2 Zeilen und 3 Spalten, je Pixel Rot/Grün/Blau:

Spalte 0Spalte 1Spalte 2
Zeile 030/200/1060/50/40255/0/0
Zeile 190/80/70255/255/255200/100/50
void f(int height, int width, RGBTRIPLE image[height][width])
{
    for (int i = 0; i < height; i++)
    {
        for (int j = 0; j < width; j++)
        {
            image[i][j].rgbtGreen = 0;
            image[i][j].rgbtBlue = 0;
        }
    }
}
  1. Stufe 1: Was ist image[1][2].rgbtRed?
  2. Stufe 2: Was steht nach f(2, 3, image); in image[0][1], und welche Farbe hat dann image[1][1]?
  3. Stufe 3: Schreiben Sie den Rumpf der inneren Schleife für „Negativ“: Jeder Farbwert wird 255 minus der alte. Was wird aus image[1][2]? (Stufe 3 beginnt mit der Tabelle oben, nicht mit dem Ergebnis von Stufe 2.)
Lösung zu Stufe 1

200. Zeile 1, Spalte 2 ist das Pixel 200/100/50, sein Rotwert 200. Häufiger Fehler: Zeile und Spalte vertauscht. image[2][1] gibt es nicht, das Bild hat nur die Zeilen 0 und 1.

Lösung zu Stufe 2

Rot 60, Grün 0, Blau 0. f setzt in jedem Pixel Grün und Blau auf 0, Rot bleibt. Aus dem weißen Pixel image[1][1] (255/255/255) wird 255/0/0, also Rot.

Lösung zu Stufe 3
image[i][j].rgbtRed = 255 - image[i][j].rgbtRed;
image[i][j].rgbtGreen = 255 - image[i][j].rgbtGreen;
image[i][j].rgbtBlue = 255 - image[i][j].rgbtBlue;

Aus 200/100/50 wird 55/155/205. Häufige Fehler: nur rgbtRed geändert; image.rgbtRed ohne Index. Die ganze Tabelle nach „Negativ“:

Spalte 0Spalte 1Spalte 2
Zeile 0225/55/245195/205/2150/255/255
Zeile 1165/175/1850/0/055/155/205

Ein Pixel wird kopiert

  • Ein ganzes struct können Sie mit = zuweisen. Was passiert dabei?

    RGBTRIPLE p = image[0][1];
    p.rgbtRed = 0;
  • Das Bild ändert sich nicht. p ist eine Kopie des Pixels, mit eigenen drei Bytes; p.rgbtRed = 0 ändert nur die Kopie. In der Tabelle aus der Übung bleibt image[0][1].rgbtRed 60. Ein struct wird bei = und bei der Übergabe an eine Funktion kopiert, ein Array nicht: Von einem Array wird nur die Adresse übergeben.

Negativ im Filter-Gerüst

  • Wie so eine Funktion im echten Gerüst aussieht, zeigt ein Filter, der in Übung 5 nicht vorkommt: Negativ. Jeder Farbwert wird 255 minus der alte. In der Vorlesung lag dafür eine Kopie des Filter-Gerüsts bereit, die nur den Schalter -n kennt. Vor der Änderung sieht helpers.c so aus:

    #include "helpers.h"
    
    // Negativ: jeder Farbwert wird 255 minus der alte
    void negativ(int height, int width, RGBTRIPLE image[height][width])
    {
        for (int i = 0; i < height; i++)
        {
            for (int j = 0; j < width; j++)
            {
                // Pixel image[i][j]
            }
        }
    }
  • Übersetzt wird mit make filter, aufgerufen mit dem Schalter, dem Eingabebild und dem Namen der Ausgabedatei:

    $ make filter
    $ ./filter -n images/yard.bmp out.bmp

    Das Programm gibt nichts aus; es schreibt das neue Bild nach out.bmp.

#include "helpers.h"

// Negativ: jeder Farbwert wird 255 minus der alte
void negativ(int height, int width, RGBTRIPLE image[height][width])
{
    for (int i = 0; i < height; i++)
    {
        for (int j = 0; j < width; j++)
        {
            // Pixel image[i][j]
            image[i][j].rgbtRed = 255 - image[i][j].rgbtRed;
            image[i][j].rgbtGreen = 255 - image[i][j].rgbtGreen;
            image[i][j].rgbtBlue = 255 - image[i][j].rgbtBlue;
        }
    }
}
  • In den Rumpf kommen die drei Zeilen aus Stufe 3 der Übung. Der helle Himmel wird fast schwarz, das orange Laub blau. negativ gibt nichts zurück und ändert trotzdem das Bild, das filter.c danach in die Datei schreibt.

  • In Übung 5 schreiben Sie vier solche Funktionen. Für den Einstieg helfen die Warm-ups 3 und 4: Sie üben den Zugriff auf image[i][j] an einem kleinen Bild ohne Datei.

Exkurs: Warum „Enhance!“ nicht funktioniert

In Filmen und Serien zoomt jemand in ein unscharfes Überwachungsbild, sagt „Enhance!“, und plötzlich ist ein Kennzeichen zu lesen. Das geht nicht: Ein Bild enthält nur die Pixel, die es hat. Vergrößert man es, werden die Pixel größer, aber es kommt keine Information dazu. Programme können Zwischenwerte schätzen und Kanten glätten, sie erfinden dabei aber Details, die nicht aufgenommen wurden.

Wie groß ein Bild auf Papier wird, hängt davon ab, wie viele Pixel auf einen Zoll (2,54 cm) kommen. Diese Angabe heißt dpi (dots per inch) oder ppi (pixels per inch). Für den Druck rechnet man oft mit 300 dpi: Das Bild aus Übung 5 mit 600 × 400 Pixeln wird dann nur 2 × 1,33 Zoll groß, also etwa 5 × 3,4 cm.

Welchen Index hat das erste Element eines Arrays in C?

Antwort

Den Index 0: Arrays sind immer 0-indiziert.

Was ist ein zweidimensionales Array in C?

Antwort

Ein Array von Arrays, wie eine Tabelle mit Zeilen und Spalten.

Was ist ein Pixel?

Antwort

Ein einzelner Farbpunkt (ein Quadrat); Pixel sind in einem Raster angeordnet.

Wofür steht RGB?

Antwort

Für Rot, Grün, Blau: drei Zahlen geben den Anteil jeder dieser Farben an.

Ein Schwarz-Weiß-Bild als Karte aus Bits: Wofür stehen 0 und 1?

Antwort

0 steht für Schwarz, 1 für Weiß.

Steht bei image[i][j] das i für die Zeile oder für die Spalte?

Antwort

Für die Zeile. j ist die Spalte, und image[0][0] ist das Pixel oben links.

Wie greifen Sie in Filter auf den Rotwert des Pixels in Zeile 0, Spalte 1 zu?

Antwort

Mit image[0][1].rgbtRed: erst das Pixel in der Tabelle, dann mit dem Punkt der Farbwert im struct.

Welche Werte kann ein BYTE (uint8_t) annehmen?

Antwort

0 bis 255, hexadezimal 0x00 bis 0xFF.

grayscale ist void und gibt nichts zurück. Warum ist das Bild danach trotzdem verändert?

Antwort

image ist ein Array, und ein Array übergibt seine Adresse. Die Funktion ändert die Pixel im Original.

Strings sind Adressen

  • Ein String ist eine Folge von Zeichen, die mit \0 endet. "HI!" braucht deshalb 4 Bytes: H, I, ! und \0. Im Hörsaal wären das vier Plätze nebeneinander.

  • Die Zeichen liegen an aufeinanderfolgenden Adressen. Um den ganzen String zu finden, reicht deshalb die Adresse des ersten Zeichens: Von dort geht man Byte für Byte weiter bis zum \0. Genau das ist eine Variable vom Typ string: die Adresse des ersten Zeichens.

  • In der CS50-Bibliothek steht dafür eine einzige Zeile:

    typedef char *string;

    string ist also nur ein anderer Name für char *, einen Pointer auf ein char. Ohne cs50.h schreiben Sie char * direkt:

    #include <stdio.h>
    
    int main(void)
    {
        char *s = "HI!";
        printf("%s\n", s);
    }

    printf mit %s bekommt die Adresse in s, gibt das Zeichen dort aus, dann das an der nächsten Adresse und so weiter, bis es auf \0 trifft.

  • s[1] ist das Zeichen eine Adresse weiter, s[2] das zwei weiter. Dass man mit Adressen auch rechnen kann (*(s + 1)), sehen Sie in Vorlesung 4.5.

  • Was passiert, wenn man einen String einer zweiten Variablen zuweist und dann die zweite ändert?
#include <cs50.h>
#include <ctype.h>
#include <stdio.h>

int main(void)
{
    string s = get_string("s: ");

    string t = s;
    t[0] = toupper(t[0]);

    printf("s: %s\n", s);
    printf("t: %s\n", t);
}
$ make kopie
$ ./kopie
s: hi!
s: Hi!
t: Hi!
  • Beide sind groß. string t = s; kopiert nur den Wert von s, und der ist eine Adresse. Danach zeigen s und t auf dieselben vier Bytes; wer über t schreibt, ändert, was man über s liest. Für eine echte Kopie braucht t eigenen Speicher. Wie man den bekommt, steht im nächsten Abschnitt.

Worauf zeigt die Variable s bei char *s = "HI!";?

Antwort

Auf das erste Byte (das erste Zeichen) der Zeichenkette im Speicher.

Wie liegen die Zeichen eines Strings im Speicher?

Antwort

Nebeneinander, an aufeinanderfolgenden Adressen.

Wie definiert die CS50-Bibliothek den Datentyp string?

Antwort

Mit typedef char *string.

Welchen Datentyp schreibt man in C ohne cs50.h statt string?

Antwort

char *.

Was kopiert string t = s;?

Antwort

Nur die Adresse: s und t zeigen danach auf dieselbe Zeichenkette.

malloc und free

  • Will man "hi!" in eigenen Speicher abschreiben, braucht man vier Bytes am Stück, die sonst niemand benutzt. Die bekommt man mit malloc (memory allocation): malloc(4) reserviert 4 Bytes und gibt die Adresse des ersten zurück. Wer die Bytes nicht mehr braucht, gibt sie mit free zurück. Beide Funktionen stehen in stdlib.h.

  • Im Hörsaal trug jedes Etikett dafür einen Status: F für frei, B für belegt. char *t = malloc(4); hieß: vier Plätze mit F nebeneinander finden, ihren Status auf B setzen und die Adresse des ersten in t schreiben. Gab es mehrere solche Gruppen, bekam die mit der kleinsten Adresse den Zuschlag.

  • Die Adresse 0x00 vergibt malloc nie. Sie heißt NULL und bedeutet „zeigt nirgendwohin“. Findet malloc keinen passenden Platz, gibt es NULL zurück; deshalb prüft man nach jedem malloc, ob t == NULL ist.

  • Dann schrieben die vier Bytes "HI!" hinein, mit strcpy(t, "HI!"), das wie das Abschreiben von Zeichen funktioniert (gleich mehr). Im ASCII-Code, hexadezimal geschrieben:

    ZeichenHI!\0OK
    Wert484921004F4B

    Drei Bytes hätten nicht gereicht: Das \0 braucht ein eigenes.

  • printf("%s\n", t) folgt der Adresse in t und gibt Zeichen für Zeichen aus, bis es auf 00 trifft.

  • free(t); setzt den Status der vier Plätze wieder auf F. free löscht nichts: Es setzt nichts auf 0. Im Hörsaal blieben die Werte einfach stehen. Am Rechner darf die C-Bibliothek einige der Bytes für ihre eigene Verwaltung überschreiben; was danach dort steht, ist nicht festgelegt, verlassen kann man sich auf nichts. Und auch t ändert sich nicht, es enthält weiter dieselbe Adresse. Ein solcher Pointer heißt Dangling Pointer: Er zeigt auf Speicher, der Ihnen nicht mehr gehört.

  • Danach kam char *u = malloc(4);, mit derselben Regel. Es stand dieselbe Gruppe auf wie vorher: Nach free waren genau dieselben Plätze frei wie vor dem ersten malloc, und die kleinste Adresse war wieder dieselbe. u bekam also dieselbe Adresse wie t.

  • Mit strcpy(u, "OK!") schrieben die vier 4F 4B 21 00. Wer jetzt noch über t liest, bekommt nicht mehr HI!, sondern OK!, obwohl niemand t angefasst hat.

  • Am Rechner ist es oft genauso. Das folgende Programm gibt t vor free aus und u nach dem zweiten malloc; beide Adressen sind meist gleich. Garantiert ist das nicht, es hängt davon ab, wie die C-Bibliothek den Speicher verwaltet.

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    int main(void)
    {
        char *t = malloc(4);
        if (t == NULL)
        {
            return 1;
        }
        strcpy(t, "HI!");
        printf("t: %p %s\n", t, t);
        free(t);
        t = NULL;
    
        char *u = malloc(4);
        if (u == NULL)
        {
            return 1;
        }
        strcpy(u, "OK!");
        printf("u: %p %s\n", u, u);
        free(u);
    }
    $ make wieder
    $ ./wieder
    t: 0xaaaaf8a24010 HI!
    u: 0xaaaaf8a24010 OK!
  • Deshalb gilt: Nach free(t) setzen Sie t = NULL;. Dann zeigt t nirgendwohin, und niemand liest versehentlich über t, was inzwischen jemand anderem gehört.

  • Wer free vergisst, gibt den Speicher nie zurück. Das heißt Speicherleck (memory leak). Bei kleinen Programmen merkt man es nicht, bei Programmen, die lange laufen, wächst der Speicherbedarf immer weiter.

  • Auch Bytes von malloc enthalten zunächst Müll (siehe Garbage Values), so wie die Etiketten im Hörsaal schon einen Wert trugen, bevor jemand schrieb.

Mit welcher Funktion fordern Sie in C einen Speicherblock einer bestimmten Größe an, um dort Daten abzulegen?

Antwort

Mit malloc.

Mit welcher Funktion teilen Sie dem Computer mit, dass er einen zuvor zugewiesenen Speicherblock wieder freigeben soll?

Antwort

Mit free.

Wozu dient malloc?

Antwort

Um einen Speicherblock einer bestimmten Größe anzufordern, in dem man Daten ablegen kann.

Wozu dient free?

Antwort

Es gibt einen mit malloc angeforderten Speicherblock wieder frei: Man ist mit ihm fertig.

Was passiert mit den Bytes, wenn Sie free(t) aufrufen?

Antwort

Sie werden als frei markiert, aber nicht gelöscht: free setzt nichts auf 0. Was dort stand, kann stehen bleiben oder von der C-Bibliothek überschrieben werden. Verlassen kann man sich auf nichts.

Was steht nach free(t); in t, und was sollten Sie deshalb tun?

Antwort

Weiter dieselbe Adresse, obwohl der Speicher Ihnen nicht mehr gehört (Dangling Pointer). Deshalb danach t = NULL;.

Kopieren (malloc, free)

  • Damit lässt sich ein String in eigenen Speicher kopieren. Wie viele Bytes braucht die Kopie? strlen("hi!") ist 3, denn strlen zählt das \0 nicht mit. Die Kopie braucht aber auch das \0, also strlen(s) + 1 Bytes.
  • Das Muster hat vier Teile: Speicher holen, prüfen, kopieren, am Ende zurückgeben. Aus kopie.c von oben wird:
#include <cs50.h>
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(void)
{
    string s = get_string("s: ");

    char *t = malloc(strlen(s) + 1);
    if (t == NULL)
    {
        return 1;
    }
    strcpy(t, s);
    t[0] = toupper(t[0]);

    printf("s: %s\n", s);
    printf("t: %s\n", t);

    free(t);
}
  • malloc(strlen(s) + 1) holt genug Bytes für alle Zeichen und das \0.
  • if (t == NULL) fängt den Fall ab, dass kein Speicher frei ist. Das Programm endet dann mit return 1, statt über NULL zu schreiben.
  • strcpy(t, s) (aus string.h) kopiert die Zeichen von s nach t, das \0 eingeschlossen. Das Ziel steht zuerst, wie bei einer Zuweisung t = s.
  • free(t) gibt den Speicher am Ende zurück.
$ make kopie
$ ./kopie
s: hi!
s: hi!
t: Hi!
  • Jetzt ist nur t groß. s und t zeigen auf verschiedene Bytes.

  • strcpy tut nichts Geheimnisvolles. Dieselbe Arbeit erledigt eine Schleife, die jedes Zeichen einzeln abschreibt, das \0 eingeschlossen (deshalb <=):

    for (int i = 0, n = strlen(s); i <= n; i++)
    {
        t[i] = s[i];
    }

    n = strlen(s) steht im ersten Teil der Schleife, damit strlen nur einmal läuft. In der Bedingung würde es bei jedem Durchlauf neu zählen.

  • Fehlt eine der beiden #include-Zeilen, meldet der Compiler, dass er malloc bzw. strlen nicht kennt, und nennt die Datei, die fehlt:

    kopie.c:10:15: error: call to undeclared library function 'malloc' with type 'void *(unsigned long)'; ISO C99 and later do not support implicit function declarations [-Wimplicit-function-declaration]

    Darunter steht note: include the header <stdlib.h> or explicitly provide a declaration for 'malloc'.

Warum reserviert man für eine Kopie von s strlen(s) + 1 Bytes?

Antwort

Für den Null-Terminator \0, der mitkopiert werden muss.

Warum ruft man strlen(s) nicht in der Bedingung einer for-Schleife auf?

Antwort

Die Bedingung wird in jedem Durchlauf erneut ausgewertet. Mit n = strlen(s) im Initialisierungsteil läuft strlen nur einmal.

Welche eingebaute C-Funktion kopiert eine Zeichenkette?

Antwort

strcpy.

Was gibt malloc zurück, wenn etwas schiefgeht?

Antwort

NULL.

String-Vergleich

  • In Vorlesung 2 haben Sie zwei Strings mit == verglichen. Mit dem, was Sie jetzt wissen, lässt sich erklären, was dabei herauskam. Das folgende Programm vergleicht zwei Strings mit == und gibt danach ihre Adressen aus. Was dabei verglichen wird, zeigt die Ausgabe.
#include <cs50.h>
#include <stdio.h>

int main(void)
{
    string s = get_string("s: ");
    string t = get_string("t: ");

    if (s == t)
    {
        printf("Gleich\n");
    }
    else
    {
        printf("Verschieden\n");
    }

    printf("s: %p\n", s);
    printf("t: %p\n", t);
}
$ make vergleich
$ ./vergleich
s: HI!
t: HI!
Verschieden
s: 0xaaaae11c3020
t: 0xaaaae11c3060
  • Die Adressen sind verschieden (Ihre sehen anders aus), also sagt == „verschieden“, obwohl beide Male HI! eingegeben wurde. get_string legt jede Eingabe an einer eigenen Stelle ab.

  • s und t sind Adressen. s == t vergleicht deshalb Adressen, nicht Zeichen: Es ist nur dann wahr, wenn beide auf dieselbe Stelle zeigen, wie nach t = s.

  • Die Zeichen vergleicht strcmp aus string.h. Es geht beide Strings Zeichen für Zeichen durch und gibt 0 zurück, wenn sie gleich sind:

    #include <cs50.h>
    #include <stdio.h>
    #include <string.h>
    
    int main(void)
    {
        string s = get_string("s: ");
        string t = get_string("t: ");
    
        if (strcmp(s, t) == 0)
        {
            printf("Gleich\n");
        }
        else
        {
            printf("Verschieden\n");
        }
    }

    Mit zweimal HI! gibt dieses Programm Gleich aus.

Wodurch wird eine Zeichenkette in C identifiziert?

Antwort

Durch ihr erstes Byte, genauer: dessen Adresse. Von dort an folgen die Zeichen.

Was vergleicht s == t, wenn s und t Strings (char *) sind?

Antwort

Die Speicheradressen der Zeichenketten, nicht die enthaltenen Zeichen.

Mit welcher Funktion vergleicht man in C die Zeichen zweier Strings?

Antwort

Mit strcmp.

Was gibt strcmp zurück, wenn die Strings gleich sind?

Antwort

0.

Übung: Kopie oder nicht

Wählen Sie die Stufe, die Sie schaffen; alle drei sind gleich viel wert. Ohne Laptop, auf Papier. Die Eingabe ist jeweils hi!.

  1. Stufe 1: Was gibt dieses Programmstück aus?

    string s = get_string("s: ");
    string t = s;
    t[0] = 'H';
    printf("%s %s\n", s, t);
  2. Stufe 2: Was gibt es jetzt aus, und wie viele Bytes holt malloc?

    string s = get_string("s: ");
    char *t = malloc(strlen(s) + 1);
    if (t == NULL)
    {
        return 1;
    }
    strcpy(t, s);
    t[0] = 'H';
    printf("%s %s\n", s, t);
    free(t);
  3. Stufe 3: In diesem Stück stecken zwei Fehler. Welche?

    string s = get_string("s: ");
    char *t = malloc(strlen(s));
    if (t == NULL)
    {
        return 1;
    }
    strcpy(t, s);
    t[0] = 'H';
    printf("%s %s\n", s, t);
Lösung zu Stufe 1

Hi! Hi! t = s kopiert nur die Adresse; t[0] = 'H' ändert die Bytes, auf die auch s zeigt. Häufiger Fehler: hi! Hi!.

Lösung zu Stufe 2

hi! Hi! t hat eigene Bytes, die Änderung trifft nur die Kopie. malloc holt 4 Bytes: strlen(s) ist 3, dazu eins für das \0.

Lösung zu Stufe 3
  1. Ein Byte zu wenig: malloc(strlen(s)) holt nur 3 Bytes, strcpy schreibt aber 4, das \0 landet hinter dem reservierten Speicher. Was dann passiert, legt C nicht fest; oft sieht man nichts, und gerade das macht den Fehler gefährlich.
  2. Kein free: Der Speicher wird nie zurückgegeben, ein Speicherleck.

Als Programme (a4-stufe1.c, a4-stufe2.c; Stufe 3 wird bewusst nicht ausgeführt):

$ ./a4-stufe1
s: hi!
Hi! Hi!
$ ./a4-stufe2
s: hi!
hi! Hi!

Wie viele Bytes holt malloc(strlen(s) + 1), wenn s der String "hi!" ist?

Antwort

4: strlen(s) ist 3, dazu ein Byte für das \0.

Ein Programm holt Speicher mit malloc und ruft nie free auf. Wie heißt dieser Fehler?

Antwort

Speicherleck (memory leak): Der Speicher wird nie zurückgegeben.

Zum Nachlesen: Vorlesung 4.5

Die folgenden Abschnitte gehörten im letzten Jahr zu dieser Vorlesung. In diesem Semester kommen sie in Vorlesung 4.5. Hier stehen sie zum Nachlesen, jeweils mit Selbsttest.

Pointerarithmetik

  • s[1] ist das Zeichen eine Adresse nach dem ersten. Dasselbe lässt sich mit Adressen schreiben: s + 1 ist die Adresse eins weiter, und *(s + 1) ist das Zeichen dort.

    #include <stdio.h>
    
    int main(void)
    {
        char *s = "HI!";
        printf("%c\n", *s);
        printf("%c\n", *(s + 1));
        printf("%c\n", *(s + 2));
    }

    Das Programm gibt H, I und ! untereinander aus. *s ist dasselbe wie s[0], *(s + 1) dasselbe wie s[1]. Die Schreibweise mit eckigen Klammern liest sich meist leichter.

Welches Zeichen liefert *s, wenn s auf einen String zeigt?

Antwort

Das erste Zeichen des Strings.

Wie schreibt man s[1] mit Pointerarithmetik?

Antwort

*(s + 1): das Zeichen an der Stelle s + 1.

Überlauf

  • Jeder Funktionsaufruf bekommt einen eigenen Frame auf dem Stack (Abschnitt Swap). Ruft sich eine Funktion immer wieder selbst auf, ohne aufzuhören, oder werden sehr viele Funktionen ineinander aufgerufen, ist der Stack irgendwann voll, und das Programm bricht ab. Das heißt Stack Overflow.
  • Ein Pufferüberlauf (buffer overflow) entsteht, wenn ein Programm mehr in einen Speicherbereich schreibt, als dafür reserviert ist, etwa zehn Zeichen in ein Array für vier. Die überzähligen Bytes landen in Speicher, der zu etwas anderem gehört. Pufferüberläufe gehören zu den häufigsten Ursachen von Sicherheitslücken.

Wann spricht man von einem Stack Overflow?

Antwort

Wenn zu viele Funktionen aufgerufen werden und dadurch der verfügbare Speicher überläuft.

Was ist ein Pufferüberlauf (Buffer Overflow)?

Antwort

Der vorbereitete Buffer ist zu klein für das, was eingelesen werden soll.

scanf

  • get_int und get_string stammen aus der CS50-Bibliothek. Ohne sie liest man Eingaben mit scanf aus stdio.h:

    #include <stdio.h>
    
    int main(void)
    {
        int x;
        printf("x: ");
        scanf("%i", &x);
        printf("x: %i\n", x);
    }

    scanf soll den gelesenen Wert in x ablegen. Weil eine Funktion nur Kopien bekommt, braucht sie dafür die Adresse von x, wie swap: &x.

  • Bei Strings wird es schwierig. Mit char *s; und scanf("%s", s); fehlt zwar zu Recht das &, denn s ist schon eine Adresse. Aber s hat nie einen Wert bekommen; es gibt keinen Speicher, in den die Zeichen passen. Der Compiler im Codespace lehnt das deshalb ab (variable 's' is uninitialized when used here).

  • Mit reserviertem Speicher geht es, aber nur, solange die Eingabe hineinpasst:

    #include <stdio.h>
    
    int main(void)
    {
        char s[4];
        printf("s: ");
        scanf("%s", s);
        printf("s: %s\n", s);
    }

    char s[4] reserviert vier Bytes, genug für cat und das \0. Wer mehr eintippt, schreibt hinter das Array: ein Pufferüberlauf. Was dann passiert, legt C nicht fest; oft merkt man nichts. scanf mit %s weiß nicht, wie groß der Speicher ist, und ist deshalb unsicher. get_string holt sich den Speicher selbst, passend zur Eingabe.

Welche eingebaute C-Funktion liest Benutzereingaben ein, etwa anstelle von get_int?

Antwort

scanf.

Warum schreibt man scanf("%i", &x) mit &x?

Antwort

Damit scanf den eingelesenen Wert an der Adresse von x speichern kann.

Warum funktioniert char *s; scanf("%s", s); nicht?

Antwort

Es wird kein Speicher für die Zeichenkette zugewiesen.

Warum ist char s[4]; scanf("%s", s); unsicher?

Antwort

Man kann nicht darauf vertrauen, dass die Eingabe in den reservierten Speicher passt.

File I/O

  • Programme können Dateien lesen und schreiben. phonebook.c hängt bei jedem Aufruf eine Zeile an die Datei phonebook.csv an:

    #include <cs50.h>
    #include <stdio.h>
    
    int main(void)
    {
        // CSV-Datei zum Anhängen öffnen
        FILE *file = fopen("phonebook.csv", "a");
        if (file == NULL)
        {
            return 1;
        }
    
        // Name und Nummer abfragen
        char *name = get_string("Name: ");
        char *number = get_string("Number: ");
    
        // Eine Zeile in die Datei schreiben
        fprintf(file, "%s,%s\n", name, number);
    
        // Datei schließen
        fclose(file);
    }
  • fopen öffnet eine Datei und gibt einen Pointer vom Typ FILE * zurück. Lässt sich die Datei nicht öffnen, gibt fopen NULL zurück; deshalb die Prüfung direkt danach, wie bei malloc.

  • Das zweite Argument von fopen ist der Modus:

    • "r" (read): nur lesen. Die Datei muss schon existieren.
    • "w" (write): schreiben. Gibt es die Datei schon, wird ihr bisheriger Inhalt überschrieben, sonst wird sie neu angelegt.
    • "a" (append): anhängen. Neuer Text landet am Ende der Datei; gibt es sie noch nicht, wird sie angelegt.

    phonebook.c öffnet mit "a". Deshalb bleiben die bisherigen Einträge erhalten, und jeder Aufruf fügt eine Zeile hinzu.

  • fprintf schreibt wie printf, aber in die Datei, die als erstes Argument kommt. fclose schließt die Datei am Ende.

  • Dateien lassen sich auch Byte für Byte kopieren. cp.c liest aus der ersten Datei und schreibt in die zweite:

    #include <stdint.h>
    #include <stdio.h>
    
    typedef uint8_t BYTE;
    
    int main(int argc, char *argv[])
    {
        if (argc != 3)
        {
            printf("Usage: ./cp quelle ziel\n");
            return 1;
        }
    
        FILE *src = fopen(argv[1], "rb");
        if (src == NULL)
        {
            return 1;
        }
        FILE *dst = fopen(argv[2], "wb");
        if (dst == NULL)
        {
            fclose(src);
            return 1;
        }
    
        BYTE b;
        while (fread(&b, sizeof(b), 1, src) != 0)
        {
            fwrite(&b, sizeof(b), 1, dst);
        }
    
        fclose(dst);
        fclose(src);
    }

    typedef uint8_t BYTE; gibt dem Typ für ein Byte einen kürzeren Namen, wie in bmp.h aus Filter. fread(&b, sizeof(b), 1, src) liest ein Byte aus src nach b, wieder über die Adresse, wie bei scanf; sizeof(b) ist die Größe von b in Bytes (mehr dazu in Vorlesung 4.5). Am Ende der Datei liest fread nichts mehr und gibt 0 zurück. Das b in "rb" und "wb" steht für binär: Die Datei wird Byte für Byte behandelt, nicht als Text.

Mit welcher Funktion öffnet man in C eine Datei?

Antwort

Mit fopen.

Mit welchem Modus öffnen Sie mit fopen eine Datei, um Text am Ende anzuhängen?

Antwort

"a" (append).

Mit welchem Modus öffnen Sie mit fopen eine Datei, die Sie nur lesen wollen?

Antwort

"r" (read).

Was passiert mit einer vorhandenen Datei, wenn Sie sie mit fopen im Modus "w" öffnen und hineinschreiben?

Antwort

Ihr bisheriger Inhalt wird überschrieben. Wer die alten Daten behalten will, öffnet mit "a".

Welchen Typ hat in phonebook.c die Variable für die geöffnete Datei?

Antwort

FILE *, einen Pointer.

Mit welcher Funktion schreibt phonebook.c Name und Nummer in die Datei?

Antwort

Mit fprintf.

Mit welcher Funktion schließt man eine Datei?

Antwort

Mit fclose.

Auf welchen Rückgabewert von fopen prüft man, um einen Fehler zu erkennen?

Antwort

Auf NULL; dann beendet sich das Programm mit return 1.

Wie wird in cp.c der Datentyp BYTE definiert?

Antwort

Mit typedef uint8_t BYTE;

Valgrind

Valgrind kommt in Vorlesung 4.5 vor. Das Beispiel benutzt sizeof und ein Array aus int, das mit malloc angelegt wird; beides lernen Sie dort kennen.

  • Valgrind ist ein Werkzeug, das ein Programm beim Laufen beobachtet und Speicherfehler meldet: Lesen und Schreiben außerhalb des reservierten Speichers und Speicher, der nie mit free zurückgegeben wurde.

  • Betrachten Sie dieses Programm memory.c:

    #include <stdio.h>
    #include <stdlib.h>
    
    int main(void)
    {
        int *x = malloc(3 * sizeof(int));
        x[1] = 72;
        x[2] = 73;
        x[3] = 33;
    }

    malloc(3 * sizeof(int)) reserviert Platz für drei int, also x[0] bis x[2]. Das Programm schreibt trotzdem nach x[3], und es ruft nie free auf. Es läuft trotzdem ohne sichtbaren Fehler durch.

  • Mit make memory und dann valgrind ./memory bekommen Sie einen Bericht, der beide Fehler nennt. Die wichtigen Zeilen darin sind Invalid write of size 4 (das Schreiben nach x[3]) und definitely lost: 12 bytes in 1 blocks (die drei int, die nie freigegeben wurden).

  • Korrigiert sieht das Programm so aus, und Valgrind meldet keinen Fehler mehr:

    #include <stdio.h>
    #include <stdlib.h>
    
    int main(void)
    {
        int *x = malloc(3 * sizeof(int));
        x[0] = 72;
        x[1] = 73;
        x[2] = 33;
        free(x);
    }

Mit welchem Werkzeug prüfen Sie, ob Ihr C-Programm speicherbezogene Probleme hat, etwa Speicher, den Sie nie freigegeben haben?

Antwort

Mit Valgrind.

Wofür verwendet man Valgrind?

Antwort

Um Programme auf speicherbezogene Probleme zu prüfen, insbesondere ob aller mit malloc zugewiesene Speicher freigegeben wird.

Welchen Fehler in memory.c meldet Valgrind außer dem Schreiben nach x[3]?

Antwort

Ein Speicherleck: x wird nie freigegeben (behoben mit free(x)).

Mit welchem Befehl prüft man das Programm memory mit Valgrind?

Antwort

valgrind ./memory

Warum ist in memory.c die Zuweisung x[3] = 33 ein Fehler, wenn vorher malloc(3 * sizeof(int)) aufgerufen wurde?

Antwort

Reserviert ist nur Platz für 3 Ganzzahlen (x[0] bis x[2]); x[3] wäre die 4. Position, außerhalb des Speicherblocks.

Zusammenfassung

In dieser Vorlesung haben Sie den Speicher als lange Reihe nummerierter Bytes kennengelernt, im Regal, im Hörsaal und am Rechner. Drei Regeln halten das zusammen.

  1. Jede Variable liegt an einer Adresse. &x liefert die Adresse, *p geht dorthin. Adressen schreibt man hexadezimal mit 0x; ein Byte sind zwei Hexadezimalziffern, FF ist 255.
  2. Eine Funktion bekommt Kopien. Soll sie am Original arbeiten, bekommt sie die Adresse, wie bei swap(&x, &y). Ein Array übergibt immer seine Adresse; deshalb ändert Ihre Funktion in Filter das Bild.
  3. malloc reserviert, free gibt zurück und löscht nichts. Danach zeigt der Pointer auf Speicher, der Ihnen nicht mehr gehört; setzen Sie ihn auf NULL. Einen String kopieren Sie mit malloc(strlen(s) + 1), NULL-Prüfung, strcpy und am Ende free.

Für Übung 5 brauchen Sie vor allem den Abschnitt über Bilder: Ein Bild ist eine Tabelle image[i][j], ein Pixel ein struct aus drei Bytes, image[i][j].rgbtRed ist ein Farbwert.

Zum Schluss blieb eine Frage offen: Wie kommt das Bild in den Speicher? In Ihrem filter.c aus Übung 5 stehen schon fopen und fread. Ihre Funktion bekommt das Bild als Tabelle im Speicher, aber vorher liegt es als Datei auf der Festplatte, und das Ergebnis muss wieder in eine Datei. Was fopen und fread dabei tun, klärt Vorlesung 4.5. Wer nicht warten will: Der Abschnitt File I/O weiter oben erklärt beide.

In Vorlesung 4.5 geht es weiter mit dem Speicher: wo im Speicher lokale Variablen und Bytes von malloc liegen (Stack und Heap), wie Sie mit scanf Eingaben lesen und was ein Pufferüberlauf ist, und wie Sie Dateien lesen und schreiben, die Sie für Übung 6 brauchen. Dateien und FILE * stehen in den Notes 4.5.

Bis zum nächsten Mal!

Die Fragen zum Selbsttest helfen beim aktiven Lesen. Sie sind kein Vorgeschmack auf die Prüfung: Fragen und Antworten auswendig zu lernen reicht nicht zum Bestehen und ist vermutlich auch keine sinnvolle Vorbereitung. Was hilft: Wie Sie Inf-Einf-B bewältigen.

Diese Seite als Markdown: ansehen herunterladen