爲什麼在我的情況下「malloc」會改變不相關的指針？

我試圖在C中實現一個二叉搜索樹（BST）。我試圖添加幾個元素到BST，但是當我添加第三個時，代碼不起作用。我在gdb中調試它，發現當它爲新節點執行malloc時，第二個節點的父節點從正確的地址值變爲0x13。爲什麼在我的情況下「malloc」會改變不相關的指針？

因爲我覺得有新節點的內存分配和舊節點的父之間沒有關係，我不知道爲什麼會出現這種情況？

這裏是我的InsertBST功能：

int InsertBST(Bst *p, int val) 
{ 
    PNode pnode = (PNode)malloc(sizeof(PNode)); 
    if (pnode != NULL) 
    { 
     pnode->data = val; 
     pnode->lc = NULL; 
     pnode->rc = NULL; 
     if (p->root == NULL) 
     { 
      pnode->parent = NULL; 
      p->root = pnode; 
      p->size++; 
      return 1; 
     } 
     else 
     { 
      PNode tem = FindVal(p->root, val); 
      if (tem != NULL) 
      { 
       printf("Sorry, the value %d has appeared!\n", val); 
       return 0; 
      } 
      else 
      { 
       tem = p->root; 
       while (tem->lc != NULL && tem->rc != NULL) 
       { 
        if (tem->data > val) 
         tem = tem->lc; 
        else 
         tem = tem->rc; 
       } 
       pnode->parent = tem; 
       if (tem->data > val) 
       { 
        tem->lc = pnode; 
       } 
       else 
       { 
        tem->rc = pnode; 
       } 
       p->size++; 
      } 
      return 1; 
     } 
    } 
    else 
    { 
     printf("Allocate memory failed!\n"); 
     return 0; 
    } 
}

p是指針這樣的結構：

typedef struct BST 
{ 
    PNode root; 
    int size; 
}Bst;

和PNode是指針狀THI的結構S：

typedef struct NODE 
{ 
    int data; 
    PNode lc; 
    PNode rc; 
    PNode parent; 
}Node;

來源

2014-01-11 user3162587

是否使用了[內存泄漏]（http://en.wikipedia.org/wiki/Memory_leak）檢測器等[Valgrind的]（HTTP： //valgrind.org/）？你用'gcc -Wall -g'編譯了嗎？你使用'gdb'調試器嗎？你在哪個操作系統上運行（Linux可能更容易）。 –

[不要強制轉換'malloc（）']的返回值（http://stackoverflow.com/questions/605845/do-i-cast-the-result-of-malloc/605858#605858）！ – 2014-01-11 11:59:09

一個很好的例子，說明如何類型化指針類型混淆。不要這樣做，這是不值得的。 'Node *'在你的所有接口中都是完美的。 –

malloc(sizeof(PNode))

將分配需要一個指針的存儲器，而不是它後面的節點結構。

嘗試

malloc(sizeof(*PNode))

或

malloc(sizeof(Node))

來源

2014-01-11 11:57:18

這就是說我分配的空間比需要的少。但是我仍然爲什麼每件事看起來都是正確的，除了樹的父母之外，我仍然感到困惑？你能幫助分析它嗎？ – user3162587

沒有什麼可分析的。假設'malloc（）'和'free（）'管理的內存從地址0x10000開始，而malloc（）需要4個字節用於自己的內務管理，並且指針大小也是4個字節。第一個malloc（）會將4個管家字節寫入0x10000-0x10003，並返回地址0x10004，並記住下一個塊從0x10008開始。第二個malloc將使用0x10008-0x1000b作爲管家，並返回0x1000c給你。現在，當您寫入第一個>數據時，您將寫入0x10004-0x1000c。當你寫入first-> lc時，你在0x100008處覆蓋malloc（）的內部數據。 –

當你寫入first-> rc時，你寫入0x1000c，恰好與second-> data存儲地址相同。當然，細節取決於malloc實現，指針大小等等，但我想可以肯定地說'PNodes背後的節點共享相同的內存，因此寫入一個節點的一個組件將寫入不同的組件還有一個不同的節點「。 –

爲什麼在我的情況下「malloc」會改變不相關的指針？

回答

相關問題