C++ 模板 - LinkedList

C++ Templates - LinkedList

提问by Drew_StackID

EDIT -- Answered below, missed the angled braces. Thanks all.

编辑 - 在下面回答，错过了尖括号。谢谢大家。

I have been attempting to write a rudimentary singly linked list, which I can use in other programs. I wish it to be able to work with built-in and user defined types, meaning it must be templated.

我一直在尝试编写一个基本的单向链表，我可以在其他程序中使用它。我希望它能够使用内置和用户定义的类型，这意味着它必须被模板化。

Due to this my node must also be templated, as I do not know the information it is going to store. I have written a node class as follows -

由于这个原因，我的节点也必须被模板化，因为我不知道它要存储的信息。我写了一个节点类如下 -

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

public:
    //Methods omitted for brevity
};

My linked list class is implemented in a seperate class, and needs to instantiate a node when adding new nodes to the end of the list. I have implemented this as follows -

我的链表类是在一个单独的类中实现的，在链表末尾添加新节点时需要实例化一个节点。我已按如下方式实施 -

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

I have set up a driver/test class as follows -

我已经设置了一个驱动程序/测试类如下 -

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

I get an error upon compilation however - error C2955: 'Node' : use of class template requires template argument list- which points me to the following line of code in my add method -

但是，我在编译时遇到错误 -错误 C2955：'Node'：使用类模板需要模板参数列表- 这将我指向我的 add 方法中的以下代码行 -

Node* temp = new Node<T>;

I do not understand why this has no information about the type, since it was passed to linked list when created in my driver class. What should I be doing to pass the type information to Node?

我不明白为什么这没有关于类型的信息，因为它在我的驱动程序类中创建时被传递到链表。我应该怎么做才能将类型信息传递给 Node？

Should I create a private node struct instead of a seperate class, and combine the methods of both classes in one file? I'm not certain this would overcome the problem, but I think it might. I would rather have seperate classes if possible though.

我应该创建一个私有节点结构而不是一个单独的类，并将两个类的方法组合在一个文件中吗？我不确定这会克服这个问题，但我认为它可能会。如果可能的话，我宁愿有单独的课程。

Thanks, Andrew.

谢谢，安德鲁。

采纳答案by villintehaspam

Might wanna try

可能想试试

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

Also, to get hints on how to design the list, you can of course look at std::list, although it can be a bit daunting at times.

此外，要获得有关如何设计列表的提示，您当然可以查看 std::list，尽管有时它可能有点令人生畏。

回答by Matthieu M.

While the answers have already been provided, I think I'll add my grain of salt.

虽然已经提供了答案，但我想我会加一点盐。

When designing templates class, it is a good idea not to repeat the template arguments just about everywhere, just in case you wish to (one day) change a particular detail. In general, this is done by using typedefs.

在设计模板类时，最好不要在任何地方重复模板参数，以防万一您希望（有一天）更改特定细节。通常，这是通过使用 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;
};

It is also better to define the methods outside of the class declaration, makes it is easier to read the interface.

最好在类声明之外定义方法，使接口更易于阅读。

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

Now, a couple of remarks:

现在，有几点说明：

• it would be more user friendly if List<T>::addwas returning an iterator to the newly added objects, like insertmethods do in the STL (and you could rename it insert too)
• in the implementation of List<T>::addyou assign memory to tempthen perform a bunch of operations, if any throws, you have leaked memory
• the setNextNullcall should not be necessary: the constructor of Nodeshould initialize all the data member to meaningfull values, included m_next

• 如果List<T>::add将迭代器返回给新添加的对象，则会更加用户友好，就像insertSTL 中的方法一样（您也可以将其重命名为 insert）
• 在执行List<T>::add你分配内存temp然后执行一堆操作，如果有任何抛出，你已经泄漏了内存
• 该setNextNull呼叫不应是必要的：的构造函数Node应该初始化所有数据成员meaningfull值，包括m_next

So here is a revised version:

所以这是一个修订版：

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

Note how the simple fact of using a proper constructor improves our exception safety: if ever anything throw during the constructor, newis required not to allocate any memory, thus nothing is leaked and we have not performed any operation yet. Our List<T>::insertmethod is now resilient.

请注意使用正确构造函数的简单事实如何提高我们的异常安全性：如果在构造函数期间有任何抛出，new则需要不分配任何内存，因此没有任何泄漏，我们还没有执行任何操作。我们的List<T>::insert方法现在是有弹性的。

Final question:

最后的问题：

Usual insertmethods of single linked lists insert at the beginning, because it's easier:

insert单链表的常用方法是在开头插入，因为这样更容易：

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

Are you sure you want to go with an insert at the end ? or did you do it this way because of the push_backmethod on traditional vectors and lists ?

您确定要在最后插入一个插入吗？或者你这样做是因为push_back传统向量和列表的方法？

回答by sepp2k

That line should read

那行应该读

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

Same for the nextpointer in the Node class.

nextNode 类中的指针也是如此。

回答by Kornel Kisielewicz

As said, the solution is

如上所述，解决方案是

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

... because Nodeitself is not a type, Node<T>is.

...因为Node它本身不是一种类型，Node<T>是。

回答by P-Nuts

You need:

你需要：

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

Might be worth a typedef NodeType = Node<T>in the CustomLinkedListclass to prevent this problem from cropping up again.

可能值得typedef NodeType = Node<T>在CustomLinkedList课堂上学习以防止再次出现此问题。

回答by UnknownGuy

And you will need to specify the template parameter for the Node *temp in printlist also.

并且您还需要在打印列表中为节点 *temp 指定模板参数。

回答by thecharliex

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

回答by Waseem Ahmad Naeem

You Should add new node in this way

您应该以这种方式添加新节点

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

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

Hope you Solved :)

希望你解决了:)

回答by Narendra kumawat

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