将此实现转换为 C 代码的最有效方法是什么?我真的是 C++ 新手,我想使用链接剪切树,因为它的效率很高。
#include <cstdio>
using namespace std;
struct Node
{ int sz, label; /* size, label */
Node *p, *pp, *l, *r; /* parent, path-parent, left, right pointers */
Node() { p = pp = l = r = 0; }
};
void update(Node *x)
{ x->sz = 1;
if(x->l) x->sz += x->l->sz;
if(x->r) x->sz += x->r->sz;
}
void rotr(Node *x)
{ Node *y, *z;
y = x->p, z = y->p;
if((y->l = x->r)) y->l->p = y;
x->r = y, y->p = x;
if((x->p = z))
{ if(y == z->l) z->l = x;
else z->r = x;
}
x->pp = y->pp;
y->pp = 0;
update(y);
}
void rotl(Node *x)
{ Node *y, *z;
y = x->p, z = y->p;
if((y->r = x->l)) y->r->p = y;
x->l = y, y->p = x;
if((x->p = z))
{ if(y == z->l) z->l = x;
else z->r = x;
}
x->pp = y->pp;
y->pp = 0;
update(y);
}
void splay(Node *x)
{ Node *y, *z;
while(x->p)
{ y = x->p;
if(y->p == 0)
{ if(x == y->l) rotr(x);
else rotl(x);
}
else
{ z = y->p;
if(y == z->l)
{ if(x == y->l) rotr(y), rotr(x);
else rotl(x), rotr(x);
}
else
{ if(x == y->r) rotl(y), rotl(x);
else rotr(x), rotl(x);
}
}
}
update(x);
}
Node *access(Node *x)
{ splay(x);
if(x->r)
{ x->r->pp = x;
x->r->p = 0;
x->r = 0;
update(x);
}
Node *last = x;
while(x->pp)
{ Node *y = x->pp;
last = y;
splay(y);
if(y->r)
{ y->r->pp = y;
y->r->p = 0;
}
y->r = x;
x->p = y;
x->pp = 0;
update(y);
splay(x);
}
return last;
}
Node *root(Node *x)
{ access(x);
while(x->l) x = x->l;
splay(x);
return x;
}
void cut(Node *x)
{ access(x);
x->l->p = 0;
x->l = 0;
update(x);
}
void link(Node *x, Node *y)
{ access(x);
access(y);
x->l = y;
y->p = x;
update(x);
}
Node *lca(Node *x, Node *y)
{ access(x);
return access(y);
}
int depth(Node *x)
{ access(x);
return x->sz - 1;
}
class LinkCut
{ Node *x;
public:
LinkCut(int n)
{ x = new Node[n];
for(int i = 0; i < n; i++)
{ x[i].label = i;
update(&x[i]);
}
}
virtual ~LinkCut()
{ delete[] x;
}
void link(int u, int v)
{ ::link(&x[u], &x[v]);
}
void cut(int u)
{ ::cut(&x[u]);
}
int root(int u)
{ return ::root(&x[u])->label;
}
int depth(int u)
{ return ::depth(&x[u]);
}
int lca(int u, int v)
{ return ::lca(&x[u], &x[v])->label;
}
};
int main(void)
{ return 0;
}
描述:链接切割树
链接切割树的 C++ 实现。链接切割树数据结构维护受以下操作约束的节点森林:
link(x, y):让以x为根的树成为y的子树, cut(x): 删除连接 x 到其父节点的边。 可以使用以下操作查询树:
root(x):找到包含x的树的根, path(x):计算根到 x 路径上节点的函数。 所有操作都需要 O(lg n) 摊销时间。 root(x) 可用于测试连通性。在此实现中,路径函数计算节点在其树中的深度。可以使用函数 lca(x, y) 回答动态最低祖先查询。
界面
For all 0 <= x, y < n,
LinkCut tree(n); /* new link-cut tree with n nodes / tree.link(x, y); / link x and y / tree.cut(x); / cut x / tree.root(x); / root of tree containing x / tree.depth(x); / depth of x in its tree / tree.lca(x, y); / lowest common ancestor of x and y */
最佳答案
以下是我可以看到的以当前形式在 C 中编译的此 C++ 代码的障碍:
Node
结构类型在很多地方都简称为Node
,而不是struct Node
。通过添加typedef struct Node Node;
声明进行修复。Node
有一个构造函数。您可以取消它,只需手动进行初始化。LinkCut
有一个析构函数。这无法在 C 中模拟,因此您可以动态分配所有LinkCut
实例,并最终由void destroy_link_cut_tree(struct LinkCut*)
之类的函数销毁释放Node
实例使用的内存。LinkCut
有一个构造函数。您可以将其替换为类似struct LinkCut* make_link_cut_tree(int)
的函数。new
用于为Node
对象数组分配内存。将其替换为malloc
并手动进行初始化。LinkCut
有成员函数。将这些替换为带有LinkCut*
参数的自由函数。这也将迫使您为它们赋予与作用于各个节点的名称不同的名称,因此您将不再需要::
来消除歧义。
关于c++ - 将链接切割树的 C++ 实现转换为 C,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/43669178/