我现在正在实现Barnes-Hut Algorithms以模拟N体问题。我只想问一下建筑树部分。
我为它构建树有两个功能。
我递归地构建树,并在构建时打印每个节点的数据,一切似乎都正确,但是当程序返回到主函数时,只有树的根和根的子级存储该值。其他节点的值未存储,这很奇怪,因为我在递归过程中打印了它们,所以它们应该已经存储了。
这里是经过修改的部分代码,我认为问题可能出在哪里:
#include<...>
typedef struct node{
int data;
struct node *child1,*child2;
}Node;
Node root; // a global variable
int main(){
.
set_root_and_build(); // is called not only once cuz it's actually in a loop
traverse(&root);
.
}
这里是函数set_root_and_build():
我已将子指针设置为NULL,但最初并未显示它。
void set_root_and_build(){
root.data = ...;
..// set child1 and child2 =NULL;
build(&root,...); // ... part are values of data for it's child
}
和构建:
void build(Node *n,...){
Node *new1, *new2 ;
new1 = (Node*)malloc(sizeof(Node));
new2 = (Node*)malloc(sizeof(Node));
... // (set data of new1 and new2 **,also their children are set NULL**)
if(some condition holds for child1){ // else no link, so n->child1 should be NULL
build(new1,...);
n->child1 = new1;
//for debugging, print data of n->child1 & and->child2
}
if(some condition holds for child2){ // else no link, so n->child2 should be NULL
build(new2,...);
n->child1 = new2;
//for debugging, print data of n->child1 & and->child2
}
}
树中的节点可能有1〜2个孩子,这里不是全部都有2个孩子。
程序在build()
函数递归中时将打印出正确的数据,但是当它返回到主函数并调用traverse()
时,由于分段错误而失败。
[我试图在traverse()
中打印所有内容,发现只有root和root.child1,root.child2像我之前提到的那样存储值。
由于必须多次调用build()
,甚至并行调用,所以不能将new1和new2定义为全局变量。 (但我认为它们不会在这里引起问题)。
有人知道哪里出了问题吗?
带有调试信息的遍历部分:
void traverse(Node n){
...//print out data of n
if(n.child1!=NULL)
traverse(*(n.child1))
...//same for child2
}
当条件不成立时,您可能没有正确设置n
的子级。您可能需要这样:
void set_root_and_build()
{
root.data = ...;
build(&root,...); // ... part are values of data for it's child
}
void build(Node *n,...)
{
n->child1 = n->child2 = NULL;
Node *new1, *new2;
new1 = (Node*) malloc(sizeof(Node));
new2 = (Node*) malloc(sizeof(Node));
// set data of new1 and new2 somehow (read from stdin?)
if (some condition holds for new1)
{
n->child1 = new1;
build(n->child1,...);
//for debugging, print data of n->child1
}
else
free(new1); // or whatever else you need to do to reclaim new1
if (some condition holds for new2)
{
n->child2 = new2;
build(n->child2,...);
//for debugging, print data of n->child2
}
else
free(new2); // or whatever else you need to do to reclaim new2
}
当然,您应该检查malloc()的返回值并处理错误。
此外,您的遍历有点奇怪,因为它遍历是复制而不是引用。您这样做有充分的理由吗?如果没有,那么也许您想要:
void traverse(Node *n)
{
...//print out data of n
if (n->child1 != NULL)
traverse(n->child1)
...//same for child2
}
您的树遍历中的问题是,您肯定会处理树,直到找到一个节点指针为NULL。
[不幸的是,在创建节点时,既没有使用malloc()
也没有使用new
初始化它们(它将用calloc()
初始化,但是cpp代码中的这种做法与malloc()
一样糟糕)。因此,遍历继续在虚无指针的虚无循环中循环/递归。
我建议您利用cpp的优势,并将您的结构稍微更改为:
struct Node { // that's C++: no need for typedef
int data;
struct node *child1,*child2;
Node() : data(0), child1(nullptr), child2(nullptr) {} // Makes sure that every created are first initalized
};
然后删除旧的malloc。并构造代码以避免不必要的分配:
if(some condition holds for child1){ // else no link, so n->child1 should be NULL
new1=new Node; // if you init it here, no need to free in an else !!
build(new1,...);
n->child1 = new1;
...
}
if (... child2) { ... }
但是请注意,分配给new
的诗人应与delete
一起释放,并注意与free()
一起。
编辑:您的代码段不匹配:
traverse(&root); // you send here a Node*
void traverse(Node n){ // but your function defines an argument by value !
...
}
请检查您是否没有超出编译器的某些警告,并且您的代码中没有滥用的强制转换。