我正试图为展开树编写一个c++模板结构,但是当我尝试测试代码时,我得到了非常奇怪的结果。
这是我的模板代码:template <class T>
struct splaytree {
struct node {
splaytree<T> *tree;
node *p, *c[2];
T v;
int w;
node(T t, splaytree<T> *st) {
v = t;
p = 0;
c[0] = 0;
c[1] = 0;
w = 1;
tree = st;
}
int side() {
return (p->c[1] == this) ? 1:0;
}
void r() {
node *x = this;
int b = x->side();
node *p = x->p;
x->w = p->w;
p->w = x->c[1^b]->w + 1 + p->c[1^b]->w;
x->p = p->p;
p->p = x;
p->c[0^b] = x->c[1^b];
x->c[1^b] = p;
}
void splay() {
node *x = this;
while (x->p) {
node *p = x->p;
if (p == tree->root) x->r();
else if (((x->side())^(p->side()))) {
x->r();
x->r();
}
else {
p->r();
x->r();
}
}
tree->root = this;
}
int index() {
this->splay();
return this->c[0]->w;
}
};
node *root;
splaytree() {
root = 0;
}
void add(T k) {
node x0(k,this);
node *x = &x0;
if (root == 0) {
root = x;
return;
}
node *i = root;
while (i != x) {
int b = (k < i->v) ? 0:1;
if (i->c[b] == 0) {
i->c[b] = x;
i->w++;
x->p = i;
}
i = i->c[b];
}
x->splay();
}
};
我用这个来测试它:
int main() {
splaytree<int> st;
st.add(2);
cout << st.root->v << endl;
cout << st.root->v << endl;
st.add(3);
cout << st.root->c[0] << endl;
}
插入元素2,然后打印根节点的值两次。不知何故,这两个打印给了我两个不同的值(2和10在Ideone的http://ideone.com/RxZMyA)。当我在我的计算机上运行这个程序时,它给我的结果是2和1875691072。在这两种情况下,当在2之后插入3时,根节点的左子节点是一个空指针,而它应该是一个包含2的节点对象。
有人能告诉我为什么我得到两个不同的值时打印相同的东西两次,我能做些什么,使我的splaytree.add()函数的工作如期进行?谢谢!
After
node x0(k,this);
node *x = &x0;
if (root == 0) {
root = x;
return;
}
root
是一个局部变量的地址。当您打印root->v
时,x0
已经超出了范围。
root
真正指向什么的赌注都结束了。