Verkettete Struktur



  • Hallo

    Ich versuche gerade eine kleine verkettete Struktur zu basteln aber irgendwie komme ich nun nicht weiter, da jetzt schon Fehler auftreten.

    //---------------------------------------------------------------------------
    #include <iostream.h>
    #pragma hdrstop
    
    //---------------------------------------------------------------------------
    
    #pragma argsused
    
    typedef struct Stack_Struct{
    int wert;
    Stack_Struct *next;
    }Stack_Zeiger_Struct;
    
    class Stack
    {
    private:Stack_Zeiger_Struct * Stacks;
    public:
            Stack(void){Stacks = NULL;};
            ~Stack();
            Stack_Struct * Einfuegen(int);
            void Ausgeben(Stack_Zeiger_Struct *n);
    
    };
    
    int main(int argc, char* argv[])
    {
    
            Stack_Struct * node;
            Stack *Zeiger;
    
            int ivar,auswahl;
    
            do{
            cout<<" Verkettete Structur\n";
            cout<<"-1- Neuen Stack hinzufuegen\n";
            cout<<"-2- Alle Elemente Ausgeben\n";
            cout<<"-3- Programm beenden\n";
            cin>>auswahl;
            switch(auswahl)
            {
            case 1:
                    cout<<"Daten eingeben:";
                    cin>>ivar;
                    //node = Zeiger->Einfuegen(ivar);
                    break;
            case 2:
                    Zeiger->Ausgeben(node);
                    break;
            case 3:
                    break;
            }
            }while(auswahl !=3);
            return 0;
    }
    //---------------------------------------------------------------------------
    
    // Methoden
    Stack::~Stack(){
    
    }
    
    Stack_Struct* Stack::Einfuegen(int var){
    
    if(Stacks == NULL)
    {
       Stack_Struct * node = new Stack_Struct;
       node->wert = var;
       node->next =0;
       Stacks= node;
       return Stacks;
      }
    }
    
    void Stack::Ausgeben(Stack_Zeiger_Struct *n){
      if(Stacks == NULL){
      cout<<"Stack ist Leer\n";
      }
      else{
      cout<<"1.Stack: "<<n->wert;
      for(int i=2;n->next!= 0;i++){
      n=n->next;
      cout<<i<<" . Element: "<<n->wert<<'\n';
        }
      }
    }
    

    liegt das am noch nicht vorhandenen delete?

    PS: <--- Anfänger 😉

    Schonmal danke für die Antworten



  • Darky1985 schrieb:

    Ich versuche gerade eine kleine verkettete Struktur zu basteln aber irgendwie komme ich nun nicht weiter, da jetzt schon Fehler auftreten.

    Irgendwelche Fehler? Oder wenigstens immer die gleichen?



  • Es kommt immer eine Zugriffsverletzung auf eine Adresse.



  • Darky1985 schrieb:

    Es kommt immer eine Zugriffsverletzung auf eine Adresse.

    Stack *Zeiger; <- Erstellst du auch irgendwo ein Objekt dafür? 🙂



  • Muss ich das? o_0
    Hatte mir den Zeiger gemacht um auf die Funktion zuzugreifen.

    node = Zeiger->Einfuegen(ivar);
    

    Im Quelltext oben steht übrigens :

    // node = Zeiger->Einfuegen(ivar);
    

    da müssen noch die " // " weg ^^



  • Ja! Der Zeiger ist doch nur ein Zeiger, da steht eine Addresse drin... Wenn du kein Objekt erstellst und ihn auf das zeigen lässt, dann zeigt der im besten Fall nur auf Grütze und ansonsten auf Spinat.
    Du könntest den Stack aber auch gleich auf dem Stack (hehe) erstellen, aka:

    Stack stack;



  • Stack stack;
    stack * Zeiger;

    Da meckert er nun das Zeiger undefiniert ist und die Fehlermeldung krieg ich nicht weg mh



  • Nun funktiert alles. Habe den *zeiger weggenommen und mit stack getauscht.Zwar gehts halt nun nicht mehr mit dem Pfeiloperator aber es funktioniert ^^.
    Wie krieg ich es denn dennoch mit dem *Zeiger hin??
    Und wenn ich 2 Zahlen Eingebe also zuerst 1. dann Enter und danach wieder eine Zahl dann gibt der irgendein kram aus aber nicht die beiden Zahlen 😞



  • Warum willst du denn alles mit Zeigern machen? Zeiger sind für dynamische Sachen gedacht (unbekannte Anzahl von Elementen, unbekanntes Element aus einer festen Anzahl, abstrakte Basisklassen mit unbekannten Ableitungen usw.) und nicht dafür, alles auf einmal mit Zeigern zu machen. Am besten ist es, wenn man sie vermeidet, wo man sie nicht braucht. Da du genau einen einzigen Stack hast (was ich deinem Code ansehe), bist du also gut ohne Zeiger bedient.
    Warum er gerade abstürzt, kann ich dir nicht sagen, ich sehe den aktuellen Code nicht. Ich würde dir aber raten, in der Stack-Klasse einen Zeiger auf den Anfang und einen auf das Ende der verketteten Liste zu verwalten und das gesamte Handling somit in der Klasse zu kapseln, wofür diese ja eigentlich gedacht sind.

    Wenn du wirklich mit Zeigern arbeiten willst:

    Stack* Zeiger = new Stack();
    
    .... // etwas mit Zeiger anstellen
    
    delete Zeiger;
    


  • 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?



  • 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


Anmelden zum Antworten