VL MRT-2 Algorithmen und Datenstrukturen in C++

VL MRT-2, SS 2014 Professur für Prozessleittechnik

Übersicht

• Erste Schritte mit Eclipse/CDT

– Wie lege ich ein C++ Projekt an?

– Wie übersetze und starte ich ein Programm?

• Unser erstes C++ Programm

– Rechnen mit komplexen Zahlen

– Wie definiere ich eine neue Objektklasse?

– Wie definiere ich Attribute und Methoden?

– Wie nutze ich das nahtlos in meinem Programm?

07.04.2014 Folie 2 VL MRT-2 (c) 2013-2014, UR

Ziel: Frequenzgangs eines Filter berechnen

• Implementierung als C++-Programm?

double R = 1000, C = 1E-6, w;

complex c, j(0,1);

for (w=1; w<1000; w+=3)

c = ( R / R + 1 / ( j * w * C ) );

• complex ist kein integrierter Datentyp von C++ (wie double, int, ...)

• Wir ergänzen heute C++ so, dass es mit komplexen Zahlen rechnen kann !

07.04.2014 VL MRT-2 (c) 2013-2014, UR Folie 3

Los geht‘s: Hello World in C++

• Integrierte Entwicklungsumgebung

– Virtuelle Maschine mit der Applicance starten

– Eclipse/CDT starten

– ggf. neuen Workspace anlegen:

File Switch Workspace Other...

• C++ Projekt anlegen – File New C++ Projekt

– Project Name: ComplexNumbers

– Project Type: Executable / Hello World C++ Projekt

07.04.2014 VL MRT-2 (c) 2013-2014, UR Folie 4

Schriftart für die

Bedienung von

Eclipse-Menus

Eclipse/CDT IDE

07.04.2014 VL MRT-2 (c) 2013-2014, UR Folie 5

Schnellzugriff

für Ausführen,

Debuggen

Wechsel der

Perspektive

Projektansicht

mit Verzeichnis

Editor

Konsolen-

ausgabe

Struktur der

Datei im Editor

ComplexNumbers.cpp – bekanntes von C

//====== [...]

#include <iostream>

using namespace std;

int main() {

cout << "!!!Hello World!!!" << endl;

return 0;

}

07.04.2014 VL MRT-2 (c) 2013-2014, UR Folie 6

Kommentare

Einstiegspunkt main

Deklaration

vordefinierter

Systemfunktionen

Funktion mit Kopf

und Körper

Build & Run

• Build All (Strg+B)

– Übersetzt und bindet alle offenen Projektdateien

– Erzeugt lauffähige Programme

– Alternative: Project Build All

– Ausgabe in View Console (CDT Build Console oder CDT Global Build Console)

• Run (Strg+F11)

– Startet das Programm des aktuellen Projekts

– Alterantive: Run Run As Local C/C++ Application

– Ausgabe in View Console (CDT Build Console)

07.04.2014 VL MRT-2 (c) 2013-2014, UR Folie 7

Zwei erste C++ Konzepte

//====== [...]

#include <iostream>

using namespace std;

int main() {

cout << "!!!Hello World!!!" << endl;

return 0;

}

07.04.2014 VL MRT-2 (c) 2013-2014, UR Folie 8

C++ Konzept:

namespace

C++ Konzept:

Strom und

Ausgabeoperator <<

1. C++ Konzept Namensraum

• Problem C: Ein Name einer Methode kann nur einmal verwendet werden Namenskonflikte

• Lösungsansatz C++: Strukturierung durch hierarchische Namensräume: „Urbas aus Dresden“

– Spezifikation eines Symbols aus einem Namensraums durch Angabe des vollständigen Namen mit Namensraumoperator :: namespace::methode

• Komfortfunktion

– Vorauswahl von Namensräumen

– using namespace namespace;

• Standard Bibliotheksfunktionen

– Namensraum std

07.04.2014 VL MRT-2 (c) 2013-2014, UR Folie 9

2. C++ Konzept Strom

• Ein Strom verarbeitet Sequenzen von Zeichen

– Ein/Ausgabe auf Konsole: std::cout, std::cin

– Bidirektional (Datei, Zeichenkette)

• Ausgabeoperator <<

