Template C++ – LinkedList

EDIT — Risposto sotto, perse l’angolo di parentesi graffe. Grazie a tutti.

Ho cercato di scrivere un rudimentale lista concatenata, che posso utilizzare in altri programmi. Io le auguro di essere in grado di lavorare con built-in e tipi definiti dall’utente, il che significa che deve essere basato su modelli.

A causa di questo mio nodo deve essere basato su modelli, come faccio a non conoscere le informazioni si tratta di andare al negozio. Ho scritto un nodo di classe come indicato di seguito –

template <class T> class Node
{
    T data; //the object information
    Node* next; //pointer to the next node element

public:
    //Methods omitted for brevity
};

Mia lista collegata classe è implementato in una classe separata, e necessario creare un’istanza di un nodo quando l’aggiunta di nuovi nodi alla fine della lista. Ho implementato come segue –

#include <iostream>
#include "Node.h"
using namespace std;

template <class T> class CustomLinkedList
{
    Node<T> *head, *tail;

public:

    CustomLinkedList()
    {
        head = NULL;
        tail = NULL;
    }

    ~CustomLinkedList()
    {

    }

    //Method adds info to the end of the list
    void add(T info)
    {
        if(head == NULL) //if our list is currently empty
        {
            head = new Node<T>; //Create new node of type T
            head->setData(info);
            tail = head;
        }
        else //if not empty add to the end and move the tail
        {
            Node* temp = new Node<T>;
            temp->setData(info);
            temp->setNextNull();
            tail->setNext(temp);
            tail = tail->getNext();
        }
    }

    //print method omitted
};

Ho impostato un driver/classe di test come indicato di seguito –

#include "CustomLinkedList.h"
using namespace std;

int main()
{
    CustomLinkedList<int> firstList;

    firstList.add(32);
    firstList.printlist();
    //Pause the program until input is received
    int i;
    cin >> i;

    return 0;
}

Ottengo un errore al momento della compilazione tuttavia – errore C2955: ‘Node’ : l’uso del modello di classe richiede un modello di lista di argomenti – che i punti di me per la seguente riga di codice nel mio metodo add –

Node* temp = new Node<T>;

Non capisco perché questo non ha alcuna informazione circa il tipo, dal momento che si è passati a una lista collegata quando creato nella mia classe del driver. Cosa devo fare per passare le informazioni sul tipo di Nodo?

Devo creare una struct nodo invece di una classe separata, e combinare i metodi di entrambe le classi in un unico file? Io non sono certo che questo avrebbe superato il problema, ma penso che potrebbe. Preferisco separare le classi, se possibile, però.

Grazie, Andrea.

  • Grazie per la super risposta rapida di tutti. Stupido errore da parte mia. Ciao.
  • Lo sapevate che la libreria standard del C++ fornisce già un elenco collegato doppiamente modello (std::list)? Inoltre, la libreria Boost fornisce “invadente” liste collegate.
  • Sì, lo so, ma fare il vostro proprio dovrebbe essere una buona pratica, in particolare per il puntatore logica. Inoltre voglio implementare alcuni metodi un po ‘ diverso. Grazie per il consiglio, però.
InformationsquelleAutor Drew_StackID | 2010-01-16



