为什么我得到这段代码的分段错误？

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()]。