爲什麼我得到這段代碼的分段錯誤？

Question

嘗試在C中創建一個簡單的矩形/ bin包裝器。獲取給定區域並找到任何給定大小的矩形的位置。

約4次遞歸是當我得到分段錯誤。

#include <stdio.h> 
#include <stdlib.h> 

typedef struct node_type PackNode; 
struct node_type { 
int x , y; 
int width , height; 
int used; 
struct node_type *left; 
struct node_type *right; 
}; 

typedef struct point_type PackPoint; 
struct point_type { 
int x,y; 
}; 


PackNode _clone(PackNode *node) { 
PackNode clone; 
clone.used = 0; 
clone.x = node->x; 
clone.y = node->y; 
clone.width = node->width; 
clone.height= node->height; 
clone.left = NULL; 
clone.right= NULL; 
return clone; 
} 
PackNode root; 
int rcount; 

PackPoint* recursiveFind(PackNode *node, int w, int h) { 
PackPoint rp; 
PackPoint *p = NULL; 
rcount++; 
printf ("rcount = %u\n", rcount); 


//left is not null go to left, if left didn't work try right. 
if (node->left!=NULL) { 
    //move down to left branch 

    p = recursiveFind(node->left, w, h); 
    if (p!=NULL) { 
    return p; 
    } else { 
    p = recursiveFind(node->right, w, h); 
    return p; 
    } 

} else { 
    //If used just return null and possible go to the right branch; 
    if (node->used==1 || w > node->width || h > node->height) { 

    return p; 
    } 

    //if current node is exact size and hasn't been used it return the x,y of the mid-point of the rectangle 
    if (w==node->width && h == node->height) { 

    node->used=1; 


    rp.x = node->x+(w/2); 
    rp.y = node->y+(h/2); 

    p = &rp; 
    return p; 
    } 


    //If rectangle wasn't exact fit, create branches from cloning it's parent. 

    PackNode l_clone = _clone(node); 
    PackNode r_clone = _clone(node); 
    node->left = &l_clone; 
    node->right = &r_clone; 

    //adjust branches accordingly, split up the current unused areas 
    if ((node->width - w) > (node->height - h)) 
    { 
    node->left->width = w; 
    node->right->x = node->x + w; 
    node->right->width = node->width - w; 

    } else { 
    node->left->height = h; 
    node->right->y = node->y + h; 
    node->right->height = node->height - h; 
    } 

    p = recursiveFind(node->left, w, h); 
    return p; 
} 
return p; 
} 





int main(void) { 
root = malloc(
root.x=0; 
root.y=0; 
root.used=0; 
root.width=1000; 
root.height=1000; 
root.left=NULL; 
root.right=NULL; 


int i; 
PackPoint *pnt; 
int rw; 
int rh; 
for (i=0;i<10;i++) { 
    rw = random()%20+1; 
    rh = random()%20+1; 
    pnt = recursiveFind(&root, rw, rh); 
    printf("pnt.x,y: %d,%d\n",pnt->x,pnt->y); 
} 



return 0; 

} 

Answer 1

沒有在你的代碼仔細觀察，你可以嘗試使用一個工具，如Valgrind的或GDB找出行數/表達導致分段錯誤。你可以從那裏向後工作。 「給男人一條魚;你今天喂他。教一個人去釣魚;和你喂他一輩子」

Answer 2

if (node->left!=NULL) { 
    //move down to left branch 

    p = recursiveFind(node->left, w, h); 
    if (p!=NULL) { 
    return p; 
    } else { 
    p = recursiveFind(node->right, w, h); 

你永遠不會檢查是否節點 - >右爲NULL，所以接下來的遞歸可解除引用NULL。

Answer 3

你在這種情況下返回一個指針到一個局部變量：

//if current node is exact size and hasn't been used it return the x,y of the mid-point of the rectangle 
    if (w==node->width && h == node->height) { 

    node->used=1; 


    rp.x = node->x+(w/2); 
    rp.y = node->y+(h/2); 

    p = &rp; 
    return p; 
    } 

這是一個大禁忌。局部變量在函數返回後不再有效，所以你正在返回的指針指向堆棧內存，現在可能被用於別的東西。當你開始做這些事情時，你會破壞你的堆棧，並且你的程序會開始非常不正常。

要解決這個問題，你需要做的幾件事情之一：（1）具有recursiveFind()返回，而不是一個指向PackNode一個PackNode通過值; （2）使用全局/靜態的PackNode實例，並返回一個指針（注意這會使得recursiveFind()非線程安全）;或（3）返回指向動態分配的PackNode（例如與malloc()一起分配）的實例的指針;這就要求recursiveFind()的調用者在稍後不再需要的時候在返回的指針上調用free()。

同樣，這段代碼也有錯：

//If rectangle wasn't exact fit, create branches from cloning it's parent. 

    PackNode l_clone = _clone(node); 
    PackNode r_clone = _clone(node); 
    node->left = &l_clone; 
    node->right = &r_clone; 

您需要在堆中分配l_clone和r_clone，不是在棧中，因爲再次，一旦這個函數返回時，那些node指針將不更有效。我建議讓_clone()返回一個指向PackNode（分配爲malloc()）而不是完整的PackNode對象的指針。但是，如果你這樣做，調用代碼需要知道在稍後不再需要該對象時在返回的指針上調用free()。

[此外，全局範圍以下劃線開頭的標識符由實現保留，因此您應該避免使用這些名稱;您應該將_clone()重命名爲clone()或clonePackNode()]。