– Delegiert Aufbereitung der Information an Objekt

– Verkettung: cout << a << b << c << endl;

• Spezielle Symbole

– endl: Zeilenvorschub

07.04.2014 VL MRT-2 (c) 2013-2014, UR Folie 10

Anwendungsbeispiel: Komplexe Zahlen

• Definition

– c = a + b i; a,b und i²=-1

• Grundlegende Rechenoperationen

– c1+c2 = (a1+a2) + (b1+b2)i

– c1-c2 = (a1-a2) + (b1-b2)i

– c1*c2 = (a1a2-b1b2) + (a1b2+b1a2)i

– c1/c2 = (a1a2+b1b2)/(a2²+ b2²)+((a1b2-b1a2) /(a2²+ b2²))i

07.04.2014 VL MRT-2 (c) 2013-2014, UR Folie 11

Abbildung in eine C++ Klasse

• Abstrakter Datentyp mit Attributen a,b

• Operatoren +, -, *, /

• Auswahl Real und Imaginärteil

• Ausgabeoperator << auf Strom

• Initialisieren, Kopieren, ...

07.04.2014 VL MRT-2 (c) 2013-2014, UR Folie 12

Anlegen einer neuen Klasse

• Im Kontextmenu des Projektbaums new class

– Class name: Complex

– Kein Destruktor, Unit Test

• Header: Complex.h

– Deklaration der Klasse

– Methoden und Attribute

• Implementierung: Complex.cpp

– Implementierung der Algorithmen

• Unit Tests: Complex_test.cpp

– Für testorienterte Entwicklung (TDD)

07.04.2014 VL MRT-2 (c) 2013-2014, UR Folie 13

Complex.h - Gerüst

class Complex {

public:

Complex();

};

07.04.2014 VL MRT-2 (c) 2013-2014, UR Folie 14

C++ Konzept:

Klasse

C++ Konzept:

Konstruktor

C++ Konzept:

Zugriffsmoderator

Complex.cpp - Gerüst

#include "Complex.h"

Complex::Complex() {

// TODO Auto-generated

}

07.04.2014 VL MRT-2 (c) 2013-2014, UR Folie 15

Einbinden der

Definition

Methode mit Name

der Klasse ist

Konstruktor

Namensraum der

Klasse

Einschub: Test Driven Development (TDD)

• Idee

– Dokumentation stimmt nie, Wahrheit im Code

– Spezifikation von Verhalten durch Testfälle

• Unit Test

– Kleinste spezifizierbare Einheit

• Vorgehensmodell

1. Modelliere Verhalten und schreibe Test

2. Erzeuge Code und teste bis es übersetzt weden kann und funktionert

• Mockups sind erlaubt und notwendig

07.04.2014 VL MRT-2 (c) 2013-2014, UR Folie 16

C++: CppUnit Framework (analog JUnit)

• Doku

– http://cppunit.sourceforge.net/doc/lastest/cppunit_cookbook.html ( ??? )

– http://mmmattos.net/wordpress/?p=183

• Installieren $ sudo apt-get install libcppunit-1.12.1

libcppunit-dev

• Einbinden der Library in Projekt project Properties C/C++ Build Settings

07.04.2014 VL MRT-2 (c) 2013-2014, UR Folie 17

CppUnit Framework

• Doku

– http://cppunit.sourceforge.net/doc/lastest/cppunit_cookbook.html ( ??? )

– http://mmmattos.net/wordpress/?p=183

• Installieren $ sudo apt-get install libcppunit-1.12.1

libcppunit-dev

• Einbinden project Properties C/C++ Build Settings

07.04.2014 VL MRT-2 (c) 2013-2014, UR Folie 18

cppunit

Complex_test.cpp: Testfallspezifikation

class ComplexTest : public CppUnit::TestFixture {

private:

Complex* c;

public:

void setUp() { c = new Complex() };

void tearDown() { delete c; };

void defaultConstructorShallInitReImg() {

CPPUNIT_ASSERT(c->Re() == 0.0);

CPPUNIT_ASSERT(c->Img() == 0.0);

}

};

07.04.2014 VL MRT-2 (c) 2013-2014, UR Folie 19

Complex_test.cpp: TestSuite und TestRunner

