图结构的深度复制

Question

图结构的深度复制

5

我有一个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将指针指向正确的嵌套结构

有没有更简单的方法？我也担心在添加更多字段时会忘记添加宏调用。

- Meinersbur

4个回答

1

我认为你无法进行深拷贝，因为指针会被分配一个内存地址，最好的方法是简单地分配一个新的图形结构并复制数据（而不是指针），并通过malloc新指针，并调整ex_node结构中的指针。这将是更彻底的解决方案...

希望对你有所帮助，此致敬礼，汤姆。

- t0mm13b

这个方案比我概述的方案要好在哪里？ - Meinersbur

@Meinersbur：我认为 'offsetof' 是用来计算结构体成员的偏移量（以字节为单位），并将其作为 size_t 值返回，所以我不确定使用 offsetof 是否是正确的方法...顺便说一句，我并不是在反对你的解决方案，我的回答只是对你所做的事情的抽象观点... - t0mm13b

1

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

现在遍历所有副本。对于所有复制的结构体中的指针变量，搜索排序列表并用其副本的地址替换它。

- Niraj Nawanit

我有一个更简单的解决方案（对我来说已经足够了）：每个 ex_* 都有一个成员 copy，它存储了一个指向副本的引用。当我有原始引用时，我也有副本的引用，无需查找（排序）列表。 - Meinersbur

对于为您定义的结构，它是有效的。但是考虑到库提供的结构。假设它没有被您定义的结构直接引用？在这种情况下，您需要将这些结构的副本引用存储到某个地方。 - Niraj Nawanit

0

是的，有一种优雅的解决方案，可以使用生成树和装饰器模式。

-首先，构建图的生成树。您可以使用DFS（深度优先搜索）或BFS（广度优先搜索）来实现此目的。使用装饰器模式为每个访问的节点分配唯一标识符。

-接下来（或同时），从头到尾遍历生成树，并通过分配新节点并连接形成生成树的边来开始构建第二棵树。

-最后，通过同步标识符再次遍历生成树，在新图中连接剩余缺失的边，使它们与旧图的连通性匹配。（例如，如果图1中的节点5具有连接到节点7和节点11的边，则使用图2的排序将其节点5连接到其节点7和11。）

- optikradio

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- dirkgently · Accepted Answer

听起来不错。我的建议是：

我不确定为什么你需要同时使用li_list和li_node。此外，你难道不需要一个li_node的数据成员吗？
总体结构看起来有点复杂（当然，我不知道你的要求），并且带有C++风格的设计（如果我错了，请原谅我）。
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);

并嵌套类型调用适当的成员复制方法...