是鏈表，樹等的遞歸析構函數嗎？

對於我目前的學習練習，我正在學習鏈表和樹。我最近看到一個建議，通過讓每個節點刪除其子/子節點來遞歸地銷燬數據結構。然而，在我發現的幾乎所有例子中，節點析構函數都是空的，一些管理類使用某種形式的迭代和刪除來處理銷燬。從可靠性和/或文體的角度來看，遞歸析構函數有什麼固有的壞處？是鏈表，樹等的遞歸析構函數嗎？

以下是我對兩種方法的理解。

遞歸破壞：

#include <iostream> 
struct Node { 
    static int count; 
    Node() : num_(count++), p_next_(0) {} 
    ~Node() { 
    std::cout << "entering " << num_ << "\n"; 
    delete p_next_; 
    std::cout << " leaving " << num_ << "\n"; 
    } 
    const int num_; 
    Node* p_next_; 
}; 
int Node::count = 0; 
int main() { 
    Node* p_head = new Node(); 
    p_head->p_next_ = new Node(); 
    p_head->p_next_->p_next_ = new Node(); 
    delete p_head; 
    return 0; 
}

下面是我採取的管理類處理破壞。假設我已經定義了以下析構函數的節點：

~Node() {std::cout << "Someone deleted " << num_ << "\n";}

我會定義以下LinkedList的管理類和隨後的主

/* other stuff from above */ 
class LinkedList { 
public: 
    LinkedList() : p_head_(new Node()) { 
    p_head_->p_next_ = new Node(); 
    p_head_->p_next_->p_next_ = new Node(); 
    } 
    ~LinkedList() { 
    while(Node* p_prev = p_head_) { 
     p_head_ = p_head_->p_next_; 
     delete p_prev; 
    } 
    } 
private: 
    Node* p_head_; 
}; 
int main() { 
    LinkedList* p_list = new LinkedList(); 
    delete p_list; 
    return 0; 
}

假設我在正確讀我的結果，我的兩種實現方式做同樣的事情。

關於我的遞歸破壞示例，我想我幾乎總是需要某種類型的管理類，當我用代碼解決真正的問題時需要一個頭部的副本，但管理類只需要刪除頭部/根節點，以確保破壞整個數據結構。對我來說，這感覺更加優雅，但我已經陷入了我認爲很整潔的代碼中。

管理類應該負責確保所有內容都被正確刪除嗎？或者底層的數據結構知道如何清理它自己更好？是否有任何不明顯的陷阱？

謝謝！

--Jordan

編輯：一個念頭出現在我。如果我有一個非常長的節點鏈，那麼在第一個例子中，我是否因爲遞歸發揮作用而擔心堆棧溢出？

edit2：我想它應該是顯而易見的。現在我只是覺得有點傻。在我的機器上，如果我有超過64910個節點，我會崩潰。所以遞歸很明顯地提出了一個問題。

來源

2011-08-06 Jordan Gray

是的，對你的第一種方法的主要論點是，與許多節點列表確實可能導致堆棧溢出，即使一個好的編譯器應該能夠弄清楚，你不需要爲每個額外的堆棧空間請致電，因爲您沒有返回的結果供您採取行動。 –

但是我認爲依靠一個好的編譯器並不安全？ –

你又對了。有些語言的遞歸是重複的主要工具，並且您可以保證類似的方法不會浪費資源。然而，C++ –

如果您對鏈表執行此操作，將會出現堆棧內存消耗問題。銷燬這樣一個鏈表將導致你的遞歸量爲Node，而遞歸深度將隨鏈表的大小線性增長。

只要做一下實驗：在你的列表中輸入幾百萬個節點，然後銷燬它。我敢打賭你會得到堆棧溢出（除非你配置你的線程來保留巨大的堆棧大小）。特別是在調試版本中，您會很早就無法運行。

OTOH這樣做對於樹木來說是可以的，至少從技術角度來看。無論如何，樹清理通常是以遞歸方式實現的，如果上面的遞歸函數屬於樹或Node並不重要，那麼這個事實並不重要。

銷燬樹的遞歸深度將隨着樹的深度以對數方式增長，這沒關係。

來源

2011-08-06 07:57:40 valdo

考慮鏈接項目的所有權。

Node對象擁有它下一個親屬有意義嗎？節點擁有附加的衛星數據肯定是有道理的，所以當節點被銷燬時，你應該清理它。

LinkedList擁有它的節點，因此它應該負責正確地銷燬它們，而不會有任何內存中剩餘物。

LinkedList對象應該能夠添加和刪除節點，因此從所有權的角度來看，它負責清除它們，例如通過迭代刪除列表中的每個節點。

來源

2011-08-06 07:09:01 Wizz

所以你的意思是認爲B/C的管理類擁有所鏈接的節點形成的底層數據結構，這是令人困惑/壞的形式向節點給予清理功能？ –

通常不是這個，但是對於這個聲明持有的節點。看看它是這樣：只有LinkedList擁有節點，以便LinkedList的負責釋放他們當列表被銷燬與刪除和析構函數會被調用。該節點的相同規則成立，並且節點負責摧毀其衛星數據 - 但它鏈接到任何其他節點，因爲這些節點（Next和Prev）的_not_由節點，而是由LinkedList的資 – Wizz

是鏈表，樹等的遞歸析構函數嗎？

回答

相關問題