int main() {

CppUnit::TestSuite suite;

CppUnit::TestResult result;

suite.addTest(new

CppUnit::TestCaller<ComplexTest>("defaultConstructo

rShallInitReImg",

&ComplexTest::defaultConstructorShallInitReImg));

CppUnit::TextUi::TestRunner runner;

runner.addTest(&suite);

return runner.run("",false);

}

07.04.2014 VL MRT-2 (c) 2013-2014, UR Folie 20

OOD: Attribute, Zugriffsmethoden und Konstruktoren

• Private Attribute – double real;

– double imag;

• Öffentliche Zugriffsmethoden – double Re();

– double Im();

• Öffentlicher Konstruktor mit Defaultwerten – complex(double r = 0.0, double i = 0.0);

07.04.2014 VL MRT-2 (c) 2013-2014, UR Folie 21

Deklaration in Complex.h

class Complex {

private:

double real;

double imag;

public:

// Konstruktoren

Complex(double r = 0.0, double i = 0.0);

// Zugriff auf die Attribute

double Re();

double Im();

};

07.04.2014 VL MRT-2 (c) 2013-2014, UR Folie 22

Zugriffsmoderator

gilt bis zum

nächsten. Default ist

protected

Parameter mit

default-werten sind

optional.

Einschränkung:

kein Default in der

Mitte, nur vom

rechten Ende her!

Implementierung in Complex.cpp

#include „Complex.h"

Complex::Complex(double r, double i) :

real(r), imag(i) {

}

double Complex::Re() {

return real;

}

double Complex::Im() {

return imag;

}

07.04.2014 VL MRT-2 (c) 2013-2014, UR Folie 23

Element-

initialisierungsliste

mit Kopier-

Konstruktoren

Import der

Prototypen

Zuordnung zum

Namensraum der

Klasse Complex

Anwendung

int main() {

Complex c0(1,2), c1, c2(c0);

cout << "c0 = (" << c0.Re() << "," << c0.Im() <<

")" << endl;

// [...]

return 0;

}

07.04.2014 VL MRT-2 (c) 2013-2014, UR Folie 24

Konstruktoren mit

Defaultwerten für r

und i

C++ legt

selbstständig einen

Kopierkonstruktor an

Complex::Complex(

double r, double i)

Ausgabe von Klassen auf Strom

• Wie sieht eine Methode aus, die das gleiche Ergebnis liefert, aber eleganter in der Anwendung ist: cout << c0 << endl; ?

• Ohne eigenen Code: Fehler!

• Lösung: Neue Methode operator<< für den Datentyp Complex

inline ostream& operator<<(ostream& lhs,

const Complex& rhs) {

return lhs << "(" << rhs.Re() << "," <<

rhs.Im() << ")";

}

07.04.2014 VL MRT-2 (c) 2013-2014, UR Folie 25

C++ Konzept: operator

• Häufig Ausdrucksmuster der Art: – Ergebnis = LinkerOperand Operator

RechterOperand;

– Arithmetik, Logik, ...

• Lösungsansatz in C oder Java: – Ergebnis = Methode(Operand1, Operand2)

– Methodennamen beginnen mit [_A-Za-z]

• C++: Überschreiben von Operatoren – Ergebnis = operatorXX(Operand1, Operand2)

– XX ist das symbolische Kürzel des Operators

07.04.2014 VL MRT-2 (c) 2013-2014, UR Folie 26

complex.h - Entwurf operator<<

• Der Ausgabeoperator genügt dem Muster

– LinkerOp Operator RechterOp

– ostrom << objekt

operator<<(ostream &lhs, Complex &rhs)

• Was soll rückgegeben werden? rhs? lhs?

• Lösung aus Forderung nach Verkettung – strom << a << b << c << endl;

– C++ löst von links nach rechts auf

– Schritt 1:(((strom << a) << b) << c) << endl;

– Schritt 2:(( ergebnis? << b) << c) << endl;

– Schritt 3:( ergebnis? << c) << endl;

! Konvention: operator<< gibt Strom zurück – ostream& operator<<(ostream &lhs, Complex &rhs)

07.04.2014 VL MRT-2 (c) 2013-2014, UR Folie 27

Ziel: Frequenzgang eines Filters berechnen

