c - 使用指向结构 "x"的 struct "x"来创建指向结构 "y"的结构 "y"

Question

假设我的 B+ 树节点结构如下:

typedef struct node 
{
    struct node * pointers; //pointers to child nodes
    int * keys; //keys in this node
    struct node * parent; //pointer to parent node
    bool is_leaf; //is the node a leaf
    int num_keys; //number of keys in this node
} node; 

还有一个新的结构，称为索引，其节点结构如下:

typedef struct index
{
    int m; //number of keys in this index
    bool flag; //does the node POINTS to a leaf
    struct index * parent_index; //pointer to parent index
    int * k; //keys in this index
    struct index * p; //pointers to child indexes
} index;

假设我按顺序输入简单的键 2、3 和 1，以启动并实现 B+ 树结构。现在我们制作了一个简单的 B+ 树来表示 2、3 和 1 个键之间的关系。现在我想将这种关系复制到一个新的结构中，即 index 。我可以导航到每个 node B+ 树并创建 int node->num_keys前往int index->m , bool node->is_leaf可以帮助实现bool index->flag经过一些思考和int * node->keys前往int * index->k 。正如您所看到的，问题始于剩下的两个指针...... 我怎样才能获得一个具有在它们之间创建关系的指针的复杂结构，并将相同的关系复制到具有相同行为的新复杂结构？

Answer 1

您需要一个克隆数据结构的递归函数。总体思路是每次调用递归函数都会复制复杂结构的一部分，但调用一个函数对每个“子”对象执行操作。特殊情况是被调用的函数可能是它本身。对于您的示例，它可能类似于:

node * copy_node(node *n) {
    node *r = malloc(sizeof(*n));
    r->num_keys = n->num_keys;
    r->is_leaf = n->is_leaf;
    r->keys = malloc(sizeof(int)*r->num_keys);
    r->pointers = malloc(sizeof(node *)*r->num_keys);
    for (int i=0; i<r->num_keys; i++) {
        r->keys[i] = n->keys[i];
        r->pointers[i] = copy_node(n->pointers[i]);
        r->pointers[i]->parent = r;
    }
    return r;
}

可以构建类似的函数来克隆index。