从动态数组中删除元素

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 的每个元素都被初始化为一个递增的整数（即 test[n] == n）。然而，程序输出

16
16

. 删除了 test 的一个元素后，人们会期望调用 test[n]，其中 n >= 删除的元素将导致 test[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* 数组，但随后您尝试将其与您的 temp< /code> 变量位于返回新数组之前的末尾。这不起作用，因为您只是替换 int* array 的本地副本，该副本在您从函数返回后会消失。

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

另外，正如这个答案中提到的，从数组中删除元素时，您甚至不需要重新分配，因为原始数组足够大，可以容纳所有内容。

大小和偏移量计算

1. 您正在使用 sizeof(int*) 来计算数组元素大小。这可能适用于某些类型，但是，例如，对于 short 数组，sizeof(short*) 不起作用。您不需要指向数组的指针的大小，您需要元素的大小，对于您的示例来说应该是 sizeof(int) 尽管在这种情况下它可能不会导致问题。< /p>

2. 数组偏移量的长度计算看起来不错，但您忘记将元素数量乘以 memcpy 的大小参数的元素大小。例如memcpy(temp, array, indexToRemove * sizeof(int));。

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

4. 您对 memcpy 的第二次调用使用 sizeOfArray - indexToRemove 作为要复制的元素数量，但您应该只复制 SizeOfArray - indexToRemove - 1 元素（或 >(sizeOfArray - indexToRemove - 1) * sizeof(int) 字节

5. 无论在哪里计算临时数组和数组的偏移量，都不需要乘以 sizeof(int)，因为指针算术已经考虑了元素的大小（我一开始就错过了这一点，这要归功于：这个答案。）

查看不正确的元素

您正在打印 test[16] （第 17 个元素）进行测试，但您正在删除第 16 个元素，这将是测试[15]。

极端情况

另外（感谢这个答案）你应该处理这些情况其中 indexToRemove == 0 和 indexToRemove == (sizeOfArray - 1)，您可以一次完成整个删除操作内存拷贝。

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

返回 0 大小的数组还意味着无需对代码进行任何额外更改，因为处理前面提到的前两种情况的每个 memcpy 之前的条件将阻止任一 memcpy 发生。

顺便提一下，代码中没有错误处理，因此存在隐式先决条件：indexToRemove 在边界内、array 不为 null 以及 array 的大小作为 sizeOfArray 传递。

示例更新了代码

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

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]);
    
    test = remove_element(test, howMany, 16);
    --howMany;
    
    printf("%d\n", test[16]);

    free(test);
    
    return 0;
}

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

最后，需要考虑的事情：使用 malloc 将内存返回给预计可以免费的用户< /code>由用户分配，并释放用户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++ 的功能，在我看来这是一个非常好的主意，特别是如果您从头开始并且您想要创建的不仅仅是一个非常简单的应用程序。我知道一些 C 开发人员确实不喜欢这个习惯用法，但它对我来说效果很好。

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

一般来说，内存管理可能非常令人困惑，而这是一种可以减少这种混乱的策略。只是一个想法。

Answer 2

您实际上并没有更改传递的指针。您只是更改了数组的副本。

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. */
}

因此，在函数之后，数组仍然指向它曾经指向的位置，但是，您也释放了它，这雪上加霜。

尝试这样的操作：

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

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

还有一个 C FAQ：更改传递的指针。

Answer 3

@cnicutar 是对的（+1），但是，你也写了：

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

虽然它应该是：

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

因为乘以 int* 的大小是由编译器完成的（这是指针算术）

另外，当移动时覆盖内存区域，请使用 memmove 而不是 memcpy。

Answer 4

此外：第二个 memcpy 调用的第二个参数应该基于 array，而不是 temp，对吧？既然您的数组存储的是整数而不是指针，那么您不应该基于 sizeof int 而不是基于 sizeof int* 进行内存分配和复制吗？难道您不需要将要复制的字节数（memcpy 的最后一个参数）乘以 sizeof int 吗？

另外，请注意 indexToRemove == 0 的情况。

Answer 5

该代码存在一些问题：

(a) 分配内存时，您需要确保使用 sizeof 的正确类型。例如，对于 int 数组，您分配一个大小为 sizeof(int) 倍数的内存块。所以：

int* test = malloc(howMany * sizeof(int*));

应该是：

int* test = malloc(howMany * sizeof(int));

(b) 您没有在 main 末尾释放数组的内存。

(c) memcpy 将要复制的字节数作为第三个参数。因此，您需要再次确保传递 sizeof(int) 的倍数。所以：

memcpy(temp, array, cnt);

应该是：

memcpy(temp, array, cnt * sizeof(int));

(d) 将项目从旧数组复制到新数组时，请确保复制正确的数据。例如，索引 indexToRemove 处的项目之前有 indexToRemove 项目，一个都不能少。同样，您需要确保在需要删除的项目之后复制正确数量的项目。

(e) 当增加指针时，您不需要乘以 sizeof(int) - 这是隐式为您完成的。所以：

temp + (cnt * sizeof(int))

实际上应该是：

temp + cnt

(f) 在您的 remove_element 函数中，您将一个值分配给局部变量 array。对局部变量的任何更改在函数外部都是不可见的。因此，在对 remove_element 的调用结束后，您将不会在 main 中看到更改。解决此问题的一种方法是从函数返回新指针，并将其分配到 main 中：

test = remove_element(test, howMany, 16);

Answer 6

所有其他答案都很好地说明了代码中的各种问题/错误。

但是，为什么要重新分配（并不是所有错误都与重新分配有关）？ “较小”的数组将很好地适合现有的内存块：

// Note: untested (not even compiled) code; it also doesn't do any
//   checks for overflow, parameter validation, etc.
int remove_element(int* array, int sizeOfArray, int indexToRemove)
{
    // assuming that sizeOfArray is the count of valid elements in the array
    int elements_to_move = sizeOfArray - indexToRemove - 1;

    memmove( &array[indexToRemove], &array[indexToRemove+1], elements_to_move * sizeof(array[0]));

    // let the caller know how many elements remain in the array
    //  of course, they could figure this out themselves...
    return sizeOfArray - 1;
}