c++ - 将链接剪切树的C++实现转换为C

将这种实现转换为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）来回答。

接口


  对于所有0   
  LinkCut树（n）； / *具有n个节点的新的链接剪切树/ tree.link（x，y）;
  /链接x和y / tree.cut（x）; /剪切x / tree.root（x）; /的根
  包含x的树/ tree.depth（x）; / x在其树中的深度/
  tree.lca（x，y）; / x和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/