Willkommen! Informatik I/II PVK. 2 Über mich Name: Benjamin Knecht Vertiefungsrichtung: Computer...

Willkommen!

Informatik I/II PVK

Informatik I/II PVK 2

Über mich

Name: Benjamin Knecht Vertiefungsrichtung: „Computer & Netzwerke“ Hilfsassistent für Technische Informatik I/II Projektleiter für Orxonox (www.orxonox.net) Verwendung von Programmiersprachen im

Studium 1. Semesterarbeit (Symbian C) 2. Semesterarbeit (Java) Masterarbeit (C++)

Informatik I/II PVK 3

Kursablauf

Montag: Grundlagen in C/C++ Dienstag: Objektorientierung in C++ und

mögliche Prüfungsaufgabe Mittwoch: Einführung in Java und

Unterschiede zu C++ Donnerstag: Konzepte der OO-

Programmierung (Bäume, Backtracking, Spieltheorie etc.)

Freitag: Prüfungsaufgaben für Informatik II, Fragen und Vertiefung Slides sind auf: www.benjaminknecht.ch/info-pvk

Informatik I/II PVK 4

Was wird besprochen?

Inhalt der Zusammenfassung Grundlagen zum Verständnis von C/C++

und Java Programmierkonzepte Prüfungsaufgaben Falls erwünscht Übungsaufgaben

Informatik I/II PVK 5

Fragen

Fragen bitte sofort stellen bei … Unklarheiten Fehler meinerseits

Anregungen zum Kursablauf mehr Theorie? mehr eigenständiges Arbeiten? Besprechung bestimmter Übungen

Informatik I/II PVK 6

Ablauf heute

Allgemeines zum Programmieren Variablen und Basistypen Operatoren Schleifen Arrays und Pointer

char-Array (string) Referenzen

Funktionen

Informatik I/II PVK 7

Programmieren allgemein

Implementierung von Algorithmen Berechnungen Such-Algorithmen

Verarbeitung von Daten Datenbanken

Simulieren von Abläufen Spiele etc...

Informatik I/II PVK 8

Erstellung eines Programms

Compiler

Quellcode

Assembler

Assemblerprogramm

Maschinencode

Linker

Ausführbares Programm

Lader/Binder

Programm im Speicherbereich

Instruktionen

...ProgramCounter

Variablen

...

Bibliotheken

Hauptspeicher

Informatik I/II PVK 9

Compiler – gcc und g++

Compiler für C++ (g++) Kompilieren

g++ -g –c file1.cpp –I ~/include/ Linken

g++ -Wall -o myprog myprog.o file1.o –L ~/lib/ -lmylib

Informatik I/II PVK 10

Fehler

Kompilierfehler (z.B.: Syntaxfehler) Linkerfehler (fehlende Bibliothek) Laufzeitfehler (runtime error)

Fehler der zur Zeit des Kompilierens nicht klar war

segmentation fault (Fehler bei Speicherzugriff)

Informatik I/II PVK 11

Variablen & Basistypen

Wir kennen folgende Basistypen char char c = 'A'; (ASCII-Satz) int int i = 100231564; double double d = 3.123456; float float f = 3.23f; bool bool isTrue = true;

Speicherplatz der Datentypen abhängig von Betriebssystem

sizeof Operator findet Grösse des Typs Rundungsungenauigkeit bei Fliesskommazahlen

Informatik I/II PVK 12

Definitionsbereiche

Befinden sich in <climits> Definiert als CHAR_MIN, SCHAR_MAX, UINT_MIN, DOUBLE_MAX etc.

unsigned und signed Erstes Bit wird für Vorzeichen benötigt

Variablen laufen über kann nur schwer geprüft werden

Informatik I/II PVK 13

Namenskonvention

Variablennamen dürfen '_', 'a-z', 'A-Z' und '0-9' enthalten.

Verboten: Zahlen am Anfang „__“ am Anfang (zwei '_') „_Grossbuchstaben“ Keywords

