1

我正在为 C 中的动态数组构建函数。在大多数情况下，它们似乎工作正常，直到需要扩展数组的容量。我的函数 _dynArrSetCapacity 似乎有两个问题。 

/* Resizes the underlying array to be the size cap

param:  v       pointer to the dynamic array
param:  cap     the new desired capacity
pre:    v is not null
post:   v has capacity newCap
*/
void _dynArrSetCapacity(DynArr *v, int newCap)
{
    assert(v != NULL);
    struct DynArr largerArray; /*create a new dynamic array*/
    initDynArr(&largerArray, newCap); /*initialize the new array*/
    int i;
    /*copy the old array into the new array*/
    for(i = 0; i < v->size; i++) {
       largerArray->data[i] = v->data[i];
       largerArray->size++;
    }
freeDynArr(v); /*free memory of the old array*/
v = &largerArray; /*point to the new array*/
}

首先，对于 for 循环中的两个语句中的每一个，我都收到错误消息“'->' 的类型参数无效（具有结构 DynArr）”。这是一个突然出现的新错误，尽管我没有对这个特定的功能进行更改，并且最初并没有给我这个错误。其次，当这个函数返回到调用它的函数时，数组的大小和容量会恢复到原来的值。我的陈述“v = &largerArray;” 似乎没有达到预期的效果，即将新数组的所有指针和值都分配给 v。下面提供了完整的代码以供上下文。任何解决这两个问题的建议将不胜感激。提前致谢。

#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 */
};


/* ************************************************************************
Dynamic Array Functions
 ************************************************************************ */

/* Initialize (including allocation of data array) dynamic array.

param:  v       pointer to the dynamic array
param:  cap     capacity of the dynamic array
pre:    v is not null
post:   internal data array can hold cap elements
post:   v->data is not null
*/
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;
}

    /* Allocate and initialize dynamic array.

param:  cap     desired capacity for the dyn array
pre:    none
post:   none
ret:    a non-null pointer to a dynArr of cap capacity
        and 0 elements in it.
    */
DynArr* newDynArr(int cap)
{
    assert(cap > 0);
    DynArr *r = (DynArr *)malloc(sizeof( DynArr));
    assert(r != 0);
    initDynArr(r,cap);
    return r;
}

/* Deallocate data array in dynamic array.

param:  v       pointer to the dynamic array
pre:    none
post:   d.data points to null
post:   size and capacity are 0
post:   the memory used by v->data is freed
*/
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;
}

/* Deallocate data array and the dynamic array ure.

param:  v       pointer to the dynamic array
pre:    none
post:   the memory used by v->data is freed
post:   the memory used by d is freed
*/
void deleteDynArr(DynArr *v)
{
    freeDynArr(v);
    free(v);
}

/* Resizes the underlying array to be the size cap

param:  v       pointer to the dynamic array
param:  cap     the new desired capacity
pre:    v is not null
post:   v has capacity newCap
*/
void _dynArrSetCapacity(DynArr *v, int newCap)
 {
    assert(v != NULL);
        struct DynArr largerArray; /*create a new dynamic array*/
    initDynArr(&largerArray, newCap); /*initialize the new array*/
    int i;
    /*copy the old array into the new array*/
    for(i = 0; i < v->size; i++) {
       largerArray->data[i] = v->data[i];
       largerArray->size++;
}

     freeDynArr(v); /*free memory of the old array*/
     v = &largerArray; /*point to the new array*/
}

/* Get the size of the dynamic array

param:  v       pointer to the dynamic array
pre:    v is not null
post:   none
ret:    the size of the dynamic array
*/
int sizeDynArr(DynArr *v)
{
    int i;
     v->size = 0;
     for (i = 0; i < v->capacity; i++) {
         if (!(EQ(v->data[i], NULL))) {
            v->size++;
    }
}
return v->size;
}

 /*     Adds an element to the end of the dynamic array

param:  v       pointer to the dynamic array
param:  val     the value to add to the end of the dynamic array
pre:    the dynArry is not null
post:   size increases by 1
post:   if reached capacity, capacity is doubled
post:   val is in the last utilized position in the array*/
void addDynArr(DynArr *v, TYPE val)
{
    /* Check to see if a resize is necessary */
    assert(v != NULL);

   if(v->size >= v->capacity) {
           _dynArrSetCapacity(v, 2 * v->capacity);
   }
   v->data[v->size] = val;
   printf("Added %d to Array to position %d\n", v->data[v->size], v->size);
   v->size++;
}

