c - 在结构中重新分配数组

Question

我正在为学校编写一个程序，该程序要求我们创建一个结构，该结构具有一个整数数组以及两个整数变量 capacity 和 size，它们跟踪(您猜对了)数组的大小和容量。当我需要为数组重新分配空间时，问题就开始了(教授不希望我们使用 realloc)。这是代码...

dynamicArray.h文件

#ifndef DYNAMIC_ARRAY_INCLUDED
#define DYNAMIC_ARRAY_INCLUDED 1

#ifndef __TYPE
#define __TYPE
# define TYPE int
# endif

typedef struct DynArr DynArr;

/* Dynamic Array Functions */
void initDynArr(DynArr *v, int capacity);
DynArr *newDynArr(int cap);

void freeDynArr(DynArr *v);
void deleteDynArr(DynArr *v);

int sizeDynArr(DynArr *v);

void addDynArr(DynArr *v, TYPE val);    

#endif

dynamicArray.c文件

#include <assert.h>
#include <stdlib.h>
#include "dynArray.h"

struct DynArr
{
    TYPE *data;     /* pointer to the data array */
    int size;       /* Number of elements in the array */
    int capacity;   /* capacity ofthe array */
};

void printArray(DynArr *v)
{
    for (int i = 0; i < v->size; i++)
    {
        printf("%d, ", v->data[i]);

    }
    printf("\n");
}

void addDynArr(DynArr *v, TYPE val)
{
    /* checking that v has been initialized*/
    assert(v != 0);

    /*check if capacity is reached and increase if necessary*/
    if(v->size >= v->capacity)
    {
        _dynArrSetCapacity(v, (v->capacity) * 2);
    }

    /*add new value to array*/
    v->data[v->size] = val;

    /*increment size of array*/
    v->size++;

}

void _dynArrSetCapacity(DynArr *v, int newCap)
{
    /*check that v is initialized*/
    assert(v!=0);

    /*create temporary array with new capacity*/
    DynArr *tmp = newDynArr(newCap);

    /*copy contents of v to new array*/
    for (int i = 0; i < v->size; i++)
    {
        tmp->data[i] = v->data[i];
        tmp->size++;
    }

    /*delete contents of old array*/
    deleteDynArr(v);

    /*assign address of new array to v*/
    v = tmp;
}

void deleteDynArr(DynArr *v)
{
    freeDynArr(v);
    free(v);
}

void freeDynArr(DynArr *v)
{
    if(v->data != 0)
    {
        free(v->data);  /* free the space on the heap */
        v->data = 0;    /* make it point to null */
    }
    v->size = 0;
    v->capacity = 0;
}

DynArr *newDynArr(int cap)
{
    assert(cap > 0);
    DynArr *r = (DynArr *)malloc(sizeof( DynArr));
    assert(r != 0);
    initDynArr(r,cap);
    return r;
}

void initDynArr(DynArr *v, int capacity)
{
    assert(capacity > 0);
    assert(v!= 0);
    v->data = (TYPE *) malloc(sizeof(TYPE) * capacity);
    assert(v->data != 0);
    v->size = 0;
    v->capacity = capacity;
}

main.c 文件

#include <stdio.h>
#include <stdlib.h>
#include "dynArray.h"

#define TYPE int

int main(int argc, char* argv[]){

    DynArr *dyn;
    dyn = newDynArr(2);

    printf("\n\nTesting addDynArr...\n");
    addDynArr(dyn, 3);
    printArray(dyn);
    addDynArr(dyn, 4);
    printArray(dyn);
    addDynArr(dyn, 10);
    printArray(dyn);
    addDynArr(dyn, 5);
    printArray(dyn);
    addDynArr(dyn, 6);
    printArray(dyn);

    return 0;
}

我删减了代码(我知道它看起来可能不像)所以这是我的问题的要点。我在 dynamicArray.c 文件中遇到段错误。具体在这个函数中

void addDynArr(DynArr *v, TYPE val)
{
    /* checking that v has been initialized*/
    assert(v != 0);

    /*check if capacity is reached and increase if necessary*/
    if(v->size >= v->capacity)
    {
        _dynArrSetCapacity(v, (v->capacity) * 2);
    }

    /*add new value to array*/
    v->data[v->size] = val;

    /*increment size of array*/
    v->size++;

}

在 v->data[v->size] = val;线。我确实注意到，当我在前面提到的代码行之前检查 v->size 的值时，它会返回垃圾值。这让我觉得，当我将 v 传递给 _dynArrSetCapacity 函数时，它是按值而不是按引用传递的，但我看不出这是怎么可能的。任何帮助将不胜感激。

Answer 1

问题出在 void _dynArrSetCapacity(DynArr *v, int newCap) 中。您可能需要检查所有涉及内存重新分配的函数是否存在类似问题。

从技术上讲，C 中没有引用，因此每个参数都是按值传递或复制的。但是你复制的是指针，而不是整个 DynArray 对象。这意味着当您执行 deleteDynArray() 时，内存会像您预期的那样消失，但是当您到达 v = tmp; 时，它会更改本地 v(本地副本)而不是传入的 v。然后当您返回 v->data[v->size] = val;，您可能正在访问尚未分配的内存，从而导致错误。

最快的解决方法(IMO 虽然不是最好的)是对任何像这样进行释放的函数使用双指针而不是单个指针:

void _dynArrSetCapacity(DynArr **v, int newCap)
{
    DynArr *tmp = newDynArr(newCap);

    /*copy contents of v to new array*/
    ......
    /*delete contents of old array*/
    deleteDynArr(*v);

    /*assign address of new array to v*/
    *v = tmp;
    (*v)->size = newCap;
}

还有一个替代方案，我认为这可能更好。您不必重新分配整个对象。只是 DynArray 对象中包含所有相关对象的内存块:TYPE *data

void _dynArrSetCapacity(DynArr *v, int newCap)
{
    TYPE *tmp = (TYPE*)malloc(sizeof(Type) * newCap);

    /*copy contents of v to new array*/
    for (int i = 0; i < v->size; ++i)
        tmp[i] = v->data[i];
    /*delete contents of old array*/
    free(v->data);

    /*assign address of new array to v*/
    v->data = tmp;
    v->size = newCap;
}