0

我有一个结构。

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)但是我想这将通过回答前者来解决。

代码

4

2 回答 2

2

浅拷贝相当于复制引用而不是值。但是，这需要稍微不同地定义结构：

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 中创建两个堆，它们将相互影响。创建副本仍然是最佳实践。

于 2020-06-10T23:01:59.990 回答
-1

你的想法很好——实现不了。

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然后取消引用它。

于 2020-06-11T00:00:14.093 回答