我如何在C++中創建一個列表？

Question

如何在C++中創建列表？我需要它來創建一個鏈表。我會怎麼做呢？有好的教程或例子可以遵循嗎？

Answer 1

我認爲你知道C++已經有一個鏈表類，並且你想實現你自己的，因爲你想學習如何去做。

首先，閱讀Why do we use arrays instead of other data structures?，其中包含基本數據結構的一個很好的答案。然後想想如何在C++中對它們進行建模：

struct Node { 
    int data; 
    Node * next; 
}; 

基本上這就是您需要實現的一個列表！ （一個非常簡單的）。然而，它沒有抽象的，你必須每手鍊接的項目：

Node a={1}, b={20, &a}, c={35, &b} d={42, &c}; 

現在，你必須有節點的鏈表，所有在棧中分配：

d -> c -> b -> a 
42 35 20 1 

下一步是寫一個包裝類List指向開始節點，並允許根據需要添加節點，保持列表的頭部的軌道（以下是非常簡化的）：

class List { 
    struct Node { 
     int data; 
     Node * next; 
    }; 

    Node * head; 

public: 
    List() { 
     head = NULL; 
    } 

    ~List() { 
     while(head != NULL) { 
      Node * n = head->next; 
      delete head; 
      head = n; 
     } 
    } 

    void add(int value) { 
     Node * n = new Node; 
     n->data = value; 
     n->next = head; 
     head = n; 
    } 

    // ... 
}; 

下一步是使List成爲一個模板，這樣你就可以填充其他值（不僅是整數）。

如果您熟悉智能指針，則可以使用智能指針替換原始指針。通常我會發現人們推薦首發的智能指針。但在我看來，你應該首先明白爲什麼你需要智能指針，然後使用它們。但是這要求你首先要了解原始指針。否則，你會使用一些神奇的工具，而不知道你爲什麼需要它。

Answer 2

你應該真的使用standard List class。當然，除非這是一個家庭作業問題，否則你想知道STL如何實現列表。

你會發現很多簡單的谷歌教程，如this one。如果您想知道鏈接列表如何在「底層」下工作，請嘗試搜索C列表示例/教程而不是C++。

Answer 3

爲什麼要重新發明輪子。只需使用STL列表容器。

#include <list> 

// in some function, you now do... 
std::list<int> mylist; // integer list 

More information...

Answer 4

我們已經在21世紀！ 不要嘗試實現已經存在的數據結構。 嘗試使用現有的數據結構。

使用STL或者Boost庫

Answer 5

如果你要使用std::list，你需要傳遞一個類型參數：

list<int> intList; 
list<int>* intListPtr = new list<int>; 

如果你想知道名單是如何工作的，我建議谷歌上搜索一些C/C++教程來獲得對該主題的理解。接下來的步驟就是學習足夠多的C++來創建一個列表類，最後是一個列表模板類。

如果您還有其他問題，請回到這裏。

Answer 6

我猜這是一個家庭作業問題，所以你可能想去here。它有一個解釋鏈表的教程，給出了很好的僞代碼，並且還有一個可以下載的C++實現。

我建議通過解釋和理解僞代碼之前盲目使用實現閱讀。如果您想在CS中繼續使用，那麼您應該深入理解這個話題。

Answer 7

升壓ptr_list

http://www.boost.org/doc/libs/1_37_0/libs/ptr_container/doc/ptr_list.html

HTH

Answer 8

創建使用C++模板

即

template <class T> struct Node 
{ 
    T data; 
    Node * next; 
}; 

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

    public: 
     void push(T const&); // push element 
     void pop();   // pop element 
     bool empty()   // return true if empty. 
}; 

然後你就可以編寫代碼列表：

List<MyClass>; 

類型T在運行時不是動態的。它僅用於編譯時。

完整示例click hear。

對於C++模板教程click hear。