在C语言中删除数组元素

Question

我对 C 语言中的数组有一个简单的问题：

从数组中删除元素并使数组变小的最佳方法是什么。

例如：该数组的大小为 n，然后我取出数组中的一些元素，那么数组的大小将减少取出的元素个数。

基本上，我把这个数组当做一副扑克牌来处理，一旦我从牌堆顶部取走一张牌，它就不应该在那里了。

编辑：在今天结束之前，我会把自己逼疯的，感谢所有的帮助，我尝试过值交换但是没有成功。

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

enum faces { Ace = 0, Jack = 10, Queen, King };
char *facecheck(int d); 
int draw(int deck, int i); 

int main() { 
    int deck[52], i, n;
    char suits[4][9] = {
        "Hearts",
        "Diamonds",
        "Clubs",
        "Spades"
    };

    n = 0;

    for (i = 0; i < 52; i++) {
        deck[i] = n;
        n++;
    };

    for (i = 0; i < 52; i++) {       
        if (i % 13 == 0 || i % 13 == 10 || i % 13 == 11 || i % 13 == 12)
            printf("%s ", facecheck(i % 13));
        else
            printf("%d ", i % 13 + 1);
        printf("of %s \n", suits[i / 13]);
    }

    draw(deck, i);

    return 0; 
}  

char *facecheck(int d) {
    static char *face[] = {
        "Ace",
        "Jack",
        "Queen",
        "King"
    };

    if (d == Ace)
        return face[0];
    else {
        if (d == Jack) 
            return face[1];
        else {
            if (d == Queen)
                return face[2];
            else { 
                if (d == King)
                    return face[3];
            }
        }
    } 
}

int draw(int deck, int i) { 
    int hand[5], j, temp[j];

    for (i = 0; i < 52; i++) {
        j = i
    }; 

    for (i = 0; i < 5; i++) {
        deck[i] = hand[]; 
        printf("A card has been drawn \n");
        deck[i] = temp[j - 1];
        temp[j] = deck[i];
    };
      
    return deck;
}

- Rini Posny

---

如果你真的想让它“变小”，实现一个链表。否则，进行一些值交换并在数组中保留一个“数组结尾”保护值。你不能从普通数组中简单地删除一个元素。 - user1898811

如果您每次更改数组时都要使用realloc或memcpy，性能的折衷是可怕的。 - Joe Frambach

不要理会那些反对者——memcpy 是正确的选择。（虽然如果你真的只是从“顶部取一张卡片”，那么就使用一个简单的堆栈——将“顶部”设置为数组的末尾，并在每次“弹出”“堆栈”时减少表示其长度的值。） - Hot Licks

@JoeFrambach 因为存在重叠内存复制，所以 memcpy() 无法正常工作。正确的方法是使用 memmove()。 - KRoy

Answer 1

实际上有两个不同的问题。第一个是保持数组元素的正确顺序，以便在删除元素后没有“空洞”。第二个是调整数组本身的大小。

C中的数组被分配为固定数量的连续元素。实际上无法删除数组中单个元素使用的内存，但可以将元素移动以填充删除元素造成的空洞。例如：

void remove_element(array_type *array, int index, int array_length)
{
   int i;
   for(i = index; i < array_length - 1; i++) array[i] = array[i + 1];
}

静态分配的数组无法调整大小。动态分配的数组可以使用realloc()函数调整大小。这可能会将整个数组移动到内存中的另一个位置，因此指向数组或其元素的所有指针都必须更新。例如：

remove_element(array, index, array_length);  /* First shift the elements, then reallocate */
array_type *tmp = realloc(array, (array_length - 1) * sizeof(array_type) );
if (tmp == NULL && array_length > 1) {
   /* No memory available */
   exit(EXIT_FAILURE);
}
array_length = array_length - 1;
array = tmp;

如果请求的大小为0或存在错误，realloc将返回一个空指针。否则，它会返回重新分配数组的指针。临时指针用于在调用realloc时检测错误，因为除了退出之外，也可以仅仅保留原始数组。当realloc无法重新分配数组时，它不会更改原始数组。

请注意，如果数组很大或者删除了很多元素，这两个操作都会非常缓慢。如果高效的插入和删除是优先考虑的，则可以使用其他数据结构，例如链表和哈希表。

- Ben

---

在第一个例子中，由于删除操作，数组长度会发生变化，因此将数组长度作为指针传递似乎是合理的，对吗？因此它变成了 (... int *array_length) 并且在函数体末尾：(*array_length)--; - Eddie's

被移除的项目的地址会发生什么？它会自动被释放吗？特别是当我们删除一个引用对象的项目时。 - mazunki

Answer 2

你需要哪种解决方案取决于你是否希望数组保留其顺序。

通常情况下，你不仅拥有数组指针，还有一个变量保存其当前逻辑大小以及一个变量保存其分配的大小。我也假设removeIndex在数组范围内。在这种情况下，删除很简单：

顺序无关紧要

array[removeIndex] = array[--logicalSize];

这样就行了。您只需将最后一个数组元素复制到要删除的元素上，并在此过程中减少数组的 logicalSize。

如果removeIndex == logicalSize-1，即要删除的是最后一个元素，则会降级为该最后一个元素的自我赋值，但这不是问题。

保留顺序

