從指針中取消值

我很久沒有做過指針算術，所以我想我會試着用C來做一個簡單的二叉搜索樹。然而，我無法得到刪除的結果。東西沿着這些路線的作品，因爲我想到：從指針中取消值

typedef struct Node{ 
    int value; 
    struct Node *left; 
    struct Node *right; 
}Node; 

typedef struct Tree{ 
    struct Node* root; 
}Tree; 

int main(){ 
    Tree *tree = createTree(); 

    treeInsert(10, tree); // Inserts 10 at root 
    treeInsert(30, tree); // Inserts 30 to root->right 
    treeInsert(5, tree);  // Inserts 5 to root->left 
    treeInsert(7, tree);  // Inserts 7 to root->left->right 
    treeInsert(12, tree); // Inserts 12 to root->right->left 

    // Removes Node "7" from the tree successfully 
    free(tree->root->left->right); // Free memory for this node in the tree 
    tree->root->left->right = NULL; // Set the pointer to NULL 

    return 0; 
}

我想寫一個nodeDelete(Node *killNode)函數來釋放與節點相關聯的內存，然後指向NULL，但我發現它不喜歡我的工作期待它。

int main(){ 
    // ... snip ... 

    Node *kill = tree->root->left->right // Points kill node to Node "7" 
    free(kill);       // Deallocates memory 
    kill = NULL;       // Points kill to NULL, but keeps 
             // tree->root->left->right **undefined** 
    // ... snip ... 
}

我想我的問題是，我告訴它kill現在指向NULL，它從樹的節點斷開，並不會影響原來的節點指針。我怎麼能告訴它我想指向tree->root->left->right而不是kill而不是NULL？在這種情況下，我需要一個指針指針嗎？

來源

2012-07-26 KChaloux

typedef結構只是不輸入「struct」是一種很糟糕的風格。 – 2012-07-26 13:58:53

@VladLazarenko是嗎？我曾在互聯網上看過它，並認爲這是一種相當普遍的做法。就像我說的，雖然，我是C新手。我在大學裏有一些C++經驗，但我會牢記它。 – KChaloux 2012-07-26 14:02:56

它在Linux編碼風格中有很好的描述（通常不僅適用於C，而且也適用於Linux內核風格）。請參閱第5章 - http://www.kernel.org/doc/Documentation/CodingStyle – 2012-07-26 14:05:42

是的，如果你想刪除該節點，你需要設置tree->root->left->right到NULL。這意味着您不能只將該指針的值傳遞給刪除函數。

你有兩個選擇：您可以將指針傳遞到父節點的被刪除，指令以及有關哪個孩子要刪除：

nodeDelete(Node *parent, int kill_right) 
{ 
    Node *kill; 

    if (kill_right) { 
     kill = parent->right; 
     parent->right = NULL; 
    } else { 
     kill = parent->left; 
     parent->left = NULL; 
    } 

    free(kill); 
}

在這種情況下，你會打電話nodeDelete(tree->root->left, 1);。

或者你可以傳遞一個指針，你要刪除的指針：

nodeDelete(Node **killptr) 
{ 
    free(*killptr); 
    *killptr = NULL; 
}

在這種情況下，你會打電話nodeDelete(&tree->root->left->right);。

來源

2012-07-26 14:07:23 caf

完美！雙指針方法正是我正在尋找的。我不知道它是否在C中。它是否與C++中的引用變量一樣工作？ – KChaloux 2012-07-26 14:10:27

您可能想要使用第二個版本 - 它的方式更短，並且可以刪除第一個版本不能使用的根節點。另外，您可能想要遞歸刪除子節點以避免內存泄漏。 – 2012-07-26 14:14:54

@MartinB這是計劃（遞歸刪除）。 @caf這個例子通過直接傳遞'＆tree-> root-> left-> right'來實現，但是如果我做了類似'Node * kill = tree-> root->的事情，它會失敗（內存空間不會被取消） - > right;'和'nodeDelete（＆kill）'... – KChaloux 2012-07-26 14:16:31

是的，你需要使用雙指針。您還需要確保你遞歸刪除節點的任何孩子都會刪除：

void nodeDelete(Node **killNode) 
{ 
    if(!*killNode) 
     return; 

    // Free child nodes 
    nodeDelete((*killNode)->left); 
    nodeDelete((*killNode)->right); 

    // Free the node itself 
    free(*killNode); 
    *killNode=NULL; 
}

就在開頭的空指針檢查是有意進行 - 這使您不必包裹遞歸調用空指針檢查。

來源

2012-07-26 14:13:22

從指針中取消值

回答

相關問題