从动态数组中删除元素

Question

所以,我有这个:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void remove_element(int* array, int sizeOfArray, int indexToRemove)
{
    int* temp = malloc((sizeOfArray - 1) * sizeof(int*)); // allocate an array with a size 1 less than the current one
    memcpy(temp, array, indexToRemove - 1); // copy everything BEFORE the index
    memcpy(temp+(indexToRemove * sizeof(int*)), temp+((indexToRemove+1) * sizeof(int*)), sizeOfArray - indexToRemove); // copy everything AFTER the index
    free (array);
    array = temp;
}

int main()
{
    int howMany = 20;
    int* test = malloc(howMany * sizeof(int*));


    for (int i = 0; i < howMany; ++i)
        (test[i]) = i;



    printf("%d\n", test[16]);
    remove_element(test, howMany, 16);
    --howMany;
    printf("%d\n", test[16]);
    return 0;
}

它是相当不言自明的,remove_element删除动态数组的给定元素.

如您所见,测试的每个元素都初始化为递增整数(即test [n] == n).但是,该计划输出

16
16

.删除了一个测试元素后,人们会期望调用[n],其中n> =删除的元素将导致删除之前的测试[n + 1].所以我期待输出

16
17

.出了什么问题？

编辑:问题现在已经解决了.这是固定代码(使用原始调试printfs),如果其他人发现它有用:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int remove_element(int** array, int sizeOfArray, int indexToRemove)
{
    printf("Beginning processing. Array is currently: ");
    for (int i = 0; i < sizeOfArray; ++i)
        printf("%d ", (*array)[i]);
    printf("\n");

    int* temp = malloc((sizeOfArray - 1) * sizeof(int)); // allocate an array with a size 1 less than the current one

    memmove(
            temp,
            *array,
            (indexToRemove+1)*sizeof(int)); // copy everything BEFORE the index

    memmove(
            temp+indexToRemove,
            (*array)+(indexToRemove+1),
            (sizeOfArray - indexToRemove)*sizeof(int)); // copy everything AFTER the index


    printf("Processing done. Array is currently: ");
    for (int i = 0; i < sizeOfArray - 1; ++i)
        printf("%d ", (temp)[i]);
    printf("\n");

    free (*array);
    *array = temp;
    return 0;

}

int main()
{
    int howMany = 20;
    int* test = malloc(howMany * sizeof(int*));


    for (int i = 0; i < howMany; ++i)
        (test[i]) = i;



    printf("%d\n", test[16]);
    remove_element(&test, howMany, 14);
    --howMany;
    printf("%d\n", test[16]);
    return 0;
}

Answer 1

我在发布的代码中看到了几个问题,每个问题都可能导致问题:

返回新数组

你的函数正在运行int* array但是你在尝试temp在返回新数组之前将它与你的变量交换.这不起作用,因为您只是替换int* array从函数返回后将消失的本地副本.

您需要将数组指针作为一个传递int**,这将允许您在函数中设置指向数组的实际指针,或者,我建议只返回函数的int*值,并返回新数组.

此外,正如本回答中所提到的,当从数组中删除元素时,您甚至不需要重新分配,因为原始数组足以容纳所有内容.

大小和偏移计算

1. 您sizeof(int*)用于计算数组元素大小.这可能适用于某些类型,但是,例如,short数组sizeof(short*)不起作用.你不希望指向数组的指针的大小,你想要的元素的大小,这应该是你的例子,sizeof(int)虽然它可能不会导致这种情况下的问题.

2. 对数组中的偏移量的长度计算看起来没问题,但是您忘记将元素的数量乘以memcpy的size参数的元素大小.例如memcpy(temp, array, indexToRemove * sizeof(int));.

3. 你对memcpy的第二次调用是使用temp加上偏移量作为源数组,但它应该array加上偏移量.

