Op deze website gebruiken we cookies om content en advertenties te personaliseren, om functies voor social media te bieden en om ons websiteverkeer te analyseren. Ook delen we informatie over uw gebruik van onze site met onze partners voor social media, adverteren en analyse. Deze partners kunnen deze gegevens combineren met andere informatie die u aan ze heeft verstrekt of die ze hebben verzameld op basis van uw gebruik van hun services. Meer informatie.

Akkoord

Vraag & Antwoord

Programmeren

[C++] Linked list

None
9 antwoorden
  • Dit is mijn eigen linked list implentatie, ik heb nog nooit met linked lists gewerkt dus misschien is ie nog niet helemaal tof.
    Weten jullie nog leuke extra's/optimalisatie's?

    [code:1:baca703af6]
    #ifndef _PLIST_H
    #define _PLIST_H

    template <class T> class pList;
    template <class T> class pNode;
    template <class T> class pListIterator;

    #define INVALID_NODE "(pNode<T> *)0"

    template <class T>
    class pNode
    {
    public:
    pNode()
    {
    }

    pNode(T* object) : data(object) { }

    ~pNode()
    {
    // delete ;
    }

    int index;
    pNode<T> * next;
    pNode<T> * prev;
    T* data;


    };


    template <class T>
    class pListIterator
    {
    public:

    pListIterator() : node(0), nodes(0)
    {
    first = new pNode<T>;
    first->index = -1;
    first->prev = last;
    first->next = last;
    first->data = 0;
    last = new pNode<T>;
    last->index = 0;
    last->prev = first;
    last->next = first;
    last->data = 0;

    node = last;

    }

    ~pListIterator()
    {
    clear();
    delete first;
    delete last;
    }

    pListIterator<T> operator++()
    {
    node = node->next();
    return *this;
    }

    pListIterator<T> operator–()
    {
    node = node->previous();
    return *this;
    }

    pNode<T> *insert(T* object, int offset = -1)
    {
    if( offset != -1)
    {
    node = first;
    for( int i =0; i <= nodes; i++)
    {
    node = node->next;
    if(node->index == offset)
    break;

    }

    }
    else
    node = last;

    pNode<T> *nodePtr = new pNode<T>(object);
    nodePtr->index = node->index++;
    nodePtr->next = node;
    nodePtr->prev = node->prev;
    node->prev->next = nodePtr;
    node->prev = nodePtr;
    //node = nodePtr;

    for( int i =0; i <= nodes; i++)
    {
    node = node->next;

    if(node == last || node == first)
    break;

    node->index++;

    }
    node = last;
    nodes++;

    return node;
    }

    void remove(int index)
    {
    pNode<T> *nodePtr = node;

    int i = 0;

    if( at(index) == (pNode<T>*)0)
    return 0;

    node->prev->next = node->next;
    node->next->prev = node->prev;
    pNode<T> * tmp = node->next;
    delete node;
    node = tmp;

    nodes–;

    for(i =0; i <= nodes; i++)
    {
    // *this++;
    node->index = node->index - 1;
    node = node->next;
    if(node == first)
    break;
    }

    node = nodePtr;

    }

    pNode<T> *at(int offset)
    {
    pNode<T> *tmp = node;
    for( int i =0; i <= nodes; i++)
    {
    // *this++;
    tmp = tmp->next;
    if(tmp->index == offset)
    break;

    }
    if(tmp == last || tmp == first)
    return 0;
    if(tmp->index != offset)
    return 0;

    node = tmp;
    return node;

    }

    pNode<T> *at() { return node; }

    void clear()
    {
    node = first->next;
    for( int i =0; i <= nodes; i++)
    {
    // *this++;
    node = node->next;
    if(node == last)
    break;
    delete node->prev;
    }

    first->index = -1;
    first->prev = last;
    first->next = last;
    first->data = 0;
    last->index = 0;
    last->prev = first;
    last->next = first;
    last->data = 0;

    node = last;
    nodes = 0;

    }

    pNode<T> *find(T* object)
    {
    pNode<T> *tmp = node;
    for( int i =0; i <= nodes; i++)
    {
    // *this++;
    tmp = tmp->next;
    if(tmp->data == object)
    break;

    }
    if(tmp == last || tmp == first)
    return 0;
    if(tmp->data != object)
    return 0;

    node = tmp;
    return node;

    }

    // Debug

    void listNodes()
    {
    node = first;
    for( int i =0; i <= nodes; i++)
    {
    // *this++;
    cout << "Node with index " << node->index << endl;
    node = node->next;
    }
    }

    pNode<T> *node;
    pNode<T> *last;
    pNode<T> *first;
    int nodes;

    };

    template <class T>
    class pList
    {
    public:

    pList() : nodes(0)
    {
    iterator = new pListIterator<T>();
    }

    ~pList()
    {
    delete iterator;
    }

    void append(T *object) { insert(object); }

    void prepend(T *object) { insert(object, 0); }

    T *get(int index) { return at(index); }

    T *operator[] (int offset) { return at(offset); }

    void operator+= (T* object) { iterator->insert(object); }

    int count() { return iterator->nodes; }

    int insert(T* object, int i = -1) { return iterator->insert(object, i)->index; }

    void remove(int i) { iterator->remove(i); }

    T* at(int index)
    {
    if(index > iterator->nodes)
    return 0;

    return iterator->at(index)->data;
    }

    int at() { return iterator->at()->index; }

    T* current() { return iterator->at()->data; }

    T* next()
    {
    iterator++;
    return iterator->at();
    }

    T* prev()
    {
    iterator–;
    return iterator->at();
    }

    int find(T* object) { return iterator->find(object)->index; }

    void clear() { iterator->clear(); }

    void listNodes() { iterator->listNodes(); } // Debug

    bool empty() { return iterator->nodes == 0; }


    private:

    int nodes;
    pListIterator<T> *iterator;

    };

    #endif
    [/code:1:baca703af6]
  • Niemand geinteresseerd in mijn linky-list :( ?
    Of snappen jullie um gewoon niet :lol: :rolleyes:
  • Nou had ik zelf ook nog even een vraagje:
    Als ik die lijst inherit door bv dit te doen:
    [code:1:dd8eb4c836]
    class myList : public pList<int>
    {
    public: myList() : pList<int>() { }
    };
    [/code:1:dd8eb4c836]
    En hem instantieer:
    [code:1:dd8eb4c836]
    myList mylistinstance;
    [/code:1:dd8eb4c836]
    Dat krijg ik een segfault :oops:
    Als ik een pointer naar een new instantie maak niet:
    [code:1:dd8eb4c836]
    myList *myListPtr = new myList();
    [/code:1:dd8eb4c836]
    Hoe kan dat? ik wil gewoon een instantie maken….
  • Ik snap je code wel phaas, maar ik vind het gewoon SAAI! :P

    Nee gelinkte lijsten maken is gewoon een saaie klus. Daarbij komt nog eens dat je STL gebruikt en dat maakt het gewoon onleesbaar en slecht onderhoudbaar. Misschien wel voor jou, maar niet voor iemand anders, maargoed da's persoonlijk.

    Jouw probleem: Je roept wel je default constructor aan van je superclass, maar je alloceert nergens geheugen ervoor. Daarom moet je wel new() gebruiken.
  • Kan ik ook gewoon zonder new() vanaf 'gewone' instantie geheugen allocaten? iets in de constructor enzo…
    Enne wat is nou precies dat STL, ben al wel eens eerder tegengekomen ..
  • Even twee dingen:

    Jij moet altijd geheugen alloceren, wat je ook doet. Echter er zijn wat dingen die de compiler al voor je doet. Als jij bijvoorbeeld schrijft:

    [code:1:6060785dc2]

    char debug[20];

    [/code:1:6060785dc2]

    Dan declareer je een array van pointer naar characters van ter grootte van twintig elementen. Die grootte staat vast, de compiler weet hoeveel bytes 1 character inneemt, namelijk 8 (in het geval van een ASCII character). Dit is een standaard-datatype, dus de compiler alloceert al ruimte voor jou.

    Bij niet standaard-datatypes, weet de compiler niet hoeveel hij moet alloceren. Jij moet eerst de definitie van jouw klasse maken, voordat hij weet hoe en wat. Daarna moet jij handmatig geheugen reserveren, dat doe je idd met new(). Overigens zul je het geheugen weer vrij moeten geven met delete(), anders krig je een memory-leak, d.w.z. dat je geheugen alloceert, maar het niet vrijgeeft. Je gaat dan inderdaad "memory zuipen".

    Op jouw eerste manier kreeg je een segfault. Dat is ook wel logisch, want je wilt een instantie maken van een klasse maar er geen geheugen aa toekennen. Zoals je zelf al snapt: dat kan niet :) . C en C++ werken via het "call by reference" principe, dus je zult er geheugen voor moeten alloceren en je houd er een pointer aan over die naar de geinstantieerde klasse (=object) wijst.

    Nu de STL. Dit is een van de uitbreidingen van C en staat voor de Standard Template Library. Is ontwikkeld destijds door HP en mah iedereen gebruiken. De STL bevat templates om een aantal zaken te vermakkelijken, bijvoorbeeld gelinkte lijsten (ja hij was er al ;) )

    Ook zit er een krachtigere macro in -> template. Jij gebruikt het ook al, die <T> bijvoorbeeld.
  • Oww op die fiets, maar het dus niet mogelijk om gewoon
    [code:1:ef9b846ccb]
    myList mylistinstance;
    [/code:1:ef9b846ccb]
    te doen?
    Want met Qt kan je bv wel gewoon
    QStringList myStringlist; [code] doen. Hoe zit dat dan? Bedankt voor je uitleg btw.
  • dat is een specifieke QT klasse en zij kunnnen achter de schermen ook al new() aanroepen, dat weet ik niet.

    Wat ik wel weet is dat in C++ dat wel moet bij instanties van zelgemaakte klasses. Die QT Klasse zit ergens in een bibliotheek en is waarschijnlijk al helemaal voor je gemaakt en gealloceerd.
  • A. komt mijn klasse ook in een systeembibliotheek,
    B. hoe roep ik dan ergens new() in mijn eigengemaakte klasse?

Beantwoord deze vraag

Dit is een gearchiveerde pagina. Antwoorden is niet meer mogelijk.