C++模板 - LinkedList

Question

編輯 - 在下面回答，錯過了有角度的大括號。謝謝大家。

我一直在試圖編寫一個基本的單向鏈表，我可以在其他程序中使用它。我希望它能夠使用內置和用戶定義的類型，這意味着它必須是模板化的。

由於這我的節點也必須模板化，因爲我不知道它將要存儲的信息。

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

public: 
    //Methods omitted for brevity 
}; 

我的鏈表類是在一個單獨的類中實現，並且需要將新節點添加到列表的末尾，當實例化一個節點 - 我有如下寫了一個節點類。我已經實現了這個原則 -

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

我已成立了一個驅動器/測試類如下 -

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

我在編譯時得到一個錯誤，但是 - 錯誤C2955：「節點」：使用類模板需要模板參數列表 - 這點我在我的add方法，把下面的代碼行 -

Node* temp = new Node<T>; 

我不明白爲什麼日沒有關於類型的信息，因爲它在我的驅動程序類中創建時傳遞給鏈接列表。 我應該如何將類型信息傳遞給Node？

我應該創建一個私有的節點結構而不是一個單獨的類，並將兩個類的方法合併到一個文件中嗎？我不確定這會克服這個問題，但我認爲它可能會。如果可能的話，我寧願有單獨的課程。

謝謝，安德魯。

Answer 1

可能想嘗試

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

此外，爲了獲得關於如何設計列表提示，你當然可以看的std ::名單，雖然它有時可以是一個有點令人生畏。

Answer 2

這行應爲

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

同爲在Node類的next指針。

Answer 3

至於說，解決的辦法是

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

...因爲Node本身不是一個類型，Node<T>是。

Answer 4

您需要：

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

可能是值得的CustomLinkedList類typedef NodeType = Node<T>，以防止再次突然出現這個問題。

Answer 5

而且您還需要爲printlist中的Node * temp指定模板參數。

Answer 6

雖然已經提供了答案，但我想我會添加我的鹽。

在設計模板類時，最好不要在任何地方重複模板參數，以防萬一您希望（有一天）更改特定的細節。一般來說，這是通過使用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; 
}; 

最好是在類聲明之外定義方法，使它更容易閱讀接口。

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

現在，一對夫婦的言論：

• 這將是更加人性化，如果List<T>::add是返回一個迭代器新添加的對象，如insert方法在STL做的（你可以重命名它插入太）
• 在分配內存temp的List<T>::add落實然後執行一串操作，如果有罰球，你已經泄漏的內存
• 的setNextNull呼叫不應是必要的：的Node構造函數應該初始化所有數據成員meaningfull值，包括m_next

因此，這裏是一個修訂版：

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

說明了如何使用簡單的事實一個合適的構造函數提高了我們的異常安全性：如果在構造函數中拋出任何東西，new需要不分配任何內存，因此沒有任何內容泄漏，我們還沒有執行任何操作。我們的List<T>::insert方法現在具有彈性。

最後一個問題：

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

你確定你想要去的，並在最後一個插入？或者你是這樣做的，因爲傳統向量和列表上的方法是push_back？

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

你應該這樣

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

希望你解決了超快速的響應都添加新節點:)

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