从动态数组中删除元素

所以，我有这个：

#include  #include  #include  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  #include  #include  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 *值，并返回新arrays。

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

大小和偏移计算

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) bytes

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发生。

而且，在代码中没有error handling，因此存在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的用户以及用户malloc编辑的free内存可能存在问题。 一般而言，如果您设计代码单元以便在单个逻辑代码单元内处理内存分配，则内存管理不太可能令人困惑且难以处理。

例如，您可以创建一个抽象数据类型模块，该模块允许您使用包含指针和长度的结构创建整数数组，然后对该数据的所有操作都通过将结构作为第一个参数的函数进行。 除了在该模块中，这也允许您避免必须执行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 ++的function，而且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：更改传递指针 。

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进行mallocing和复制，而不是基于sizeof int* ，因为你的数组存储整数而不是指针？ 你不需要将sizeof int复制的字节数（ memcpy的最后一个参数）乘以吗？

另外，观察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项之前有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; }