Empfohlen wird camelCase für Variablen und für Klassennamen CamelCase

Mehr gute Styletipps: http://www.orxonox.net/wiki/c++_styleguide

Informatik I/II PVK 14

Typenkonversion

Implizite Konvertierung int i = 3.425; // i == 3

Explizite Konvertierung (float)15/4

Typenkonversion hat höhere Präzendenz als /

Informatik I/II PVK 15

Null

Basistypen haben alle einen speziellen Null-Wert

int 0 double 0.0 float 0.0f char '\0' bool false (Pointer) null

Informatik I/II PVK 16

Arithmetische Operatoren

5 bekannte arithmetische Operatoren +, -, *, /, %

Lesevorgang von links nach rechts Unterschiedliche Präzedenz

*, /, % binden stärker als +, - Präzedenzliste in Zusammenfassung

Informatik I/II PVK 17

Verkürzte Operatoren

++, --, +=, *= etc. i++; ist eine Kurzform von i=i+1; i--; entspricht i=i-1;

achte auf Unterschied von i++ und ++i

i+=3; ist eine Kurzform von i=i+3; etc.

Informatik I/II PVK 18

Anweisungen

Werte werden kopiert mit = int a = 3; int b = a; // Kopie von Integer

Deklaration schafft bereits Speicherplatz, aber noch undefiniert

Wird erst bei grösseren Objekten wichtig

Informatik I/II PVK 19

Vergleichsoperatoren

Vergleichsoperatoren erzeugen einen boolschen Ausdruck

==, !=, <, <=, >, >= lässt sich immer nach true oder false

auswerten bool tiny = number <= 0.000001;

true → 1 false → 0 0 → false != 0 → true Achtung == nie mit = verwechseln!

Informatik I/II PVK 20

Logische Operatoren

Logische Operatoren verknüpfen boolsche Ausdrücke

&&, ||, ! bool b = 17 < a && a < 30;

auf keinen Fall 17 < a < 30 ist immer true

b != 0 && a/b < 1.3 sollte b == 0 gelten, teilen wir bei a/b durch 0 obiger Ausdruck wird aber fehlerfrei

ausgewertet, weil ein false auf der linken Seite weiteres Auswerten erübrigt

Informatik I/II PVK 21

Bit Operatoren

Bitoperatoren verändern Werte auf Bitebene

<<, >>, |, &, ^, ~ es gibt auch verkürzte Versionen (<<= etc.) i >>= 1; entspricht i /= 2; Vorsicht: ^ ist nicht für Exponenten sondern

XOR-Operation ~ nicht mit boolschem ! verwechseln

Informatik I/II PVK 22

Scopes

Scopes werden mit {, } eingegrenzt Variablen sind nur innerhalb ihres Scopes

sichtbar Scopes können beliebig verschachtelt werden Existieren Variablen mit gleichem Namen, so

zählt die „lokalere“ Variable

Informatik I/II PVK 23

Scopes Beispiel

int a = 3;int main(){

double b = a*3.14159;{

char a = 'h';b -= a;b += ::a;

}a++;return 0;

}

Obwohl die Variable a mehrmals deklariert wird, ist folgender Code korrekt.

Wegen dem Scope ist klar, für welche Bereiche a ein int ist und wann ein char

::a holt vom Scope versteckte, globale Variablen hervor

Informatik I/II PVK 24

if-else Statements

if (Bedingung1)

{

Anweisung1; // Falls Bedingung1 wahr

}

else

{

Anweisung2; // Falls Bedingung1 falsch

}

Informatik I/II PVK 25

if-else Statements

Vorsicht bei einzeiligen if-Statements und Verschachtelung

if (x < 0) if (y != 0) // do something else if (y != 0) // do something else

Informatik I/II PVK 26

if-else Statements

else gehört zu zweitem if if (x < 0)

if (y != 0) // do something else if (y != 0) // do something else

