从动态数组中删除元素 [英] Removing elements from dynamic arrays

问题描述

所以，我有这个：

#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删除动态数组的给定元素。

It's reasonably self-explanatory, remove_element removes a given element of a dynamic array.

您可以看到，每个测试元素都初始化为一个递增整数（即test [n] == n）。但是，程序输出

As you can see, each element of test is initialised to an incrementing integer (that is, test[n] == n). However, the program outputs

16
16

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

. Having removed an element of test, one would expect a call to to test[n] where n >= the removed element would result in what test[n+1] would have been before the removal. So I would expect the output

16
17

。出了什么问题？

编辑：问题现在已经解决。如果有人发现它有用，这里是固定的代码（带有粗略的调试printfs）：

The problem has now been solved. Here's the fixed code (with crude debug printfs), should anyone else find it useful:

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

推荐答案

我在发布的代码，每个代码都可能导致问题：

I see several issues in the posted code, each of which could cause problems:

您的函数正在使用 int *数组，但是在返回新数组之前，您试图在最后将其与 temp 变量交换。这将不起作用，因为您只是替换 int *数组的本地副本，该副本在从函数返回后将消失。

Your function is taking an int* array but then you are trying to swap it with your temp variable at the end prior to returning the new array. This will not work, as you are simply replacing the local copy of int* array which will disappear after you return from the function.

您要么需要以 int ** 的形式传递数组指针，否则就可以在函数中设置指向数组的实际指针，或者，我建议只需为您的函数返回一个int *值
，并返回新数组。

You either need to pass your array pointer in as an int**, which would allow you to set the actual pointer to the array in the function, or, I would suggest just returning a value of int* for your function, and returning the new array.

此外，如此答案，从数组中删除元素时，您甚至不需要重新分配，因为

Also, as mentioned in this answer, you really don't even need to reallocate when deleting an element from the array, since the original array is big enough to hold everything.

1. 您正在使用 sizeof（int *）用于计算数组元素的大小。这可能对某些类型有效，例如，对于 short 数组 sizeof（short *）不起作用。您不希望指向数组的指针大小，而是想要元素的大小，在您的示例中，该大小应为 sizeof（int），尽管这可能不会导致在这种情况下会出现问题。

1. You are using sizeof(int*) for calculating the array element size. This may work for some types, but, for instance, for a short array sizeof(short*) does not work. You don't want the size of the pointer to the array, you want the size of the elements, which for your example should be sizeof(int) although it may not cause problems in this case.

您对数组中的偏移量的长度计算看起来不错，但您忘记将元素数相乘由memcpy的size参数的元素大小决定。例如 memcpy（temp，array，indexToRemove * sizeof（int））; 。

Your length calculation for the offsets into the arrays looks ok, but you're forgetting to multiply the number of elements by the element size for the size parameter of the memcpy. e.g. memcpy(temp, array, indexToRemove * sizeof(int));.

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

Your second call to memcpy is using temp plus the offset as the source array, but it should be array plus the offset.

您对memcpy的第二次调用使用的是 sizeOfArray-indexToRemove 要复制的元素，但您只应复制 SizeOfArray-indexToRemove-1 元素（或（sizeOfArray-indexToRemove-1）* sizeof（int）字节

Your second call to memcpy is using sizeOfArray - indexToRemove for the number of elements to copy, but you should only copy SizeOfArray - indexToRemove - 1 elements (or (sizeOfArray - indexToRemove - 1) * sizeof(int) bytes

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

Wherever you are calculating offsets into the temp and array arrays, you don't need to multiply by sizeof(int), since pointer arithmetic already takes into account the size of the elements. (I missed this at first, thanks to: this answer.)

看着不正确的元素

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

looking at incorrect element

You are printing test[16] (the 17th element) for testing, but you are removing the 16th element, which would be test[15].

也（感谢此答案），您应该处理 indexToRemove == 0 和 indexToRemove的情况==（sizeOfArray-1），您可以在一个memcpy中完成整个删除操作。

Also (thanks to this answer) you should handle the cases where indexToRemove == 0 and indexToRemove == (sizeOfArray - 1), where you can do the entire removal in one memcpy.

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

Also, you need to worry about the case where sizeOfArray == 1. In that case perhaps either allocate a 0 size block of memory, or return null. In my updated code, I chose to allocate a 0-size block, just to differentiate between an array with 0 elements vs. an unallocated array.

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

Returning a 0-size array also means there are no additional changes necessary to the code, because the conditions before each memcpy to handle the first two cases mentioned will prevent either memcpy from taking place.

仅提及，没有错误处理在代码中，因此存在隐式先决条件，即 indexToRemove 是有界的， array 不为空，并且 array 的大小作为 sizeOfArray 传递。

And just to mention, there's no error handling in the code, so there are implicit preconditions that indexToRemove is in bounds, that array is not null, and that array has the size passed as 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 将内存返回给预期免费的用户可能会出现问题 d由用户提供，并具有可用的内存，用户 malloc 可以使用。通常，如果设计代码单元以使内存分配在单个逻辑代码单元中进行处理，则内存管理不太可能造成混乱和难以处理。

a few words on memory management/abstract data types

Finally, something to consider: there are possible issues both with using malloc to return memory to a user that is expected to be freed by the user, and with freeing memory that a user malloced. In general, it's less likely that memory management will be confusing and hard to handle if you design your code units such that memory allocation is handled within a single logical code unit.

例如，您可能会创建一个抽象的数据类型模块，该模块允许您使用保存指针和长度的结构创建整数数组，然后对该数据的所有操作都通过将结构作为第一个参数的函数进行。除了该模块内的内容，这还使您不必进行诸如 elemNumber * sizeof（elemType）之类的计算。像这样的东西：

For instance, you might create an abstract data type module that allowed you to create an integer array using a struct that holds a pointer and a length, and then all manipulation of that data goes through functions taking the structure as a first parameter. This also allows you, except within that module, to avoid having to do calculations like elemNumber * sizeof(elemType). Something like this:

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开发人员确实不喜欢这种习惯用法，但对我来说效果很好。

This is a basically implementing some C++-like functionality in C, and it's IMO a very good idea, especially if you are starting from scratch and you want to create anything more than a very simple application. I know of some C developers that really don't like this idiom, but it has worked well for me.

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

The nice thing about this way of implementing things is that anything in your code that was using the function to remove an element would not ever be touching the pointer directly. This would allow several different parts of your code to store a pointer to your abstract array structure, and when the pointer to the actual data of the array was reallocated after the element was removed, all variables pointing to your abstract array would be automatically updated.

通常，内存管理可能会非常混乱，这是一种可以减少内存管理的策略。只是一个想法。

In general, memory management can be very confusing, and this is one strategy that can make it less so. Just a thought.

这篇关于从动态数组中删除元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！