/*  Get an element from the dynamic array from a specified position

param:  v       pointer to the dynamic array
param:  pos     integer index to get the element from
pre:    v is not null
pre:    v is not empty
pre:    pos < size of the dyn array and >= 0
post:   no changes to the dyn Array
ret:    value stored at index pos
*/

TYPE getDynArr(DynArr *v, int pos)
{
   assert(pos < v->size && pos >= 0);
   return v->data[pos];
}

/*  Put an item into the dynamic array at the specified location,
overwriting the element that was there

param:  v       pointer to the dynamic array
param:  pos     the index to put the value into
param:  val     the value to insert
pre:    v is not null
pre:    v is not empty
pre:    pos >= 0 and pos < size of the array
post:   index pos contains new value, val
*/
void putDynArr(DynArr *v, int pos, TYPE val)
{
    assert(pos >= 0 && pos < v->size);

    v->data[pos] = val;
    v->size++;
}

/*  Swap two specified elements in the dynamic array

param:  v       pointer to the dynamic array
param:  i,j     the elements to be swapped
pre:    v is not null
pre:    v is not empty
pre:    i, j >= 0 and i,j < size of the dynamic array
post:   index i now holds the value at j and index j now holds the value at i
 */
void swapDynArr(DynArr *v, int i, int  j)
{
    int temp = 0;
    assert(i >= 0 && i < v->size);
    assert(j >= 0 && j < v->size);
    temp = v->data[i];
    v->data[i] = v->data[j];
    v->data[j] = temp;

}

/*  Remove the element at the specified location from the array,
shifts other elements back one to fill the gap

param:  v       pointer to the dynamic array
param:  idx     location of element to remove
pre:    v is not null
pre:    v is not empty
pre:    idx < size and idx >= 0
post:   the element at idx is removed
post:   the elements past idx are moved back one
*/
 void removeAtDynArr(DynArr *v, int idx)
{
    int i;
    assert(idx < v->size && idx >= 0);

        printf("%d is being removed from array\n", v->data[idx]);
    v->data[idx] = 0;
    for (i = idx; i < v->size; i++) {
        v->data[i] = v->data[i + 1];
    }

    v->size--;
    v->data[v->size+1] = NULL;
}



/* ************************************************************************
    Stack Interface Functions
************************************************************************ */

/*  Returns boolean (encoded in an int) demonstrating whether or not the
dynamic array stack has an item on it.

param:  v       pointer to the dynamic array
pre:    the dynArr is not null
post:   none
ret:    1 if empty, otherwise 0
*/
int isEmptyDynArr(DynArr *v)
{
   if(v->size == 0) return 1;
       return 0;
}

/*  Push an element onto the top of the stack

param:  v       pointer to the dynamic array
param:  val     the value to push onto the stack
pre:    v is not null
post:   size increases by 1
        if reached capacity, capacity is doubled
        val is on the top of the stack
*/
void pushDynArr(DynArr *v, TYPE val)
{
    addDynArr(v, val);
    printf("Pushed %d on Stack\n",val);
}

/*  Returns the element at the top of the stack

param:  v       pointer to the dynamic array
pre:    v is not null
pre:    v is not empty
post:   no changes to the stack
*/
TYPE topDynArr(DynArr *v)
{
    assert(sizeDynArr(v) != 0);
    return getDynArr(v, sizeDynArr(v) - 1);
}

/* Removes the element on top of the stack

param:  v       pointer to the dynamic array
pre:    v is not null
pre:    v is not empty
post:   size is decremented by 1
        the top has been removed
*/
void popDynArr(DynArr *v)
{
    assert(sizeDynArr(v) != 0);
    removeAtDynArr(v, sizeDynArr(v) - 1);
    v->size--;
}

/* ************************************************************************
Bag Interface Functions
 ************************************************************************ */

/*  Returns boolean (encoded as an int) demonstrating whether or not
the specified value is in the collection
true = 1
false = 0

param:  v       pointer to the dynamic array
param:  val     the value to look for in the bag
pre:    v is not null
pre:    v is not empty
post:   no changes to the bag
*/
int containsDynArr(DynArr *v, TYPE val)
{

int i;
    for (i = 0; i < v->size; i++) {
        if(EQ(v->data[i], val)) {
            return 1;
        }
     }
    return 0;
}

/*  Removes the first occurrence of the specified value from the collection
if it occurs

param:  v       pointer to the dynamic array
param:  val     the value to remove from the array
pre:    v is not null
pre:    v is not empty
post:   val has been removed
post:   size of the bag is reduced by 1
 */
 void removeDynArr(DynArr *v, TYPE val)
 {
    int i;
    for (i = 0; i < v->size; i++) {
            if (EQ(val, v->data[i])) {
                 removeAtDynArr(v, i);
                 return;
            }
    }
}

