Listen sind Strukturen, die einen Wert speichern und auf ihrem Nachfolger verweisen.

struct CWaggon {
    AnsiString data;      // die Nutzdaten
    CWaggon *next;        // Zeiger auf den nächsten Knoten
};

Ein solcher Datentyp wird auch als rekursiver Datentyp bezeichnet.

Im Programm muss nur ein Zeiger gespeichert werden, der auf den ersten Knoten der Liste verweist:

CWaggon *first; // Zeiger auf den ersten Knoten

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:

Einhängen eines neuen Knotens

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

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

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

CWaggon *tmp = new CWaggon; // 1.1

und dem die Daten durch eine Anweisung wie

tmp->data = d2; // 1.2

zugewiesen werden. Dadurch ergibt sich:

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

tmp->next = n0; // 2.1
n0 = tmp;       // 2.2

in die Liste eingehängt:

Diese Anweisungen werden mit der Funktion

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}

durch den Aufruf

 n0 = newWaggon(d2,n0);                   // 2.1

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

 first = newWaggon(di,first);

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

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

                                   // 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}

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:

CWaggon *tmp=start;
while (tmp != 0) {
    Form1->Memo1->Lines->Add(tmp->data);
    tmp = tmp->next;
}

dopplete Verkettung

Dabei wird nicht nur auf das folgende, sonder auch auf das vorherige Element verwiesen.

struct CWaggon {
    AnsiString data;
    CWaggon *next;
    CWaggon *previous;
};
 
CWaggon *first=0, *last=0;

Einhängen

vorne

hinten

Bäume

Einhängen eines neuen Knotens

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();
}

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.

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;
        }
    }
}

Objektorientierung

Deklaration

Funktionen können innerhalb als auch außerhalb deklariert werden:

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());
    }
};

Eine Deklaration von außen ist mit :: möglich:

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());
}

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:

class C0 {
    int x;
    int f() { return x; }
};
 
struct C1 {
  private:
    int x;
    int f() { return x; }
};

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

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.
}

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

class C0 {
  public:
    int x;
    int f() { return x; }
};
 
struct C1 {
    int x;
    int f() { return x; }
};

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:

class C1 {
    int x; 
  public:
    int f(C p);
};
 
class C2 {
  public: 
    int f(C p);
  private:
    int x;
};

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.

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_;
    }
};

Damit können folgendermaßen Objekte dieser Klasse definiert werden:

C2DPunkt p(3); // p=(3,0)
C2DPunkt q(5,6); // q=(5,6)

Dagegen wird diese Definition vom Compiler nicht akzeptiert:

C2DPunkt p; //Fehler: Keine Übereinstimmung für 'C2DPunkt::C2DPunkt()' gefunden

Die beiden Konstruktoren von C2DPunkt können auch durch einen einzigen mit einem Default-Argument ersetzt werden:

class C2DPunkt{
    double x,y;
  public:
    C2DPunkt(double x_, double y_ = 0) {
        x = x_;
        y = y_;
    }
};

Programmierung

Strukturen

Definition

Typdefinition

anonyme Variablendefinition

Verschachtelung von Strukturen

Zugriffe

Zeiger

Definition

Dereferenzierung

von Strukturen und Klassen

Referenzierung

Beispiel

generische Zeiger

dynamische Erzeugung

und Löschung

Listen

Einhängen eines neuen Knotens

Durchlaufen

dopplete Verkettung

Einhängen

vorne

hinten

Bäume

Einhängen eines neuen Knotens

Löschen eines Knotens

Objektorientierung

Deklaration

Datenkapselung

Drei verschiedene Zugriffsrechte

Konstruktoren