double R, C, w;

Complex c, j;

c = ( R / R + 1 / ( j * w * C ) );

• Definition

– a,b,d ; i²=-1; c = a + b i;

• Arithmetik

– c1+c2 = (a1+a2) + (b1+b2)i

– c1-c2 = (a1-a2) + (b1-b2)i

– c1*c2 = (a1a2-b1b2) + (a1b2+b1a2)i

– c1/c2 = (a1a2+b1b2)/(a2²+ b2²)+((a1b2-b1a2) /(a2²+ b2²))i

07.04.2014 VL MRT-2 (c) 2013-2014, UR Folie 28

Complex * double

double / Complex

Ausflug: Überladen von Operatoren in C++

• Fast alle Operatoren sind überladbar:

• Nicht überladen werden können

:: .* . ?:

• Es gibt keine neuen Operatoren

07.04.2014 VL MRT-2 (c) 2013-2014, UR Folie 29

Regeln (1/2)

• Ein überladener Operator muss mindestens einen Operanden vom Typ Klasse besitzen

• Priorität, Assoziativität und Anzahl der Operanden eines Operators können nicht verändert werden

– Beispiel: A == B + C;

– Resultiert, unabhängig vom Typ von A,B,C und den ggf. überladenen Operatoren immer in: operator==(A, operator+(B, C));

07.04.2014 VL MRT-2 (c) 2013-2014, UR Folie 30

Regeln (2/2)

• Kurzschlusseigenschaft von logischem und (&&), logischem oder (||) bleiben nicht erhalten

– Es werden immer beide Operanden ausgewertet

– Reihenfolge der Auswertung ist nicht festgelegt

• Reihenfolge der Auswertung für Kommaoperator ist nicht definiert

07.04.2014 VL MRT-2 (c) 2013-2014, UR Folie 31

Operator als Elementfunktion einer Klasse

• Überladene Operatoren dürfen sowohl als herkömmliche Nichtelementfunktion als auch als Elementfunktion definiert werden.

• Beispiel: Binärer Operator += : c += j

• Definition als Nichtelementfunktion: Complex& operator+=(const Complex& lhs,

const Complex& rhs)

• Definition als Elementfunktion: Complex& Complex::operator+=(const Complex&

rhs)

07.04.2014 VL MRT-2 (c) 2013-2014, UR Folie 32

Elementfunktion vs Nichtelementfunktion

• Definition als Nichtelementfunktion: Complex& operator+=(const Complex& lhs,

Const complex& rhs)

• Definition als Elementfunktion: Complex& Complex::operator+=(const Complex&

rhs)

• Achtung: Bei einer Definition als Elementfunktion ist der erste Operand das Objekt, repräsentiert durch den impliziten Zeiger this.

07.04.2014 VL MRT-2 (c) 2013-2014, UR Folie 33

Der implizite Zeiger this

• Jede Elementfunktion hat einen impliziten Parameter: this

• this ist ein Zeiger auf ein Objekt des Klassentyps.

• this ist an das Objekt gebunden, für das die Elementfunktion aufgerufen wurde.

• this wird immer dann benötigt, wenn wir uns auf das Objekt als Ganzes beziehen wollen.

07.04.2014 VL MRT-2 (c) 2013-2014, UR Folie 34

Beispiel complex

• Per Definition muss += eine Referenz (= ein Stellvertreter, gekennzeichnet durch das &) auf das Objekt zurückgeben

// complex += complex

Complex& Complex::operator+=(const

Complex& rhs) {

real+=rhs.real; imag+=rhs.imag;

return *this;

}

07.04.2014 VL MRT-2 (c) 2013-2014, UR Folie 35

Heuristiken für Operatorüberladung (1/4)

• Der Compiler überlädt automatisch:

– Zuweisungsoperator (=): Elementweise Zuweisung

– Addressierungs- (&) und Kommaoperator (,)

• Arithmetische Operatoren (+, -, *, /, …)

– gemäß Häufigkeit und eindeutiger Interpretierbarkeit

• Zuweisungsoperatoren (+=, -=, …)

– Günstig, wenn entsprechender arithmetischer Operator definiert ist

07.04.2014 VL MRT-2 (c) 2013-2014, UR Folie 36

