kramann.info
© Guido Kramann

Login: Passwort:










Informatik3
1 Vom_struct_zur_Klasse
..1.1 Vom_struct_zur_Klasse
..1.2 struct_Programm
..1.3 Klassen_Programm
..1.4 Offene_Fragen
..1.5 Historie
..1.6 Objektabstraktion
..1.7 OO_Kundenverwaltung
..1.8 Objektfaehigkeiten
..1.9 Formatierung
..1.10 Motivation
..1.11 Uebung1
..1.12 Uebung2
2 UML
..2.1 Volumenberechnung
..2.2 UML_Klassendiagramm
..2.3 Konstruktor
..2.4 Statische_Variable
3 Strings
..3.1 Klassenbibliotheken
..3.2 stringUML
..3.3 Uebung3
4 Initialisierungen
4 bluej
5 Zeiger_und_Arrays
..5.1 Zeiger
..5.2 Zeiger_und_Funktion
..5.3 Uebung4
6 Vererbung
..6.1 MesswerteUML
..6.2 MesswerteProgramm
..6.3 VererbungsProgramm
..6.4 Vector
..6.5 Uebung
7 Modifikatoren
..7.1 public_Vererbung
..7.2 protected_Vererbung
8 Listen_und_Templates
..8.1 Containertypen
....8.1.1 ListeUML
....8.1.2 ListeProgramm
..8.2 Templates
....8.2.1 Listentemplate
....8.2.2 STLvectorTemplate
..8.3 Uebung5
..8.4 Uebung6
..8.5 Uebung7
9 Java
..9.1 Uebung
..9.2 GettingStarted
..9.3 Animation
..9.4 Hybrid
..9.5 Threads
10 Delegation
11 LayoutProjekt
12 Fenster
13 Uebung
14 Zwischenprojekt
..14.1 Befehle
..14.2 Planung
..14.3 JNI
..14.4 JNIumsetzen
..14.5 Anwendungsklasse
..14.6 GUI01
..14.7 GUI02
15 Rasterlayout
..15.1 Bilder_Packages
..15.2 interfaces
..15.3 ArrayList
..15.4 clone
..15.5 Uebung
16 Nuetzliches
..16.1 Threads
..16.2 Animation
..16.3 RungeKutta
..16.4 Loesungsansatz
..16.5 Internetprogrammierung
....16.5.1 Codegenerierung
....16.5.2 PHP_Programmierung
....16.5.3 PHP_OOP
....16.5.4 Java
17 Algorithmen
..17.1 RungeKutta
..17.2 Loesungsansatz
..17.3 Evoopt
..17.4 Uebung12
..17.5 Uebung8_2014
..17.6 Ausdruecke
18 Uebung10
19 UML_ALT
..19.1 Flaechenberechnung
..19.2 UML_Flaechenberechnung
..19.3 Implementierung
..19.4 ListeUML
..19.5 ListenImplementierung
..19.6 Anwendung

19.5 Implementierung der Klassen Liste und ListenContainer in C++

Schauen wir uns nun die Implementierungen der Klassen ContainerListe und Liste an. Dazu vorab:

Hinweis: Bei der nachfolgenden Implementation entspricht die Klasse "Liste" einem Listenelement und "ListenContainer" der eigentlichen Liste.

Ein Problem, das beim linearen Durchsuchen einer Liste auftaucht, ist es herauszufinden, ob ein Element das letzte Element ist.

Eine mögliche Lösung ist, das aktuelle Element darauf hin zu prüfen, ob es seinerseits einen Nachfolger besitzt. Indem man nachfolger-Zeiger, die auf kein Objekt verweisen zu Null-Pointern macht, sie also auf 0 setzt, kann dieser Zustand klar definiert werden.

Achtung: der Mechanismus NULL aus C funktioniert in C++ nicht richtig, deshalb immer 0 und nicht NULL verwenden.

Angenommen die Referenz auf das erste Element, also das kopfelement selbst, zeigt auf 0. Dann kann man nicht damit beginnen nach Nachfolgern zu suchen. Um eine einheitliche Behandlung in den Algorithmen zu gewährleisten, bleibt deshalb das erste Element leer, d.h. es enthält keine Daten und zählt auch nicht zur eigentlichen Liste dazu.

using namespace std;

class Liste
{
    public: 
        Liste()
        {
            nachfolger = 0;
        }
        Liste(string indaten)
        {
            daten = indaten;
            nachfolger = 0;
        }
        Liste *nachfolger;
        string daten;
};
 

Code 19.5-2: Liste.h

using namespace std;

class ListenContainer
{
    private:
        Liste kopfelement;
    public:
        ListenContainer()
        {
            //Zunächst leere Liste erzeugen:
            kopfelement.nachfolger = 0;
        }

        //Übergebenes String in neues Listen-Element packen und dieses an das Ende der Liste hängen
        void append(string text)
        {
            Liste* element = new Liste(text);
            Liste* zeiger = &kopfelement;

            while(zeiger->nachfolger!=0)
                zeiger = zeiger->nachfolger;

            zeiger->nachfolger = element;
        }  

        //Refrerenz auf das i-te Listenelement suchen und dessen String-Inhalt zurückgeben
        string get(int index)
        {
            Liste* zeiger = kopfelement.nachfolger;

            for(int i=0;i<index;i++)
            {
                if(zeiger == 0)
                    return 0;
                zeiger = zeiger->nachfolger;
            }                    

            return zeiger->daten;      
        }

        //i-tes Listenelement löschen
        void del(int index)
        {
            //Hier muss der Zeiger auf das vorangehende und das nachfolgende Element
            //efunden werden.
            Liste* zeiger     = kopfelement.nachfolger;
            Liste* zeigervor  = &kopfelement;
            Liste* zeigernach = 0;            

            for(int i=0;i<index;i++)
            {
                if(zeiger == 0)
                    return;
                zeigervor = zeiger;
                zeiger = zeiger->nachfolger;
            }                    
            zeigernach = zeiger->nachfolger;
            
            //Vorgänger-Element mit Nachfolger-Element verbinden:
            zeigervor->nachfolger = zeigernach;

            //Speicher für aktuelles Element freigeben:
            delete zeiger;
        }

        //die ganze Liste löschen.
        void clear()
        {                 
            Liste* zeiger;
            Liste* zeigervor  = &kopfelement;

            //Speicher bereinigen:
            while(kopfelement.nachfolger != 0)
            {
                zeiger    = kopfelement.nachfolger;
                zeigervor = &kopfelement;                
                while(zeiger->nachfolger != 0)
                {
                    zeigervor = zeiger;
                    zeiger = zeiger->nachfolger;
                }
                zeigervor->nachfolger=0;
                delete zeiger;
            }
        }

        //Liefert die Länge der Liste zurück
        int getSize()
        {
            int laenge = 0;
            Liste* zeiger = &kopfelement;
            
            while(zeiger->nachfolger!=0)
            {
                laenge++;
                zeiger = zeiger->nachfolger;
            }

            return laenge;
        }
 };
 

Code 19.5-3: ListenContainer.h