Wissensspeicher 15

Baumtraversierung

Tiefensuche
- inorder: links, Knoten, rechts → sortierte Ausgabe bei binärem Suchbaum
- preorder: Knoten, links, rechts
- postorder: links, rechts, Knoten
Breitensuche
- breadth-first-search
- Zuerst alle Knoten einer Ebene abarbeiten, dann absteigen

Graphen

Verallgemeinerung eines Baumes
Besteht aus Kanten und Knoten
Gerichtet und ungereichtet
Wichtiges Werkzeug in der Informatik zur Modellierung

Live-Demo - Vererbung 1

#include <iostream>

using namespace std;

class KString {
private:
	char* mString;
	int mLength;

public:
	KString(char const* s)	{
		mLength = strlen(s);              // Länge ohne '\0'
		mString = new char[mLength + 1];  // + 1 wegen '\0'
		strcpy(mString, s);               // kopiert s nach mString
	}
	void setString(char const* s) {
		int length = strlen(s);
		if (length > mLength) {
			delete[] mString;
			mString = new char[length + 1];
		}
		strcpy(mString, s);
		mLength = length;
	}
	char* getString() { return mString; }
	int length() { return mLength; }
	void print() { cout << mString << endl; }
	~KString() {
		delete[] mString;
	}
};

class KVersalien : public KString {
private:
	void up() {
		for (int i = 0; i < mLength; ++i) {
			if (islower(mString[i])) {
				mString[i] = toupper(mString[i]);
			}
		}
	}

public:
	KVersalien(char const* s) : mLength(0) { }
	void print() { cout << mString << endl; }
	void setString(char const* s) {
		KString::setString(s);
		up();
	}
};

int main() {
  KString s1{"erster String"};
  s1.print();
  cout << "s1.length()=" << s1.length() << endl;

	return 0;
}

compiler

✕

Live-Demo - public-Vererbung

#include <iostream>

using namespace std;

class A {
private:
    int pi = 3;
protected:
    int plank = 6;
public:
    int boltzmann = 1;
};

class B : public A {
public:
    int getPlank() { return plank; }
    int getBoltzmann() { return boltzmann; }
};

int main() {
    B b;

    cout << "pi = " << b.pi << endl;
    cout << "boktzmann = " << b.boltzmann << endl;
    cout << "plank = " << b.plank << endl;

	return 0;
}

compiler

✕

Live-Demo - protected-Vererbung

#include <iostream>

using namespace std;

class A {
private:
    int pi = 3;
protected:
    int plank = 6;
public:
    int boltzmann = 1;
};

class B : protected A {
public:
    int getPlank() { return plank; }
    int getBoltzmann() { return boltzmann; }
};

int main() {
    B b;

    // Die Ausgabe von B::pi geht nicht, da private.
    cout << "boktzmann = " << b.boltzmann << endl;
    cout << "plank = " << b.plank << endl;

	return 0;
}

compiler

✕

Live-Demo - private-Vererbung

#include <iostream>

using namespace std;

class A {
private:
    int pi = 3;
protected:
    int plank = 6;
public:
    int boltzmann = 1;
};

class B : private A {
public:
    int getPlank() { return plank; }
    int getBoltzmann() { return boltzmann; }
};

int main() {
    B b;

    // Die Ausgabe von B::pi geht nicht, da private.
    cout << "boktzmann = " << b.boltzmann << endl;
    cout << "plank = " << b.plank << endl;

	return 0;
}

compiler

✕

Live-Demo - Funktionen der Oberklasse nutzen

#include <iostream>

using namespace std;

class KString {
protected:
	char* mString;
	int mLength;

public:
	KString(char const* s)	{
		mLength = strlen(s);              // Länge ohne '\0'
		mString = new char[mLength + 1];  // + 1 wegen '\0'
		strcpy(mString, s);               // kopiert s nach mString
	}
	void setString(char const* s) {
		int length = strlen(s);
		if (length > mLength) {
			delete[] mString;
			mString = new char[length + 1];
		}
		strcpy(mString, s);
		mLength = length;
	}
	char* getString() { return mString; }
	int length() { return mLength; }
	void print() { cout << mString << endl; }
	~KString() {
		delete[] mString;
	}
};

class KVersalien : public KString {
private:
	void up() {
		for (int i = 0; i < mLength; ++i) {
			if (islower(mString[i])) {
				mString[i] = toupper(mString[i]);
			}
		}
	}

public:
	KVersalien(char const* s) : KString(s) { up(); }
	void print() { cout << mString << endl; }
	void setString(char const* s) {
            // TODO
	}
};

int main() {
  KString s1{"erster String"};
  s1.print();
  cout << "s1.length()=" << s1.length() << endl;

	return 0;
}

compiler

✕

Live-Demo - Vererbungstest

#include <iostream>

using namespace std;

class KString {
protected:
	char* mString;
	int mLength;

public:
	KString(char const* s)	{
		mLength = strlen(s);              // Länge ohne '\0'
		mString = new char[mLength + 1];  // + 1 wegen '\0'
		strcpy(mString, s);               // kopiert s nach mString
	}
	void setString(char const* s) {
		int length = strlen(s);
		if (length > mLength) {
			delete[] mString;
			mString = new char[length + 1];
		}
		strcpy(mString, s);
		mLength = length;
	}
	char* getString() { return mString; }
	int length() { return mLength; }
	void print() { cout << mString << endl; }
	~KString() {
		delete[] mString;
	}
};

