Verkettete Struktur



  • Darky1985 schrieb:

    irgendwie dachte ich, dass verkettete Listen dynamisch sind. Wollte ja mehrere Daten eingeben können aber das Funktioniert ja nicht.. NOCH nicht. Was müsst ich am Code denn ändern damit es Funktioniert?

    Definitionssache. Wenn du eine Liste willst, sollte die dynamisch sein. Ein Stack allerdings ist statisch, ansonsten ist es ein Heap. 😉

    Hmm. Was falsch ist, ist schwer zu sagen. Schau mal hier im Forum per Suche. Wir hatten hier Unmengen an Listen. 😉

    Ansonsten geh mal vorsichtig mit dem Debuger durch, dann findest du für gewöhnlich die Fehler.



  • Ja, natürlich hat der Stack einen dynamischen Inhalt, aber der Stack selber ist ja nur einmal vorhanden. Hrmmm, was ist denn mal ein gutes Beispiel... Also du hast einen Monitor, und den wechselst du ja auch nicht aus, nur weil er etwas anderes anzeigen soll. Und darum steht _der Monitor_ auf deinem Tisch, und nicht nur ne Addresse im Mediamarkt, wo ein Monitor mit dem Bildinhalt steht. Hehe



  • Tolles Beispiel 🙂 Aber wenn der Stack doch dynamisch ist.. wieso kann ich ihm nur einen Wert zuweisen? Den zweiten wert zeigt er ja total falsch an dann kommt irgendeine sehr hohe Zahl bei der Ausgabe.



  • drakon schrieb:

    Ein Stack allerdings ist statisch, ansonsten ist es ein Heap. 😉

    Ein Stack als Datenstruktur hat mit dem Heap als dynamischem Allokationspool aber herzlich wenig zu tun...



  • Darky1985 schrieb:

    wieso kann ich ihm nur einen Wert zuweisen? Den zweiten wert zeigt er ja total falsch an dann kommt irgendeine sehr hohe Zahl bei der Ausgabe.

    Also grundsätzlich solltest du dich ohnehin nochmal mit den C++ Grundlagen beschäftigen (Zeigerarithmetik eingeschlossen). Und was du schreibst ist kein Stack (Wenn hier auch die begriffe Stack und Heap imho nichts zu suchen haben), sondern eine einfach verkettete Liste (Ja, auch mit dieser lässt sich ein Stack realsieren).

    Nachfolgend eine Schrittweise Erklärung. Es ist weder eine Optimallösung, noch ist das Programm getestet. Versuch aber bitte das ganze auch zu verstehen, und konkrete Fragen zu stellen.

    //---------------------------------------------------------------------------
    #include <iostream> // <iostream.h> ist kein Ansi C++
    #pragma hdrstop     // Hinweis: Compilerspezifische Angabe
    //---------------------------------------------------------------------------
    #pragma argsused    // Hinweis: Compilerspezifische Angabe
    //...
    

    Seit dem C++ Standard von nun mehr 1998, sind alle Header der Standardbibliothek ohne .h am Ende. Ergänzend ist zu sagen, das alle C-Header die unter C++ verwendet werden, zudem mit dem Präfix c versehen wurden sind (z.B. ist der alte C-Header <stdio.h> nun <cstdio>, <math.h> nun <cmath>...).

    Alle Bestandteile der Standardbibliothek liegen zudem im Namensraum std. Daher ist vor allen Funktionen/Typen... der Standardbibliothek entweder ein std:: einzufügen (z.B. std::cout) oder man verwendet (ACHTUNG: NIEMALS IN HEADERN, und immer nach allen includes) "using namespace std;".

    Des weiteren:

    "typedef struct Stack_Struct" ist unter C++ völlig sinnfrei, da eine Struktur bereits eine Typdefinition ist. Zudem ist "Stack_Zeiger_Struct" auch Schwachsinn als Variable. Erstens ist der Name irreführent (Da kein Zeiger) und zweitens: Wozu EINE Variable des Typs, den du dynamisch verwenden willst.

    Zudem solltest du Interna niemals Preis geben. Auf einen Stack solltest du etwas einfügen und wieder runternehmen können, wie die interen Struktur aussieht sollte der Anwender des Stacks nicht wissen.

    Daher wäre es besser, die Schnittstelle des Stacks so zu definieren, das der Anwender keine Informationen zum internen Aufbau haben muss, und die interne Datenstruktur auch in der Klasse private zu deklarieren, nicht außerhalb.

    Zudem würde ich unter C++ immer die Möglichkeiten verwenden, Daten über einen Konstruktor zu initialisieren. Dein "next"-Zeiger sollte immer auf 0 initialisiert werden (um Anzuzeigen, das noch kein "next" existiert). Ich sehe hier mal beides als Parameterübergabe vor, und komme später auf die Gründe zu Sprechen...

    //---------------------------------------------------------------------------
    //...
    class Stack
    {
        private:
            struct StackDatensatz{
                int wert;
                StackDatensatz *next;
    
                StackDatensatz(
                    int wert,
                    StackDatensatz* next)
                :   wert(wert), // Initialisierungsliste ist der Zuweisung vorzuziehen
                    next(next)
                {
                }
            };
    //...
    

    Deine Schnittstelle sollte, wie für einen Stack üblich, mindestens eine Funktion zum hinzufügen, und eine zum entfernen bereitstellen. In der Regel mit Push und Pop bezeichnet.

    Aus Gründen der Exceptionsicherheit, auf die ich hier aber nicht weiter eingehen will, wird in C++ in der Regel mit 3 Funktionen gearbeitet:
    a) Push zum Hinzufügen
    b) Pop zum Entfernen (ohne Rückgabe)
    c) Einer Get-Methode zum Auslesen des obersten Elementes

    Passen wir mal die Schnittstelle an (ich werde hier wie von dir bevorzugt versuchen im deutschen zu bleiben):

    // Die Klassendeklaration sollte im Header, nicht der cpp-Datei stehen...
    class Stack
    {
        private:
            struct StackDatensatz //... Siehe oben
            // Oberstes Element im Stack, NULL wenn nicht gesetzt
            StackDatensatz * stackElement;
    
        public:
            Stack(); // (void) ist unter C++ eigentlich unüblich
            ~Stack();
    
            // Bitte auch in der Deklaration immer die Parameter benennen, normalerweise
            // schaut man in den Header um die Schnittstelle zu verstehen, nicht in
            // die Implementierung
            // Hinzufuegen eines Elementes, auf den Stack
            void Hinzufuegen(int wert);
            // Auslesen des obersten Elementes vom Stack
            int Auslesen();
            // Entfernen des obersten Elementes von dem Stack
            void Entfernen();
    };
    //...
    

    Soweit so gut. Wo du schon einmal richtig liegst, ist die initialisierung des ersten Elementes. Aber dein Destruktor räumt nichts auf. Wenn ein Element vorhanden ist, so muss dies am Schluß bei der dynamischen Allozierung (new) auch entfernt werden (delete).

    Unter der Annahme das unsere "Entfernen" Methode immer das zuletzt hinzugefügte Element entfernt, und unser "stackElement" anschließend auf das nächste zeigt (ggf. auf NULL sofern kein anderes existiert), werden wir das erstmal simpel lösen:

    //...
    Stack::Stack()
    :   stackElement(NULL)
    {
    }
    
    Stack::~Stack()
    {
        // Solange Elemente existieren, diese Löschen...
        while(stackElement != NULL)
            Entfernen();
    }
    //...
    

    Soweit ist es nun auch noch recht einfach, nun wird es problematischer...
    Beginnen wir zunächst mit dem Zurückliefern des zu oberst liegenden Elementes.
    Hier gibt es nur ein Problem: Was machen, wenn kein Element auf dem Stack liegt?

    Üblicherweise wirft man hier in C++ eine exception...

    //...
    int Stack::Auslesen()
    {
        // Wenn ein Element vorhanden ist, den Wert des selben zurückliefern
        if(stackElement != NULL)
            return stackElement->wert;
    
        // Wie soll auf einen Fehler reagiert werden? Normalerweise: Exception
        throw("Leerer Stack" /* Ersetzen, durch den von dir vorgesehenen
               Exceptiontyp */);
    }
    

    So... nun kommt die Zeigerarithmetik ins Spiel... Am besten sollte man als Anfänger dazu sich mal ein einfaches Diagramm oder eine einfache Beschreibung in Pseudocode durchspielen.

    Gehen wir mal das Hinzufügen an:

    //...
    void Hinzufuegen(int wert)
    {
        // stackElement soll immer auf das zuletzt angelegte Element zeigen.
        // Da du aber eine dynamisch wachsende Liste verwaltest, musst du dir
        // das Vorelement aber merken. Dazu rufe lege ich mal ein Element wie
        // folgt an:
        StackDatensatz * element = new StackDatensatz(wert, stackElement);
    
        // Wir legen ein neues Element an, übergeben diesen den zu speichernen
        // wert, sowie das Bisherige stackElement als next (Falls noch leer, ist
        // dies NULL.
    
        // Anschließend ersetzen wir das bisherige oberste Element...
        stackElement = element;
        // Nun zeigt stackElement auf das neue Element, und stackElement->next
        // auf das nachfolgende. NULL wenn kein weiteres Existiert...
    }
    //...
    

    Bitte nimm dir mal Zeit es bis hierhin zu verstehen. Spiele es mal auf einen Blatt für das hinzufügen ein paar Elemente durch. Wenn du damit fertig bist, geht man zum nächsten Schritt: dem Entfernen über.

    //...
    void Entfernen()
    {
        // Falls stackElement NULL ist, tun wir hier garnichts, oder werfen
        // alternativ eine Exception.
        if(!stackElement)
            return;
    
        // stackElement soll gelöscht, und durch seinen Nachfolger ersetzt werden
        // (stackElement->next). Dazu müssen wir uns aber den Nachfolger merken...
        StackDatensatz * nachfolger = stackElement->next;
        delete stackElement;
        stackElement = nachfolger;
        // Falls der Nachfolger NULL war, ist der Stack nun leer
        // (stackElement == NULL)
    }
    //...
    

    Ich würde dem ganzen noch mindestens eine Methode mitgeben um zu prüfen ob noch Elemente vorhanden sind, bzw. ob der Stack leer ist...

    //...
    bool IstLeer()
    {
        return stackElement == NULL;
    }
    //...
    

    cu André



  • Da hat sich aber jemand Zeit genommen 🙂 👍



  • Decimad schrieb:

    Da hat sich aber jemand Zeit genommen 🙂 👍

    Ich hoffe nur, das es etwas bringt. In einigen Fällen hätte ich lange Beschreibungen echt sparen können (Es bringt nur dann etwas wenn diese auch gelesen und verstanden werden).



  • uff danke schonmal ich gehe das gleich mal durch.Wegen dem .h und dem typedef und dem fehlenden namespace std; das wird uns gerade im Studium so gezeigt. Wurde also schon negativ vorgeprägt..



  • Darky1985 schrieb:

    Wegen dem .h und dem typedef und dem fehlenden namespace std; das wird uns gerade im Studium so gezeigt. Wurde also schon negativ vorgeprägt..

    Ich weiß, es kommt nicht gut an, aber gibt es mal einen Studenten mit Zivilcourage der die Dozenten darauf hinweist, das sie kein C++ lehren (z.B. .h in Zusammenhang mit den namespace std ist seit 10 [in Worten zehn!!!] Jahren ungültig)? Oder C++ lehren, das eher den Namen C verdient hat (z.B. typedef bei Strukturen)?

    Ich bin auch gerne bereit - Zeit voraus gesetzt - irgendwelche Manuskripte quer zu lesen (vorausgesetzt ein Dozent/Lehrer ist wiederum bereit, diese weiterzugeben, und sich mit den gemachten Anmerkungen zu beschäftigen). Sofern die Email-Funktion nicht abgeschaltet sein sollte: Hinterlegt ist eine.

    cu André


  • Administrator

    asc schrieb:

    Ich weiß, es kommt nicht gut an, aber gibt es mal einen Studenten mit Zivilcourage der die Dozenten darauf hinweist, das sie kein C++ lehren (z.B. .h in Zusammenhang mit den namespace std ist seit 10 [in Worten zehn!!!] Jahren ungültig)? Oder C++ lehren, das eher den Namen C verdient hat (z.B. typedef bei Strukturen)?

    Versucht, vergeblich 🙂
    Bei mir kamen Antworten wie:
    "Es doch eigentlich nur ums Prinzip, damit man schon mal was von Zeigern gehört hat."
    "Es soll nicht die Sprache vermittelt werden, sondern nur ein Eindruck gegeben werden."
    "Wer C oder C++ lernen will, kann das richtig in seiner Freizeit tun."
    usw. usf.

    Zudem hat man meinen Antrag bisher abgewiesen, dass wir einen Kurs oder eine Vorlesung zu C++ anbieten. Allerdings sind wir auch nur ein wirklich kleines Departement. Da muss ich den Professoren zustimmen.

    Grüssli



  • Ich bin der Meinung, dass es schon eine gewisse Schwierigkeit darstellt, eine bestimmte Programmiersprache vernünftig zu beherrschen. Alle, die das aus dem Ärmel schütteln, sind bestimmt in der Wirtschaft besser aufgehoben, als für 7€ die Stunde als Hiwi Übungsaufgaben auszuarbeiten.



  • So nachdem der Weihnachtsstress vorbei ist, konnte ich mich nun hiermit weiter beschäftigen.

    Also ich hänge nun bei der Methode Hinzufügen und wollte mal nachfragen, ob das soweit richtig ist.

    #include <iostream>
    using namespace std;
    
    class Stack{
    
    private:
            struct Stackstruct{
                    int wert;
                    Stackstruct *next;
                    };
            Stackstruct *stackElement;
    public:
            Stack();
            ~Stack();
            int Auslesen();
            void Entfernen();
            void Hinzufuegen(int var);
    };
    
    int main()
    {
    
         return 0;
    }
    
    // Methoden
    Stack::Stack()
    {
            stackElement = NULL;
    }
    
    Stack::~Stack()
    {
            while(stackElement!=0)
            {
                    Entfernen();
            }
    };
    
    int Stack::Auslesen()
    {
            if(stackElement!=0)
            {
                    return stackElement->wert;
            }
            else{
                    throw"Stack ist leer";
            }
    }
    
    void Stack::Entfernen()
    {
    }
    
    void Stack::Hinzufuegen(int var)
    {
    
            if(stackElement==0)
            {
            Stackstruct * newElement = new Stackstruct;
            stackElement->wert = var;
            stackElement->next = NULL;
            }
            else
            {
            Stackstruct *newElement = new Stackstruct;
            stackElement = newElement;
            stackElement->wert = var;
            stackElement = stackElement->next;
            }
    }
    


  • Darky1985 schrieb:

    Also ich hänge nun bei der Methode Hinzufügen und wollte mal nachfragen, ob das soweit richtig ist.

    Kurz gesagt: Nein.
    Wenn du schon die vorgeschlagene Variante mit den Konstruktoren ignorierst, musst du auch aufpassen was du mit den alten Werten machst (Zudem muss Entfernen auch die Elemente löschen).

    void Stack::Hinzufuegen(int var)
    {
        if(stackElement==0)
        {
            // Hier musst du stackElement anlegen, und setzen
        }
        else
        {
            // Hier musst du stackElement "merken", und ein neues Element
            // anlegen. Dieses bekommt das bisherige stackElement als Next.
            // anschließend muss das neue Element stackElement ersetzen.
        }
    }
    

    cu André
    P.S: Wie wäre es wenn du meinen alten Text wirklich einmal durchliest und versuchst zu verstehen, bevor du schlecht übernimmst und noch schlechter implementierst?



  • Anscheind muss ich mir das nochmal genauer durchlesen, da ich nicht weiß was du gerade meinst. Hab doch alles übernommen bis auf

    StackDatensatz(
                    int wert,
                    StackDatensatz* next)
                :   wert(wert), // Initialisierungsliste ist der Zuweisung vorzuziehen
                    next(next)
                {
                }
    

    oder ist dies hier auch gemeint?

    Was macht dein Konstruktor eigendlich anders als meiner? Habe diese Deklaration noch nicht gesehen.



  • Darky1985 schrieb:

    Anscheind muss ich mir das nochmal genauer durchlesen, da ich nicht weiß was du gerade meinst. Hab doch alles übernommen bis auf

    Du hast beileibe nicht alles übernommen, geschweige den gelesen.
    Noch dazu eine weitere Bitte: Rück deinen Code sinnvoll ein, der ist so recht schwierig zu überschauen.

    Darky1985 schrieb:

    Was macht dein Konstruktor eigendlich anders als meiner? Habe diese Deklaration noch nicht gesehen.

    Zum einen hast du gar keinen Konstruktor, außer vielleicht den vom Compiler generierten, zum anderen habe ich dies alles in meinem Text beschrieben. Du hast diesen Text meiner Meinung aber noch nicht einmal gelesen, geschweige den versucht ihn zu verstehen (Den dann würden deine Fragen mit Sicherheit konkreter sein).

    Leg dir bitte ein sinnvolles C++ Buch zu (z.B. C++ Primer), und halte dich an die Lernreihenfolge, wenn du schon wirklich ausführliche Beschreibungen nicht einmal ansatzweise liest.

    cu André



  • Stack::Stack()
    {
            stackElement = NULL;
    }
    

    Das ist doch der Konstruktor und Stack::~Stack der Destruktor..
    Deinen Text habe ich schon mehrmals gelesen aber so wie es aussieht ohne Erfolg. Nunja..



  • hmm... wahrscheinlich hat asc den übersehen oder sich komisch ausgedrückt - ich jedenfalls sehe deinen CTor ^^

    btw nennt sich

    Stack::Stack() 
    :   stackElement(NULL) //<--- das hier
    { 
    }
    

    Initialisierungsliste... und man sollte sie auch nutzen ^^

    bb



  • unskilled schrieb:

    hmm... wahrscheinlich hat asc den übersehen oder sich komisch ausgedrückt - ich jedenfalls sehe deinen CTor ^^

    Aber nicht den von StackDatensatz...



  • asc schrieb:

    unskilled schrieb:

    hmm... wahrscheinlich hat asc den übersehen oder sich komisch ausgedrückt - ich jedenfalls sehe deinen CTor ^^

    Aber nicht den von StackDatensatz...

    OK - den hab ich natürlich auch noch nicht entdecken können ^^

    bb



  • Ich hab mal meinen Stringstack ausgegraben:

    /*
      Die Implementierung eines String-Stack nach dem LIFO-Prinzip.
    */
    
    #include <iostream>
    #include <string>
    using namespace std;
    
    class StringStack {
      private:
        struct Element {
          string s;
          Element *vorgaenger;
        };
        Element *aktuelles;
        int zaehler;
    
      public:
        StringStack();
        ~StringStack();
        bool leer();
        void push(string s);
        string pop();
    };
    
    StringStack::StringStack() {
      aktuelles = NULL;
      zaehler = 0;
    }
    
    StringStack::~StringStack() {
      Element *temp = NULL;
      while(aktuelles != NULL) {
        temp = aktuelles;
        aktuelles = aktuelles->vorgaenger;
        delete temp;
      }
      temp = NULL;
    }
    
    bool StringStack::leer() {
      return zaehler == 0;
    }
    
    void StringStack::push(string s) {
      Element *neues = new Element;
      neues->s = s;
      neues->vorgaenger = NULL;
      if(aktuelles != NULL) {
        neues->vorgaenger = aktuelles;
      }
      aktuelles = neues;
      ++zaehler;
    }
    
    string StringStack::pop() {
      if(zaehler > 1) {
        string temp = aktuelles->s;
        aktuelles = aktuelles->vorgaenger;
        --zaehler;
        return temp;
      }
      else if(zaehler == 1) {
        string temp = aktuelles->s;
        aktuelles = NULL;
        --zaehler;
        return temp;
      }
      else {
        return "Fehler: pop() bei leerem Stack.";
      }
    }
    
    int main() {
      StringStack *stack = new StringStack();
      stack->push("Test");
      stack->push("C");
      stack->push("C++");
      while(!stack->leer()) {
        cout << stack->pop() << endl;
      }
      delete stack;
      stack = NULL;
      return 0;
    }
    

    Falls Fragen auftreten, einfach stellen 😉


Anmelden zum Antworten