memmove(array + removeIndex, array + removeIndex + 1, (--logicalSize - removeIndex)*sizeof(*array));

稍微有些复杂，因为现在我们需要调用 memmove() 函数来执行元素的移动操作，但仍然只需一行代码就能搞定。同样，在这个过程中也会更新数组的 logicalSize。

- cmaster - reinstate monica

Answer 3

如果每次删除内容时都重新分配内存，那么实际上你并不需要这样做。如果你知道你的 deck 的大致大小，那么选择适当的数组大小并保持对列表当前 end 的指针。这是一个堆栈。

如果您不知道您的 deck 的大小，并且认为它可能会变得非常大并且大小会发生变化，则必须执行更复杂的操作并实现链接列表。

在 C 中，您有两种简单的方法声明数组。

1. On the stack, as a static array

   int myArray[16]; // Static array of 16 integers
   

2. On the heap, as a dynamically allocated array

   // Dynamically allocated array of 16 integers
   int* myArray = calloc(16, sizeof(int));
   

标准C不允许调整这两种类型的数组大小。您可以创建一个特定大小的新数组，然后将旧数组的内容复制到新数组中，或者您可以遵循上述建议使用其他抽象数据类型（例如：链表、堆栈、队列等）。

- Chris Farmiloe

---

你如何使用指针来实现某个功能，比如说将数组作为一副牌，这样你就知道它的值（52）等等。我在编写代码时遇到了困难，已经绞尽脑汁几天了，试图弄清楚一些东西，所以我的大脑已经编码出了问题，因此我需要帮助。 - Rini Posny

你能否编辑你的问题，包括你已经尝试过的代码？创建一个数组非常简单。更多细节会让事情变得清晰明了。 - Cloud

标准C允许使用realloc()动态调整已分配数组的大小。现在你可以说realloc()会复制，但实际上它并不会（当可能时，它会在原地增加/缩小，或者在真正需要移动数组时使用memmove而不是memcpy）。 - cesss

Answer 4

有趣的是，数组可以通过索引随机访问。随机删除一个元素可能会影响其他元素的索引。

    int remove_element(int*from, int total, int index) {
            if((total - index - 1) > 0) {
                      memmove(from+i, from+i+1, sizeof(int)*(total-index-1));
            }
            return total-1; // return the new array size
    }

请注意，由于存在重叠内存，memcpy在这种情况下无法使用。

通过与最后一个元素进行交换，其中一种有效的方式（优于内存移动）是删除一个随机元素。

    int remove_element(int*from, int total, int index) {
            if(index != (total-1))
                    from[index] = from[total-1];
            return total; // **DO NOT DECREASE** the total here
    }

但是在删除后，顺序会改变。

如果删除是在循环操作中进行的，则重新排序可能会影响处理。内存移动是保持数组元素顺序的一种昂贵的替代方法。另一种在循环中保持顺序的方法是推迟删除。可以通过相同大小的有效性数组来实现。

    int remove_element(int*from, int total, int*is_valid, int index) {
            is_valid[index] = 0;
            return total-1; // return the number of elements
    }

这将创建一个稀疏数组。最后，通过进行一些重新排序，可以使稀疏数组变得更加紧凑（不包含两个有效元素之间包含无效元素的情况）。

    int sparse_to_compact(int*arr, int total, int*is_valid) {
            int i = 0;
            int last = total - 1;
            // trim the last invalid elements
            for(; last >= 0 && !is_valid[last]; last--); // trim invalid elements from last

            // now we keep swapping the invalid with last valid element
            for(i=0; i < last; i++) {
                    if(is_valid[i])
                            continue;
                    arr[i] = arr[last]; // swap invalid with the last valid
                    last--;
                    for(; last >= 0 && !is_valid[last]; last--); // trim invalid elements
            }
            return last+1; // return the compact length of the array
    }

- KRoy

Answer 5

我通常都这样做，而且总是有效的。

---

/试试这个/

for (i = res; i < *size-1; i++) { 

    arrb[i] = arrb[i + 1];
}

*size = *size - 1; /*in some ides size -- could give problems*/

- Abel_yai

---

嘿，你能解释一下这段代码片段是做什么的吗？ - f.khantsis

当你在数组中找到某个值后，它会删除这个值。 - Abel_yai

Answer 6

试试这个简单的代码：

#include <stdio.h>
#include <conio.h>
void main(void)
{ 
    clrscr();
    int a[4], i, b;
    printf("enter nos ");
    for (i = 1; i <= 5; i++) {
        scanf("%d", &a[i]);
    }
    for(i = 1; i <= 5; i++) {
        printf("\n%d", a[i]);
    }
    printf("\nenter element you want to delete ");
    scanf("%d", &b);
    for (i = 1; i <= 5; i++) {
        if(i == b) {
            a[i] = i++;
        }
        printf("\n%d", a[i]);
    }
    getch();
}

- Liaquat Hussain

---

不鼓励仅提供代码的答案。请添加一些解释，说明如何解决问题，或者这与现有答案有何不同。来自审核 - Nick

这段代码有很多缺点，无法竞争成为“最佳删除元素的方式”。此外，该算法不正确，不能移动所有元素（只是复制一个并使其重复）。更不用说在 a[i] = i++; 中的未定义行为和糟糕的编码风格了。我建议您删除这个答案。 - Dmitry Kuzminov