Problem mit ADT Liste



  • Hallo,

    ih habe diesen Code im laufe des Nachmittags getippt, doch er funktioniert nicht. Einer der Fehlerpunkte, der mir auffiel ist, dass der Pointer des zuletzt eingefügten Objekts NIEMALS (auch mit NULL - Aufforderung) leer ist. In der Main Schleife hängt das Programm dementsprechend fest ( bei test->print(); ). ICh hoffe ihr findet den Wurm im Code. 😉

    #include <cstdlib>
    #include <cstddef>
    #include <iostream>
    
    using namespace std;
    
    template <typename Datatype>
    
    class List {
    public:
    
        struct Entry {
            Datatype content; //Content to save
            Entry *next; //Pointer to next entry
        };
    
        Entry Anf; //Create startentry
        Entry *Pos; //Create active position
    
        List() { //Konstructor for List
            //Anf = new Entry();  //Create startentry
            Anf.next = NULL; //Set next entry to NOT defined
            Pos = &Anf; //Set active position to the first entry
        }
    
        bool isEmpty() {
            if (Anf.next == NULL) { //Is the "first" entry empty?
                return true;
            } else {
                return false;
            }
        }
    
        void gotofirst() {
            Pos = &Anf; //Set active position to the start
        }
    
        void gotonext() {
            Pos = Pos->next; //Set active position to the next
        }
    
        void insert(Datatype content) {
            Entry newEntry; //Prepare new entry
            newEntry.content = content; //Insert content for new entry
            newEntry.next = NULL; //Pos->next; //Set next pointer of the new entry to the next entry of the active position
            Pos->next = &newEntry; //Insert the new entry now
        }
    
        bool isLast(){
            return (Pos->next == NULL);
        }    
    
        Datatype getcontent(){
            return Pos->next->content;
        }
    
        int getnext(){
            return (int) Pos->next->next;
        }
    
        void print() {
            cout << "Content of the list:" << endl;
            while(!isEmpty()) {
                cout << "Next entry:" << endl;
                cout << "Content: " << getcontent() << endl;
                cout << "Adress of next: " << getnext() << endl;
                gotonext();
            }
            cout << "End." << endl;
        }
    };
    
    int main(int argc, char** argv) {
    
        List<int> *test = new List<int>();
    
        cout << test->isEmpty() << endl;
        cout << test->isLast() << endl;
    
        test->insert(1);
        //test->insert(2);
        //test->insert(3);
        test->print();
    
        test->gotofirst();
        //test->gotonext();
    
        cout << (int) test->getcontent() << endl;
    
        return 0;
    }
    

  • Mod

    Beachte die Lebenszeiten deiner Objekte.



  • Bitte erkläre mir wo ich die Lebenszeit meiner Objekte falsch gesetzt habe, oder wo ich die Verbindungen gekappt habe, sodass ich Daten verliere. 😕


  • Mod

    Deine ganze Liste besteht nur aus Zombies. Sämtliche Einträge.

    Aber auch sonst ist die logische Struktur deiner Liste einfach falsch. Was soll beispielsweise das Anf sein?



  • Diese Liste soll die Implementation (wenn auch noch die Löschfunktion fehlt) einer ADT Liste sein. Anf stellt hierbei den Zeiger auf das erste Element dar. Pos soll der Zeiger auf das Element vor der eigentlichen Auswahl sein.
    Kern des Problems ist, dass der Zeiger des zuletzt hinzugefügten Elements auf Pos verweist (was die Endlosschleife erklärt) und nicht auf NULL o.ä (also das nächste Element).. Meine Frage ist wie ich dies behebe, und vorallem: Was sollen Zombies sein - die Objekte die fehlerhafterweise nicht gebunden werden (= verkettet)?

    Danke.



  • Wie lange lebt newEntry in insert? Was steht dann in der Liste?

    Anf ist kein Zeiger sondern ein Element.



  • @manni66

    Ja, Anf ist ein Element, aber nur, damit ich den Zeiger auf das nächste Element nutzen kann. Anf ist somit der Dummy, auf den pos zeigt, da Pos ja immer auf das Element in der Liste verweisen muss, vo dem ich eigentlich arbeiten möchte.
    newEntry dürfte zudem in insert nur ein Durchlauf als spezifisches Element existieren - danach sollte doch nur noch der Zeiger des vorherigen Elements (in dem Falle Anf) auf dieses Objekt zeigen - und newEntry neu genutzt werden können, oder?
    In der Liste wäre somit Anf mit dem Zeiger next auf das erste Element (ehem. newEntry) dieses verweist auf den Zeiger, den zuvor Anf hatte - NULL. Dies ist aber irgendwie nicht der Fall. Hier liegt das Problem (zeiger von ehem. newEntry).

    Simonmicro 😋



  • Dies alles basiert auf dem folgendem Code, welcher in Java geschrieben wurde:

    public class ADT_list {
    
        final private Eintrag anf;    // Der Anfang der Liste
        private Eintrag pos;
    
        /**
         * Konstruktor
         */
        public ADT_list() {
            anf = pos = new Eintrag();
            pos.next = null;
        }
    
        /**
         * Liste leer?
         */
        public boolean empty() {
            return anf.next == null;
        }
    
        /**
         * Listenende?
         */
        public boolean endpos() {
            return pos.next == null;
        }
    
        /**
         * Liste in den Anfangszustand versetzen
         */
        public void reset() {
            pos = anf;
        }
    
        public void advance() {
            if (endpos()) {
                throw new RuntimeException(); // Kontrollierter Abbruch
            }
            pos = pos.next;
        }
    
        /**
         * Liefert aktuelles Element
         */
        public Object elem() {
            if (endpos()) {
                throw new RuntimeException();
            }
            return pos.next.inhalt;
        }
    
        /**
         * Element vor aktuellem Element einfügen.
         */
        public void insert(Object x) {
            Eintrag NewEntry = new Eintrag(); //Generate new entry
            NewEntry.inhalt = x;
            NewEntry.next = pos.next;
            pos.next = NewEntry;
        }
    
        /**
         * Liste auf Standardausgabe
         */
        public void ausgeben() {
            int i = 0; //Only the "index"
            this.reset();
            while (this.endpos() == false) {
                this.advance();
                System.out.println(i + ": " + pos.toString()); //Print the data
                i++;
            }
        }
    
        /**
         * Aktuelles Element löschen
         */
        public void delete() {
            if (pos.next != null) {
                pos.next = pos.next.next; //Delete the pointer - gc will do the rest
            } else {
                pos.next = null;
            }
        }
    }
    
    class Eintrag {
    
        Object inhalt;
        Eintrag next;
        // Konstruktor nicht nötig, da Standardkonstruktor ausreicht
    }
    


  • Falls ich als Anfänger mal eine Interpretation versuchen darf:

    void insert(Datatype content) {
       Entry newEntry; //Variable newEntry wird erzeugt
       newEntry.content = content; //Werte werden zugewiesen
       newEntry.next = NULL; // in C++ wäre es eher nullptr
       Pos->next = &newEntry; //Adresse von newEntry wird zugewiesen
        } // newEntry wird zerstört und damit ist die Adresse ungültig
    

    Ich würde eher

    Entry* newEntry = new Entry;
    

    Es fehlt dann allerdings noch ein Destruktor für die korrekte "Entsorgung" der Objekte...

    Oder gleich smartpointer.



  • Simonmicro schrieb:

    newEntry dürfte zudem in insert nur ein Durchlauf als spezifisches Element existieren

    Ja

    Simonmicro schrieb:

    danach sollte doch nur noch der Zeiger des vorherigen Elements (in dem Falle Anf) auf dieses Objekt zeigen

    Da das Objekt jetzt nicht mehr existiert zeigt der Zeiger auf Müll.

    C++ ist nicht Java! Es können nicht nur einfache Datentypen wie int oder double auf dem Stack liegen sondern auch komplexe selbst definierte (wie in deinem Fall).



  • 😃 Was für ein Zufall!
    Ich wollte gerade meine korrigierte Version hochstellen - auch ich hatte den Fehler vorhin gefunden. Dennoch vielen Dank für alle eure Anstrengungen!

    EDIT: UND es war ein Fehler in der print Funktion: Dort wurde die Abfrage, ob die Liste leer ist, anstelle ob das letzte Element ausgewählt ist, verwendet 🙄 !

    /*
     * You're not allowed to make any changes to any of this files or share them as well.
     * For more information please contact me.
     * All rights reserved.
     */
    
    /* 
     * File:   main.cpp
     * Author: Simon Beginn
     *
     * Created on 21. Januar 2017, 13:59
     */
    
    #include <cstdlib>
    #include <cstddef>
    #include <iostream>
    
    using namespace std;
    
    template <typename Datatype>
    
    class List {
    public:
    
        struct Entry {
            Datatype content; //Content to save
            Entry *next; //Pointer to next entry
    
            Eintrag() {
                this->next = NULL;
            }
        };
    
        Entry Anf; //Create startentry
        Entry *Pos; //Create active position
    
        List() { //Konstructor for List
            //Anf = new Entry();  //Create startentry
            Pos = &Anf; //Set active position to the first entry
            Anf.next = NULL; //Set next entry to NOT defined
        }
    
        bool isEmpty() {
            if (Anf.next == NULL) { //Is the "first" entry empty?
                return true;
            } else {
                return false;
            }
        }
    
        void gotofirst() {
            Pos = &Anf; //Set active position to the start
        }
    
        void gotonext() {
            Pos = Pos->next; //Set active position to the next
        }
    
        void insert(Datatype x) {
            Entry *newEntry = new Entry(); //Prepare new entry
            newEntry->content = x; //Insert content for new entry
            newEntry->next = Pos->next; //Set next pointer of the new entry to the next entry of the active position
            Pos->next = newEntry; //Insert the new entry now
        }
    
        bool isLast(){
            return (Pos->next == NULL);
        }    
    
        Datatype getcontent(){
            return Pos->next->content;
        }
    
        int getnext(){
            return (int) Pos->next->next;
        }
    
        void print() {
            cout << "Content of the ADT list:" << endl;
            while(!isLast()) {
                cout << "EINTRAG: " << &Pos->next;
                cout << "       INHALT: " << Pos->next->content;
                cout << "       Weiter mit: " << Pos->next << endl;
                gotonext();
            }
            cout << "End." << endl;
        }
    };
    
    int main(int argc, char** argv) {
    
        List<int> *test = new List<int>();
    
        //cout << test->isEmpty() << endl;
        //cout << test->isLast() << endl;
    
        test->insert(1);
        test->insert(2);
        test->insert(3);
        test->print();
    
        test->gotofirst();
        //test->gotonext();
    
        //cout << (int) test->getcontent() << endl;
    
        return 0;
    }
    

Log in to reply