Informatik I/II PVK 27

Inline if

Wenn man einen Ausdruck schnell testen will

(Bedingung) ? wahr : falsch Bsp: int a = (x > 0) ? x : 0;

Gilt aber generell als schlechter Programmierstil

Informatik I/II PVK 28

switch Statement switch (Integerausdruck) {

case Konstante1:

Anweisung1;

break;

case Konstante2:

case Konstante3:

Anweisung2;

break;

default:

Standardanweisung;

}

Integerausdruck kann auch ein char sein

Informatik I/II PVK 29

for, while und do-while Schleife

for (Initialisierung; Bedingung; Update) {} while (Bedingung) {} do {} while (Bedingung)

for (int i = 0, int j = 1; j < size; i++, j++)

Ist Bedingung leer, so ist sie immer true

Vorzeitiges abbrechen (break) oder weiterfahren (continue) möglich. Ansonsten Ausführung bis Bedingung falsch.

Alle Schleifen sind gegenseitig austauschbar

Informatik I/II PVK 30

Arrays

Arrays sind fixe Bereiche einer konstanten Länge und eines beliebigen Typs im Speicher

Deshalb müssen Arrays auch mit einer Konstanten deklariert/initialisiert werden

int days[30]; // 30 ist konstant int days[30] = {20, 21, 24, 32, 24, 20, 16}; int days[] = {20, 21, 24}; // size 3

Der Index des Arrays geht von 0 bis length-1 int t = (days[0] + days[1])/2; Wird auf ein Element ausserhalb der Grösse des

Arrays zugegriffen wird ein Laufzeitfehler ausgelöst

Informatik I/II PVK 31

Mehrdimensionale Arrays

Arrays können auch beliebig mehrdimensional sein

int test[][2] = {{1,2},{2,3},{4,5}}; Grösse des Arrays kann aber nur für erste

Dimension wie oben automatisch erkannt werden

int test[][] = {{1,2},{4,5}}; Geht also nicht

Informatik I/II PVK 32

Char-Arrays

Eine besondere Sorte von Arrays sind die char-Arrays oder Strings

char name[] = „Stefan“; Strings sind terminiert mit dem null-char '\0'

Das obere Array hat also die Länge 7 Vorsicht: 'a' + 'b' wird nicht zu „ab“.

Stattdessen werden ASCII werte addiert.

Weil char-Arrays so grauenhaft sind, wird in C++ ein string Object zur Verfügung gestellt

char-Arrays sind in der Regel also zu vermeiden

Informatik I/II PVK 33

Pointer Ein Pointer zeigt irgendwo auf den Speicher

Variable Funktion etc.

int number = 100;int* pt = &number;*pt = 200;

& liefert die Speicheradresse einer beliebigen Variable

Mit * kann man den Pointer wieder dereferenzieren und auf den Wert an der Speicheradresse zugreifen.

Je nach Architektur ist ein Pointer nur wenige Bytes gross (Adresse im Speicher)

Informatik I/II PVK 34

Pointer 2

Pointer sind meistens von einem Datentyp. Es gibt aber auch den void-Pointer

(void)* pt = (void*)&a; Oder aber einen Pointer auf einen Pointer

int a = 5;int* b = &a;int** c = &b;

Vorsicht bei solchen Deklarationen double *p1, p2;

Die Pointer Variable hat jedoch ihren eigenen Typ

Informatik I/II PVK 35

Arrays sind ja nur Pointer

Die Variable des Arrays zeigt auf das erste Element im Speicher

int a[] = {1,5,9,4,8,6}

1

5

9

4

8

6

...

a

Informatik I/II PVK 36

Arrays sind ja nur Pointer

Die Variable des Arrays zeigt auf das erste Element im Speicher

int a[] = {1,5,9,4,8,6}

1

5

9

4

8

6

...

a

int* b = a;

,b

Informatik I/II PVK 37

Arrays sind ja nur Pointer

