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
swapaus 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
mallocundfree, 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
0x00bis0x0E. 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: Wert Adresse: Wert Adresse: Wert 0x00:030x01:CA0x02:030x03:020x04:050x05:040x06:B80x07:580x08:860x09:0D0x0A:070x0B:0A0x0C:0B0x0D:0C0x0E:ACAdresse und Inhalt sind zwei verschiedene Dinge. Das Fach
0x0Aenthält den Wert07; das Fach0x07enthält58. Wer nach „der 07“ fragt, muss sagen, ob er die Adresse0x07meint oder den Inhalt07. Deshalb tragen Adressen das Präfix0x.Ein Wert kann selbst eine Adresse sein. Im Fach
0x0Bliegt0A. Liest man0Aals Adresse, kommt man zum Fach0x0A, und dort liegt07. Liest man auch das als Adresse, kommt man zum Fach0x07mit dem Wert58. Ob0Aeine 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
0x00und0x02beide03: 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
0x11ganz rechts, und0x12sitzt in Reihe 2 ganz links. Im Saal liegt zwischen beiden die ganze Breite des Mittelblocks; für den Speicher spielt das keine Rolle:0x12ist das Byte nach0x11.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 nurint n;. - Dasselbe gilt für Speicher, den Sie sich später in dieser Vorlesung mit
mallocholen: 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 fasteht für 10,bfür 11 und so weiter bisffü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
09kommt0A, nach0Fkommt10, und10ist 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 . 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.
0x64ist ,0x1Fist ,0xE5ist . Der Mittelblock des Hörsaals hat 230 Plätze,0x00bis0xE5; jede dieser Adressen passt in ein Byte.Das Präfix
0xsagt, dass eine Zahl hexadezimal gemeint ist.0x10ist 16,10ist zehn.Hexadezimalzahlen begegnen Ihnen auch bei Farben:
#FF0000ist 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,
cund lesen es als Zeichen, alschar c. Dann istcder Wert auf Ihrem Etikett und&cIhre 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.pist der Wert auf Ihrem Etikett,*pist der Wert auf dem Etikett, auf daspzeigt, und&pist Ihre eigene Adresse.Ob ein Wert ein Zeichen ist oder eine Adresse, sagt allein der Typ.
5Aist alscharder BuchstabeZ(im ASCII-Code ist Z die 90, hexadezimal5A), alschar *ist es die Adresse0x5A, Reihe 5 im Mittelblock.In der Vorlesung haben wir das an einzelnen Plätzen ausprobiert. Eine Person nannte
&c(ihre Adresse) undc(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über0x0Anach0x07.Dann haben wir über den Pointer geschrieben:
*p = 'H';. Die Person am Ziel schrieb48auf ihr Etikett, dennHist im ASCII-Code hexadezimal48. Auf dem Platz vonpä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 *pgelesen 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:Ausdruck Bedeutung im Hörsaal pder Wert auf Ihrem Etikett, gelesen als Adresse *pder Wert auf dem Etikett, auf das pzeigt&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
E6oder größer. Diese Adressen gibt es im Mittelblock nicht, er endet bei0xE5. 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 CNULLund steht für „zeigt nirgendwohin“. Im Hörsaal gab es zwar einen Platz0x00, als Ziel eines Pointers gilt die 0 aber nicht: Wer00hatte, ging nirgendwohin. Mehr dazu beimalloc.
- In der Vorlesung haben Sie das am Handy geprüft (live.inf.zone): erst gelesen, was bei
*psteht, dann über*pgeschrieben. Wer statt*pden 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
intbelegt 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.&nliest man „die Adresse vonn“.*geht zu der Stelle im Speicher, auf die eine Adresse zeigt.
- Mit
printfund dem Platzhalter%pgeben Sie eine Adresse aus. Ein Pointer auf eininthat den Typint *:int *p = &n;legt eine Variablepan, deren Wert die Adresse vonnist.
#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
50Beide Adressen sind gleich, denn
penthält die Adresse vonn. 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 mit0x7ff.*pgeht zu dieser Adresse und liest dort einint:50.Der Stern hat zwei Bedeutungen, und das verwirrt am Anfang:
- In einer Deklaration wie
int *psagt er, dasspein Pointer ist, hier einer auf einint. - In einem Ausdruck wie
printf("%i\n", *p)heißt er: Geh zur Adresse inp. Das nennt man dereferenzieren.
- In einer Deklaration wie
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
&beiint *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
swapzwei 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 2und dannx ist 1aus.erhoeheerhöht seine Kopiea, nichtx.Das
printfinerhoehesteht dort mit Absicht: Ohne es brichtmakeab, weilaeinen 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 2swapvertauschtaundb, also seine Kopien.xundyinmainbleiben, wie sie waren.- Damit
swapanxundyvonmainherankommt, bekommt es nicht ihre Werte, sondern ihre Adressen. Die Parameter werden Pointer,int *aundint *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
swapund ruft weiterswap(x, y)auf, übersetzt das Programm nicht. Der Compiler meldet, dass einintübergeben wird, wo einint *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 vonxundy:
#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 1Warum der Aufruf mit
&tauscht, zeigten in der Vorlesung die Kartons aus Vorlesung 1 und 3: ein türkiser fürmainmit den Kartenxundy, ein blauer fürswap. Bisher kamen in den blauen Karton Karteikarten mit Kopien der Werte; wasswapmit diesen Karten macht, erreichtmainnie.Diesmal bekommt der blaue Karton keine Kopien der Werte, sondern zwei Zettel mit Adressen: „Adresse von
x“, „Adresse vony“. Folgt man einer solchen Adresse (*a), landet man im türkisen Karton, beixselbst. Dort tauschtswapdie Werte, mittmpals 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
mainwar danach sortiert. Beiswap(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
mittelwertaus den Montagsfragen underhoehevon 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++;
}printfmit%pundnotenohne&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 1noteninmainundwerteinmittelwertsind dieselbe Adresse.mittelwertarbeitet also auf denselben Bytes wiemain. Beixundasind die Adressen verschieden:aist 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
mittelwertsteht vor2.25, weilprintfinmainden Mittelwert erst ausgeben kann, wennmittelwertfertig 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
mittelwertversehentlichint wertestattint werte[], nennt ernotenselbst 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;.
- Stufe 1: Welchen Wert hat
xnachf(x);? - Stufe 2: Welchen Wert hat
xnachg(&x);? - Stufe 3: Welchen Wert hat
xnachh(&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): 5Warum 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:
#FF0000ist volles Rot, kein Grün, kein Blau;#000000ist Schwarz,#FFFFFFWeiß.
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, also6;tabelle[0][0]steht oben links.In Übung 5 heißt die Tabelle
image, undimage[i][j]ist das Pixel in Zeileiund Spaltej. 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 -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 alsstructdefiniert:typedef uint8_t BYTE; typedef struct { BYTE rgbtBlue; BYTE rgbtGreen; BYTE rgbtRed; } RGBTRIPLE;BYTEist ein anderer Name füruint8_t, eine ganze Zahl aus genau 8 Bits ohne Vorzeichen, also von 0 bis 255 bzw.0x00bis0xFF. Das ist das Byte, das auf jedem Etikett im Hörsaal stand.Mehr als 255 passt nicht hinein. Weist man einem
BYTEeinen 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].namein Vorlesung 3:image[i][j].rgbtRedist der Rotwert des Pixels in Zeilei, Spaltej. Drei BytesFF,00,00fü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]);heightundwidthsind die Zahl der Zeilen und Spalten,imagedas Bild. Die beiden Zahlen stehen vorimage, 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 0 | Spalte 1 | Spalte 2 | |
|---|---|---|---|
| Zeile 0 | 30/200/10 | 60/50/40 | 255/0/0 |
| Zeile 1 | 90/80/70 | 255/255/255 | 200/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;
}
}
}- Stufe 1: Was ist
image[1][2].rgbtRed? - Stufe 2: Was steht nach
f(2, 3, image);inimage[0][1], und welche Farbe hat dannimage[1][1]? - 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 0 | Spalte 1 | Spalte 2 | |
|---|---|---|---|
| Zeile 0 | 225/55/245 | 195/205/215 | 0/255/255 |
| Zeile 1 | 165/175/185 | 0/0/0 | 55/155/205 |
Ein Pixel wird kopiert
Ein ganzes
structkönnen Sie mit=zuweisen. Was passiert dabei?RGBTRIPLE p = image[0][1]; p.rgbtRed = 0;Das Bild ändert sich nicht.
pist eine Kopie des Pixels, mit eigenen drei Bytes;p.rgbtRed = 0ändert nur die Kopie. In der Tabelle aus der Übung bleibtimage[0][1].rgbtRed60. Einstructwird 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
-nkennt. Vor der Änderung siehthelpers.cso 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.bmpDas 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.
negativgibt nichts zurück und ändert trotzdem das Bild, dasfilter.cdanach 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
\0endet."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 Typstring: die Adresse des ersten Zeichens.In der CS50-Bibliothek steht dafür eine einzige Zeile:
typedef char *string;stringist also nur ein anderer Name fürchar *, einen Pointer auf einchar. Ohnecs50.hschreiben Siechar *direkt:#include <stdio.h> int main(void) { char *s = "HI!"; printf("%s\n", s); }printfmit%sbekommt die Adresse ins, gibt das Zeichen dort aus, dann das an der nächsten Adresse und so weiter, bis es auf\0trifft.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 vons, und der ist eine Adresse. Danach zeigensundtauf dieselben vier Bytes; wer übertschreibt, ändert, was man übersliest. Für eine echte Kopie brauchtteigenen 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 mitmalloc(memory allocation):malloc(4)reserviert 4 Bytes und gibt die Adresse des ersten zurück. Wer die Bytes nicht mehr braucht, gibt sie mitfreezurück. Beide Funktionen stehen instdlib.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 intschreiben. Gab es mehrere solche Gruppen, bekam die mit der kleinsten Adresse den Zuschlag.Die Adresse
0x00vergibtmallocnie. Sie heißtNULLund bedeutet „zeigt nirgendwohin“. Findetmallockeinen passenden Platz, gibt esNULLzurück; deshalb prüft man nach jedemmalloc, obt == NULList.Dann schrieben die vier Bytes
"HI!"hinein, mitstrcpy(t, "HI!"), das wie das Abschreiben von Zeichen funktioniert (gleich mehr). Im ASCII-Code, hexadezimal geschrieben:Zeichen HI!\0OKWert 484921004F4BDrei Bytes hätten nicht gereicht: Das
\0braucht ein eigenes.printf("%s\n", t)folgt der Adresse intund gibt Zeichen für Zeichen aus, bis es auf00trifft.free(t);setzt den Status der vier Plätze wieder auf F.freelö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 auchtä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: Nachfreewaren genau dieselben Plätze frei wie vor dem erstenmalloc, und die kleinste Adresse war wieder dieselbe.ubekam also dieselbe Adresse wiet.Mit
strcpy(u, "OK!")schrieben die vier4F 4B 21 00. Wer jetzt noch übertliest, bekommt nicht mehrHI!, sondernOK!, obwohl niemandtangefasst hat.Am Rechner ist es oft genauso. Das folgende Programm gibt
tvorfreeaus undunach dem zweitenmalloc; 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 Siet = NULL;. Dann zeigttnirgendwohin, und niemand liest versehentlich übert, was inzwischen jemand anderem gehört.Wer
freevergisst, 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
mallocenthalten 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, dennstrlenzählt das\0nicht mit. Die Kopie braucht aber auch das\0, alsostrlen(s) + 1Bytes. - Das Muster hat vier Teile: Speicher holen, prüfen, kopieren, am Ende zurückgeben. Aus
kopie.cvon 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 mitreturn 1, statt überNULLzu schreiben.strcpy(t, s)(ausstring.h) kopiert die Zeichen vonsnacht, das\0eingeschlossen. Das Ziel steht zuerst, wie bei einer Zuweisungt = s.free(t)gibt den Speicher am Ende zurück.
$ make kopie
$ ./kopie
s: hi!
s: hi!
t: Hi!Jetzt ist nur
tgroß.sundtzeigen auf verschiedene Bytes.strcpytut nichts Geheimnisvolles. Dieselbe Arbeit erledigt eine Schleife, die jedes Zeichen einzeln abschreibt, das\0eingeschlossen (deshalb<=):for (int i = 0, n = strlen(s); i <= n; i++) { t[i] = s[i]; }n = strlen(s)steht im ersten Teil der Schleife, damitstrlennur 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 ermallocbzw.strlennicht 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: 0xaaaae11c3060Die Adressen sind verschieden (Ihre sehen anders aus), also sagt
==„verschieden“, obwohl beide MaleHI!eingegeben wurde.get_stringlegt jede Eingabe an einer eigenen Stelle ab.sundtsind Adressen.s == tvergleicht deshalb Adressen, nicht Zeichen: Es ist nur dann wahr, wenn beide auf dieselbe Stelle zeigen, wie nacht = s.Die Zeichen vergleicht
strcmpausstring.h. Es geht beide Strings Zeichen für Zeichen durch und gibt0zurü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 ProgrammGleichaus.
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!.
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);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);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
- Ein Byte zu wenig:
malloc(strlen(s))holt nur 3 Bytes,strcpyschreibt aber 4, das\0landet hinter dem reservierten Speicher. Was dann passiert, legt C nicht fest; oft sieht man nichts, und gerade das macht den Fehler gefährlich. - 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 + 1ist 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,Iund!untereinander aus.*sist dasselbe wies[0],*(s + 1)dasselbe wies[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_intundget_stringstammen aus der CS50-Bibliothek. Ohne sie liest man Eingaben mitscanfausstdio.h:#include <stdio.h> int main(void) { int x; printf("x: "); scanf("%i", &x); printf("x: %i\n", x); }scanfsoll den gelesenen Wert inxablegen. Weil eine Funktion nur Kopien bekommt, braucht sie dafür die Adresse vonx, wieswap:&x.Bei Strings wird es schwierig. Mit
char *s;undscanf("%s", s);fehlt zwar zu Recht das&, dennsist schon eine Adresse. Abershat 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ürcatund das\0. Wer mehr eintippt, schreibt hinter das Array: ein Pufferüberlauf. Was dann passiert, legt C nicht fest; oft merkt man nichts.scanfmit%sweiß nicht, wie groß der Speicher ist, und ist deshalb unsicher.get_stringholt 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.chängt bei jedem Aufruf eine Zeile an die Dateiphonebook.csvan:#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 TypFILE *zurück. Lässt sich die Datei nicht öffnen, gibtfopenNULLzurück; deshalb die Prüfung direkt danach, wie beimalloc.Das zweite Argument von
fopenist 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.fprintfschreibt wieprintf, aber in die Datei, die als erstes Argument kommt.fcloseschließt die Datei am Ende.Dateien lassen sich auch Byte für Byte kopieren.
cp.cliest 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 inbmp.haus Filter.fread(&b, sizeof(b), 1, src)liest ein Byte aussrcnachb, wieder über die Adresse, wie beiscanf;sizeof(b)ist die Größe vonbin Bytes (mehr dazu in Vorlesung 4.5). Am Ende der Datei liestfreadnichts mehr und gibt 0 zurück. Dasbin"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
freezurü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 dreiint, alsox[0]bisx[2]. Das Programm schreibt trotzdem nachx[3], und es ruft niefreeauf. Es läuft trotzdem ohne sichtbaren Fehler durch.Mit
make memoryund dannvalgrind ./memorybekommen Sie einen Bericht, der beide Fehler nennt. Die wichtigen Zeilen darin sindInvalid write of size 4(das Schreiben nachx[3]) unddefinitely lost: 12 bytes in 1 blocks(die dreiint, 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.
- Jede Variable liegt an einer Adresse.
&xliefert die Adresse,*pgeht dorthin. Adressen schreibt man hexadezimal mit0x; ein Byte sind zwei Hexadezimalziffern,FFist 255. - 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. mallocreserviert,freegibt zurück und löscht nichts. Danach zeigt der Pointer auf Speicher, der Ihnen nicht mehr gehört; setzen Sie ihn aufNULL. Einen String kopieren Sie mitmalloc(strlen(s) + 1), NULL-Prüfung,strcpyund am Endefree.
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