9 Replies
  1. 8

    Potrebbe desiderare di provare

    Node<T>* temp = new Node<T>;

    Anche, per ottenere suggerimenti su come progettare l’elenco, ovviamente si può guardare std::list, anche se può essere un po ‘ scoraggiante, a volte.

    • Sì, al momento sto guardando alcuni metodi per farlo. La maggior parte non ne ho bisogno, però, che è bello perché non ho l’esperienza per implementare alcuni metodi di sicurezza. Grazie per la risposta.
  2. 12

    Mentre le risposte sono già state fornite, penso che aggiungerò il mio grano di sale.

    Durante la progettazione di modelli di classe, è una buona idea di non ripetere gli argomenti di modello quasi ovunque, solo nel caso in cui si desidera per un giorno a cambiare un dettaglio particolare. In generale, questo è fatto tramite typedef.

    template <class T>
    class Node
    {
    public:
      //bunch of types
      typedef T value_type;
      typedef T& reference_type;
      typedef T const& const_reference_type;
      typedef T* pointer_type;
      typedef T const* const_pointer_type;
    
      //From now on, T should never appear
    private:
      value_type m_value;
      Node* m_next;
    };
    
    
    template <class T>
    class List
    {
      //private, no need to expose implementation
      typedef Node<T> node_type;
    
      //From now on, T should never appear
      typedef node_type* node_pointer;
    
    public:
      typedef typename node_type::value_type value_type;
      typedef typename node_type::reference_type reference_type;
      typedef typename node_type::const_reference_type const_reference_type;
      //...
    
      void add(value_type info);
    
    private:
      node_pointer m_head, m_tail;
    };

    È anche di meglio definire i metodi al di fuori della dichiarazione di classe, rende più facile leggere l’interfaccia.

    template <class T>
    void List<T>::add(value_type info)
    {
      if(head == NULL) //if our list is currently empty
      {
        head = new node_type;
        head->setData(info);
        tail = head;
      }
      else //if not empty add to the end and move the tail
      {
        Node* temp = new node_type;
        temp->setData(info);
        temp->setNextNull();
        tail->setNext(temp);
        tail = tail->getNext();
      }
    }

    Ora, un paio di osservazioni:

    • sarebbe più facile se List<T>::add era il ritorno di un iteratore per la recente aggiunta di oggetti, come insert metodi di fare in STL (e si potrebbe rinominare inserire troppo)
    • in attuazione di List<T>::add si assegna la memoria di temp quindi eseguire un sacco di operazioni, se uno getta, si dispone di perdita di memoria
    • il setNextNull chiamata non dovrebbe essere necessario: il costruttore di Node deve inizializzare tutti i dati membro significativa dei valori, inclusi m_next

    Così qui è una versione riveduta:

    template <class T>
    Node<T>::Node(value_type info): m_value(info), m_next(NULL) {}
    
    template <class T>
    typename List<T>::iterator insert(value_type info)
    {
      if (m_head == NULL)
      {
        m_head = new node_type(info);
        m_tail = m_head;
        return iterator(m_tail);
      }
      else
      {
        m_tail.setNext(new node_type(info));
        node_pointer temp = m_tail;
        m_tail = temp.getNext();
        return iterator(temp);
      }
    }

    Nota come il semplice fatto di utilizzare una corretta costruttore migliora la nostra eccezione di sicurezza: se mai buttare nulla durante il costruttore, new è richiesto di non allocare memoria, dunque nulla è trapelato, e noi non hanno eseguito alcuna operazione di sicurezza. Il nostro List<T>::insert metodo è ora resiliente.

    Domanda finale:

    Solito insert metodi di singole liste collegate inserire all’inizio, perché è più facile:

    template <class T>
    typename List<T>::iterator insert(value_type info)
    {
      m_head = new node_type(info, m_head); //if this throws, m_head is left unmodified
      return iterator(m_head);
    }

    Sei sicuro di voler andare con un inserto alla fine ? o l’hai fatto in questo modo a causa del push_back metodo tradizionale di vettori e liste ?

  3. 1

    Che la linea dovrebbe leggere

    Node<T>* temp = new Node<T>;

    Stesso per il next puntatore al Nodo di classe.

    • Ben individuato, ho completamente perso l’auto-riferimento. Grazie.
  4. 0

    Hai bisogno di:

    Node<T> *temp = new Node<T>;

    Potrebbe essere la pena di un typedef NodeType = Node<T> in CustomLinkedList classe per evitare che questo problema ritaglio di nuovo.

    • Ho saltato il typedef nel mio libro. Vado indietro e guardare a tutto, grazie per il suggerimento.
  5. 0

    E sarà necessario specificare il parametro di modello per il Nodo *temp in printlist anche.

    • Grazie. Ho cambiato ora – penso che mi limiterò a modificare fuori del mio post non è pertinente alla domanda davvero, e sprechi di spazio.
  6. 0
    //file: main.cc
    
    #include "linkedlist.h"
    
    int main(int argc, char *argv[]) {
        LinkedList<int> list;
        for(int i = 1; i < 10; i++) list.add(i);
        list.print();
    }
    
    //file: node.h
    
    #ifndef _NODE_H
    #define _NODE_H
    
    template<typename T> class LinkedList;
    template<typename T>class Node {
        friend class LinkedList<T>;
        public:
            Node(T data = 0, Node<T> *next = 0)
                : data(data), next(next)
            { /* vacio */ }
        private:
            T data;
            Node<T> *next;
    };
    
    #endif//_NODE_H
    
    //file: linkedlist.h
    
    #ifndef _LINKEDLIST_H
    #define _LINKEDLIST_H
    
    #include <iostream>
    using namespace std;
    
    #include "node.h"
    
    template<typename T> class LinkedList {
        public:
            LinkedList();
            ~LinkedList();
            void add(T);
            void print();
        private:
            Node<T> *head;
            Node<T> *tail;
    };
    
    #endif//_LINKEDLIST_H
    
    template<typename T>LinkedList<T>::LinkedList()
        : head(0), tail(0)
    { /* empty */ }
    
    template<typename T>LinkedList<T>::~LinkedList() {
        if(head) {
            Node<T> *p = head;
            Node<T> *q = 0;
    
            while(p) {
                q = p;
                p = p->next;
                delete q;
            }
    
            cout << endl;
        }
    }
    
    template<typename T>LinkedList<T>::void add(T info) {
        if(head) {
            tail->next = new Node<T>(info);
            tail = tail->next;
        } else {
            head = tail = new Node<T>(info);
        }
    }
    
    template<typename T>LinkedList<T>::void print() {
        if(head) {
            Node<T> *p = head;
    
            while(p) {
                cout << p->data << "-> ";
                p = p->next;
            }
    
            cout << endl;
        }
    }
  7. 0

    Si Dovrebbe aggiungere un nuovo nodo in questo modo

    Node<T>* temp=new node<T>;

    Spero che hai Risolto 🙂

  8. 0
    #include<iostream>
    using namespace std;
    
    template < class data > class node {
        private :
            data t;
            node<data > *ptr;
        public:
        node() {
            ptr = NULL;
        }
        data get_data() {
            return t;
        }
        void set_data(data d) {
            t = d;
        }
        void set_ptr(node<data > *p) {
            ptr = p;
        }
        node * get_ptr() {
            return ptr;
        }
    };
    template <class data > node < data > * add_at_last(data  d  , node<data > *start) {
        node< data > *temp , *p  = start;
        temp = new node<data>();
        temp->set_data(d);
        temp->set_ptr(NULL);
        if(!start) {
            start = temp;
            return temp;
        }
        else {
            while(p->get_ptr()) {
                p = p->get_ptr();
            }
            p->set_ptr(temp);
        }
    }
    template < class data > void display(node< data > *start) {
        node< data > *temp;
        temp = start;
        while(temp != NULL) {
            cout<<temp->get_data()<<" ";
            temp = temp->get_ptr();
        }
        cout<<endl;
    }
    template <class data > node < data > * reverse_list(node<data > * start) {
        node< data > *p = start , *q = NULL , *r = NULL;
        while(p->get_ptr()) {
            q = p;
            p = p->get_ptr();
            q->set_ptr(r);
            r = q;
        }
        p->set_ptr(r);
        return p;
    }
    int main() {
        node < int > *start;
        for(int i =0 ; i < 10 ; i ++) {
            if(!i) {
                start = add_at_last(i , start);
            }
            else {
                add_at_last(i , start);
            }
        }
        display(start);
        start = reverse_list(start);
        cout<<endl<<"reverse list is"<<endl<<endl;
        display(start);
    }

Lascia un commento