关于C语言实现动态数组，数组元素地址不连续的问题

Question

我现在实现的动态数组元素，实际上并没有连续内存地址，我不知该怎么处理能让元素地址连续。

我的动态数组定义：

typedef struct DArray DArray;
struct DArray {
    void* *data;
    uint capacity;
    uint data_size;
};

数组创建代码：

DArray* __attribute__((overloadable)) DArray_create(int capacity) {
    
    DArray *array = malloc(sizeof(DArray));
    guard_mem(array);
    
    guard(capacity > 0, "You must set an capacity > 0.");
    
    array->data = calloc(capacity, sizeof(void *));
    guard_mem(array->data);
    
    array->data_size = 0;
    array->capacity = capacity;
    
    return array;
    
error:
    if (array) {
        free(array);
    }
    return NULL;
}

DArray* __attribute__((overloadable)) DArray_create(void) {
    return DArray_create(10);
}

元素添加代码：

int DArray_resize(DArray *array, int newCapacity) {
    
    array->data = realloc(array->data, newCapacity * sizeof(void *));
    array->capacity = newCapacity;
    
    guard_mem(array->data);
    
    return 0;
    
error:
    return -1;
}

int DArray_add(DArray *array, int index, void *element) {
    
    guard(index >= 0 && index <= array->data_size, "Add failed. Require index >= 0 and index <= size.");
    
    if (array->data_size == array->capacity) {
        DArray_resize(array, 2 * (array->capacity));
    }
    
    for (int i = array->data_size - 1; i > index; i--) {
        array->data[i+1] = array->data[i];
    }
    
    array->data[index] = element;
    
    array->data_size += 1;
    
    return 0;
error:
    return -1;
}

main函数测试用例：

    int array [10] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    
    DArray *dArray = DArray_create();
    for (int i = 0; i < 10; i++) {
        DArray_addLast(dArray, &array[i]);
    }
    
    DArray_printInfo(dArray);
    for (int i = 0; i < DArray_getSize(dArray); i++) {
        printf("%d, ", *((int *)DArray_getElementAt(dArray, i)));
    }
    printf("\n");
    printf("index 9 address: %p", DArray_getElementAt(dArray, 9));
    printf("\n");
    printf("----------------");
    printf("\n");
    
    int array2 [2] = { 10, 11 };
    DArray_addLast(dArray, &array2[0]);
    DArray_printInfo(dArray);
    for (int i = 0; i < DArray_getSize(dArray); i++) {
        printf("%d, ", *((int *)DArray_getElementAt(dArray, i)));
        
    }
    printf("\n");
    printf("index 10 address: %p", DArray_getElementAt(dArray, 10));
    printf("\n");
    printf("----------------\n");

输出结果：

Array size = 10, capacity = 10 

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 

index 9 address: 0x7ffeefbff554

----------------

Array size = 11, capacity = 20 

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 

index 10 address: 0x7ffeefbff528

----------------

可以看到，第10个元素和新添加的第11个元素的内存地址不连续。事实上，在添加的时候，也是用两个数组的元素地址对其赋值的，所以肯定是不连续的。不知道老师有没有能让其地址连续的设计？

Answer 1

liuyubobobo 2018-08-02 11:19:51

我果然可能没有理解你的意思。。。

在添加第11个元素的时候，触发了resize，所以此时array->data的地址可能发生改变。测试一下，在出发了resize以后，index9的地址是不是也变了？其实，index9和index10的地址是连续的，只不过新的index10的地址不和旧的index9的地址连续？

• 提问者 daxuexinsheng #1

  是这样的。动态数组里的 void * 是连续的，但是 void * 只想的对象是不连续的。

• 提问者 daxuexinsheng #2

  动态数组里 记录对象的地址的 地址 是连续的，但是对象的地址是随意指的。

• liuyubobobo 回复 提问者 daxuexinsheng #3

  那是自然的。数组是一个连续空间。你设计的每一个空间都存储一个指针。指针指向的地址当然不连续。但是这些指针是连续存储的。这是数组是连续空间的意思。

点开查看后面7条评论