~~SLIDYSHOW~~

====== Programmierung ======

  * 8. Klasse: [[inf:inf8bi_201112:turbo_cpp:Datenstrukturen]]
  * 7. Klasse: [[inf:inf7b_201011:Visual-C]]
  * 6. Klasse: [[informatik:k6inf:Programmierung]]

===== Strukturen =====
Strukturen sind vereinfachte Klassen und fassen somit Eigenschaften (Variablen) zusammen.

==== Definition ====

=== Typdefinition ===

einfache Def. eines neuen Typs:
<code cpp>
struct CDatum {
    int Tag;
    int Monat;
    int Jahr;
}; // Das Semikolon beendet die Definition

CDatum variable;
</code>

Typdef. und Erstellung einer Variable
<code cpp>
struct CDatum {
    int Tag;
    int Monat;
    int Jahr;
} d; // d ist eine Variable des Datentyps CDatum.

CDatum variable;
</code>

=== anonyme Variablendefinition ===

<code cpp>
struct { // Dieser Datentyp hat keinen eigenen Namen.
    int Tag; 
    int Monat;
    int Jahr;
} d; // Der Datentyp von d ist anonym
</code>
==== Verschachtelung von Strukturen ====
<code cpp>
struct Kontobewegung {
    int KontoNr;
    char NameInhaber[20];
    struct {
       int Tag;
       int Monat;
       int Jahr;
    } Datum;
    char BewArt;
    double Betrag;
};
</code>
==== Zugriffe ====
Zugriff ist per '.' Punkt möglich.
<code cpp>
test.variable;
</code>

<code cpp>
Kontobewegung k;

// kann man die Elemente der Variablen k folgendermaßen ansprechen: 
k.KontoNr // ein Ausdruck des Datentyps int
k.Datum // ein Ausdruck des Datentyps CDatum

// Die drei Elemente von K.Datum lassen sich einzeln ansprechen durch 
k.Datum.Tag // ein Ausdruck des Datentyps int
k.Datum.Monat
k.Datum.Jahr
</code>

Definitionen sind auch mit geschwungenen Klammern möglich:
<code cpp>
struct CDatum {
    int Tag;
    int Monat;
    int Jahr;
} d;

CDatum test = {1, 2, 3};
cout << test.Monat; // 2
</code>



===== Zeiger =====

Ein Zeiger speichert eine Speicheradresse und verweist so auf einen bestimmten Platz im Speicher. Mit der Dereferenzierung wird auf die unter der gespeicherten Adresse gespeicherten Daten zugegriffen.

