图结构的深层复制

Question

我在C中有一个图形结构,并希望对其进行深度复制(包括节点和边缘).

结构如下所示:

struct li_list {
    struct li_node n;
};

struct li_node {
    struct li_node *next, *prev;
};

struct gr_graph {
    struct li_list nodes;
    int nodecount;
};

struct gr_node {
    struct li_node node;
    struct gr_graph *graph;
    int pred_count, succ_count;
    struct li_list pred, succ;
};

struct gr_edge {
    struct li_node succ, pred;
    struct gr_node *from, *to;
    unsigned long marks;
};

这些结构本身并不存在,而是在另一个结构中"继承",如下所示:

struct ex_node {
    struct gr_node _; // "Superclass"
    int id;
    struct ex_node *union_find_parent;
    ...
}

是否有一个优雅的解决方案来创建这样的结构的深层副本,包括更新对副本的引用？

注意:嵌套结构的成员不指向它包含的根结构,而是指向它们相关的嵌套结构(例如,ex_node._.pred.n.next指向a ex_edge._.pred).当必须更新这些时,这意味着繁琐的指针算法.

到目前为止我的解决方案是

1. 记忆所有结构
2. 迭代所有副本
3. 为包含引用的所有字段调用一堆宏(由于C中缺少RTTI,我可能不会这样做)
4. 宏使用
   • offsetof 计算根结构的地址
   • 检索复制的等效项的地址
   • offsetof 使指针指向正确的嵌套结构

有没有更简单的方法来做到这一点？我还害怕在添加更多字段时忘记添加宏调用.

Answer 1

我认为你本身不能进行深层复制，因为指针将有一个分配给指针的内存地址，我能想到的深层复制的最佳方法是简单地分配一个新的图形结构并复制数据（不是指针）并通过新指针构建它malloc并调整结构中的指针ex_node。这将是一个更彻底的解决方案......

希望这有帮助，最诚挚的问候，汤姆。