Heuristiken zur Operatorüberladung (2/4)

• Gleichheits- und relationale Operatoren

– Wenn Schlüssel in assoziativem Container, dann mindestens <

– Wenn Eintrag in sequentiellem Container, dann < und == für Algorithmen wie find (==) und sort (<)

– Wenn == dann auch !=, wg. Erwartung der Anwender der Klassen

– Wenn < dann ist auch >,>= und <= ratsam

• Ein/Ausgabe

– IO-Strom-Operatoren <<, >>

07.04.2014 VL MRT-2 (c) 2013-2014, UR Folie 37

Elementfkt vs. Nichtelementfkt.

• Elementfunktionen müssen sein:

– Zuweisung (=), Indizierung ([]), Aufruf (()) und Elementzugriffspfeil (->)

• Elementfunktion sollten sein:

– Operatoren die den Zustand ihres Objekts verändern oder damit eng verknüpft sind

– Zuweisungsoperatoren ( += -= ), Inkrementierung (++), Dekrementierung (--), Dereferenzierung (*)

• Nichtelementfunktionen sollten sein:

– Symetrische Operatoren wie Arithmetik (+ - * /) Gleichheit (==), relationale (< > <= >=) und bitweise (& | ^) Operatoren

07.04.2014 VL MRT-2 (c) 2013-2014, UR Folie 38

Rechenoperationen

• Ziel: Frequenzgang eines Filters berechnen

double R, C, w;

complex c, j;

c = ( R / R + 1 / ( j * w * C ) );

• Definition

– a,b,d und i²=-1

– c = a + b i;

• Arithmetik

– c1+c2 = (a1+a2) + (b1+b2)i, c1-c2 = (a1-a2) + (b1-b2)i

– c1*c2 = (a1a2-b1b2) + (a1b2+b1a2)i

– c1/c2 = (a1a2+b1b2)/(a2²+ b2²)+((a1b2-b1a2) /(a2²+ b2²))i

07.04.2014 VL MRT-2 (c) 2013-2014, UR Folie 39

complex + complex

• Elementfunktion operator+= // complex += complex

Complex& Complex::operator+=(const Complex& rhs) {

real+=rhs.real; imag+=rhs.imag;

return *this; }

• Nichtelementfunktion operator+ // complex = complex + complex

inline Complex operator+(const Complex& lhs, const

Complex& rhs) {

Complex cret(lhs);

return cret += rhs;

}

07.04.2014 VL MRT-2 (c) 2013-2014, UR Folie 40

Test Driven Development

// given

Complex c(2,1), j(0,-1), r;

// when // then

r = j * j r == e(-1, 0)

r = c + c r == e( 4, 2)

r = c – j r == e( 2, 0)

r = c * j r == e(-1, 2)

r = c * c r == e( 3, 4)

r = c * 2 r == e( 4, 2)

r = 2 * c r == e( 4, 2)

r = c / j r == e( 1, 2)

r = c / c r == e( 1, 0)

07.04.2014 VL MRT-2 (c) 2013-2014, UR Folie 41

Selbstständig vervollständigen... (kontrolliertes copy , paste & modify)

• EF: operator+=(const double)

• NEF: operator+ (const double, const complex&)

• Analog für -, * und /

07.04.2014 VL MRT-2 (c) 2013-2014, UR Folie 42

Berechnung Transferfunktion

Complex j(0,1);

double C(1e-6), R(1000);

Complex transfer_function(double w) {

return R / ( R + 1 / ( j * w * C ));

}

int main() {

for (double w=1; w < 1000; w += 3 ) {

Complex r = transfer_function(w);

cout << w << " " << r.Re() << " " << r.Im() <<

endl; }

return 0;

}

07.04.2014 VL MRT-2 (c) 2013-2014, UR Folie 43

Anzeigen mit gnuplot

• Starten des Programms von der Konsole und Umleiten der Ausgabe in eine Datei: $ cd MRT2-VL/ComplexNumbers

$ Debug/ComplexNumbers > q.q

• Anzeigen der 3ten über der 2ten Spalte $ gnuplot -e "plot 'q.q'

using 2:3 with lines;

pause mouse any"

07.04.2014 VL MRT-2 (c) 2013-2014, UR Folie 44