{{https://upload.wikimedia.org/wikipedia/commons/thumb/9/90/Pointers-de.svg/200px-Pointers-de.svg.png?}}

==== Definition ====
<code cpp>
int *p;
</code>
Erstellt einen Zeiger auf eine Ganzzahl.

==== Dereferenzierung ====
Mit der Dereferenzierung kann auf den Wert der referenzierten Variable zugreifen.
<code cpp>
int *p;
*p = 17;
</code>

=== von Strukturen und Klassen ===
Mit dem -> Operator
<code cpp>
struct T {
    int a, b;
}
T *var;
(*var).a = 1;
var->b = 2;
</code>

==== Referenzierung ====
Gibt die Adresse einer regulären Variable zurück.
<code cpp>
int i=17; double d=18; char c='A';

&i // Zeiger auf int
&d // Zeiger auf double
&c // Zeiger auf char
</code>

==== Beispiel ====

<code>
int* pi; double* pd;
pi = &i; // pi wird die Adresse von i zugewiesen
pd = &d; // pd wird die Adresse von d zugewiesen
char* pc=&c;// initialisiere pc mit &c
</code>

==== generische Zeiger ====
Der Datentyp void* wird als generischer Zeigertyp bezeichnet. Einem generischen Zeiger kann ein Zeiger auf einen beliebigen Zeigertyp zugewiesen werden. 

Ein generischer Zeiger zeigt aber auf keinen bestimmten Datentyp. Deshalb ist es nicht möglich, einen generischen Zeiger ohne explizite Typkonversion zu dereferenzieren. Mit einer expliziten Typkonversion kann er aber in einen beliebigen Zeigertyp konvertiert werden.
<code cpp>
int* pi;
void* pv;

// ist die erste und die dritte der folgenden Zuweisungen möglich: 
pv = pi;
pi = pv; // Fehler: Konvertierung nicht möglich
pi = (int*)pv; // explizite Typkonversion

// Die Dereferenzierung eines generischen Zeigers ist ohne explizite Typkonversion nicht möglich: 
*pi = *pv; // Fehler: Kein zulässiger Typ
int i = *((int*)pv); // das geht
</code>

==== dynamische Erzeugung ====
Für einen Datentyp T reserviert „new T“ so viele Bytes auf dem Heap, wie für eine Variable des Datentyps T notwendig sind. Der Ausdruck „new T“ hat den Datentyp „Zeiger auf T“. Sein Wert ist die Adresse des reservierten Speicherbereichs und kann einer Variablen des Typs „Zeiger auf T“ zugewiesen werden:
<code cpp>
int* pi;
pi=new int; //reserviert sizeof(int) Bytes und weist pi die Adresse dieses Speicherbereichs zu
*pi=17;     // initialisiert den reservierten Speicherbereich

// Am besten initialisiert man eine Zeigervariable immer gleich bei ihrer Definition: 
int* pi=new int (3445234); // initialisiert pi mit der Adresse
*pi=17;
</code>
=== und Löschung ===
Zur Vermeidung von Speicherlecks ist eine explizite Löschung empfohlen.
<code cpp>
delete pi;
</code>


===== Listen =====
Listen sind Strukturen, die einen Wert speichern und auf ihrem Nachfolger verweisen.
<code cpp>
struct CWaggon {
    AnsiString data;      // die Nutzdaten
    CWaggon *next;        // Zeiger auf den nächsten Knoten
};
</code>
Ein solcher Datentyp wird auch als rekursiver Datentyp bezeichnet.

{{inf:inf8bi_201112:datenstrukturen:bck-292.jpg}}

Im Programm muss nur ein Zeiger gespeichert werden, der auf den ersten Knoten der Liste verweist:
<code cpp>
CWaggon *first; // Zeiger auf den ersten Knoten
</code>
Den letzten Knoten der Liste kennzeichnet man durch einen Zeiger next mit dem Wert 0. Grafisch wird dieser Wert oft durch einen schwarzen Punkt dargestellt. 
Dann hat die verkettete Liste einen eindeutigen Anfang und ein eindeutiges Ende:

{{inf:inf8bi_201112:datenstrukturen:bck-293-1.jpg}}

==== Einhängen eines neuen Knotens ====

Als nächstes sollen Anweisungen gesucht werden, mit denen man vor einem Knoten, auf den ein Zeiger n0 zeigt,

{{inf:inf8bi_201112:datenstrukturen:bck-293-2.jpg}}

einen neuen Knoten einfügen kann, auf den n0 dann zeigt:

{{inf:inf8bi_201112:datenstrukturen:bck-293-3.jpg}}

Das ist mit den Anweisungen unter 1. und 2. möglich:

1. Ein Zeiger //tmp// soll auf einen neuen Knoten zeigen, der mit //new// erzeugt wird

<code cpp>
CWaggon *tmp = new CWaggon; // 1.1
</code>

und dem die Daten durch eine Anweisung wie

<code cpp>
tmp->data = d2; // 1.2
</code>

zugewiesen werden. Dadurch ergibt sich:

{{inf:inf8bi_201112:datenstrukturen:bck-293-4.jpg}}

2. Der neue Knoten //*tmp// wird dann mit den beiden Anweisungen

<code cpp>
tmp->next = n0; // 2.1
n0 = tmp;       // 2.2
</code>

in die Liste eingehängt:

{{inf:inf8bi_201112:datenstrukturen:bck-294-1.jpg}}

Diese Anweisungen werden mit der Funktion

<code cpp>
CWaggon *newWaggon(T &data, CWaggon *next) // gibt Zeiger auf neuen Listenknoten{d0,nx0} zurück,  
{                                         // wobei d0 und nx0 die Argumente für data und next sind.
 CWaggon *n = new CWaggon;                // 1.1
 n->data = data;                          // 1.2
 n->next = next;                          // 2.2
 return n;                                // Nachbedingung: Der Rückgabewert zeigt auf 
}                                         // einen neuen Knoten {d0,nx0}
</code>

durch den Aufruf

<code cpp>
 n0 = newWaggon(d2,n0);                   // 2.1
</code>

ausgeführt. //n0// zeigt danach auf einen neu erzeugten Knoten, dessen Element //next// auf den Knoten zeigt, auf den das Argument für //next// zeigt. Falls das Argument für //next// den Wert 0 hat, zeigt der Funktionswert auf einen Knoten mit //next//==0. 

Das Ergebnis der ersten drei Ausführungen der Anweisung
<code cpp>
 first = newWaggon(di,first);
</code>

mit den Daten //d1, d2// usw., wobei der Wert von //first// zuerst 0 sein soll, ist in dem folgenden Ablaufprotokoll dargestellt. Dabei sind die Zeiger auf die von //newWaggon// erzeugten Knoten mit //n1, n2// usw. bezeichnet, und ein Knoten, auf den ein solcher Zeiger zeigt, mit //->{di,nj}//. Der Ausdruck //->{d2,n1}// in der Spalte //n2// ist also nichts anderes als eine Kurzschreibweise für

{{inf:inf8bi_201112:datenstrukturen:bck-294-2.jpg}}

Die Werte in den Spalten //n1, n//2 usw. erhält man einfach durch Einsetzen der Argumente in die Nachbedingung von //newWaggon//:

<code cpp>
                                   // first         n1          n2        n3
first = 0;                               0
first = newWaggon(d1,first);             n1        ->{d1,0}
first = newWaggon(d2,first);             n2                    ->{d2,n1}
first = newWaggon(d3,first);             n3                              ->{d3,n2}
</code>

Dieses Ablaufprotokoll illustriert, wie der erste dieser Aufrufe einen ersten Knoten mit //next//==0 erzeugt, auf den first dann zeigt, und wie jeder weitere Aufruf einen neuen Knoten am Anfang in die verkettete Liste einhängt, auf die //first// zeigt.

Die Funktionsweise von newWaggon beruht insbesondere darauf, dass eine mit new erzeugte Variable bis zum Aufruf von //delete// existiert. Im Unterschied zu einer gewöhnlichen Variablen wird ihr Speicherplatz nicht mit dem Verlassen des Blocks wieder  freigegeben, in dem sie erzeugt wurde.

– Deshalb existiert die Variable //*tmp//, die mit ''CWaggon *tmp=new CWaggon;'' erzeugt wurde, auch noch nach dem Verlassen der Funktion //newWaggon//.

– Der Zeiger //tmp// ist dagegen eine „gewöhnliche“ lokale Variable, deren Speicherplatz mit dem Verlassen des Blocks wieder freigegeben wird. Da der Wert von //tmp// dem Element //next// des Funktionswerts zugewiesen wird, kann man die lokal erzeugte Variable //*tmp// über den Funktionswert auch außerhalb der Funktion verwenden, in der sie erzeugt wurde.

==== Durchlaufen ====
Um die Liste zu Durchlaufen, kann man sich mit einem Hilfszeiger durch die Liste bis zu Ende durchhangeln:
<code cpp>
CWaggon *tmp=start;
while (tmp != 0) {
    Form1->Memo1->Lines->Add(tmp->data);
    tmp = tmp->next;
}
</code>

==== dopplete Verkettung ====
Dabei wird nicht nur auf das folgende, sonder auch auf das vorherige Element verwiesen.
<code cpp>
struct CWaggon {
    AnsiString data;
    CWaggon *next;
    CWaggon *previous;
};
 
CWaggon *first=0, *last=0;
</code>

{{https://upload.wikimedia.org/wikipedia/commons/thumb/5/5e/Doubly-linked-list.svg/500px-Doubly-linked-list.svg.png}}

=== Einhängen ===
== vorne ==

<code cpp>
CWaggon *tmp = new CWaggon;
tmp->data = Edit1->Text;
tmp->next = first;
tmp->previous = 0;
if (tmp->next!=0)
    tmp->next->previous = tmp;
else last = tmp;
first = tmp;
Edit1->Text  = "";
</code>
== hinten ==
<code cpp>
CWaggon *tmp = new CWaggon;
tmp->data = Edit2->Text;
tmp->previous = last;
tmp->next = 0;
if (tmp->previous!=0)
     tmp->previous->next = tmp;
else first = tmp;
last = tmp;
Edit2->Text = "";
</code>


===== Bäume =====

Baumstrukturen werden aus Knoten aufgebaut, die einen Zeiger auf einen linken und rechten Teilbaum enthalten:

{{:inf:inf8bi_201112:datenstrukturen:baeume1.png|Binärbäume}}

Ein Baumknoten kann durch den Datentyp ''CKnoten'' dargestellt werden:

<code cpp>
struct CKnoten {
  int data;       // die Nutzdaten sind in diesem Beispiel nur Zahlen
  CKnoten* left;
  CKnoten* right;
};
</code>

Der Zeiger auf den obersten Knoten des Baums wird oft als root bezeichnet:

<code cpp>
CKnoten *root=0;
</code>

==== Einhängen eines neuen Knotens ====

<code cpp>
void einhaengen(CKnoten *&parent, CKnoten *neu) {
    if (parent==0) {
        parent=neu;
    } else {
        if (neu->data<=parent->data) {
            einhaengen(parent->left,neu);
        } else {
            einhaengen(parent->right,neu);
        }
    }
}

void __fastcall TForm3::Button1Click(TObject *Sender) {
    CKnoten *neu = new CKnoten;
    if (Edit1->Text != "") { 
        neu->data = StrToInt(Edit1->Text);
        neu->left = 0;
        neu->right = 0;
        Edit1->Text = "";
        einhaengen(root,neu);
    }
    Edit1->Focused();
}
</code>

==== Löschen eines Knotens ====
Knoten h wird gelöscht. Es werden 3 Fälle unterschieden:
  * Nur linker Teilbaum existiert
  * Nur rechter Teilbaum existiert
  * Beide Teilbäume existieren

In den ersten beiden Fällen wird einfach der Teilbaum nach oben gerückt, im 3 Fall muss der Wert der Wurzel verglichen werden.
<code cpp>
if (h!=0) {
    if (StrToInt(Form1->Edit3->Text) <= h->data)
        loeschen(h->left);
    else if (StrToInt(Form1->Edit3->Text) > h->data)
        loeschen(h->right);
    if (StrToInt(Form1->Edit3->Text) == h->data) {
        if (h->left == 0 && h->right == 0) {   //Blatt
            delete(h);
            h = 0;
        } else if (h->left != 0 && h->right == 0) {    //Halbblatt  links
            // CKnoten *h1 = h;
            // h wird h->left;
            delete(h);   //delete(h1) if not works
            h = h->left;   //to delete if not works
        } else if (h->left == 0 && h->right != 0) {    //Halbblatt rechts
            // CKnoten *h1 = h;
            // h wird h->right;
            delete(h);   //delete(h1) if not works
            h = h->right;   //to delete if not works
        } else if (h->left != 0 && h->right != 0) {   //2 Kinder
            CKnoten *h1 = h;     //Hilfsknoten
            CKnoten *h2 = h->left;
            h = h->right;              //größerer Teil rückt nach oben
            delete(h1);
            h1 = h;
            while (h1->left != 0)
                h1 = h1->left;  //weiterwandern, immer links bis 0
            h1->left = h2;
        }
    }
}
</code>

===== Objektorientierung =====
Klassen funktionieren ähnlich wie Strukturen, bieten aber mehr Möglichkeiten.
Sie bestehen aus 2 Arten von Elementen:

  * Eigenschaften (Variablen)
  * Methoden (Funktionen)

==== Deklaration ====

Funktionen können innerhalb als auch außerhalb deklariert werden:
<code cpp>
class Punkt {
    double x, y;
    void Init(double x_, double y_) {
        x = x_;
        y = y_;
    }
    AnsiString toStr() {
        return "(" + FloatToStr(x) + "|" + FloatToStr(y) + ")";
    } // z.B. (2,35|3,46)
    void show() {
        Form1->Memo1->Lines->Add(toStr());
    }
};
</code>
Eine Deklaration von außen ist mit :: möglich:
<code cpp>
void C2DPunkt::Init(double x_, double y_) {
    x = x_;
    y = y_;
}
 
AnsiString C2DPunkt::toStr() {
    return "(" + FloatToStr(x) + "|" + FloatToStr(y) + ")";
} // z.B. (2,35|3,46)
 
void C2DPunkt::show() {
    Form1->Memo1->Lines->Add(toStr());
}
</code>

==== Datenkapselung ====
=== Drei verschiedene Zugriffsrechte ===

Mit den Zugriffsrechten **private, protected** und **public** kann man für jedes Klassenelement explizit festlegen, ob man über ein Objekt darauf zugreifen kann.

Diese //Spezifizierer// definieren ab ihrer Angabe einen Abschnitt mit Zugriffsrechten, die für alle folgenden Elemente bis zum nächsten solchen Spezifizierer oder bis zum Ende der Klasse gelten. Ein Element aus einem //private, protected// oder
//public// Abschnitt heißt auch //private, protected// oder //public// Element.

  * Ein **//public//** Element kann ohne Einschränkungen angesprochen werden, d.h. sowohl über ein Objekt als auch in einer Elementfunktion der Klasse.
  * Ein **//private//** Element kann nur in einer Element- oder friend-Funktion der Klasse angesprochen werden, aber nicht über ein Objekt.
  * Ein **//protected//** Element kann wie ein privates Element und außerdem noch in einer abgeleiteten Klasse angesprochen werden.

//Ohne die Angabe// eines Zugriffsrechts sind alle Elemente einer mit //class// definierten Klasse //private//, während alle Elemente einer mit //struct// definierten Klasse //public// sind. Dieses voreingestellte Zugriffsrechte ist der einzige Unterschied zwischen einer mit //class// und einer mit //struct// definierten Klasse.

Alle Elemente der Klassen C0 und C1 haben dieselben Zugriffsrechte:

<code cpp>
class C0 {
    int x;
    int f() { return x; }
};

struct C1 {
  private:
    int x;
    int f() { return x; }
};
</code>

Jeder Zugriff auf diese Elemente über ein Objekt führt zu einer Fehlermeldung:

<code cpp>
void test(C0 a, C1 b) {
    a.x=1;//Fehler: Zugriff auf 'C0::x' nicht möglich
    a.f();//Fehler: Zugriff auf 'C0::f()' nicht mögl.
    b.x=1;//Fehler: Zugriff auf 'C1::x' nicht möglich
    b.f();//Fehler: Zugriff auf 'C1::f()' nicht mögl.
}
</code>

Mit dem Zugriffsrecht //public// sind alle diese Zugriffe zulässig:

<code cpp>
class C0 {
  public:
    int x;
    int f() { return x; }
};

struct C1 {
    int x;
    int f() { return x; }
};
</code>

Eine Klasse kann eine **beliebige Anzahl von Abschnitten** mit verschiedenen Zugriffsrechten in einer **beliebigen Reihenfolge** enthalten. Die Reihenfolge der Abschnitte ist dabei ohne Bedeutung.

Die beiden Klassen C1 und C2 sind gleichwertig. Oft werden die verschiedenen Abschnitte wie bei C1 in der Reihenfolge //private, protected// und //public// aufgeführt. Wenn man sie aber wie bei C2 in der umgekehrten Reihenfolge anordnet, kommen die Elemente, die für das breiteste Publikum interessant sind, am Anfang:

<code cpp>
class C1 {
    int x; 
  public:
    int f(C p);
};

class C2 {
  public: 
    int f(C p);
  private:
    int x;
};
</code> 

=== Konstruktoren ===

Ein **Konstruktor** ist eine Methode der Klasse, die denselben Namen wie die Klasse hat. Der Konstruktor hat keinen Rückgabetyp. Eine Klasse kann mehrere Konstruktoren haben, welche sich //überladenen//, also durch ihre Parameter unterscheiden. Die Parameter können auch Default-Argumente haben.

Ein Konstruktor wird in den folgenden Situationen automatisch aufgerufen:

  * Wenn man ein Objekt durch eine Definition erzeugt. Dabei muss nach dem Namen des Objekts eine Liste von Argumenten angegeben werden, die zur Parameterliste des Konstruktors passt. Bei der Definition des Objekts wird dann der Konstruktor mit diesen Argumenten aufgerufen.

<code cpp>
class C2DPunkt {
    double x, y;
  public:
    C2DPunkt (double x_) { // ein Parameter: x-Wert
        x = x_;
        y = 0;
    }
    C2DPunkt (double x_, double y_) {
        x=x_;
        y=y_;
    }
};
</code>

Damit können folgendermaßen Objekte dieser Klasse definiert werden:
<code cpp>
C2DPunkt p(3); // p=(3,0)
C2DPunkt q(5,6); // q=(5,6)
</code>

Dagegen wird diese Definition vom Compiler nicht akzeptiert:
<code cpp>
C2DPunkt p; //Fehler: Keine Übereinstimmung für 'C2DPunkt::C2DPunkt()' gefunden
</code>
Die beiden Konstruktoren von C2DPunkt können auch durch einen
einzigen mit einem Default-Argument ersetzt werden:
<code cpp>
class C2DPunkt{
    double x,y;
  public:
    C2DPunkt(double x_, double y_ = 0) {
        x = x_;
        y = y_;
    }
};
</code>