Pointer "auslagern" bei verketteten Listen



  • Hallo,
    zuerst entschuldige ich mich für den schlecht getroffenen Titel. Mir ist einfach nichts besseres eingefallen..

    Nun zu meinem Problem:
    Ich mache momentan eine Ausbildung (FI-AE) und habe vor kurzem die Aufgabe bekommen, verschiedene Listen zu programmieren (zuerst in C und nun objektorientiert). Das ist soweit auch kein Problem. Jetzt soll ich jedoch den "next-Pointer" aus meiner Klasse "ListNode" in die jeweiligen Klassen der Listen versetzen. Ist das möglich?

    Header (stark gekürzt um es übersichtlich zu halten):

    class ListNode
    {
    public:
        ListNode();
        ~ListNode();
        void setFirstname(string);
        void setLastname(string);
        void setNext(ListNode*);
        void setPrev(ListNode*);
        string getFirstname(void) const;
        string getLastname(void) const;
        ListNode* getNext(void) const;
        ListNode* getPrev() const;
    
    private:
        ListNode *next;    //Dieser Pointer soll in die jeweiligen Klassen der
                           //Listen und da verwaltet werden
        ListNode *prev;    //Und der hier auch
        string firstname;
        string lastname;
    };
    
    class Stack
    {
    public:
        Stack();
        ~Stack();
        void push(ListNode*);
        void pop(void);
        ListNode* top(void) const;
        bool isEmpty(void) const;
        void clear(void);
    
    private:
        ListNode *firstElement;
        ListNode *lastElement;
    };
    
    class doubleLinkedList
    {
    public:
        doubleLinkedList();
        ~doubleLinkedList();
        void add(ListNode*);
        void clear(void);
        void inserAfter(ListNode*, ListNode*);
        bool isEmpty(void) const;
        void remove(ListNode*);
    
    private:
        ListNode *topElement;
        ListNode *lastElement;
    };
    

    Stack.cpp:

    Stack::Stack()
    {
        firstElement = NULL;
        lastElement = NULL;
    }
    
    Stack::~Stack()
    {
        firstElement = NULL;
        lastElement = NULL;
    }
    
    void Stack::push(ListNode *node)
    {
        if(node == NULL)
            return;
    
        if(isEmpty())
            firstElement = node;
    
        else
            lastElement->setNext(node);
    
        lastElement = node;
    }
    
    ListNode* Stack::top(void) const
    {
        return lastElement;
    }
    
    bool Stack::isEmpty(void) const
    {
        if(firstElement == NULL)
            return true;
    
        return false;
    }
    
    void Stack::pop(void)
    {
        ListNode* tmpNode = new ListNode();
        tmpNode = firstElement;
    
        while(tmpNode->getNext() != lastElement)
            tmpNode = tmpNode->getNext();
    
        tmpNode->setNext(NULL);
        delete lastElement;
        lastElement = tmpNode;
    }
    
    void Stack::clear(void)
    {
        ListNode* node = firstElement;
    
        while(NULL != node)
        {
            ListNode* nextNode = node->getNext();
            delete node;
            node = nextNode;
        }
        firstElement = NULL;
        lastElement = NULL;
    }
    

    doublelinkedlist.cpp:

    doubleLinkedList::doubleLinkedList()
    {
        topElement = NULL;
        lastElement = NULL;
    }
    
    doubleLinkedList::~doubleLinkedList()
    {
        topElement = NULL;
        lastElement = NULL;
    }
    
    void doubleLinkedList::add(ListNode *node)
    {
        if(node == NULL)
            return;
    
        if(isEmpty())
            topElement = node;
    
        else
        {
            lastElement->setNext(node);
            node->setPrev(lastElement);
        }
    
        lastElement = node;
    }
    
    void doubleLinkedList::clear(void)
    {
        ListNode* node = topElement;
    
        while(NULL != node)
        {
            ListNode* nextNode = node->getNext();
            delete node;
            node = nextNode;
        }
        topElement = NULL;
        lastElement = NULL;
    }
    
    bool doubleLinkedList::isEmpty(void) const
    {
        if(topElement == NULL)
            return true;
    
        return false;
    }
    
    void doubleLinkedList::inserAfter(ListNode *after, ListNode *node)
    {
        if(NULL == after || NULL == node || isEmpty())
            return;
    
        ListNode* listNode = new ListNode();
        *listNode = *node;
    
        ListNode* tmpNode = after->getNext();
        after->setNext(listNode);
        listNode->setPrev(after);
        listNode->setNext(tmpNode);
        tmpNode->setPrev(listNode);
    }
    
    void doubleLinkedList::remove(ListNode *node)
    {
        if(isEmpty())
            return;
    
        ListNode* tmpNode = new ListNode();
        tmpNode = topElement;
    
        if(topElement == node)
        {
            ListNode* tmpNode = topElement;
            topElement = topElement->getNext();
            delete tmpNode;
            tmpNode = NULL;
            if(NULL == topElement)
                return;
        }
    
        while(tmpNode != NULL)
        {
            if(tmpNode->getNext() == node)
            {
                tmpNode->setNext(tmpNode->getNext()->getNext());
                tmpNode->setPrev(tmpNode->getPrev()->getPrev());
            }
            tmpNode = tmpNode->getNext();
        }
        delete node;
        delete tmpNode;
    }
    

    Danke im Voraus.

    mfg


  • Mod

    Das macht herzlich wenig Sinn und ist daher auch nicht möglich* (oder du beschreibst dein Problem so schlecht, dass ich es falsch verstehe). Was möchtest du damit erreichen?

    *: Streng genommen, ist es natürlich schon möglich, aber es erfordert ungeheure Verrenkungen, bei denen alles verloren geht, was eine Liste ausmacht.



  • So etwas dachte ich mir schon und ich sehe den Sinn darin selber nicht wirklich.
    Mein Ausbilder meinte, dass es Sinn macht, weil ich den Pointer für das vorherige Element auch darin habe (prev) aber ihn nur bei der doppelt verketteten Liste brauche und es dementsprechend für die anderen Listen nicht brauche.
    Wie gesagt verstehe ich die Logik hinter der Aufgabe auch nicht wirklich.

    Edit: Ich bearbeite mal eben meinen ersten Post um das "Problem" zu verdeutlichen.

    mfg



  • Hallo OraMortis,

    OraMortis schrieb:

    ... Jetzt soll ich jedoch den "next-Pointer" aus meiner Klasse "ListNode" in die jeweiligen Klassen der Listen versetzen. Ist das möglich?

    Ich denke, dass ist schon möglich (SeppJ hat das wahrscheinlich anders verstanden). Der übliche Weg dazu, führt über ein Template.

    Das Ziel ist es doch, die Klasse, die Du benutzt, von den Innereien des Containers (also des Stacks, bzw. der doubleLinkedList) frei zu halten.
    Deine Klasse wäre hier doch

    class Name
    {
    public:
        // Methoden
        std::string firstname;
        std::string lasttname;
    };
    

    Einen Container z.B. einen Stack, kann man jetzt ganz allgemein halten:

    template< typename T > // T wird später zu 'Name' (s.o.)
    class Stack
    {
        struct ListNode // eine private nested class; geht außerhalb von Stack niemanden was an
        {
            ListNode( const T& x, ListNode* n )
                : next( n )
                , data( x )
            {}
            ListNode* next; // Zeiger auf den nächsten, prev braucht es hier nicht
            T data; // die User-Klasse
        };
    public:
        // Methoden im Prinzip wie unten, nur das nach außen nur T und nicht
        // 'ListNode' angeboten wird. Z.B.:
        void push( const T& data )
        {
            firstElement = new ListNode( data, firstElement );
        }
        T& top()
        {
            assert( firstElement ); // bei leerem Stack wäre das ein fataler Fehler
            return firstElement->data;
        }
    private:
        ListNode *firstElement;
    };
    
    // später 
    typedef Stack< Name > NamensStack;
    

    Tipp: berücksichtige die 'Regel der drei', in der Praxis sind die Klassen, so wie Du sie gepostet hast, ein kapitaler Fehler!
    Tipp 2: Benutze Initialisierungslisten

    Gruß
    Werner



  • OT:
    Mir fallen da noch einige andere Sachen auf, die du beherzigen solltest:

    1. In deiner Header Datei übergibst du in mehreren Methoden string . Das setzt voraus, dass du in deinem Header irgendwo sowas wie using namespace std; verwendest. Das hebelt das namespace-Konzept völlig aus, da durch sie Mehrdeutigkeiten aufgelöst werden sollen. In einer Header Datei solltest du niemals namespaces ausleeren, sondern deine Variablen/Parameter vollständig qualifizieren.
      Ausserdem übergibst du strings by Value , was unnötige Kopien nach sich ziehen kann. Wenn möglich solltest du sie als const std::string& übergeben, was keine Kopien erzeugt. Sie by Value zu übergeben ist in Ordnung, wenn du statt einer Zuweisung an ein Attribut swap benutzt (was ich ausser bei Zuweisungsoperatoren noch nirgendwo gesehen habe).
    // Option 1
    void MyClass::set_name( const string& Name )
    {
       MyMemberName_ = Name;
    }
    
    // oder Option 2
    void MyClass:set_name( string Name )
    {
       swap( MyMemberName, Name );
    }
    
    1. In C++ lässt man üblicherweise das void bei parameterlosen Funktion/Methoden weg. Ich weiss nicht, ob dein Ausbilder das so von dir verlangt, aber es ist unüblich.

Log in to reply