Die Variable des Arrays zeigt auf das erste Element im Speicher

int a[] = {1,5,9,4,8,6}

1

5

9

4

8

6

...

a

int* b = a;b = &a[3];

b

Informatik I/II PVK 38

Arrays sind ja nur Pointer

Die Variable des Arrays zeigt auf das erste Element im Speicher

int a[] = {1,5,9,4,8,6}

1

5

9

8

6

...

a

int* b = a;b = &a[3];

b*b = 10;10

Es können also mehrere Pointer auf ein Ziel zeigen oder auf Teile von Objekten

Informatik I/II PVK 39

Referenzen

Eine Referenz ist ein Alias einer anderer Variable (also ein anderer Name, aber die gleiche Stelle im Speicher)

int fussball = 11;int& soccer = fussball; keine Kopie des Wertes

Eine Referenz muss beim Deklarieren initialisiert werden und kann ihre Speicheradresse nachher nicht mehr ändern

Eine Referenz verhält sich wie ein Pointer der bereits dereferenziert wurde.

Informatik I/II PVK 40

Dynamische Speicherverwaltung

Bisher war bereits zu Compilezeit klar wieviel Speicher genutzt wird.

Man kann aber auch zur Laufzeit Speicher allozieren.

Dies macht man mit dem new-Operator double* p_value = new double;

Der new-Operator gibt immer einen Pointer des erzeugten Typs zurück. Also die Adresse des allozierten Speicher.

Informatik I/II PVK 41

Dynamische Speicherverwaltung

Speicher der mit new alloziert wurde wird nicht mehr am Ende des Scopes freigegeben.

Deshalb muss der Programmierer alles was er mit new erzeugt hat irgendwann auch selbst wieder mit delete löschen.

Ansonsten gibt es Memory Leaks double* p_value = new double;...delete p_value;

Informatik I/II PVK 42

Dynamische Arrays

Arrays können jetzt auch dynamisch erstellt werden (also nicht mit konstanter Länge)

int* a_ptr = new int[10]; delete [] a_ptr;

Alle Pointer (ausser void-Pointer) kann man inkrementieren

a_ptr+1 == &a_ptr[1] *(a_ptr+2) == a_ptr[2]

Informatik I/II PVK 43

Funktionen

typenName funktionsName (argumentenListe)

{

Anweisungen;

return value;

}

Sowohl typenName als auch argumentenListe kann void sein

Bei einem Funktionsaufruf werden Argumente und Rückgabewert hin und her kopiert.

Informatik I/II PVK 44

Inline Funktionen

Bei einem konventionellen Funktionsaufruf passiert dies:

Speichern der aktuellen Adresse (für Rücksprung) Sichern von lokalen Variablen Kopieren der Argumente Abarbeiten der Funktion Kopieren des return-values Rücksprung Wiederherstellung des Ausgangszustandes

Deshalb gibt es inline-Funktionen, welche direkt in den Code kopiert werden.

inline double square(double x) { return x*x; }

Informatik I/II PVK 45

Call by Value

double cube(double x)

{

return x*x*x;} Bei kleinen Werten wie double kein Problem, aber

was ist mit grösseren Objekten wie zum Beispiel Arrays?

Informatik I/II PVK 46

Functioncall für Arrays

int smallest(int arr[]); Da ein Array aber auch ein Pointer ist könnte man

das auch so schreiben: int smallest(int* arr);

Das gilt natürlich nicht nur für Arrays sondern auch für Pointer allgemein.

Dieser Aufruf kopiert das Array nicht, sondern nur die Adresse

Das heisst aber auch, dass alle Veränderungen auf den Originaldaten stattfinden!

Informatik I/II PVK 47

Call by Reference

int devide(double& x, double q) {

if (q != 0) {x /= q;return 0;

}return 1;

} Ändert den Originalwert von x x muss nicht dereferenziert werden Rückgabewert gibt an, ob die Operation geglückt

ist

