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

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将返回NULL指针.否则,它返回一个指向重新分配的数组的指针.临时指针用于在调用realloc时检测错误,因为不是退出它也可以保持原始数组不变.当realloc无法重新分配数组时,它不会改变原始数组.

请注意,如果数组很大或者删除了很多元素,这两个操作都会相当慢.如果有效插入和删除是优先事项,还可以使用其他数据结构,如链接列表和散列.

Answer 2

每次删除内容时,你真的不想重新分配内存.如果你知道你的粗大小的甲板,然后选择您阵列的适当大小,并保持一个指向当前端列表.这是一个堆栈.

如果你不知道你的套牌的大小,并认为它可以变得非常大并且不断改变大小,那么你将不得不做一些更复杂的事情并实现一个链表.

在C中,您有两种简单的方法来声明数组.

1. 在堆栈上,作为静态数组

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

2. 在堆上,作为动态分配的数组

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

标准C不允许调整这些类型的数组的大小.您可以创建一个特定大小的新数组,然后将旧数组的内容复制到新数组,或者您可以按照上面的建议之一获取不同的抽象数据类型(即:链表,堆栈,队列,等等).

Answer 3

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

    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
    }

Answer 4

您需要什么解决方案取决于您是否希望阵列保留其顺序。

通常，您永远不会只有数组指针，您还有一个保存其当前逻辑大小的变量，以及一个保存其分配大小的变量。我还假设removeIndex是在数组的范围内。鉴于此，删除很简单：

订单无关

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

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

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

保留订单

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

有点复杂，因为现在我们需要调用memmove()来执行元素的移位，但仍然是单行的。同样，这也会logicalSize在过程中更新数组的 。