int main(int argc, char** argv){
    printf("Program: Dynamically-allocated Array\n");
    int cap = 10;
    int i;

DynArr *r;
r = newDynArr(cap);


    for (i = 0; i < cap; i++) {
        pushDynArr(r, i);
    }

    r->size = sizeDynArr(r);
    if(isEmptyDynArr(r) == 1) {
        printf("Array is empty\n");
    }

    else if(isEmptyDynArr(r) == 0) {
        printf("Array is not empty\n");
    }
    removeDynArr(r, 5);

    printf("Before adding to array, size is %d and capacity is %d\n", r->size, r->capacity);
    printf("The top of the array before push is %d\n", topDynArr(r));

    for (i = r->size; i < cap + 4; i++) {
       pushDynArr(r,i);
    }

    printf("After adding to array, size is %d and capacity is %d\n", r->size, r->capacity);
    printf("The top of the array after push is %d\n", topDynArr(r));

    printf("The top of the array before remove is %d\n", topDynArr(r));
    printf("Before removing from array, size is %d and capacity is %d\n", r->size, r->capacity);

    for (i = r->size; i < cap; i++) {
        pushDynArr(r,i);
    }

    printf("After removing from array, size is %d and capacity is %d\n", r->size, r->capacity);
    printf("The top of the array after remove is %d\n", topDynArr(r));

    if (containsDynArr(r, 3) == 1) {
        printf("Value 30 is in the array.\n");
    }

    printf("The top of the array before pop is %d\n", topDynArr(r));
    popDynArr(r);
    printf("The top of the array after pop is %d\n", topDynArr(r));

deleteDynArr(r);

   return 0;
}
4

3 回答 3

2

struct DynArr largerArray是一个栈变量，它只存在于当前栈中。指向堆栈上的内存地址v = &largerArray。v然后你的函数返回并且堆栈被销毁，所以v指向不存在的内存，当其他函数回收这个堆栈空间时，它将被进一步覆盖。

您也永远不会真正创建动态数组。

DynArr *r;
initDynArr(r, cap);

r是一个指向 DynArray 的指针，这是它的类型，但是您没有将它初始化为实际指向这样的数组，并initDynArr()假设它r已经指向 DynArray，但事实并非如此，它未初始化。正确的要么是

DynArr r;
initDynArr(&r, cap);

在这种情况下 DynArray 存在于堆栈中或

DynArr *r = malloc(sizeof(*r));
initDynArr(r, cap);

在这种情况下 DynArray 存在于堆上。

你的代码在内存管理方面有很多错误，我什至不知道从哪里开始。

也许你应该看看这个页面。这个人已经实现了你在这里尝试实现的东西。

于 2013-01-19T03:35:32.107 回答
2

忘记堆栈。largerArray是自动管理的。该对象将在_dynArrSetCapacity返回时被销毁。

当你传递给 C 中的函数时，你是按值传递的。这意味着该函数接收新对象中的数据副本，而不是旧对象。如果更改新对象，旧对象将保持不变。v = &largerArray;无效，因为v是副本，而不是原件。请注意，在下面的示例中， in 与inint x不是parse_by_value_example同一个对象int x。main

#include <stdio.h>
int parse_by_value_example(int x);
int main(void) {
    int x = 0, y;
    y = parse_by_value_example(x);
    printf("Value of x: %d. Value of y: %d\n", x, y);
    return 0;
}
int parse_by_value_example(int x) {
    x = 42;
    return x;
}

我认为您混淆了 C 中“数组”的定义。在 C 中，数组是sizeof (array)元素数量和元素大小的乘积，整个数组是一个连续的分配。例如，以下代码不会导致任何断言失败：

size_t array_capacity = 42;
int array[array_capacity];
assert(sizeof (array) == sizeof (array_capacity) * sizeof (array[0]));

数组[]下标运算符实际上是一个指针下标运算符；数组衰减为指针，除非它们在诸如 之类的表达式中&array，sizeof (array)或者它们在初始化中使用。

你在看哪本书？看来你遇到了麻烦。我有信心，只要您在遇到它们时进行练习（不要跳过它们），您将从 K&R 2E 中受益。

于 2013-01-19T03:52:02.907 回答
0

在_dynArrSetCapacity中，您只需将本地指针更改v为指向您的本地堆栈变量，这不会影响 . 指向的真实数据v。你需要使用

*v = largerArray;

从 复制largerArray。

于 2013-01-19T03:49:49.040 回答