Informatik I/II PVK 48

Default Argumente

double pow(double x, int e = 2); Defaultwerte werden nur in den Prototypen

gesetzt.

Dies erzeugt eigentlich zwei Funktionen (eine mit und eine ohne das zweite Argument)

pow(2.0); // ist 2^2 (= 4) pow(2.0, 3); // ist 2^3 (= 8)

Defaultargumente müssen immer zuletzt stehen double pow(int e = 2, double x);

ist also nicht erlaubt

Informatik I/II PVK 49

Functionpointer

Prototypen kennen wir ja schon: double f(double x);

Funktionspointer sind einfach Pointer auf den Speicher wo die Funktion sich befindet

double (*pf)(double); Dieser Functionpointer kann auf alle Funktionen

zeigen die einen double annehmen und einen double als Rückgabewert haben.

Ein Aufruf geht dann ganz einfach: pf = f; double result = pf(8.23);

Informatik I/II PVK 50

Templates

Eine Funktion (oder sogar Klasse) kann für unterschiedliche Typen erzeugt werden.

template <class Any>void Swap(Any &a, Any &b){ … }

Beispiele dazu wären vector<> und list<>

Der Compiler erzeugt jeweils die Funktionen einzeln für jeden Typ on demand

Informatik I/II PVK 51

Prüfungsaufgabe 1

Programmanalyse Meistens eine Funktion gegeben und deren

„Funktion“ gefragt. Vorgehen:

Verschiedene Werte ausprobieren und Resultate vergleichen

Array-Zustände mitnotieren Auf Syntax achten Keywords

Informatik I/II PVK 52

Prüfungsaufgabe 1

Schreiben Sie für die folgenden drei Teilaufgaben jeweils den Inhalt des Arrays a in die dafür vorgesehene Tabelle. Die Werte des Arrays werden dabei von einer Teilaufgabe zur nächsten übertragen. Das Array a werde an der Adresse 100 angelegt.

int a [8] = {2,4,6,8,10,12,14,16};

a[3] = 5; *a = a[6];

a[6] = (int)a; int* b = &a[4];

for (int i=0; i<4; i++) b[i] = 2*a[i];

Informatik I/II PVK 53

Lösung zu vorherigem Slide

2 4 6 5 10 12 14 16

14 4 6 5 10 12 100 16

14 4 6 5 28 8 12 10

Informatik I/II PVK 54

Prüfungsaufgabe 1 (cont.)

Zu ermitteln ist der Inhalt von c direkt nach dem Aufruf von foo in main. Schreiben Sie das Resultat in die dafür vorgesehene Tabelle.

void foo(int src[], int dest[], int size) {

for (int i=0; i<size; i++) {

int a=0;

for (int i2=0; i2<=i; i2++) {

a = a+src[i2];}

dest[i] = a;

}

}

int main() {

int b[6] = {2,5,0,-4,-4,1};

int c[6] = {0,0,0,0,0,0};

foo(b,c,6);

return 0;

}

Informatik I/II PVK 55

Lösung zu vorherigen Slide

2 7 7 3 -1 0

Jeweils die Summe der vorherigen Elemente des Ursprungsarrays

Informatik I/II PVK 56

Prüfungsaufgabe 1 (cont.)

Zu wie vielen Lesezugriffen auf das Array b führt der obige Aufruf von foo(b,c,6)?

Die Funktion foo ist ineffizient implementiert. Schreiben Sie eine neue Funktion foo, mit der gleichen Funktionalität aber nur einer for-Schleife. Die Signatur ist bereits angegeben.

void foo(int src[], int dest[], int size)

{

//Insert your code here

Informatik I/II PVK 57

Lösung zu vorherigen Slide

1 + 2 + 3 + 4 + 5 + 6 = 21 Zugriffe auf das Array void foo(int src[], int dest[], int size)

{

int sum = 0;

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

{

sum += src[i];

dest[i] = sum;

}

}