c - C 中的动态数组函数 - 设置容量并创建更大的数组

Question

我正在用 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;
}

Answer 1

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

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

#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 中受益。