BEngTKI2010 Grundlagen der Programmiersprache C

Transcrição

BEngTKI2010
Grundlagen der Programmiersprache C
Matthias K. Krause
Hochschule für Telekommunikation Leipzig
Deutsche Telekom AG
22. September 2010
Zusammenfassung
Prüfungsbedingungen: Die Prüfung im Fach Grundlagen der Programmierung wird als 90
minütige schriftliche Klausur durchgeführt. Es sind keine Hilfsmittel erlaubt.
Voraussetzung für die Zulassung zur Prüfung ist die Teilnahme an den Übungen und die Abgabe
der zugehörigen Aufgaben.
Dieses Skript entsteht im Rahmen der Vorbereitung einer Lehrveranstaltung zu Grundlagen der
Programmierung. Der Aufbau entspricht nicht der üblichen Darstellung und Beschreibung der Grundlagen einer Programmiersprache, sondern führt schrittweise in verschiedene Bestandteile der Sprache
ein, so daß von Anfang an konkrete Programme Mittelpunkt der Betrachtung sein sollen und die gleiche Problematik wie Variablendeklarationen und -definitionen durchaus mehrfach vorkommen kann.
Ziel der Lehrveranstaltung ist die Gestaltung von Algorithmen zur Lösung konkreter Aufgaben und
deren Umsetzung in eine Programmiersprache.
Es ist somit als Studienanleitung und nicht als Lehrbuch zu verstehen und ersetzt nicht das
Selbststudium von Originalliteratur zur Sprache C und die selbständige kreative Auseinandersetzung
mit der Programmierung.
(c: direkt )
1
1
Einführung
1.1
Literatur
einige Online-Quellen
• Jürgen Wolf: C von A bis Z, Galileo Computing 2006
http://openbook.galileocomputing.de/c_von_a_bis_z/
• C-Tutorial, Roboternetz
http://www.rn-wissen.de/index.php/C-Tutorial
gute kompakte “Einseitenbeschreibung“
• http://de.wikibooks.org/wiki/C-Programmierung
• Martin Leslie: C Referenz: http://www.itee.uq.edu.au/~comp2303/Leslie_C_ref/C/cref.html
Header: http://www.itee.uq.edu.au/~comp2303/Leslie_C_ref/C/FUNCTIONS/funcref.htm
(dt.Übersetzung von G.Junghanns): http://home.fhtw-berlin.de/~junghans/cref/index.html
fehlende Links (15.09.2010)
oder als Papier
• Brian W. Kernighan, Dennis M. Ritchie, et al.: Programmieren in C. ANSI C [1]
• ANSI C 2.0 , Herdt-Verlag [2]
• ...
1.2
Erstellung eines Programmes
Compiler, Linker
Kommandozeile
IDE (Integrated Development Environment), einige Beispiele
• Dev-C++, basiert auf der GNU-Compiler-Collection
(http://www.bloodshed.net)
• gcc (GNU Compiler Collection) mit C- und C++-Compiler (neben vielen anderen), läuft auf
POSIX-Betriebssystemen (Unix, Linux, . . . ), und ist in Cygwin (www.cygwin.com, einer POSIXEmulation für MS-Windows) enthalten
• Turbo-C++ (Borland)
• Visual C++ (Microsoft), hier gibt es ein kostenlos verwendbares Visual Studio C++ Express
(http://www.microsoft.com/express/)
devC++: hier benutzen wir bei Werkzeuge: Compiler Optionen die Standardeinstellung.
(“Alle ANSI-C Programme unterstützen: Yes“ würde zu einigen zusätzlichen Einschränkungen der möglichen Syntax führen.)
1.3
Vorbetrachtungen
Wir wollen, bevor die einzelnen Sprachelemente von C detailliert besprochen werden, einige einfache
Programme betrachten. Zunächst das obligatorische Hallo Welt-Programm:
Listing 1: Das Hallo-Welt-Programm
1
2
#include <stdio.h>
#include <stdlib.h>
3
4
int main(int argc, char *argv[]) {
5
printf("Hallo Welt\n");
// in den Gaensefuesschen (double quotes) steht eine Zeichenkette (String)
6
7
8
}
2
Wir sehen Präprozessoranweisungen und die Methode main(), die in allen C- und C++-Programmen das
Hauptprogramm darstellt.
Als folgendes betrachten wir ein Programm, welches eine Anzahl Quadratwurzeln ausgibt, zugleich sehen
wir C- und C++-Kommentare:
Listing 2: Ein einfaches Programm
1
2
3
4
5
6
7
/* sqrt_va */
/* Preprozessoranweisungen
#include -> Einfuegen eines externen Files
hier werden sogenannte Headerfiles geholt
*/
#include <stdio.h>
#include <stdlib.h>
8
9
10
11
12
13
14
15
/* Hauptprogramm: die Methode main() */
// int main(int argc, char *argv[])
int main(){
// Variablendefinitionen und Initialisierungen
int letzte = 10;
int i;
float wurzel;
16
printf("Wir berechnen die Quadratwurzel von 0 bis %d.\n\n",letzte);
// %d bedeutet Ausgabe von int
17
18
19
// die Schleife:
for (i = 0; i <= letzte; i++) {
// eine Anweisung, die eine Zuweisung ist, links eine Variable (LValue),
// rechts ein Ausdruck mit einem Wert
wurzel = sqrt(i); // sqrt(i) - Quadratwurzel (squareroot) aus i
printf ("Wurzel aus %3d = %7.3f\n", i, wurzel );
}
20
21
22
23
24
25
26
27
}
Für die Ausgaben in Zeile 17 und 25 werden folgende Variablen unter Verwendung von Formatierungsanweisungen ausgegeben:
Variable
letzte
i
wurzel
Format
%d
%3d
%7.3f
Ausgabe als Integerzahl mit soviel Stellen wie nötig
Ausgabe als Integerzahl mit mindestens 3 Stellen
Ausgabe als Gleitkommazahl mit insgesamt 7, davon 3 Nachkommastellen
3
Und noch ein kleines Beispiel mit etwas Arithmetik und Inkrement-/ Dekrementoperatoren ( ++
als Prefix- (steht vor dem Operanden) und Postfix-Operator (steht nach dem Operanden).
Listing 3: Etwas Arithmetik
1
2
3
/* etwasArithmetik.c */
int i,j,k;
float breite,hoehe,flaeche;
4
5
6
7
8
9
10
11
12
i=5;
j = i++;
i=5;
j = ++i;
i=5;
j = i--;
i=5;
j = --i;
// i =
j =
// i =
j =
// i =
j =
// i =
j =
13
14
15
16
breite = 15.0;
hoehe = 2.5;
flaeche = breite * hoehe; // flaeche =
17
18
19
20
float radius, umfang;
radius = 0.5 ;
umfang = 2. * 3.1415 * radius ; // umfang =
Zeile 6:
Zeile 8:
Zeile 10:
Zeile 12:
Der Wert von i wird zuerst verwendet (j zugewiesen), danach wird inkrementiert
(Postfix-Operator).
Der Wert von i wird zuerst inkrementiert, danach wird er verwendet (j zugewiesen) (Prefix-Operator)
Der Wert von i wird zuerst verwendet (j zugewiesen), danach wird dekrementiert (Postfix-Operator)
Der Wert von i wird zuerst dekrementiert, danach wird er verwendet (j zugewiesen) (Prefix-Operator)
4
-- )
2
Programmiersprachenkonzepte und Programmierung
2.1
Einordnung der Programmierung in die Informatik
Bestandteile der Informatik:
• Theoretische Informatik
Automatentheorie,
Algorithmenanalyse,
Theorie der Programmierung,
Theorie der Berechenbarkeit,
...
• Praktische Informatik
Programmiersprachen,
Programmiermethoden,
Algorithmen und Datenstrukturen,
Betriebssysteme,
Softwaretechnik,
...
• Angewandte Informatik
Informationssysteme, . . .
• Technische Informatik
Rechnerarchitektur,
Hardwarekomponenten,
Prozessoren,
...
2.2
Definition und Charakterisierung
Eine Programmiersprache ist eine formale Sprache, die zur Erstellung von Verarbeitungsanweisungen
für Rechnersysteme verwendet wird. Sie richtet sich deshalb in Form und Funktion als Sprache an die
Struktur und Bedeutung von Information. Programmiersprachen dienen der Informationsverarbeitung.
Eine höhere Programmiersprache (engl. high level language) ist eine Programmiersprache, die die
Abfassung eines Computerprogramms in einer abstrakten Sprache ermöglicht (die so zwar für Menschen,
aber nicht unmittelbar für Computer verständlich ist).
Grundmerkmale/Charakteristika einer Programmiersprache:
• Lexik: bestimmt den Aufbau der Grundelemente der Sprache, das sind Ziffern, Buchstaben, Sonderzeichen, Schlüsselworte (reservierte Wortsymbole), Konstanten
• Syntax: gibt die Struktur der Sprache an (zulässige Ausdrücke, . . . )
• Semantik: ordnet den zulässigen Ausdrücken eine Bedeutung zu
5
Syntax-Beschreibungen sind auf verschiedenen Wegen möglich, z.B. über Syntaxdiagramme und
die Erweiterte Backus-Naur-Form (EBNF):
Beispiele für natürliche Zahlen [aus Wikipedia]
Finden Sie den Fehler in der folgenden EBNF!
Wir finden zwei Produktionen in der EBNF, eine für das Nichtterminalsymbol <natzahl> und eine für
das Terminal <ziffer> ,
<ziffer> besteht alternativ aus einer Ziffer von 0 bis 9,
<natzahl> aus einer beliebigen Menge Ziffern (Wiederholung).
• Syntaxdiagramme stellen eine graphische Sprache zur Beschreibung von Grammatiken dar, sie
sind recht übersichtlich und gut lesbar.
• Die Erweiterte Backus-Naur-Form (EBNF) ist eine formale Metasprache zur Beschreibung
von Grammatiken. Eine EBNF definiert Produktionsregeln ( symbol = symbolfolge ; ), in denen
eine Symbolfolge (rechts vom =) einem Symbol zugeordnet wird. Dieses Symbol kann ein Terminal
sein, dann besteht es nur aus Symbolen, die nicht weiter aufgelöst werden müssen, oder aber ein
Nichtterminalsymbol, dann stehen auf der rechten Seite auch Symbole, die weiter verfolgt werden
müssen.
Einige Beispiele für Symbolfolgen:
AB
A|B
[A]
{A}
( A | B ) C
{ "{" }
[’]’]
A gefolgt von B
A oder B
nichts oder A
nichts oder A oder AA oder ...
AC oder BC
nichts oder { oder {{ oder ...
nichts oder ]
Verwendung
Definition
Endezeichen einer Produktionsregel (Definition)
Logisches Oder
Option (0 bis 1)
Optionale Wiederholung (0 bis mehrmals)
Gruppierung
Anführungszeichen (double quotes)
Anführungszeichen (single quotes)
Kommentar
Spezielle Sequenz
Ausnahme
Zeichen
= (auch := oder ::=)
;
|
[ ... ]
{ ... }
( ... )
" ... "
’ ... ’
(* ... *)
? ... ?
-
In der BNF (Vorstufe zu EBNF) ist es üblich, Nichtterminale in den Produktionsregeln in spitze
Klammern einzufügen. In EBNF muß das nicht unbedingt geschehen. Diese Schreibweise wird aber
6
hier bei der (nicht in EBNF formulierten) Syntaxdarstellung für C verwendet. Die spitze Klammer
klammert dann etwas ein, was vom Programmierer einzusetzen ist.
z.B. printf ( <format>, <variablenliste> )
In der EBNF ist es üblich, nicht weiter auflösbare Symbole in den Produktionsregeln in Anführungszeichen zu schreiben (doppelte, Gänsefüßchen, "...", double quotes ODER einfache, single quotes,
’...’). Dadurch werden in der EBNF vorkommende Zeichen (wie z.B. {...}) von den gleichen in
der Sprache beschriebenen Zeichen zu unterscheiden.
Übung 1 Ein Bezeichner beginnt mit einem Buchstaben, gefolgt von beliebig vielen Buchstaben oder
Ziffern. Formulieren Sie die Grammatik in EBNF! Modifizieren Sie die Grammatik so, daß merde kein
gültiger Bezeichner sein darf !
Bestandteile der beiden Metasprachen / Übersetzung von EBNF zu Syntaxdiagramm [aus Wikipedia]
2.3
Abarbeitung von Programmen
Bei der Definition einer höheren Programmiersprache hatten wir erfahren, daß ein Quelltext zunächst
nicht maschinenabarbeitbar ist, er muß also erst in ein sogenanntes Maschinenprogramm überführt werden. Für diesen Weg vom Quelltext zur Maschinensprache unterscheidet man
• Compilersprachen übersetzen den Quelltext (Translation, ein i.A. mehrstufiger Prozeß) und lassen
ein abarbeitbares Programm entstehen (unter Microsoft-Windows z.B. Dateien mit der Endung
exe)
• Interpretersprachen arbeiten den Quelltext Zeile für Zeile ab, indem diese erst übersetzt und anschließend sofort abgearbeitet wird
• Mischformen, z.B. kann der Quelltext zunächst als ganzes übersetzt und dann sofort abgearbeitet
werden (z.B. bei Perl), ein maschinenabarbeitbares Programm existiert nicht in Dateiform.
Die Programmiersprache C ist eine klassische Compilersprache, im Abschnitt 8.3 (S.43) wird der Prozeß
vom Quelltext zum ausführbaren Programm dargestellt.
7
3
Algorithmen und die Sprache C
3.1
3.1.1
Vereinbarung von Variablen (Daten)
Elementare Datentypen
• Ganzzahltypen
char (1 Byte) für ein Character (Zeichen), z.B. ein ASCII-Zeichen
int (n Byte, rechnerabhängig, es gilt short ≤ int ≤ long)
Wir befragen den Rechner mit
printf ( "Groesse von int in Byte : %2d\n", sizeof(int) );
short (2 Byte), long (4 Byte), long long (8 Byte)
• Gleitkommatypen (rationale Zahlen)
float (4 Byte), double (8 Byte), long double (12 Byte)
• Boolscher Typ . . . Wahrheitswert (wahr/falsch, true/false) existiert nicht in C,
man nimmt einen beliebigen Typ (z.B. int), und es gilt die Zuordnung
W ert = 0 −→ f alse
W ert 6= 0 −→ true
3.1.2
Variablen und Felder
Deklaration: Bekanntgabe einer Variablen ohne Speicherplatzbereitstellung.
Definition: Bekanntgabe einer Variablen mit Speicherplatzbereitstellung.
Gültigkeitsbereich von Variablendefinitionen:
• global, wenn Definition außerhalb der Methoden (z.B. oft vor main()) erfolgt, diese Definition ist
überall dort gültig, wo sie nicht durch eine lokale Definition überdeckt wird
Ablage in Datensegment(en)
• lokal innerhalb des Blockes, in dem sie definiert wurden. (Ein Block ist eine Folge von Anweisungen,
die in geschweifte Klammern eingeschlossen ist: { Anweisungen } )
kann durch eine lokalere Definition (mit gleichem Variablennamen) überdeckt werden
Ablage auf dem Stack, in der Reihenfolge der Definition, die Parameter der Methoden werden beim
Methodenruf in umgekehrter Reihenfolge der Definition abgelegt!
Wo welche Variablen/Daten zur Laufzeit des Prozesses leigen, wird unter 3.6 (S.15) nochmals vertieft.
Listing 4: Beispiele für Variablen und Felder
1
2
3
4
...
int i;
float f1,f2;
float pi = 3.1415;
5
6
7
float spektrum_xwerte[256];
float spektrum_ywerte[256];
8
9
10
11
double x[100] = {1, 2, 3, 4, 5, 6}; // ... und Init. der 1. sechs El.
double matrix[5][5]; // 25 Elemente
...
Listing 5: Zugriff auf Feldelemente
13
14
15
16
...
x[0] = f1; // 1.Element von x
x[99] = f2; // letztes Element von x
...
Syntaxbeschreibung von Variablendefinitionen (keine Felder) (EBNF):
8
var_def
typ
ganzzahltyp
gleitkommatyp
varname
varinit
=
=
=
=
=
=
typ varname [ varinit ] { ’,’ varname [ varinit ] } ’;’ ;
ganzzahltyp | gleitkommatyp ;
"char" | "short" | "int" | "long" | "long long" ;
"float" | "double" | "long double" ;
buchstabe { buchstabe | zahl } ; (* ohne Leerzeichen!!! *)
’=’ zahlenliteral ;
Eigentlich müsste beim Zahlenliteral zwischen solchen für ganze Zahlen (3 -25 +8 0) und solchen für
Gleitkommazahlen (3.1415 -25.3 +8.9 0.0 .0 .234 1.234e-5) unterschieden werden! Das würde die
gesamte Grammatik etwas komplizierter machen, worauf hier verzichtet werden soll.
Syntaxbeschreibung von Felddefinitionen (EBNF):
feld_def
feldklammern
varinit
= typ varname feldklammern [ varinit ] { ’,’ varname ... } ’;’ ;
= ’[’ integerkonstante ’]’ { ’[’ integerkonstante ’]’ } ;
= ... ;
Übung 2 Was druckt das folgende Programm aus, welche Variablendefinition ist von wo bis wo gültig?
1
2
3
/* varGueltigkeit.c */
...
int i = 100000;
4
5
6
7
8
9
10
11
12
13
14
15
16
int main(int argc, char *argv[])
{
printf("%d\n", i);
int i = 5;
printf("%d\n", i);
{
int i = 100;
printf("%d\n", i++);
printf("%d\n", ++i);
}
printf("%d\n", i);
}
3.2
Darstellung von Algorithmen und ihre Umsetzung in C
Einige Darstellungsmöglichkeiten:
• Textform (verbale Beschreibung)
• Struktogramm (Nassi Shneiderman)
• Programmablaufplan
• Pseudokode
• konkrete Programmiersprache
• ...
Im weiteren sollen grundlegende Algorithmenbausteine in ihrer Darstellung als Nassi-ShneidermanDiagramme (Struktogramme) und deren Umsetzung in C beschrieben werden.
3.2.1
Elementarblock/-baustein (Aktion)
9
3.2.2
Strukturblock
Der Ruf eines Strukturblockes:
3.2.3
Sequenz (Folge)
3.2.4
Alternative (Einfachverzweigung)
Syntax:
if ( <bedingung> )
<anweisung1>
else
<anweisung2>
Syntax (EBNF):
if-statement
bedingung
anweisung
einzelanweisung
block
=
=
=
=
=
"if" "(" bedingung ")" anweisung [ "else" anweisung ] ;
BoolscherAusdruck ;
einzelanweisung | block ;
ausdruck ’;’ ;
’{’ { anweisung } ’}’ ;
Beispiel:
if ( Nenner != 0 )
Quotient = Zaehler / Nenner;
else
printf("Division durch Null!");
10
3.2.5
Selektion (Mehrfachverzweigung, Mehrfachauswahl)
Syntax:
1
2
3
4
5
6
7
8
9
10
switch (<Ausdruck>)
{
case konstante1:
<Anweisung>
...
break;
case konstante2:
<Anweisung>
...
break;
11
12
/* weitere case-Marken */
13
14
15
16
17
default:
<Anweisung>
...
} /* Ende von switch */
Der Ausdruck nach switch muß einen Ganzzahltyp liefern (char, int, ...), dieser Wert wird dann in den
Konstanten an den case-Marken gesucht, wird eine passende Konstante gefunden, wird an dieser Stelle
der Code der switch-Anweisung weiter abgearbeitet und am break verlassen. Wird kein passender Wert
gefunden, wird zum default gesprungen. Die Konstanten dürfen Literale, aber auch Variablen sein, aber
diese müssen zur Compilezeit bekannt sein.
Beispiel:
Listing 6: Ausschnitt aus switch.c
1
2
3
4
5
6
7
8
9
10
11
printf("Eingabe a oder b oder ...:");
switch (getch()) { // getch() liest einen charakter von der Konsole
case ’a’:
printf("a\n");
break;
case ’b’:
printf("b\n");
break;
default:
printf("watt anneres\n");
} /* Ende von switch */
3.2.6
Schleife (Wiederholung, Iteration)
Abweisende (kopfgesteuerte) Schleife
Die while-Schleife:
11
while (<bedingung>)
<anweisung>
Die for-Schleife:
Syntax:
for (<initialisierung>;<bedingung>;<ausdruck>)
<anweisung>
Darstellung als while-Schleife:
<initialisierung>;
while (<bedingung>) {
<anweisung>
<ausdruck>;
}
Beispiele:
1
2
3
4
5
6
7
8
a =
c =
for
a
for
b
c
}
b = 0;
1;
(i = 0; i < 6; i++)
= a + i;
(i = 0; i < 10; i++) {
= b + i;
= c * i;
Nichtabweisende (fußgesteuerte) Schleife
do
<anweisung>
while (<bedingung>);
3.3
Algorithmenentwurf
Begriffe:
Mathematisches Modell
Algorithmus, Abarbeitungsvorschrift für das mathematische Modell, formalisierte Rechenvorschrift als
lösender Algorithmus
Die Lösung einer quadratischen Gleichung
y = a ∗ x2 + b ∗ x + c
Bestimmung der Nullstellen der Gleichung, d.h. man sucht die x-Werte, für die sich y = 0 ergibt.
0 = a ∗ x2 + b ∗ x + c
12
Überführung in die Normalform
0 = x2 + p ∗ x + q
p = b/a
q = c/a
Die zwei Lösungen sind
q
2
x1,2 = − p2 ± p4 − q
bzw. mit a,b,c als Parameter
q
b
b2
c
x1,2 = − 2a
± 4a
2 − a
Fallunterscheidung für d =
b2
4a2
−
c
a
• d > 0 : 2 Lösungen x1 , x2
• d = 0 : 1 entartete Lösung x1,2 = x1 = x2
• d < 0 : keine reelle Lösung
Übung 3 Entwickeln Sie einen Algorithmus für die Berechnung der Lösungen der quadratischen Gleichung als Struktogramm und das entsprechende C-Programm.
Übung 4 Entwickeln Sie einen Algorithmus für die Berechnung des Skalarproduktes zweier Vektoren ~a
und ~b
Skalarprodukt = a1 × b1 + . . . + an × bn
einschließlich vorangehender Eingabe der Dimension n und der beiden Vektoren! Setzen Sie den Algorithmus in ein C-Programm um!
--L-Begin-------------------------------------------------------------------------Lösung zu Übung 4:
--L-End----------------------------------------------------------------------------
3.4
Modularisierung
Bei der Analyse einer Problemstellung wird man versuchen, das Problem von oben nach unten in Einzelprobleme zu zerlegen (Top-Down-Entwurf), diese Einzelprobleme werden in zu entwickelnden Algorithmen umgesetzt.
Diese Algorithmen haben die Eigenschaften
• Allgemeingültigkeit, d.h., sie sind jeweils für eine Klasse von Aufgaben geeignet,
• und Determiniertheit, d.h., zu jedem Zeitpunkt ist genau bestimmt, was als nächstes zu tun ist.
Dieser Vorgang der Zerlegung wird als Modularisierung bezeichnet.
Ein Modul ist durch seine Schnittstelle (das ist hier die Liste der formalen Parameter / Formalparameter) und die konkrete Implementierung (Modul-Block) charakterisiert:
Modul
<Modulname> (<Formalparameterliste>)
{
<Modul-Block>
}
mit (EBNF)
Formalparameterliste = ’’ | Formalparameter { ’,’ Formalparameter } ;
Formalparameter
= typ name ;
13
Nutzung eines Moduls (Modulaufruf), hier nehmen Aktualparameter (aktuelle Parameter) den
Platz der Formalparameter ein:
<Modulname> (<Aktualparameterliste>)
mit (EBNF)
Aktualparameterliste = ’’ | Aktualparameter { ’,’ Aktualparameter } ;
Aktualparameter
= ausdruck ;
Methoden
Modularisierung wird in C durch Unterprogrammtechnik oder exakter gesagt durch Methoden umgesetzt.
Das folgende Beispiel zeigt ein Listing, in dem eine Methode mit folgenden Eigenschaften
• Name: max
• Parameteranzahl: 2 , Typ jeweils double (formale Parameter)
• Rückgabetyp: double
definiert und in der main-Methode gerufen wird:
Listing 7: Methodendefinition und Ruf
1
2
#include <stdio.h>
#include <stdlib.h>
3
4
5
6
7
double max (double z1, double z2) {
if (z1 >= z2) return z1;
else
return z2;
}
8
9
10
11
12
13
int main(){
double a = 3.2, b = 5.67;
printf("Das Maximum von %lf und %lf ist %lf \n", a, b, max(a,b));
}
Diese Methode bestimmt das Maximum der zwei übergebenen aktuellen Parameter und gibt den größeren
der beiden Werte zurück.
Syntax (EBNF):
methoden_definition = methodenkopf methodenkoerper ;
methoden_deklaration = methodenkopf ";" ;
methodenkopf
=
formalparameterliste
formalparameter
=
methodenkoerper
=
typ
= [
typ
"{"
methodenname "(" formalparameterliste ")" ;
formalparameter { "," formalparameter} ] ;
varname ;
... "}" ;
methodenruf
= methodenname "(" aktualparameterliste ")" ;
aktualparameterliste = [ aktualparameter { "," aktualparameter} ] ;
aktualparameter
= ausdruck ;
Die Art der Parameterübergabe an eine Methode wird als Call by value bezeichtet, dazu wird bei
der Methode eine Kopie des Wertes des aktuellen Aufrufparameters abgelegt. Dieser Wert kann in der
Methode zwar verändert werden, wird aber NICHT zurückgegeben.
3.5
Rekursion
Unter Rekursion versteht man die Definition eines Verfahrens (Funktion, Problem) durch sich selbst.
Wichtig ist in diesem Zusammenhang, daß eine Abbruchbedingung auf den Eingabedaten definiert ist.
14
Standardbeispiel Berechnung der Fakultät
n > 1 −→ n! = n ∗ (n − 1)!
n = 1 −→ n! = 1
Übung 5 Entwickeln Sie einen Algorithmus für die Berechnung der Fakultät als Struktogramm und das
entsprechende C-Programm!
3.6
Variablen im Speicher
Prinzipiell wird der Speicher in Segmente unterteilt (Größe dieser ist abhängig vom Speichermodell),
folgende Aufteilung gilt für klassische unixoide Betriebssysteme (Herold [3]):
• Code-Segment (auch Text-Segment): der Programmcode in Maschinensprache
• Datensegmente für globale und statische Variablen
– Data-Segment: Daten, die zur Laufzeit genau einmal existieren und beim Start initialisiert
werden müssen (initialisierte globale und statische lokale Variablen)
– Block-started-by-Symbol (auch als Block-Storage-Segment bezeichnet) (BSS): Daten, die zur
Laufzeit genau einmal existieren und nicht initialisiert werden müssen
• Heap-Segment (Heap): Speicher zur freier Verfügung des Programms, wird mit malloc reserviert
und mit free wieder freigegeben (wächst von unten nach oben)
• Stack-Segment (Stack): Daten die zur Laufzeit in geordneter Reihenfolge entstehen und in genau
umgekehrter Reihenfolge entfernt werden müssen (wächst von oben nach unten),
– das sind natürlich die Aufrufparameter der Methoden in umgekehrter Reihenfolge ihrer
Definition,
– alle Variablen (außer static), die innerhalb von Methoden definiert werden in Reihenfolge
ihrer Definition,
– und weitere Daten, auf die hier nicht eingegangen werden soll
Unter http://www.wachtler.de/ck/9_Speichermodell_Prozesses.html findet man ein gutes Beispiel,
wo die Variablen eines Prozesses zu einem C-Programm im Speicher angelegt werden.
15
4
Ausgabe / Eingabe
Betrachten wir ein Programm nach dem EVA-Prinzip, EVA ist hier ein Akronym (eine als Wort ausgesprochene Abkürzung mit den Anfangsbuchstaben für Eingabe, Verarbeitung und Ausgabe):
Listing 8: Ein einfaches Programm nach dem EVA-Prinzip
1
2
3
4
5
6
7
/* sqrt_eva */
/* Preprozessoranweisungen
#include -> Einfuegen eines externen Files
hier werden sogenannte Headerfiles geholt
*/
#include <stdio.h>
#include <stdlib.h>
8
9
10
11
12
13
14
int main(){
// Variablen
int zeilen;
int i;
float wurzel;
15
// eine einfachste Ausgabe:
printf("\nEingabe der letzten Zahl (ganze Zahl): ");
// eine Eingabe, sie landet in der Variablen zeilen:
scanf("%d",&zeilen); // & ermittelt die Adresse der Variablen
// eine Ausgabe von Text und einer Variablen:
printf("Wir berechnen die Quadratwurzel von 0 bis %d.\n\n",zeilen);
// %d bedeutet Ausgabe von int
16
17
18
19
20
21
22
23
// die Schleife:
for (i = 0; i <= zeilen; i++)
printf ("Wurzel aus %3d = %7.3f\n", i, sqrt(i) ); // sqrt(i) - Quadratwurzel aus i
24
25
26
27
getch();
28
29
}
4.1
Ausgabe mit printf(. . . )
Formatgesteuerte Ausgabe (ein wenig EBNF):
printf(<format> [, <argument> ] ... );
Listing 9: Beispiele zu printf
1
...
2
3
4
5
printf("Hallo Welt\n");
printf("%s\n", "Hallo Welt");
printf("%s %s\n", "Hallo", "Welt");
6
7
8
char *s = "Hallo Welt";
printf("%s\n",s);
9
10
11
int i = 15;
printf("i = %d\n",i); // Ausgabe: i=15
12
13
14
15
float f = 3.1415;
printf("f=%10.6f\n",f); // Ausgabe: f= 3.141500
...
16
4.2
Eingabe mit scanf(. . . ) u.a.
Formatgesteuerte Eingabe:
scanf( <format> [, <adresse> ] ... );
scanf liest den Eingabestrom entsprechend der Formatzeichen im Formatstring <format>, Trennzeichen
sind Leerzeichen etc. Es wird entsprechend der gefundenen Formatzeichen gescannt, und dann aufgehört,
wobei unter Umständen noch Zeichen und Zeilenvorschub im Puffer stehen bleiben können, die dann u.U.
von anderen Leseoperationen wie einem folgenden gets(...) oder auch dem nächsten scanf gelesen
werden.
Listing 10: Beispiele zu scanf
1
2
3
4
5
6
7
int iz;
float fz;
printf("\nEingabe int float:");
scanf("%d%f", &iz, &fz);
printf("\nEingabe string:");
char charfeld[100];
scanf("%s",charfeld);
Das & vor den Variablennamen ist der Adressoperator, dadurch entsteht ein Call by Reference, über
die Reference ist das scanf in der Lage, Werte zurückzugeben.
Der Ausdruck charfeld (Zeile 7) ist eigentlich wie jeder Feldname ein Pointer (Zeiger, Referenz, siehe
5.1.1, S.21).
Zu den Formatierungszeichen siehe
• blaues Heftchen
• oder ANSI C 2.0 [2, S.26]
Zeilenweise Eingabe:
// char *<adresse>;
gets( <adresse> );
gets liest den Eingabestrom stdin ab der aktuellen Stelle bis zum nächsten newline. Wenn von der
letzten Eingabe noch ein ungelesenes newline / ENTER (und davor ggf. noch Zeichen) im Puffer ist, liest
gets diese Zeichen, ohne nochmals anzuhalten.
Vorsicht: Sowohl beim scanf als auch beim gets ist als Parameter die Adresse eines vorhandenen
Strings (bzw. eines Puffers) zu verwenden (d.h., falls ein Pointer verwendet wird, muß dieser auf einen
entsprechenden Puffer zeigen, siehe Zeile 6/7 im Listing 10), die Verwendung eines nicht entsprechend
initialisierten Pointers führt zum Fehler! Die Größe der Eingabe beim scanf oder gets kann natürlich
vorher nicht mit Sicherheit vorausgesagt werden, so daß die Gefahr eines Bufferoverflows besteht. Diese
Gefahr wird vermieden
• durch die Angabe der Länge im Formatstring (z.B. %10s) beim scanf
• bzw. durch Verwendung von fgets statt gets, wenn buffersize den hinter adresse reservierten
Platz nicht übersteigt. Hier wird aus dem Gerät hinter filepointer gelesen.
// char *<adresse>;
// int buffersize;
// FILE *filepointer;
fgets( <adresse>, <buffersize>, <filepointer> );
Auch hier kann man einfach von der Standardeingabe (Konsole) lesen:
char line[100];
fgets( line, 100, stdin );
17
Der Ausdruck line ist eigentlich ein Pointer (Zeiger, Referenz), was an späterer Stelle (siehe 5.1.1,
S.21) noch genauer behandelt wird.
Ein Beispiel, in dem jede (selbst eine letzte nicht mit Zeilenvorschub abgeschlossene) Zeile eines Files
gelesen und auf der Konsole ausgegeben werden:
Listing 11: Lesen und drucken eines Files
1
2
3
/* readFile.c */
#include <stdio.h>
#include <stdlib.h>
4
5
6
7
{
char line[1000];
8
FILE *f;
f = fopen("_i.txt","r");
9
10
11
while (!feof(f)) {
fgets(line,1000,f);
printf("%s",line);
}
return 0;
12
13
14
15
16
17
}
In Zeile 9 wird eine Variable f definiert, die ein Zeiger (Pointer) auf einen Typ FILE darstellt und in der
nächsten Zeile mit einem zum Lesen geöffneten File _i.txt verknüpft wird.
Die mit gets(...) oder fgets(...) erhaltenen Strings (Charakterfelder) können mit Funktionen wie
atoi(...), atof(...) (steht für “ASCII to Integer/Float“) oder sscanf(...) weiter in entsprechende
Zahlenformate gewandelt werden (siehe C-Standardbibliothek 6)
4.3
Ein-/Ausgabeumlenkung (I/O redirection)
In Übung 4 (S.13) hatten wir ein Skalarprodukt berechnen lassen, alle Eingaben kamen interaktiv von
der Konsole. Die Lösung könnte so aussehen:
Listing 12: Berechnen eines Skalarproduktes
1
2
3
4
5
/* skalarProdukt.c */
#include <stdio.h>
#include <stdlib.h>
#define N 100
void ausgabe(char *name, int DIM, double *vec);
6
7
8
9
10
11
12
13
14
{
int DIM = 0, i;
double a[N], b[N], sp = 0.0 ;
while (DIM <= 0 || DIM > N) {
printf("Dimension ( 0 < DIM < %d ): ", N);
scanf("%d",&DIM);
}
15
16
17
18
19
20
21
printf("a[0] ... a[%d] : ",DIM-1);
for (i=0;i<DIM;i++)
scanf("%lf",&a[i]);
printf("b[0] ... b[%d] : ",DIM-1);
for (i=0;i<DIM;i++)
scanf("%lf",&b[i]);
22
23
18
for (i=0;i<DIM;i++){
sp+=a[i]*b[i];
}
24
25
26
27
printf("Ausgaben:\n");
ausgabe("a",DIM,a);
ausgabe("b",DIM,b);
printf("Skalarprodukt: %7.1lf\n",sp);
28
29
30
31
32
system("PAUSE");
return 0;
33
34
35
}
36
37
38
39
40
41
42
43
44
void ausgabe(char *name, int DIM, double *vec ) {
/* oder
(char name[], int DIM, double vec[]) */
printf("%5s = ( %5.1lf", name, vec[0]);
int i;
for (i=1; i<DIM; i++)
printf(" , %5.1lf ", vec[i]);
printf(" )\n");
}
In Zeile 11 wird verhindert, daß die Dimension der Vektoren die in Zeile 4 festgelegte Größe überschreitet. Wenn in Zeile 13 bereits alle durch scanf(...)s zu lesenden Werte eingegeben werden, so hält das
Programm kein weiteres Mal an! Daraus kann man schließen, daß das Programm die Daten der Standardeingabe nur irgendwie zeitig genug bekommen muß, dann wird es schon klappen. Wir versuchen
folgendes:
skalarProdukt.exe < sp.txt
Das ist eine Eingabeumlenkung, an Stelle der Tastatur wird hier die Datei sp.txt auf die Standardeingabe
der Applikation umgelenkt. Wenn sp.txt den Inhalt
3
2. 3. 5
1.0 2 -1.
hat, so macht die Applikation ihre Ausgaben, muß aber nicht auf Eingaben warten. So kann man sich
durch Aufbewahren von Daten in Dateien lästige Interaktionen sparen und etwas für die Automatisierung
von Berechnungen tun.
Übung 6 Im Listung 12 zum Skalarprodukt wurde bei der Ausgabe bereits etwas abstrahiert und modularisiert. Setzen Sie diesen Prozeß fort!
Die folgenden Aufrufe enthalten Ausgabeumlenkungen:
progname > 1.txt
progname 2> 2.txt
lenken die Standardausgabe in eine Datei 1.txt bzw. die Standardfehlerausgabe in eine Datei 2.txt .
progname > 1.txt
2> 2.txt
lenkt die Standardausgabe in eine Datei 1.txt und die Standardfehlerausgabe in eine Datei 2.txt .
progname > 1und2.txt
2>&1
lenkt die Standardausgabe und die Standardfehlerausgabe in eine Datei 1und2.txt .
Übung 7 Testen Sie die Ausgabeumleitungen z.B. mit einem Befehl wie dir oder dir *.grks , wenn
sich keine Datei mit der Endung grks im Verzeichnis befindet. Was landet auf
stdout , was auf
stderr ?
19
4.4
Betrachtungen zur Formatierung der Ausgabe
Was bei der Ausgabe einer Zahl (z.B. vom Typ int) ausgegeben wird, hängt in hohem Maße vom Bitmuster der Zahl und von den Formatierungszeichen ab, gibt man eine Ganzzahl mit der Formatierung %u
aus, so wird das Bitmuster unabhängig vom tatsächlichen Wert und Typ als unsigned int interpretiert,
d.h., für gewisse (welche?) Zahlenbereiche ergibt das falsche Formatflag einen falschen Wert. Das soll am
folgenden Beispiel demonstriert werden:
max signed int
min signed int
max unsigned int
2n−1 − 1
−2n−1
2n − 1
high
Bits
low
01111111111111111111111111111111
10000000000000000000000000000000
11111111111111111111111111111111
%12d
2147483647
-2147483648
-1
%12u
2147483647
2147483648
4294967295
Die Bitdarstellung der negativen Zahlen entspricht dem Zweierkomplement.
Das ganze wurde mit folgendem Programm erzeugt:
1
/* printfInteger.c */
2
3
#include <math.h>
4
5
6
7
/* Deklaration einer Methode,
die das Bitmuster von 4 Byte int als String zurueckgibt */
char * intToBitsAsString (int intZahl);
8
9
10
11
12
int main(){
const signed int MaxSInt = pow(2,31)-1;
const signed int MinSInt = - pow(2,31);
const unsigned int MaxUInt = pow(2,32)-1;
13
unsigned int u;
int i;
printf("
high
%%12d
%%12u\n");
14
15
16
17
Bits
low\
18
printf("max signed int %32s %12d %12u\n",
intToBitsAsString (MaxSInt), MaxSInt, MaxSInt);
printf("min signed int %32s %12d %12u\n",
intToBitsAsString (MinSInt), MinSInt, MinSInt);
printf("max unsigned int %32s %12d %12u\n",
intToBitsAsString (MaxUInt), MaxUInt, MaxUInt);
19
20
21
22
23
24
25
getch();
26
27
}
28
29
...
Die Methode aus Zeile 7 werden wir später verstehen (Listing 25 auf S. 27)
Noch verwirrender wird es bei kürzeren Zahlen (short, char). Wenn Typ (signed oder unsigned) und
Formatierungsflag übereinstimmen, kann man jedoch unabhängig von der Anzahl der Bytes mit dem
richtigen Wert rechnen.
20
5
5.1
Daten und Operationen
Strukturierte Datentypen
5.1.1
Felder (Arrays)
Syntax:
<typ> <bezeichner>[<konst_ausdruck>]...;
Syntax (EBNF)
felddefinition = typ bezeichner ’[’ konst_ausdruck ’]’ { ’[’ konst_ausdruck ’]’ } ’;’ ;
Listing 13: Beispiele für Felddefinitionen
1
2
3
4
float f[100];
char charfeld[80];
double spektrum[2][100];
double c[2][2][2];
Die Namen der Arrays (f, charfeld, spektrum, c) alleinstehend verwendet enthalten Zeiger (Pointer)
auf die Anfänge der Felder. Deshalb kann auch eine Methode wie fgets(line, ...) (siehe S.17) trotz
des scheinbaren “Call by value“ den String in den Parameter line schreiben!
Speicherstruktur eines Arrays: C unterstützt mehrdimensionale Felder, die Elemente werden nacheinander im Speicher abgelegt, der rechte Index variiert am schnellsten. Reihenfolge der Elemente des
Arrays c :
c[0][0][0]
c[0][0][1]
c[0][1][0]
c[0][1][1]
c[1][0][0]
c[1][0][1]
c[1][1][0]
c[1][1][1]
Bei der Initialisierung von Arrays kann die Dimension durch eine Schachtelung von geschweiften Klammern berücksichtigt werden, muß aber nicht. Beide Schreibweisen sind gleichwertig:
Listing 14: Beispiele für Felddefinitionen mit Initialisierungen
1
2
int i[2][2] = { 1,2,3,4 };
int j[2][2] = { { 1,2 } , { 3,4 } };
Übung 8 Entwickeln Sie einen Algorithmus und ein C-Programm zur Befüllung einer Datenstruktur
int ifeld[I][J][K];
mit int-Zahlen, beginnend bei 1, so daß im Speicher eine aufsteigende Reihe natürlicher Zahlen steht.
I,J,K seien int-Konstanten.
Strings
Strings sind Arrays of Character, die in C mit einer numerischen Null (also einem Element, in dem alle
Bits 0 sind, abgeschlossen werden. Eine andere Kennzeichnung des Endes gibt es nicht!
Listing 15: C-Strings
char s[10] = "Eva";
Das Feld s hat eine Gesamtlänge von 10, der zunächst mal mit dem String Eva initialisiert wird, aber Platz
für mehr bietet. In den ersten drei Elementen (c[0] . . . c[2]) steht Eva, in c[3] steht eine numerische
0 (nicht das ASCII-Zeichen 0), danach stehen undefinierte Zeichen. Das bedeutet, daß in einem String
der Länge N Platz für N-1 Zeichen ist. Die abschließende numerische 0 ist als Stringende notwendig und
wird von allen String-Funktionen genutzt.
’E’
’v’
’a’
0
?
?
?
?
?
?
Vorsicht: Der Initialisierer darf max. ein Zeichen weniger als die Länge enthalten. Soll die Länge des
Feldes genau an den Initialisierer angepasst sein, gibt man keine Länge an:
Listing 16: C-Strings mit angepasster Länge
char s[] = "Eva";
21
Außerhalb einer Variablendefinition mit Initialisierung ist diese Art der Zuweisung nicht möglich, es wird
die Methode strcpy(...) oder strncpy(...) verwendet, das entsprechende Headerfile string.h (siehe
Kapitel 6, S.31) ist mittels #include <string.h> einzufügen:
Listing 17: Zuweisung eines Strings an ein Array
#include <string.h>
...
char s[10];
strcpy(s, "Eva");
strncpy(s, "Eva", 10);
Hier ist wieder auf die ausreichende Größe des Arrays Wert zu legen!
Soll auf dem Stack beim Ruf einer Methode ein Feld angelegt werden, dann folgendermaßen:
Listing 18: Anlegen eines Arrays mit variabler Größe
1
2
3
4
5
6
...
void myMethod(int size){
...
char feld(size);
...
}
Natürlich kann die Größe size auch in Zeile 3 festgelegt werden!
5.1.2
Strukturen
Syntax:
struct <bezeichner> {
<typ1> <var1>;
...
};
Syntax (EBNF):
struct_def = "struct" [structname] "{"
typ membername
{ "," typ membername }
"}" [ varname {"," varname } ] ";" ;
Auf den Namen der Struktur (structname) kann verzichtet werden, wenn er später nie wieder verwendet
wird und hier alle benötigten Variablendefinitionen erfolgen.
Listing 19: Beispiel für Strukturen
1
2
3
4
struct rechteck {
float laenge;
float breite;
};
5
6
struct rechteck r1, r2;
7
8
9
10
r1.laenge = 3.;
r1.breite = 4.5;
/* oder : struct rechteck r3 = {2.5, 3.0} ; */
11
12
printf("Flaeche : %4.1f", r1.laenge * r1.breite);
rechteck ist der Name der Struktur, r1 und r2 sind die Namen von Variablen dieses Typs.
. . . das Gleiche wie die Anweisungen in Zeile 1 bis 6 machen folgende Zeilen:
22
1
2
3
4
struct rechteck {
float laenge;
float breite;
} r1, r2;
5
6
...
Mit sizeof läßt sich der Speicherplatzbedarf eines Ausdrucks, Typs, . . . bestimmen:
int sizeof( <ausdruck> );
int sizeof( <typ_spec> );
sizeof entspricht den Ausrichtungsanforderungen der Datentypen im Speicher, d.h., es kann durchaus
mehr Platz als die Summe der einzelnen Speicherbedarfe gemeldet werden! So kann zum Beispiel die
Ausrichtungsanforderung bestehen, daß ein float immer an einer durch 4 teilbaren Adresse (Beginn
eines Wortes) beginnt. Das testen wir mit folgendem Programm:
Listing 20: Speicherbedarf von Daten/Strukturen
1
2
3
4
struct mydata {
float zahl;
char chr;
};
5
6
printf("Platzbedarf : %d\n", sizeof(struct mydata));
Es spielt für den Speicherbedarf keine Rolle, ob in Zeile 3 ein, zwei, drei oder vier Character (1 Byte)
definiert werden, der Bedarf liegt immer bei 8 Byte, da die nächste Einheit des Types mydata erst wieder
an einer durch 4 teilbaren Adresse stehen kann:
zahl
chr
leer
leer
leer
typedef
Soll auf die Verwendung des Schlüsselwortes struct bei den Variablendefinitionen verzichtet werden,
kann mit typedef die Definition eines Typs realisiert werden:
Syntax (EBNF):
typedef = "typedef" "struct" [structname] "{"
typ membername
{ "," typ membername }
"}" structtypname ";" ;
nutzung_struct = "struct" structname varname {"," varname} ";" ;
nutzung_typedef = structtypname varname {"," varname} ";" ;
. . . so wird Listing 19 unter Verwendung von typedef zu:
Listing 21: Beispiel zur Definition eigener Typen mit typedef
1
2
3
4
typedef struct rechteck {
float laenge;
float breite;
} t_rechteck;
5
6
7
8
struct rechteck r1, r2;
t_rechteck r3;
...
Auf den Namen des Strukturtyps (rechteck) kann in Zeile 1 verzichtet werden, wenn nur noch über den
neu definierten Namen des Typs (t_rechteck) wie in Zeile 7 zugegriffen werden soll.
23
5.1.3
Aufzählungstyp (enum)
Der Datentyp enum ist ein kardinaler (Ganzzahl) Typ, der syntaktisch in Definition und formaler Nutzung
wie struct zu verwenden ist.
Listing 22: Aufzählungstypen
1
2
3
4
5
6
enum ampel
{
ROT, // 0
GELB, // 1
GRUEN // 2
} a1, a2;
7
8
9
a1 = GRUEN;
a2 = 1;
Eine Variable vom enum-Typ ampel kann jetzt die Werte 0 bis 2 haben, ROT, GELB und GRUEN sind
Symbole für diese Werte, so daß die Lesbarkeit des Quelltextes verbessert wird.
Die zugeordneten Ganzzahlwerte können durch Zuweisungen beeinflußt werden, fehlen diese, wird von
Eintrag zu Eintrag inkrementiert:
1
2
3
4
5
6
7
enum farben
{
rot,
gruen,
blau=5,
violett
};
//
//
//
//
0
1
5
6
Es gibt bei der Zuweisung keine Einschränkung, so daß unterschiedliche Bezeichnungen dem selben Wert
zugeordnet sein können.
Die Verwendung von typedef unterliegt den gleichen syntaktischen Regeln wie bei struct (siehe S.23).
5.1.4
union
Auch hier ähnelt die Syntax der Vereinbarung von Strukturen, ebenso die Definition eigener Typen.
Syntax:
union <bezeichner> {
<typ1> <var1>;
...
};
Syntax (EBNF):
union_def = "union" [unionname] "{"
typ membername
{ ";" typ membername }
"}" [ varname {"," varname } ] ";" ;
Auf den Namen der Union (unionname) kann verzichtet werden, wenn er später nie wieder verwendet
wird und hier alle benötigten Variablendefinitionen erfolgen.
Alle im Block angegebenen Variablen (membername) beginnen an der gleichen Speicheradresse, der Compiler reserviert so viel Platz, wie die größte dieser Variablen an Speicher benötigt. Somit hat man Zugriff
auf denselben Speicherbereich über alternative Wege/ Variablen. Ändert man eine, ändern sich die Werte
aller anderen auch!
Mit dem folgenden Beispiel wird gezeigt, welche Endianness auf dem System verwendet wird, auf einem
Intelsystem wird ui.c[0] gleich 1 sein, die anderen Elemente von c sind 0, was little endian bedeutet.
Listing 23: Beispiel für eine union
1
#include <stdlib.h>
24
2
#include <stdio.h>
3
4
5
6
7
8
9
int main(){
int n;
union {
char c[4];
int i;
} ui;
10
ui.i = 1;
for (n=0;n<4;n++) {
printf("%4d",ui.c[n]);
}
11
12
13
14
15
printf("\n");
getchar();
16
17
18
}
Vorsicht: Dieses Programm zeigt auf Systemen mit unterschiedlicher Endianness unterschiedliche Ergebnisse, diese Art der Analyse von Inhalten von Datentypen, die mehr als ein Byte enthalten, steht der
Portierung der Programme auf andere Systeme entgegen. Besser ist die Analyse über Masken gleicher
Größe und gleichen Typs, wie es im Listing 25 auf S. 27 erfolgt.
Die Verwendung von typedef unterliegt den gleichen syntaktischen Regeln wie bei struct (siehe S.23).
5.1.5
Bitfelder
Bitfelder charakterisieren die in einer struct erfolgte Zusammenfassung von Bitgruppen einer bestimmten
Anzahl Bits innerhalb eines Zahlentyps.
Im folgenden Beispiel wird eine struct mit dem Namen flags definiert, die innerhalb eines vorzeichenlosen Characters (unsigned char) zwei vier Bit lange Gruppen f1 und f2 enthält, die mit den Werten
0 ... 15 belegt werden können.
Listing 24: Beispiel für ein Bitfeld
1
2
3
struct flags {
unsigned char f1:4,f2:4;
};
Dabei enthält f1 Bit 0 bis 3 und f2 Bit 4 bis 7 des Bytes.
Daß sie wirklich in einem Byte liegen, kann mit den folgenden Zeilen gezeigt werden:
5
6
7
8
union {
struct flags f;
unsigned char c;
} u;
9
10
11
12
13
14
15
u.f.f1=15;
u.f.f2=1;
printf("%u\n",u.c);
u.f.f1=0;
u.f.f2=8;
printf("%u\n",u.c);
Das Übereinanderlegen einer normalen ein oder mehrere Bytes langen Variablen mit einem Bitfeld kann
zur Analyse von Bitfolgen in der Variablen verwendet werden.
Übung 9 Eine drei Byte lange Zahl enthält 4 gleichgroße Bereiche, die eine Adressinformation speichern
(ähnlich numerischen IPv4-Adressen). Die niederwertigen Bits speichern die niederwertigen (rechts stehenden) Adressteile. Drucken Sie die Adresse wie eine numerische IP-Adresse aus. (Da es keinen 3-Byte
Datentyp gibt, können Sie die little-endian-Eigenschaft des PCs nutzen.)
25
5.2
Speicherklassen für Variablen
Folgende Schlüsselworte sind (als Vorsatz vor dem Typ) für Variablen möglich:
• auto . . . Alle lokalen Variablen sind auch ohne die Angabe des dieses Schlüsselwortes automatisch
automatische Variablen.
• extern . . . Dient zur Deklaration einer an anderer Stelle definierten Variablen
• static . . . Lokale statische Variablen werden im globalen Bereich angelegt und behalten ihren Wert
auch beim Verlassen des Blockes, in dem sie definiert sind. Außerhalb des Blockes sind sie allerdings
nicht sichtbar!
• register . . . Die Variablen werden nach Möglichkeit in Registern gehalten.
5.3
5.3.1
Operatoren
Arithmetische Operatoren
<ausdruck> +
<ausdruck> <ausdruck> *
<ausdruck> /
<ausdruck> %
- <ausdruck>
5.3.2
Logische Operatoren und Vergleiche
<ausdruck> &&
<ausdruck> ||
! <ausdruck>
<ausdruck> ==
<ausdruck> !=
<ausdruck> <
<ausdruck> <=
<ausdruck> >
<ausdruck> >=
5.3.3
<ausdruck>
<ausdruck>
<ausdruck>
<ausdruck>
<ausdruck>
<ausdruck>
<ausdruck>
<ausdruck>
<ausdruck>
<ausdruck>
<ausdruck>
<ausdruck>
<ausdruck>
Bitoperatoren und Shift
~ <ausdruck>
<ausdruck> & <ausdruck>
<ausdruck> | <ausdruck>
<ausdruck> ^ <ausdruck>
<ausdruck> << <ausdruck>
<ausdruck> >> <ausdruck>
5.3.4
Casts, sizeof, Adresse, Indirection
(<typ>) <ausdruck>
sizeof(<ausdruck>)
* <adresse>
& <Lvalue>
5.3.5
Strukturen und Felder
<struktur>.<bezeichner>
<zeiger-auf-struktur> -> <bezeichner>
<adresse>[<ausdruck>]
26
5.3.6
Zuweisungsoperator, Inkrement, Dekrement
<Lvalue> = <ausdruck>
++ <Lvalue>
-- <Lvalue>
<Lvalue> ++
<Lvalue> -5.3.7
Der ? :-Operator
<bedingung> ? <ausdruck> : <ausdruck>
5.3.8
Verkürzte Schreibweisen
<Lvalue>
<Lvalue>
<Lvalue>
<Lvalue>
<Lvalue>
<Lvalue>
<Lvalue>
<Lvalue>
<Lvalue>
<Lvalue>
5.3.9
+= <ausdruck>
-= <ausdruck>
*= <ausdruck>
/= <ausdruck>
%= <ausdruck>
^= <ausdruck>
&= <ausdruck>
|= <ausdruck>
<<= <ausdruck>
>>= <ausdruck>
Kommaoperator
<ausdruck> , <ausdruck> ...
5.3.10
Vorrang (precedence) der Operatoren
multiplicative
additive
shift
relational
equality
bitwise AND
bitwise exclusive OR
bitwise inclusive OR
logical AND
logical OR
conditional
assignment
comma operator
5.3.11
() [] -> .
++ -- ! ~ (type) sizeof
+ -(unär) *(indirection) &(adress)
* / %
+ << >>
< > <= >=
== !=
&
^
|
&&
||
?:
= += -= *= /= %= &= ^= |= <<= >>=
,
Assoziativität
links nach rechts
rechts nach links
links nach rechts
links nach rechts
links nach rechts
links nach rechts
links nach rechts
links nach rechts
links nach rechts
links nach rechts
links nach rechts
links nach rechts
rechts nach links
rechts nach links
links nach rechts
Ein Beispiel: Druck von Bitmustern
Das folgende, etwas komlexere Beispiel zeigt, wie mit verschiedenen Operatoren das Bitmuster einer
Zahl (hier int) gescannt werden kann. Das Ergebnis wird als C-String in eine Variable namens bitfeld
gesteckt, die Methode intToBitsAsString(...) gibt einen Zeiger darauf zurück.
Listing 25: Ausgabe von Bitmustern
1
2
3
4
5
/* MultiMit2.c */
/* druckt das Bitmuster einer 4-Byte-int-Zahl aus */
void printBits(int intZahl){
int Muster = 1;
// rechtestes Bit (LSB) ist 1
// Muster = Muster << 31; // linkestes Bit (MSB) ist 1 (bei 4 Byte)
6
27
int i;
for (i=0; i<32; i++){
printf ("%c", ( (intZahl & (Muster<<(31-i)) ) != 0 ) ? ’1’ : ’0’ );
}
7
8
9
10
11
}
12
13
14
15
16
17
18
19
20
21
22
23
char bitfeld[33];
char * intToBitsAsString (int intZahl){
int Muster = 1;
// rechtestes Bit ist 1
// Muster = Muster << 31; // linkestes Bit ist 1 (bei 4 Byte)
int i;
for (i=0; i<32; i++){
bitfeld[i] = ( (intZahl & (Muster<<(31-i)) ) != 0 ) ? ’1’ : ’0’ ;
}
bitfeld[32] = ’\0’;
return bitfeld;
}
24
25
26
int main(){
int i,e=1;
27
for (i=0; i<40; i++) {
printf ("%3d %1u ",i,e);
printBits(e);
printf (" %s ", intToBitsAsString(e));
printf("\n");
e*=2;
}
getch();
28
29
30
31
32
33
34
35
36
}
5.4
Pointer (Zeiger)
Der Inhalt eines Zeigers ist eine Adresse einer Speicherzelle.
Listing 26: Einfache Beispiele zu Zeigern
1
2
3
4
int i = 5;
int * ip;
ip = &i;
*ip = 13;
In Zeile 1 wird eine int-Variable i definiert und mit dem Wert 5 initialisiert,
in Zeile 2 eine Variable ip, die die Adresse einer int-Variable enthalten soll.
In Zeile 3 wird ip die Adresse von i zugewiesen,
danach wird in Zeile 4 der Speicherzelle, auf die ip zeigt (also i) der Wert 13 zugewiesen.
Der Stern (*) vor einer Zeigervariablen bedeutet: Nimm den Inhalt der Speicherzelle, auf die diese Variable
zeigt, und interpretiere ihn als den Typ, für den der Zeiger definiert wurde!
Zeigerarithmetik
Mit Zeigern kann wie mit Ganzzahlen gerechnet werden, die Addition von 1 bedeutet die Erhöhung um
so viele Bytes, wie der Typ, auf den der Pointer zeigt, benötigt. Natürlich ist es wenig sinnvoll, zwei
Zeiger zu addieren oder zu multiplizieren, die Differenz zweier Zeiger vom gleichen Typ zeigt jedoch die
Anzahl der Elemente, die sich zwischen den Zeigern befinden.
Listing 27: Zeigerarithmetik
1
2
3
4
5
6
double f[10] = {0,10,20,30,40,50,60,70,80,90};
double *fp;
fp = f; // zeigt auf den Anfang des Feldes f ( f[0] )
... *fp ;
// ... f[0]
... *(fp+2) ; // ... f[2]
... fp[2] ; // ... f[2]
28
7
8
9
... *(fp+5) ; // ... f[5]
*(fp+9) = 99. ; // f[9] = 99.;
// bis jetzt blieb der Zeiger fp unveraendert
10
11
12
13
14
15
fp = fp + 5 ;
fp = &f[5] ;
... *(fp+2) ;
fp++;
fp[3] = 90. ;
//
//
//
//
//
fp zeigt auf f[5];
fp zeigt auf f[5];
... f[7]
fp zeigt auf f[6];
f[9] = 90.;
Übung 10 Implementieren Sie die Methode strcpy(...) oder strncpy(...) des Headerfiles string.h .
Listing 28: Zeiger auf mehrdimensionale Arrays
1
2
3
4
5
6
double ff[10][100];
double *ffp;
ffp = ff[0] ;
// ffp zeigt auf den Beginn des Feldes f
ffp = &ff[0][0]; // ffp zeigt auf den Beginn des Feldes f
ffp = ff[5] ;
// ffp zeigt auf f[5][0]
ffp = &ff[5][0]; // ffp zeigt auf f[5][0]
Genauer betrachtet wäre ff (der Name eines zweidimensionalen Arrays) etwas wie ein Zeiger auf einen
Zeiger auf double.
Listing 29: Zeiger auf Strukturen
1
2
3
4
5
6
7
8
struct {
double x,y;
} punkt, *punktp;
punkt.x = 1.;
punkt.y = 2.;
punktp = &punkt;
... (*punktp).y;
... punktp->y;
In Zeile 7 und Zeile 8 wird das Element y der Struktur, auf die der Zeiger punktp zeigt, angesprochen.
In Zeile 8 wird dazu der -> - Operator genutzt.
Wir benutzen den sizeof-Operator, um etwas über die Größen von Arrays und Zeigern zu erfahren:
Listing 30: Zeiger und Größe
1
2
3
4
/* StringZeigerSizeof.c */
...
char c3[] = "Maria";
printf("%d\n",sizeof(c3)); // 6
5
char c[10] = "Eva";
char *cp;
cp = c;
printf("%d\n",sizeof(c)); // 10
printf("%d\n",sizeof(*c)); // 1
printf("%d\n",sizeof(cp)); // 4
printf("%d\n",sizeof(*cp)); // 1
...
6
7
8
9
10
11
12
13
14
}
Ein statisch vom Compiler angelegtes Feld liefert seine Größe mit sizeof(...) (Zeile 9), wird die Speicherzelle nach der Größe befragt, mit dem Feldnamen verbunden ist (also das erste Element), so hat das
natürlich die Größe 1 (Zeile 10). Der Zeiger cp hat natürlich die Größe 4 wie jeder Zeiger, und die Zelle,
auf die er zeigt, wieder 1.
29
Zeiger auf Funktionen
Listing 31: Zeiger auf eine Funktion
1
2
3
4
5
int max(int, int);
...
int (*fp)(int, int); // fp ist ein Funktionszeiger
fp = &max;
... (*fp)(33, 4); // Ruf von max(3,4)
In Zeile 3 wird der Funktionszeiger fp vereinbart, in Zeile 4 wird ihm die Adresse der Methode max(...)
zugewiesen, und in Zeile 5 wird diese dann gerufen.
Die Vereinbarung aus Zeile 3 kann durchaus auch in einer Parameterliste stehen, dann wird ein Funktionszeiger (also die Adresse einer Funktion) einer anderen Funktion als Parameter übergeben.
Listing 32: Funktionszeiger als Funktionsparameter
1
2
3
4
5
6
7
8
9
/* Deklaration */
void drucke(int, int, int (*fp) (int, int));
int method (int, int);
...
...
/* Aufruf */
drucke(13, 25, &method);
...
...
10
11
12
13
/* Definition */
void drucke(int i1, int i2, int (*fp) (int, int)) {
...
14
/* Aufruf */
int erg = (*fp)(i1, i2);
...
15
16
17
18
}
Auf diese Weise kann man wiederkehrende, schematische Aufgaben wie das Berechnen und Drucken eines
Arrays mit den entsprechenden Schleifen in (realisiert in einer Methode/Funktion) von der eigentlichen
(auch in einer Methode/Funktion liegenden) Berechnungsvorschrift trennen.
30
6
Die C-Standardbibliothek
Die Deklarationen der Methoden der Standardbibliothek und eine Reihe von Variablen- und Konstantendefinitionen (z.B. M_PI) werden in Headerfiles aufbewahrt, die, wenn die Methoden im Quelltext gerufen
werden sollen, vorher per #include-Anweisung in ebendiesen eingefügt werden. Einige Headerfiles sind:
• stdlib.h (Verschiedene Standardfunktionen (Konvertierungen, Speichermanagement, . . . ))
Listing 33: Ausgewählte Member von stdlib.h
1
2
3
double atof (const char *ptr);
int atoi (const char *ptr);
double atol (const char *ptr);
4
5
6
void exit(int fehlercode);
int system(const char* command);
7
8
int rand();
9
10
11
void* malloc(size_t size);
void free(void *ptr);
• stdio.h (Ein- und Ausgabe)
Listing 34: Ausgewählte Member von stdio.h
1
2
3
int feof(FILE* ptr);
FILE *fopen(const char *filename, const char *mode);
int fclose( FILE *stream);
4
5
6
7
int getc (FILE*);
int fgetc (FILE*);
int getchar (void);
8
9
int ungetc (int, FILE*);
10
11
12
13
14
char* gets (char*);
char* fgets (char*, int, FILE*);
int putchar (int);
15
16
17
int putc (int, FILE*);
int fputc (int, FILE*);
18
19
20
int puts (const char*);
int fputs (const char*, FILE*);
21
22
23
24
int printf( const char *format, ...);
int fprintf( FILE *stream, const char *format, ...);
int sprintf( const char *str, const char *format, ...);
25
26
27
28
int scanf( const char *format, ...);
int fscanf( FILE *stream, const char *format, ...);
int sscanf( const char *str, const char *format, ...);
29
30
int fflush( FILE *stream);
• string.h (Zeichenketten)
Listing 35: Ausgewählte Member von string.h
1
2
3
char* strcpy(char* s1, const char* s2);
char* strcat(char* s1, const char* s2);
void* strncpy(char* s1, const char* s2, size_t n);
31
4
5
size_t strlen(const char* s);
int strcmp(const char* s1, char* s2);
6
7
8
9
int strchr(const char* s, int c);
void* memcpy(void* s1, const void* s2, size_t n);
void* memmove(void* s1, const void* s2, size_t n);
• math.h (Mathematische Funktionen wie Winkelfunktionen, Logarithmen, Potenzen, . . . )
Listing 36: Zahlen in math.h
1
2
3
4
5
6
7
8
9
10
11
12
13
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
#define
M_E
M_LOG2E
M_LOG10E
M_LN2
M_LN10
M_PI
M_PI_2
M_PI_4
M_1_PI
M_2_PI
M_2_SQRTPI
M_SQRT2
M_SQRT1_2
2.7182818284590452354
1.4426950408889634074
0.43429448190325182765
0.69314718055994530942
2.30258509299404568402
3.14159265358979323846
1.57079632679489661923
0.78539816339744830962
0.31830988618379067154
0.63661977236758134308
1.12837916709551257390
1.41421356237309504880
0.70710678118654752440
Listing 37: Ausgewählte Member von math.h
1
2
3
4
5
6
7
8
9
double
double
double
double
double
double
double
double
double
cos(double x); //Kosinus von x
sin(double x); //Sinus von x
tan(double x); //Tangens von x
acos(double x); //arccos(x)
asin(double x); //arcsin(x)
atan(double x); //arctan(x)
cosh(double x); //Cosinus Hyperbolicus von x
sinh(double x); //Sinus Hyperbolicus von x
tanh(double x); //Tangens Hyperbolicus von x
10
11
12
13
double exp(double x); //Exponentialfunktion (e hoch x)
double log(double x); //natürlicher Logarithmus (Basis e)
double log10(double x); //dekadischer Logarithmus (Basis 10)
14
15
16
double sqrt(double x); //Quadratwurzel von x
double pow(double x, double y); // Berechnet x hoch y
• ctype.h (Tests und Funktionen auf Zeichentypen)
• stdarg.h (Variable Argument-Listen für Funktionen)
• errno.h (Codes von Systemfehlern)
• time.h (Datum und Uhrzeit)
32
7
Dynamische Datenstrukturen
7.1
Dynamische Bereitstellung von Speicherplatz
Die dynamische Bereitstellung von Speicherplatz erfolgt mit malloc, hier werden <size> Bytes dynamisch
bereitgestellt, der zurückgegebene Pointer entspricht den Ausrichtungsanforderungen aller Datentypen im
Speicher, d.h., mit malloc kann auch Speicherplatz für andere Datentypen werden.
void *malloc( size_t );
Durch die Typisierung des Zeigers, dem der Rückgabewert zugewiesen wird, kann dann die dem Datentyp
entsprechende Zeigerarithmetik stattfinden, die die Feldzugriffe wie auf statischen Feldern aussehen lassen:
1
2
#include <stdio.h>
#include <stdlib.h>
3
4
5
{
6
char *s;
7
8
s = malloc(10 * sizeof(char));
// gleichwertig mit s = malloc(10);
9
10
11
s[0] = ’H’;
s[1] = ’a’;
s[2] = ’l’;
s[3] = ’l’;
s[4] = ’o’;
s[5] = ’\0’;
// s[6] = ’!’; // ???
// s[10] = ’!’; // ???
12
13
14
15
16
17
18
19
20
//
printf("%s\n",s);
21
22
23
system("PAUSE");
return 0;
24
25
26
}
Übung 11 Was würde die Wiedereinkommentierung von Zeile 19 bewirken? Wird ein Ausrufezeichen
gedruckt? Und was passiert bei Abarbeitung von Zeile 20?
Listing 38: Dynamische Schaffung eines float-Arrays
1
2
#include <stdio.h>
#include <stdlib.h>
3
4
5
6
7
8
{
int i;
float *s;
9
10
s = malloc(10 * sizeof(float));
11
12
13
14
for (i=0;i<10;i++) {
s[i]=i/100.;
}
15
16
17
for (i=0;i<10;i++) {
printf("%10.5f\n",s[i]);
33
}
18
19
free (s);
20
21
system("PAUSE");
return 0;
22
23
24
}
In Zeile 20 wird der alloziierte Bereich mit der Methode free wieder frei gegeben
void free ( void *ptr );
7.2
Verkettete Listen
Verkettete Listen sind verzeigerte Listen von dynamisch erstellten Speicherstrukturen, man unterscheidet
einfach verkettete Listen, bei denen jedes Element einen Zeiger auf den Nachfolger enthält, und
doppelt verkettete Listen, deren Elemente Zeiger auf Vorgänger und Nachfolger enthalten.
Eine Typdefinition für die Datenstruktur eines Elementes einer einfach verketteten Liste, welches ohne
Einschränkung der Allgemeinheit als Daten einen Floatwert enthält. Hier könnten auch mehrere Daten
oder eine (oder mehrere) Strukturen stehen:
typedef struct element{
// Datenbereich:
float wert;
// Zeigerbereich:
struct element *next;
} ELEMENT;
Die doppelt verkettete Liste hat einen zusätzlichen Zeiger zum Vorgänger!
Um einen Punkt zu haben, an dem die Liste ”festgebunden” ist, legt man einen Zeiger auf das erste
Listenelement an, der, wenn die Liste noch leer ist, einen NULL-Zeiger enthält:
ELEMENT *head = NULL;
Der NULL-Zeiger wandert bei Befüllen der Liste zum letzten Element, da dieses keinen Nachfolger hat.
Zu einem beliebigen Element der Liste gelangt man, von head ausgehend, durch Vorwärtshangeln an den
Zeigern. In einer doppelt verketteten Liste kann man, ausgehend vom Ende der Liste, oder von einem
beliebigen Element, auch rückwärtshangeln.
Einige wichtige Funktionen auf einer solchen Liste:
• ELEMENT *newElement (float value) ;
kreiert ein neues Element mit dem Wert value und gibt einen Zeiger auf das Element zurück. Eine
Einordnung in die Liste erfolgt erst mit insertElement( ... )
• ELEMENT *insertElement( ELEMENT *head, int pos, ELEMENT *elem) ;
fügt das Element, auf das der Zeiger elem zeigt, an der Stelle pos in die Liste ein
Vorsicht: Wenn pos==0, dann ändert sich der head der Liste, da ein neues erstes Element eingeschoben wird, deshalb wird als Rückgabewert der neue (oder unveränderte alte) Wert zurückgegeben!
• ELEMENT *getElement (ELEMENT *head, int pos) ; liefert einen Zeiger auf das Element pos
zurück, die Nummerierung beginnt wie bei Arrays bei 0
• void deleteElement( ELEMENT *elem) ;
löscht das Element, auf das elem zeigt. Wird von removeElement( ... ) verwendet
• ELEMENT *removeElement( ELEMENT *head, int pos) ;
entfernt das Element an der Stelle pos und löscht es mit deleteElement(...)
Vorsicht: Wenn pos==0, dann ändert sich der head der Liste, da das zweite Element erstes Element
wird, deshalb wird als Rückgabewert der neue (oder unveränderte alte) Wert zurückgegeben!
• int getSize(ELEMENT *head) ;
liefert die Anzahl Elemente in der Liste
34
• ELEMENT *nextElement (ELEMENT *elem) ;
liefert einen Zeiger auf das Nachfolgerelement von elem
. . . und einige nützliche Hilfsfunktionen:
• ELEMENT *createList(int size, float *array) ;
kreiert eine Liste der mit size festgelegten Länge, das Feld, auf das array zeigt, muß mindestens
die entsprechende Länge haben und wird zur Wert-Initialisierung der Listenelemente verwendet!
• void printList(ELEMENT *kopf) ;
druckt die Werte der Liste aus
Eine Implementation einfach verketteter Listen - Variante 1
Zunächst die Headerfiles und eine Typdefinition für den Grundbaustein der Listen, den Typ ELEMENT:
1
/* dynListe1.c */
2
3
4
#include <stdio.h>
#include <stdlib.h>
5
6
7
8
9
10
11
// Datenbereich:
float value;
// Zeigerbereich:
} ELEMENT;
Es folgen die Grundfunktionen, die Elemente schaffen, vernichten, in Listen einfügen:
13
14
15
16
17
18
20
21
22
24
25
26
27
28
29
30
31
33
34
35
36
37
38
39
40
ELEMENT *newElement (float value) {
ELEMENT *neu = malloc (sizeof(ELEMENT));
neu->value = value;
neu->next = NULL;
return neu;
}
ELEMENT *nextElement (ELEMENT *elem) {
return elem->next;
}
ELEMENT *getElement (ELEMENT *head, int nr) {
if (nr >= getSize(head) || nr < 0) return NULL;
int i = 0;
while (i++ < nr) {
head = head->next;
}
return head;
}
ELEMENT *insertElement( ELEMENT *head, int pos, ELEMENT *neu) {
// wird an Position 0 eingefügt, ändert sich der Kopf der Liste,
// deshalb wird der ggf. geänderte Listenkopf zurückgegeben!
if (neu == NULL || pos > getSize(head)) return head;
if (pos == 0) {
neu->next = head;
head = neu;
} else {
35
ELEMENT *hilfs = getElement(head , pos - 1);
neu->next = hilfs->next;
hilfs->next = neu;
41
42
43
}
return head;
44
45
46
48
49
50
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
69
70
71
72
73
74
75
76
}
void deleteElement( ELEMENT *elem) {
free(elem);
}
ELEMENT *removeElement( ELEMENT *head, int pos) {
// wird an Position 0 gelöscht, ändert sich der Kopf der Liste,
// deshalb wird der ggf. geänderte Listenkopf zurückgegeben!
if (pos > getSize(head)-1) return head;
ELEMENT *del = NULL;
if (pos == 0) {
del = head;
head = head->next;
} else {
ELEMENT *hilfs = getElement(head , pos - 1);
del = nextElement(hilfs);
hilfs->next = del->next;
}
deleteElement(del);
return head;
}
int getSize(ELEMENT *head) {
int size = 0;
while (head != NULL) {
size++;
head = head->next;
}
return size;
}
. . . und etwas komplexere Hilfsfunktionen:
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
ELEMENT *createList(int groesse, float *feld) {
int i=0;
ELEMENT *head, *lauf;
head = newElement(feld[0]);
lauf = head;
while (++i<groesse) {
lauf->next = newElement(feld[i]);
lauf = lauf->next;
}
lauf->next = NULL;
return head;
}
void printList(ELEMENT *head) {
int i = 0;
while (head != NULL) {
printf("Element %3d: %10.3f\n", i++, head->value);
head = head->next;
// oder: head = nextElement(head);
}
36
97
}
. . . und als letztes Listing ein beispielhaftes Hauptprogramm mit einigen Listenmanipulationen:
99
int main(...) {
100
ELEMENT *head = NULL;
101
102
printf("Anzahl Elemente: %5d\n", getSize(head));
head = insertElement(head, 0, newElement(2000.));
head = insertElement(head, getSize(head), newElement(3000.));
printList(head);
head = removeElement(head, 1);
printList(head);
///////////////////////////////////////////////
int i = 0;
const int N = 20;
float f [N];
103
104
105
106
107
108
109
110
111
112
113
114
115
116
for (i=0; i<N; i++) {
f[i] = i;
}
head = createList(N, f);
printf("El. 5 -> wert : %5.1f\n", getElement(head,5)->value);
head = insertElement(head, 0, newElement(-1000.));
printList(head);
117
118
119
120
121
122
123
124
125
126
127
128
129
}
Kritische Designbetrachtung
Nachteilig ist vor allem, daß beim Ruf der Methoden
ELEMENT *insertElement( ELEMENT *head, int pos, ELEMENT *elem) ;
ELEMENT *removeElement( ELEMENT *head, int pos) ;
die Zuweisung des unter Umständen geänderten Kopfes durch den Anwendungsprogrammierer selbst
verwaltet werden muß, denn die Variable head selbst ist ja durch die Methoden nicht änderbar, da diese
nur eine Kopie von head besitzen.
Dies ließe sich dadurch ändern, daß nicht ELEMENT *head, also die Kopfvariable selbst, sondern die Adresse
der Kopfvariablen ELEMENT **head_adr übergeben wird, was in Variante 5 erläutert wird,
Kritische Designbetrachtung - Variante 2
. . . oder aber durch folgendes, leicht modifiziertes Design, bei dem es eine (ihre Adresse nicht verändernde)
statische oder dynamische Datenstruktur des Typs LIST gibt, die ein Member head besitzt, welches wie
gehabt auf das erste Element zeigt und durch die ihrerseits leicht modifizierten Methoden
int insertElement( LIST *liste, int pos, ELEMENT *elem) ;
int removeElement( LIST *liste, int pos) ;
selbständig und ohne Zutun des Nutzers der Listenmethoden modifiziert wird. Der Rückgabewert könnte
zur Mitteilung der fehlerfreien Ausführung oder eines Fehlercodes genutzt werden. Alle anderen Methoden
bekämen nun ebenfalls anstelle der Zeigervariablen auf den Kopf (erstes Element) ELEMENT *head eine
Zeigervariable auf die Listenvariable LIST *liste übergeben.
1
2
// Datenbereich:
37
3
4
5
6
float value;
// Zeigerbereich:
} ELEMENT;
7
8
9
10
11
12
13
typedef struct{
// Datenbereich:
...
// Zeigerbereich:
ELEMENT *head;
} LIST;
Im Datenbereich könnte z.B. die Länge der Liste aufbewahrt und durch die Länge ändernden Methoden
modifiziert werden, was zu verbesserter Performance führen würde.
15
16
17
18
19
20
LIST myList;
myList.head = NULL;
insertElement(&myList,
removeElement(&myList,
0, newElement(3000.));
1);
Da es im struct keine Initialisierung gibt, muß in Zeile 2 der Kopf der neuen Liste explizit auf NULL
gesetzt werden, was wieder ein Nachteil im Design ist, da das durch den Anwendungsprogrammierer
vergessen werden kann.
Wenn ebenso wie die Generierung eines neuen Elementes die Generierung einer neuen Liste von einer
speziellen Methode erledigt wird, können alle notwendigen Handlungen durch diese Methode erfolgen.
Die Gefahr, daß etwas vergessen wird, ist bei fehlerfreier Implementierung der Methode gebannt.
1
2
3
4
5
6
// dyn. Erstellung einer leeren Liste
LIST *newList(){
LIST *neu = malloc (sizeof(LIST));
neu->head = NULL;
return neu;
}
7
8
LIST *myListP = newList();
9
10
11
12
13
insertElement(myListP,
removeElement(myListP,
1);
Wenn nun noch die Datenstruktur LIST selbst über die Methoden zu ihrer Modifikation verfügen würde
...
1
LIST *newList();
2
3
LIST *myListP = newList();
4
5
6
7
...
myListP -> insertElement(0, newElement(3000.));
...
38
. . . wäre eine Kopplung von Daten und Methoden erreicht, die wir später in der objektorientierten
Programmierung kennenlernen werden und die in Programmiersprachen wie C++ und Java realisiert
ist.
Durch Übergabe der Adresse der Kopfvariablen (also ein Call by Reference) kann nun diese selbst in den
Methoden
int insertElement( ELEMENT **head_adr, int pos, ELEMENT *elem) ;
int removeElement( ELEMENT **head_adr, int pos) ;
modifiziert werden, über den Rückgabewert könnte angezeigt werden, ob das Einfügen funktioniert hat,
oder man nutzt den leeren Typ void.
7.3
Stack (LIFO) und Queue (FIFO)
Die Methoden zum Datenaustausch mit einem Stack (LIFO) sind
• void push(float);
legt einen Wert auf den Stack
• float pop();
nimmt einen Wert vom Stack
und mit einer Queue (FIFO)
• void enqueue(float);
schiebt einen Wert in die Queue
• float dequeue();
nimmt einen Wert aus der Queue
Anstelle des float kann natürlich jeder beliebige Datentyp stehen.
Implementation mit Hilfe der verketteten Liste
39
8
8.1
Weiterführende Themen
Zeiger auf Funktionen und void-Zeiger
Im folgenden Beispiel wird eine Sortierung mit Comparator-Funktion entsprechend
void qsort (void*, size_t, size_t, int (*)(const void*, const void*));
aus der stdlib.h vorgestellt. Der Methode qsort(...) wird ein Zeiger auf eine Methode, den Comparator, übergeben.
Der Comparator vergleicht im Sortiervorgang zwei Daten (die zwei Parameter) und entscheidet darüber,
welches Datum größer ist. Mit
typedef int (*compare_t) (void* l,void* r);
wird ein Zeigertyp compare_t definiert, der auf einen Comparator zeigt. Der Rückgabewert ist
-1 , wenn l < r
1 , wenn l > r
0 , wenn l = r
Bei der Typdefinition werden void-Zeiger als typneutrale Parameter verwendet, die Implementationen
für konkrete Comparatoren verwenden ebenfalls void-Zeiger, erst im Inneren casten diese Methoden auf
den eigentlichen Datentyp. Dadurch unterscheiden sicht die Typmuster der verschiedenen Comparatoren
nicht und ihre Zeiger (bzw. Adressen) genügen somit der Typdefinition compare_t.
Listing 39: Sortierung - die Prototypen
1
2
3
4
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define ANZAHL 50
5
6
7
8
9
10
11
12
/* Def. des Funktionszeigertyps compare_t,
* Verwendung zur Typangabe des comparators
* in Parameterlisten)
*/
typedef int (*compare_t) (void* l,void* r);
int compare_d(void *, void *); // fuer double
int compare_i(void *, void *); // fuer int
13
14
15
16
17
18
19
20
21
int sort ( void* p, int sizeOfType, int sizeOfArray,
compare_t compare );
/* Parameter:
* p
... Adresse des Feldanfangs,
* sizeOfType ... Groesse des Datentypes des Feldes,
* sizeOfArray ... Anzahl der Feldelemente
* compare
... Adresse der Vergleichsmethode
*/
Listing 40: Sortierung - das Hauptprogramm
24
25
26
27
28
29
int main(int argc, char *argv[]) {
int da[ANZAHL];
...
sort(da,sizeof(int),ANZAHL,compare_i);
...
}
Es folgt das eigentliche Sortieren. Da die Routine für jeden Datentyp funktionieren soll, erfolgt ganz
allgemein ein Cast auf einen Ein-Byte-Datentyp (unsigned char), die Adressrechnungen (Zugriffe auf
die Elemente) werden manuell über die Anzahl der Elemente (sizeOfArray) und die Größe des Datentyps
der Elemente (sizeOfType) durchgeführt.
Listing 41: Sortierung - die Methodenimplementierung der Sortierung
31
32
33
34
/*******************************************************
ein simples Bubblesort fuer Felder beliebiger Typen,
zu implementieren ist eine compare-Methode
*/
int sort ( void* p, int sizeOfType, int sizeOfArray,
40
35
36
37
38
39
40
41
/*
*
*
*
*
*/
compare_t compare ) {
Parameter:
p
... Adresse des Feldanfangs,
sizeOfType ... Groesse des Datentypes des Feldes,
sizeOfArray ... Anzahl der Feldelemente
compare
... Adresse der Vergleichsmethode
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
// Pointer mit Typgroesse 1 Byte durch Umcasten
unsigned char *ptr0 = (unsigned char *) p;
unsigned char *ptr;
// ptr[i*sizeOfType] zeigt auf auf das i-te Element
// ptr + i*sizeOfType
ebenso
int getauscht = 1;
while (getauscht) {
getauscht = 0;
int i;
for (i=0, ptr=ptr0; i<sizeOfArray-1; i++, ptr+=sizeOfType) {
if ( ((*compare)(ptr , ptr + sizeOfType)) > 0 ) {
printf("*");
unsigned char temp;
int j;
for (j=0;j<sizeOfType;j++) {
temp = ptr[j];
ptr[j] = ptr[j+sizeOfType];
ptr[j+sizeOfType] = temp;
printf("#");
}
getauscht = 1;
}
}
}
}
/* Ende sort ********************************************/
Listing 42: Sortierung - die Methodenimplementierung der Comparatoren
70
71
72
73
74
75
76
77
78
79
80
81
82
83
int compare_d (void * l, void * r){
double li = *(double*)l;
double re = *(double*)r;
if
(li < re) return -1;
else if (li > re) return 1;
else
return 0;
}
int compare_i(void * l, void * r){
int li = *(int*)l;
int re = *(int*)r;
if
(li < re) return -1;
else if (li > re) return 1;
else
return 0;
}
Erst am Anfang der Methodenkörper erfolgen die konkreten Casts auf die eigentlichen Typen der Parameter, hier int und double, es könnte aber auch eine Struktur sein, aus der dann eine bestimmte
Membervariable verglichen wird.
41
8.2
Übernahme von Kommandozeilenargumenten . . .
. . . und bedarfsabhängige dynamische Schaffung von Speicherplatz
Das Betriebssystem (bzw. die Shell, in der das Programm gerufen wird) übergibt dem main zwei Parameter, eine Anzahl int argc und einen Pointer char **argv (was das Gleiche wie char *argv[]
bedeutet), der auf ein argc-langes Array von char*-Pointern zeigt, welche wiederum auf char-Bereiche
mit den Strings der einzelnen Argumente zeigen:
Listing 43: Kommandozeilenargumente
1
2
3
4
/* KdoZeilenParam.c */
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
5
6
7
#define BUFSIZE 100
#define NFIELD 10
8
9
10
{
11
12
13
14
15
int i;
for (i=0; i<argc; i++) {
printf("Parameter %2d: %s\n",i, argv[i]);
}
Zunächst wurden in der Schleife um Zeile 14 die Argumente ausgedruckt, im C ist das erste Kommandozeilenargument, das im Prozeß sichtbar ist, der Aufrufname des Programms.
Im folgenden werden die Argumente in ein auf dem Stack angelegtes 2-dim. Array param umkopiert:
Listing 44: ...
17
18
19
20
21
22
// Umkopieren in ein auf dem Stack angelegtes 2-dim Array
char param[argc][BUFSIZE];
strncpy(param[i],argv[i],BUFSIZE);
printf("Parameter %2d (l=%2d): %s\n",i, strlen(param[i]), param[i]);
}
Nun werden die Argumente in auf dem Heap dynamisch angelegte längenangepaßte Bereiche umkopiert,
die durch das auf dem Stack liegende paramp[i] “verpointert“ sind:
Listing 45: ...
24
25
26
27
28
29
char *paramp[argc];
paramp[i] = malloc(strlen(argv[i])+1);
strcpy(paramp[i],argv[i]);
printf("Parameter %2d (l=%2d): %s\n",i, strlen(paramp[i]), paramp[i]);
}
. . . und jetzt wird auch das paramp[] als dynparamp[] auf den Heap gelegt, was die gesamte Speicherstruktur nun bei Kenntnis von dynparamp global erreichbar macht:
Listing 46: ...
31
32
33
34
char **dynparamp = malloc(argc * sizeof(char *));
dynparamp[i] = malloc(strlen(argv[i])+1);
strcpy(dynparamp[i],argv[i]);
42
printf("Parameter %2d (l=%2d): %s\n",i, strlen(dynparamp[i]), dynparamp[i]);
35
}
36
37
return 0;
38
39
}
8.3
Arbeit mit der GNU-Compiler-Collection (GCC)
Eine Abbildung zur Wirkung von GCC aus dem Wikipedia-Artikel “GNU Compiler Collection”
43
gcc --help
Usage: gcc [options] file...
Options:
-pass-exit-codes
Exit with highest error code from a phase
--help
Display this information
--target-help
Display target specific command line options
(Use ’-v --help’ to display command line options of sub-processes)
-dumpspecs
Display all of the built in spec strings
-dumpversion
Display the version of the compiler
-dumpmachine
Display the compiler’s target processor
-print-search-dirs
Display the directories in the compiler’s search path
-print-libgcc-file-name Display the name of the compiler’s companion library
-print-file-name=<lib>
Display the full path to library <lib>
-print-prog-name=<prog> Display the full path to compiler component <prog>
-print-multi-directory
Display the root directory for versions of libgcc
-print-multi-lib
Display the mapping between command line options and
multiple library search directories
-print-multi-os-directory Display the relative path to OS libraries
-Wa,<options>
Pass comma-separated <options> on to the assembler
-Wp,<options>
Pass comma-separated <options> on to the preprocessor
-Wl,<options>
Pass comma-separated <options> on to the linker
-Xassembler <arg>
Pass <arg> on to the assembler
-Xpreprocessor <arg>
Pass <arg> on to the preprocessor
-Xlinker <arg>
Pass <arg> on to the linker
-save-temps
Do not delete intermediate files
-pipe
Use pipes rather than intermediate files
-time
Time the execution of each subprocess
-specs=<file>
Override built-in specs with the contents of <file>
-std=<standard>
Assume that the input sources are for <standard>
-B <directory>
Add <directory> to the compiler’s search paths
-b <machine>
Run gcc for target <machine>, if installed
-V <version>
Run gcc version number <version>, if installed
-v
Display the programs invoked by the compiler
-###
Like -v but options quoted and commands not executed
-E
Preprocess only; do not compile, assemble or link
-S
Compile only; do not assemble or link
-c
Compile and assemble, but do not link
-o <file>
Place the output into <file>
-x <language>
Specify the language of the following input files
Permissible languages include: c c++ assembler none
’none’ means revert to the default behavior of
guessing the language based on the file’s extension
Options starting with -g, -f, -m, -O, -W, or --param are automatically
passed on to the various sub-processes invoked by gcc. In order to pass
other options on to these processes the -W<letter> options must be used.
For bug reporting instructions, please see:
<URL:http://cygwin.com/problems.html>.
Übung 12 Demonstrieren Sie die Wirkung des Präprozessors mit Hilfe der Nutzung der passenden Option (gcc -E file.c)!
Übung 13 Testen Sie Optionen von gcc!
44
8.4
Programmierfehler
Übung 14 Was passiert bei folgendem Programm, geben Sie bei der Eingabe in Zeile 11 auch mal mehrere
Zeichen ein!
1
int main() {
2
3
4
5
int i = 42;
// char davor;
char ende=’n’;
6
7
8
9
10
11
12
13
14
15
do {
printf("i = %d\n", i);
printf("Weiter? [j/n]: ");
fflush(stdin);
scanf("%s", &ende);
//
printf("davor = %c (int %d)\n", davor, davor);
printf("i = %d\n", i);
i++;
} while (ende == ’j’);
16
17
}
Die ASCII-Tabelle
Code
0.
1.
2.
3.
4.
5.
6.
7.
.0
NUL
DLE
SP
0
@
P
‘
p
.1
SOH
DC1
!
1
A
Q
a
q
.2
STX
DC2
"
2
B
R
b
r
.3
ETX
DC3
#
3
C
S
c
s
.4
EOT
DC4
$
4
D
T
d
t
.5
ENQ
NAK
%
5
E
U
e
u
.6
ACK
SYN
&
6
F
V
f
v
.7
BEL
ETB
’
7
G
W
g
w
45
.8
BS
CAN
(
8
H
X
h
x
.9
HT
EM
)
9
I
Y
i
y
.A
LF
SUB
*
:
J
Z
j
z
.B
VT
ESC
+
;
K
[
k
{
.C
FF
FS
,
<
L
\
l
|
.D
CR
GS
=
M
]
m
}
.E
SO
RS
.
>
N
^
n
~
.F
SI
US
/
?
O
_
o
DEL
Literatur
[1] D. M. R. Brian W. Kernighan, Programmieren in C, ANSI C, Hanser, 1990.
[2] D. Frischalowski and J. Pallmer, ANSI C 2.0, Herdt-Verlag, 2005.
[3] H.Herold, Linux Unix Systemprogrammierung, Addison-Wesley, 2004.
Glossar und Abkürzungsverzeichnis
Definition
Deklaration
Vereinbarung (Variablen, Funktionen) mit Speicherbereitstellung
Vereinbarung (Variablen, Funktionen) ohne Speicherbereitstellung
EBNF
EVA
Erweiterte Backus-Naur-Form, eine Metasprache zur Beschreibung von SyntaxGrammatiken für Sprachen (z.B. Programmiersprachen)
Byte- (oder ggf. Bit-)Anordnung im Speicher, liegt das niederwertigste Byte
(LSB, also das Ende der Zahl) an der niedrigsten Adresse, spricht man von
“little endian”
Akronym für Eingabe, Verarbeitung, Ausgabe
FIFO
First In First Out
IDE
Integrated Development Environment (Integrierte Entwicklungsmgebung), eine
Umgebung mit Fenstern und Menus zur Entwicklung von Programmen (im
Gegensatz zur Entwicklung an der Kommandozeile)
LIFO
LSB
Last In First Out
Least Significant Bit (/Byte) . . . das niederwertigste Bit/Byte einer Zahl (oder
anderen Struktur)
(engl. left value - linker Wert) ein Ausdruck, dem ein Wert zugewiesen werden
kann, der also auf der linken Seite einer Zuweisung stehen kann
Endianness
Lvalue
MSB
Most Significant Bit (/Byte) . . . das höchstwertige Bit/Byte einer Zahl (oder
anderen Struktur)
Parser
(engl. parse - zerteilen) eine zweite Compilerphase, die den vom Scanner erhaltenen Tokenstrom in einer syntaktischen Analyse verarbeitet
Rekursion
die Definition eines Verfahrens (Funktion, Problem) durch sich selbst
Scanner
(engl. scan - abtasten) eine erste Compilerphase für die lexikalische Analyse,
generiert eine Tokenfolge, die die grundlegenden lexikalischen Einheiten (Wortsymbole (Schlüsselworte, reservierte Worte), Klammern, Operatoren, Bezeichner, Literale, . . . ) zum Inhalt hat
Zweierkomplement
Um das Vorzeichen einer Zahl zu wechseln, wird vom Bitmuster 1 subtrahiert
und dann werden alle Bits negiert (Einerkomplement), was als Zweierkomplement bezeichnet wird. Vorzeichenbehaftete Ganzzahlen werden im Zweierkomplement dargestellt, der Zahlenbereich liegt zwischen −2n−1 und 2n−1 − 1 (n
. . . Anzahl der Bits). Die eigentliche Zahl ist in den Bits 1 . . . n-1 codiert, das
höchstwertige Bit n (MSB . . . most significant bit) zeigt mit dem Wert 1 eine
negative Zahl an.
46
Index
Aktualparameter, siehe Parameter, aktueller
Ausgabeumlenkung, siehe I/O redirection
auto, 26
Pointer, siehe Zeiger
Präprozessor, 3
printf, 16
Bitfeld, 25
Block Started by Symbol, 15
Block Storage Segment, 15
BSS, 15
Bufferoverflow, 17
Queue, 39
register, 26
Rekursion, 14, 46
scanf, 17
Scanner, 46
sizeof, 23, 29
Stack, 8, 15, 39
static, 15, 26
stdarg.h, 32
stdio.h, 31
stdlib.h, 31
strcpy, 22
String, 21
string.h, 22, 31
strncpy, 22
struct, 22
call by reference, 17
call by value, 14
Code Segment, 15
Comparator, 40
ctype.h, 32
Data Segment, 8, 15
Definition, 46
Deklaration, 46
EBNF, 6, 46
Eingabeumlenkung, siehe I/O redirection
Endianness, 46
little endian, 24
enum, 24
errno.h, 32
Erweiterte Backus-Naur-Form, siehe EBNF
EVA, 16
extern, 26
Top-Down-Entwurf, 13
typedef, 23–25
union, 24
void-Zeiger, 40
Zeiger, 28
auf Funktionen, 30, 40
Zeigerarithmetik, 28
Zweierkomplement, 20, 46
fgets, 17
FIFO, 39, 46
Formalparameter, siehe Parameter, formaler
free, 34
gets, 17
Headerfiles, 31
Heap, 15
I/O redirection, 18
IDE, 46
Kommandozeilenargumente, 42
LIFO, 39, 46
Liste
verkettete, 34
LSB, 46
malloc, 33
math.h, 32
Methoden, 14
Modul, 13
Modularisierung, 13
MSB, 46
Parameter
aktueller, 14
formaler, 13, 14
Parser, 46
47
Inhaltsverzeichnis
1 Einführung
1.1 Literatur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 Erstellung eines Programmes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3 Vorbetrachtungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
2
2
2
2 Programmiersprachenkonzepte und Programmierung
2.1 Einordnung der Programmierung in die Informatik . . . . . . . . . . . . . . . . . . . . . .
2.2 Definition und Charakterisierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3 Abarbeitung von Programmen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
5
5
7
3 Algorithmen und die Sprache C
3.1 Vereinbarung von Variablen (Daten) . . . . . . . . . . . . .
3.1.1 Elementare Datentypen . . . . . . . . . . . . . . . .
3.1.2 Variablen und Felder . . . . . . . . . . . . . . . . . .
3.2 Darstellung von Algorithmen und ihre Umsetzung in C . . .
3.2.1 Elementarblock/-baustein (Aktion) . . . . . . . . . .
3.2.2 Strukturblock . . . . . . . . . . . . . . . . . . . . . .
3.2.3 Sequenz (Folge) . . . . . . . . . . . . . . . . . . . . .
3.2.4 Alternative (Einfachverzweigung) . . . . . . . . . . .
3.2.5 Selektion (Mehrfachverzweigung, Mehrfachauswahl)
3.2.6 Schleife (Wiederholung, Iteration) . . . . . . . . . .
3.3 Algorithmenentwurf . . . . . . . . . . . . . . . . . . . . . .
3.4 Modularisierung . . . . . . . . . . . . . . . . . . . . . . . .
3.5 Rekursion . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.6 Variablen im Speicher . . . . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
8
8
8
8
9
9
10
10
10
11
11
12
13
14
15
4 Ausgabe / Eingabe
4.1 Ausgabe mit printf(. . . ) . . . . . . . . . . . .
4.2 Eingabe mit scanf(. . . ) u.a. . . . . . . . . . .
4.3 Ein-/Ausgabeumlenkung (I/O redirection) . .
4.4 Betrachtungen zur Formatierung der Ausgabe
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
16
16
17
18
20
5 Daten und Operationen
5.1 Strukturierte Datentypen . . . . . . . . . . . . . .
5.1.1 Felder (Arrays) . . . . . . . . . . . . . . . .
5.1.2 Strukturen . . . . . . . . . . . . . . . . . .
5.1.3 Aufzählungstyp (enum) . . . . . . . . . . .
5.1.4 union . . . . . . . . . . . . . . . . . . . . .
5.1.5 Bitfelder . . . . . . . . . . . . . . . . . . . .
5.2 Speicherklassen für Variablen . . . . . . . . . . . .
5.3 Operatoren . . . . . . . . . . . . . . . . . . . . . .
5.3.1 Arithmetische Operatoren . . . . . . . . . .
5.3.2 Logische Operatoren und Vergleiche . . . .
5.3.3 Bitoperatoren und Shift . . . . . . . . . . .
5.3.4 Casts, sizeof, Adresse, Indirection . . . . . .
5.3.5 Strukturen und Felder . . . . . . . . . . . .
5.3.6 Zuweisungsoperator, Inkrement, Dekrement
5.3.7 Der ? :-Operator . . . . . . . . . . . . . . .
5.3.8 Verkürzte Schreibweisen . . . . . . . . . . .
5.3.9 Kommaoperator . . . . . . . . . . . . . . .
5.3.10 Vorrang (precedence) der Operatoren . . .
5.3.11 Ein Beispiel: Druck von Bitmustern . . . .
5.4 Pointer (Zeiger) . . . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
21
21
21
22
24
24
25
26
26
26
26
26
26
26
27
27
27
27
27
27
28
.
.
.
.
.
.
.
.
6 Die C-Standardbibliothek
31
7 Dynamische Datenstrukturen
7.1 Dynamische Bereitstellung von Speicherplatz . . . . . . . . . . . . . . . . . . . . . . . . .
7.2 Verkettete Listen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.3 Stack (LIFO) und Queue (FIFO) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
33
33
34
39
48
8 Weiterführende Themen
8.1 Zeiger auf Funktionen und void-Zeiger . . . . . .
8.2 Übernahme von Kommandozeilenargumenten . . .
8.3 Arbeit mit der GNU-Compiler-Collection (GCC)
8.4 Programmierfehler . . . . . . . . . . . . . . . . .
49
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
40
40
42
43
45

BEngTKI2010 Grundlagen der Programmiersprache C

Transcrição

Documentos relacionados

Folien

Sturz auf den Mond

Eingebaute Datentypen (primitive types)

Demenz - Universitätsspital Basel

Aufgabe 2 - Verwendung von Zählern

Portable Pixmaps und Ein- und Ausgabe von Bildern

Skript

Teil3

Rapid Application Development, RAD

pdf, fortlaufend - HTWK Fakultät Informatik, Mathematik und

go to: 20sek.ch