class KVersalien : public KString {
private:
	void up() {
		for (int i = 0; i < mLength; ++i) {
			if (islower(mString[i])) {
				mString[i] = toupper(mString[i]);
			}
		}
	}

public:
	KVersalien(char const* s) : KString(s) { up(); }
	void print() { cout << mString << endl; }
	void setString(char const* s) { KString::setString(s); up(); }
};

int main() {
	KString s1{"erster String"};
	s1.print();
	cout << "s1.length()=" << s1.length() << endl;

	s1.setString("kurz");
	s1.print();
	cout << "s1.length()=" << s1.length() << endl;
	cout << endl;

	s1.setString("erster String ueberschrieben");
	s1.print();
	cout << "s1.length()=" << s1.length() << endl;
	cout << endl;

	KVersalien v1{s1.getString()};
	v1.print();
	cout << "v1.length()=" << v1.length() << endl;
	cout << endl;

	v1.setString("versalien-string auch nochmal ueberschrieben");
	v1.print();
	cout << "v1.length()=" << v1.length() << endl;
	cout << endl;

	return 0;
}

compiler

✕

Live-Demo - Mehrfachvererbung

#include <iostream>

using namespace std;

class Pferd {
public: 
    string geraeusch() {
       return "wiehern"; 
    } 
};

class Mensch {
public:
    string geraeusch() {
       return "hallo"; 
    }
    void print() {
        cout << "Ich bin ein Mensch!" << endl;
    }
};

class Chimaere : public Mensch, public Pferd {
public:
    string geraeusch() {
       return Mensch::geraeusch() + Pferd::geraeusch(); 
    }
};


int main() {
    Chimaere c;

    cout << c.geraeusch() << endl;
    cout << c.Mensch::geraeusch() << endl;
    cout << c.Pferd::geraeusch() << endl;

    c.print();

	return 0;
}

compiler

✕

Wissensspeicher 16

Vererbung

Weitergabe von Daten (Attributen) und Operationen (Methoden) an andere Klassen
Wiederverwendung und ggf. Spezialisierung von Programmcode (siehe KVersalien::setString())
Syntax: class B : public class A {
Auch Mehrfachvererbung möglich
Sichtbarkeit der Vererbung gibt obere Grenze für die weitere Sichtbarkeit an
- class B : public class A {: Sichtbarkeit aller geerbten Elemente bleibt erhalten
- class B : protected class A {: Sichtbarkeit aller geerbten Elemente wird auf Unterklassen beschränkt
- class B : private class A {: Sichtbarkeit aller geerbten Elemente wird auf diese Klasse beschränkt
Aufruf von Methoden der Oberklasse mit Klassennamen: KString::setString()
Aufruf des Konstruktors der Oberklasse in der Initializer List:

KVersalien(.. s) : KString(s) {}
Aufrufe der Konstruktoren der Oberklassen wird dringend empfohlen

„Beispiel mit 3 Klassen: Testprogramm” - Revisited

Was kann man bei der Implementierung der Klassen Mann und Frau verbessern?

(Betrachtet das Problem eher gesellschaftlich – im Jahr 2024.)

Die Methoden heirateMann() und heirateFrau sind nicht mehr zeitgemäß
Eigentlich soll eine Person eine Partnerschaft eingehen → gehePartnerschaftEin()
Funktionalität in die gemeinsame Oberklasse verlagern

class Person {
private:
    Person *mParterIn;
    void gehePartnerschaftEin(Person *p) { mPartnerIn = p; }
    /* ... Rest ... */
public:
    /* ... Rest ... */
    Person* partnerInVon() { return mPartnerIn; }
    bool heirate(Person *p) {
        if (p == nullptr) {
            return false;
        }
        if (p->partnerInVon() != nullptr ||
            this->partnerInVon() != nullptr) {
            return false;
        }
        p->gehePartnerschaftEin(this);
        this->gehePartnerschaftEin(p);
        return true;
    }
};

One Variable to Rule Them All

Instanzen von Unterklassen können Zeigervariablen der Oberklasse zugewiesen werden
Nützlich bei der Speicherung von Objekten unterschiedlichen Typs mit gemeinsamer Oberklasse
Beispiel: Liste von Personen (Mann, Frau, Divers) oder TU-Angehörige(r) (Student:in, Mitarbeiter:in, Prof)

class TUPerson { /* ... */ };
class Student : public TUPerson { /* ... */ };
class Employee : public TUPerson { /* ... */ };

int main() {
    list<TUPerson*> members;

    TUPerson *p = new Student();
    members.enqueue(p);

    p = new Employee();
    members.enqueue(p);

    return 0;
}

Live-Demo - Variablenzuweisung

#include <iostream>
#include <list>

using namespace std;

class A {
public:
    void print() { cout << "Hello!" << endl; }
};

class B : public A {
public:
    void print() { cout << "Bye!" << endl; }
};

class C : public A {
public:
    void print() { cout << "Ciao!" << endl; }
};

int main() {
    list<A*> elements;
    A a;
    B b;
    C c1, c2;

    elements.push_back(&b);
    elements.push_back(&c1);
    elements.push_back(&c2);
    elements.push_back(&a);

    for (A *elem : elements) {
        elem->print();
    }

	return 0;
}

compiler

✕

Aufruf der korrekten Variante?
→ virtuelle Methoden
→ Kapitel 11