釋放內存 - Visual C

我已經定義就像一棵樹釋放內存 - Visual C

struct tree { 
    char label[MAX_LENGTH]; 
    char value[MAX_LENGTH]; 
    struct tree *child; 
    struct tree *next; 
};

，現在我需要釋放該樹分配的內存。我寫了下面的代碼。

unsigned int tree_free(struct tree *root) 
{ 
    struct tree *current = NULL, *next = NULL, *child = NULL; 
    unsigned int freecnt = 0; 

    current = root; 
    while(current != NULL) 
    { 
     next = current->next; 
     child = current->child;  
     xfree(current); 
     freecnt += tree_free(child) + 1; 
     current = next; 
    } 
    return freecnt; 
}

該方法返回它釋放的項目數，以便我可以根據所做的分配數來驗證它。此代碼有效。但我不確定這是否是正確的做事方式。

這是一個後綴樹實現。對於項目S，堆棧，過，過流，計算器樹看起來像

root 
-s 
--stack 
---stackoverflow 
-over 
--overflow

任何建議，以提高代碼的歡迎。

來源

2010-08-14 Navaneeth K N

您遺漏了一些細節：（1）樹的結構是什麼？從代碼中可以看出它不是「香草」二叉樹。（2）什麼是'xfree'？ – 2010-08-14 14:19:02

這不是一棵二叉樹。這是後綴樹的一種實現。 xfree只是free（）的一個包裝。樹會有多個子元素，而不僅僅是二元樹。 – 2010-08-14 14:21:20

編輯我的帖子來說清楚。 – 2010-08-14 14:24:10

如果你需要釋放一棵樹，你需要走它，所以我認爲代碼是正確的。我會以同樣的方式完成它（遞歸地走樹，沿途釋放對象）。我唯一不同的做法是在遞歸之後運行xfree（即交換xfree(current);和freecnt += tree_free(child) + 1;）。因爲現在在刪除節點之前刪除節點，但是我覺得在刪除父節點之前刪除該節點會更好。

此外，您可以擺脫child變量，因爲您只需要使用它一次，並有真正的需求。將爲您節省每個遞歸堆棧空間sizeof(pointer) ;-)

來源

2010-08-14 14:26:12 DarkDust

謝謝。我會試一試 – 2010-08-14 14:30:11

這是一個相當不錯的解決方案。你正在使用子遞歸（這不會太深），但迭代的兄弟姐妹（如果你使用遞歸，將深入）。您的代碼當然可以作爲遞歸解決方案（對於child和next調用tree_free）更優雅，但堆棧溢出的風險將大大增加，所以我認爲您在那裏做出了正確的選擇。

說了這麼多，有沒有必要child可言，如果你重新安排你的操作順序：如果你認爲你的兄弟列表的長度不會那麼大

unsigned int tree_free (struct tree *root) { 
    struct tree *current = NULL, *next = NULL; 
    unsigned int freecnt = 0; 

    current = root; 
    while(current != NULL) 
    { 
     freecnt += tree_free (current->child) + 1; 
     next = current->next; 
     xfree (current); 
     current = next; 
    } 
    return freecnt; 
}

，你可以嘗試優雅的解決方案：

unsigned int tree_free (struct tree *root) { 
    unsigned int freecnt; 

    if (root == NULL) return 0; 
    freecnt = tree_free (root->child) + tree_free (root->next); 
    xfree (root); 
    return freecnt + 1; 
}

這是未經檢驗的，所以我不作任何保證或適用性的聲明，特別是因爲它可能是你的大量SIBL的具體情況危險鏈接。我更多地將它包含爲遞歸的可能性的指示。我的建議是使用第一個。

來源

2010-08-14 14:31:39 paxdiablo

非常感謝你。很高興聽到執行情況良好。再次感謝。 – 2010-08-14 14:34:05

釋放內存 - Visual C

回答

相關問題