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


Log in to reply