代码之家 › 专栏 › 技术社区 › Meinersbur

图结构的深度复制

Meinersbur · 技术社区 · 15 年前

结构如下:

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 ). 这意味着当必须更新这些指针时,需要进行繁琐的指针运算。

到目前为止我的解决办法是

Memcopy所有结构
遍历所有副本
宏使用
- offsetof 计算根结构的地址
- 抵消 使指针指向正确的嵌套结构

4 回复 | 直到 15 年前

t0mm13b 15 年前

我不认为你可以做深度复制,因为指针会有一个内存地址分配给指针,我能想到的最好的方法就是简单地分配一个新的图结构,复制数据(不是指针),然后从那里建立它 malloc ex_node 结构。那将是一个更彻底的解决办法。。。

希望这有帮助, 谨致问候,

dirkgently 15 年前

听起来不错。我的0.02美元:

不知道你为什么两样都需要 li_list li_node . 此外,您不需要一个数据成员来 李丘节点
memcpy 不是必需的。一个简单的任务就足够了。

所以:

struct foo {
   int datum;
   int *p;
   foo_copy pfoo;
};

typedef void (*foo_copy)(const struct foo *src, struct foo *dst);

void foo_cp(const struct foo *src, struct foo *dst)
{ 
    *dst = *src; // copy non-pointer data
    dst->p = malloc(sizeof *dst->p);
    dst->p = *src->p;
}


// somewhere else
struct foo s;
// initalize
struct foo *t = malloc(sizeof *t);  
s.copy(&s, &t);

Niraj Nawanit 15 年前

memcpy所有结构并创建一个排序列表,其中每个条目包含原始结构的地址和结构副本的地址。

现在迭代所有副本。对于所有复制的结构中的每个指针变量,在排序列表中搜索指针并将其替换为其副本的地址。

optikradio 12 年前

-首先,建立图的生成树。您可以使用DFS(深度优先搜索) 每个访问过的节点都有一个唯一的标识符。

通过分配新节点并连接,开始构建第二棵树形成生成树的边。

-最后,再对生成树进行一次遍历,并使用标识符,连接新图形中剩余的缺失边,以便它们与旧图的连通性。使用graph2的顺序将其node5连接到node7和11。)