如何对一个数组进行浅层复制，并将该副本存储在一个结构中。

Question

我有一个结构。

typedef struct Heap {
    int length;
    int size;
    int A[];
} Heap;

我试图对一个给定的数组进行浅层复制，并将其存储在这个结构中。这样，当数组被改变或元素交换时，就会在原数组中进行镜像。

Heap * build_max_heap(int A[], int length) {
    Heap * heap = malloc(sizeof(Heap) + length*sizeof(int *));
    *heap = (Heap) { length, length };
    memcpy(heap->A, A, length*sizeof(int *));

    /*
    for(int i = floor(((heap->length)-1)/2); i >= 0; --i) {
        max_heapify(heap, i);
    }
    */

    return heap;
}

int main() {
    int A[] = {0, 3, 7, 61, 3, 40, 4, -1, 8, 10};

    Heap * heap = build_max_heap(A, 10);

    A[0] = 100;

    for(int i = 0; i < 10; ++i) {
        printf("%i, ", A[i]);
    }

    printf("\n");

    for(int i = 0; i < 10; ++i) {
        printf("%i, ", heap->A[i]);
    }

    return 0;
}

目前返回的结果如下。

100, 3, 7, 61, 3, 40, 4, -1, 8, 10,
0, 3, 7, 61, 3, 40, 4, -1, 8, 10,

我期望的结果是

100, 3, 7, 61, 3, 40, 4, -1, 8, 10,
100, 3, 7, 61, 3, 40, 4, -1, 8, 10,

同样 heap->A[0] = 100; 应该有同样的效果。我也不确定 length*sizeof(int *) 是正确的还是应该改成 length*sizeof(int) 然而我想这将通过回答前者来解决。

编码

Answer 1

浅层复制相当于复制引用而不是值。但是，这就需要用不同的方式来定义这个结构。

typedef struct Heap {
    int length;
    int size;
    int *A;
} Heap;

这样一来，数组的值 A 并不包含在结构体之后，我们可以自由地分配任何指针给它。然后，我们只需将堆初始化为。

Heap * build_max_heap(int A[], int length) {
    Heap * heap = malloc(sizeof(Heap));
    *heap = (Heap) { length, length, A };
    /* ... heapify code etc ... */
    return heap;
}

但你必须谨慎使用这个方法 -- 这意味着如果你从A中创建两个堆，它们会互相影响。最好的做法还是创建一个副本。

Answer 2

你的想法是好的--实现却不是。

typedef struct Heap {
    size_t length;
    size_t size;
    int A[];
} Heap;

Heap *build_max_heap(int *A, size_t length) {
    Heap * heap = malloc(sizeof(*heap) + length*sizeof(*A));
    *heap = (Heap) { length, length };
    memcpy(heap-> A, A, length*sizeof(*A));

    /* another stuff */

    return heap;
}

这种在结构末尾添加数据的结构是很常见的。我只允许一个分配（和一个空闲）而不是两个。它也更有效率，因为它不需要读取指针。A 然后再去引用它。