我有一个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本身并不存在,但可以在另一个struct中通过继承来使用,例如:
struct ex_node {
struct gr_node _; // "Superclass"
int id;
struct ex_node *union_find_parent;
...
}
有没有一种优雅的方案来创建一个深度复制,包括更新到副本的引用?
注意:嵌套结构的成员不指向它所包含的根结构,而是指向它们相关的嵌套结构(例如,ex_node._.pred.n.next指向ex_edge._.pred)。当这些引用必须更新时,这意味着烦琐的指针算术运算。
我目前的解决方案是:
1. Memcopy所有结构体 2. 遍历所有副本 3. 对于包含引用的所有字段调用一堆宏(由于C中缺少RTTI,我可能无法绕过这个问题) 4. 这些宏使用
- 通过offsetof计算根结构的地址 - 获取复制的等效地址 - 使用offsetof将指针指向正确的嵌套结构
有没有更简单的方法?我也担心在添加更多字段时会忘记添加宏调用。
li_list
是li_node
的“容器”,n
是哨兵。###li_list
和gr_graph
来自一个库; 只有ex_*
是我写的。它的使用方式如下。该技术在这里描述:https://dev59.com/q0XRa4cB1Zd3GeqPveIw ### 您的解决方案仅适用于树,而不适用于图。 - Meinersbur