4. 你对memcpy的第二次调用是sizeOfArray - indexToRemove用于复制的元素数量,但你应该只复制SizeOfArray - indexToRemove - 1元素(或(sizeOfArray - indexToRemove - 1) * sizeof(int)字节

5. 无论在计算temp和数组数组的偏移量时,都不需要乘以sizeof(int),因为指针算法已经考虑了元素的大小.(我最初错过了这个,感谢:这个答案.)

看着不正确的元素

您正在打印test[16](第17个元素)进行测试,但是您要删除第16个元素test[15].

角落案件

也(感谢这个答案),你应该处理这种情况的案件indexToRemove == 0和indexToRemove == (sizeOfArray - 1),在那里你可以做一个memcpy的整个拆除.

另外,你需要担心的情​​况sizeOfArray == 1.在这种情况下,可能要么分配0大小的内存块,要么返回null.在我更新的代码中,我选择分配一个0大小的块,只是为了区分具有0个元素的数组与未分配的数组.

返回0大小的数组也意味着代码不需要进行其他更改,因为在每个memcpy之前处理前两种情况的条件将阻止memcpy发生.

而且,在代码中没有错误处理,因此有一些隐含的前提条件indexToRemove在边界中,array不是null,并且array传递的大小为sizeOfArray.

示例更新代码

int* remove_element(int* array, int sizeOfArray, int indexToRemove)
{
    int* temp = malloc((sizeOfArray - 1) * sizeof(int)); // allocate an array with a size 1 less than the current one

    if (indexToRemove != 0)
        memcpy(temp, array, indexToRemove * sizeof(int)); // copy everything BEFORE the index

    if (indexToRemove != (sizeOfArray - 1))
        memcpy(temp+indexToRemove, array+indexToRemove+1, (sizeOfArray - indexToRemove - 1) * sizeof(int)); // copy everything AFTER the index

    free (array);
    return temp;
}

int main()
{
    int howMany = 20;
    int* test = malloc(howMany * sizeof(int*));

    for (int i = 0; i < howMany; ++i)
        (test[i]) = i;

    printf("%d\n", test[16]);
    remove_element(test, howMany, 16);
    --howMany;
    printf("%d\n", test[16]);
    return 0;
}

关于内存管理/抽象数据类型的几句话

最后,需要考虑的事项:使用malloc将内存返回给用户期望free的用户以及free用户malloc编辑的内存可能存在问题.通常,如果您设计代码单元以便在单个逻辑代码单元内处理内存分配,则内存管理不太可能令人困惑且难以处理.

例如,您可以创建一个抽象数据类型模块,该模块允许您使用包含指针和长度的结构创建整数数组,然后对该数据的所有操作都通过将结构作为第一个参数的函数进行.除了在该模块中,这也允许您避免必须进行类似的计算elemNumber * sizeof(elemType).像这样的东西:

struct MyIntArray
{
   int* ArrHead;
   int ElementSize;

   // if you wanted support for resizing without reallocating you might also
   //   have your Create function take an initialBufferSize, and:
   // int BufferSize;
};

void MyIntArray_Create(struct MyIntArray* This, int numElems /*, int initBuffSize */);
void MyIntArray_Destroy(struct MyIntArray* This);
bool MyIntArray_RemoveElement(struct MyIntArray* This, int index);
bool MyIntArray_InsertElement(string MyIntArray* THis, int index, int Value);

等等

这基本上是在C中实现一些类似C++的功能,而且IMO是一个非常好的主意,特别是如果你从头开始并且你想创建的东西不仅仅是一个非常简单的应用程序.我知道有些C开发人员真的不喜欢这个习语,但它对我来说效果很好.

这种实现方式的好处是代码中使用该函数删除元素的任何东西都不会直接触及指针.这将允许代码的几个不同部分存储指向抽象数组结构的指针,并且在删除元素后重新分配指向数组实际数据的指针时,将自动更新指向抽象数组的所有变量.

一般来说,内存管理可能会非常混乱,而这是一种可以减少内存管理的策略.只是一个想法.

Answer 2

您实际上并没有更改传递的指针.你只能改变你的副本中array.

void remove_element(int* array, int sizeOfArray, int indexToRemove)
{
    int* temp = malloc((sizeOfArray - 1) * sizeof(int*));

    free (array); /* Destroys the array the caller gave you. */
    array = temp; /* Temp is lost. This has **no effect** for the caller. */
}

因此,在该函数之后,数组仍然指向它用于指向BUT的位置,您还释放了它,这增加了对伤害的侮辱.

尝试这样的事情:

void remove_element(int **array, int sizeOfArray, int indexToRemove)
                        ^^
{
    int *temp = malloc((sizeOfArray - 1) * sizeof(int*));
    /* More stuff. */

    free(*array);
    *array = temp;
}

还有一个C FAQ:更改传递指针.