Plantillas C++ - LinkedList

Question

EDITAR - Respondió a continuación, perdió las llaves angulares. Gracias a todos.

He estado intentando escribir una lista rudimentaria individualmente enlazada, que puedo usar en otros programas. Deseo que sea capaz de trabajar con tipos integrados y definidos por el usuario, lo que significa que debe ser templado.

Debido a esto mi nodo también debe ser templado, ya que no sé la información que va a almacenar. He escrito una clase de nodo de la siguiente manera -

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

public: 
    //Methods omitted for brevity 
}; 

Mi clase de lista enlazada se implementa en una clase independiente, y necesita crear una instancia de un nodo al añadir nuevos nodos al final de la lista. He implementado de la siguiente manera -

#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 
}; 

He creado una clase de controlador/prueba de la siguiente -

#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; 
} 

consigo un error en la compilación sin embargo - error C2955: 'nodo': uso de la plantilla de clase requiere plantilla de lista de argumentos - que me apunta a la siguiente línea de código en mi método add -

Node* temp = new Node<T>; 

no entiendo por qué º no tiene información sobre el tipo, ya que se pasó a la lista vinculada cuando se creó en mi clase de controlador. ¿Qué debería estar haciendo para pasar la información de tipo al nodo?

¿Debo crear una estructura de nodo privada en lugar de una clase separada, y combinar los métodos de ambas clases en un archivo? No estoy seguro de que esto supere el problema, pero creo que sí. Preferiría tener clases separadas si es posible.

Gracias, Andrew.

Answer 1

quiero ser que intente

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

Además, para obtener consejos sobre cómo diseñar la lista, se puede, por supuesto vistazo a std :: lista, aunque puede ser un poco complicado a veces.

Answer 2

Esa línea debe decir

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

Lo mismo para el puntero next en la clase de nodo.

Answer 3

Como se ha dicho, la solución es

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

... porque Node sí mismo no es un tipo, es Node<T>.

Answer 4

que necesita:

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

podría valer la pena typedef NodeType = Node<T> en la clase CustomLinkedList a evitar que este problema apareciendo de nuevo.

Answer 5

Y deberá especificar también el parámetro de la plantilla para la temperatura del nodo * en la lista de impresión.

Answer 6

Si bien las respuestas ya han sido proporcionadas, creo que voy a agregar mi grano de sal.

Al diseñar la clase de plantillas, es una buena idea no repetir los argumentos de la plantilla en cualquier lugar, en caso de que desee (un día) cambiar un detalle en particular. En general, esto se hace mediante el uso de typedefs.

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; 
}; 

También es mejor definir los métodos fuera de la declaración de clase, hace que sea más fácil de leer la interfaz.

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(); 
    } 
} 

Ahora, un par de comentarios:

• sería más fácil de usar si List<T>::add regresaba un iterador a los objetos recién añadidos, como insert métodos hacen en la STL (y que podría cambiar el nombre se inserte también)
• en la implementación de List<T>::add se asigna memoria para temp a continuación, realizar un montón de operaciones, en su caso tiros, que se han filtrado de memoria
• el setNextNull llamada no debería ser necesario: el constructor de Node debe inicializar todo el miembro de datos a los valores meaningfull, incluido m_next

Así que aquí es una versión revisada:

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 cómo el simple hecho de utilizar un constructor adecuado mejora nuestra seguridad de excepción: si alguna vez se lanza algo durante el constructor, new es necesario para no asignar ninguna memoria, por lo tanto, no se ha filtrado nada y aún no hemos realizado ninguna operación. Nuestro método List<T>::insert ahora es resistente.

Pregunta final:

habituales insert métodos de listas enlazadas simples insertar al principio, porque es más fácil:

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); 
} 

¿Seguro que quiere ir con un inserto al final? o lo hiciste de esta manera debido al método push_back en vectores y listas tradicionales?

Answer 7

// 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; 
    } 
} 

Answer 8

se debe añadir un nuevo nodo de esta manera

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

Espero que resuelto :)

Answer 9

#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); 
}