C语言 从C中的数组中删除元素

Removing elements from an array in C

提问by Rini Posny

I just have a simple question about arrays in C

我只是有一个关于 C 中数组的简单问题

What's the best way to remove elements from an array and in the process make the array smaller.

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

i.e the array is n size, then I take elements out of the array and then the array grows smaller by the amount that I removed it from.

即数组是 n 大小，然后我从数组中取出元素，然后数组随着我从中删除它的数量变小。

basically I'm treating the array like a deck of cards and once I take a card off the top of the deck it shouldn't be there anymore.

基本上，我将阵列视为一副牌，一旦我从牌组顶部取下一张牌，它就不应该再在那里了。

EDIT: I'm going to drive myself crazy before the end of the day, thanks for all the help I'm trying the value swapping thing but it's not working right.

编辑：我会在一天结束之前让自己发疯，感谢所有帮助我尝试价值交换的事情，但它不起作用。

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

enum faces{Ace = 0, Hyman = 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",
        "Hyman",
        "Queen",
        "King" };

    if(d == Ace)
        return face[0];
    else
    {
        if(d == Hyman) 
            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;
}

回答by Ben

There are really two separate issues. The first is keeping the elements of the array in proper order so that there are no "holes" after removing an element. The second is actually resizing the array itself.

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

Arrays in C are allocated as a fixed number of contiguous elements. There is no way to actually remove the memory used by an individual element in the array but the elements can be shifted to fill the hole made by removing an element. For example:

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

Statically allocated arrays can not be resized. Dynamically allocated arrays can be resized with realloc(). This will potentially move the entire array to another location in memory, so all pointers to the array or to its elements will have to be updated. For example:

静态分配的数组不能调整大小。动态分配的数组可以用 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;

realloc will return a NULL pointer if the requested size is 0, or if there is an error. Otherwise it returns a pointer to the reallocated array. The temporary pointer is used to detect errors when calling realloc because instead of exiting it is also possible to just leave the original array as it was. When realloc fails to reallocate an array it does not alter the original array.

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

Note that both of these operations will be fairly slow if the array is large or if a lot of elements are removed. There are other data structures like linked lists and hashes that can be used if efficient insertion and deletion is a priority.

请注意，如果数组很大或者删除了很多元素，那么这两个操作都会相当慢。如果优先考虑有效的插入和删除，还可以使用其他数据结构，如链表和哈希。

回答by Chris Farmiloe

You don't really want to be reallocing memory every time you remove something. If you know the rough size of your deckthen choose an appropriate size for your array and keep a pointer to the current endof the list. This is a stack.

您真的不想在每次删除某些内容时重新分配内存。如果你知道你的套牌的大致大小，那么为你的数组选择一个合适的大小，并保留一个指向列表当前末尾的指针。这是一个堆栈。

If you don't know the size of your deck, and think it could get really big as well as keeps changing size, then you will have to do something a little more complex and implement a linked-list.

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

In C, you have two simple ways to declare an array.

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

1. 在堆栈上，作为一个静态数组

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

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

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

Standard C does not allow arrays of either of these types to be resized. You can either create a new array of a specific size, then copy the contents of the old array to the new one, or you can follow one of the suggestions above for a different abstract data type (ie: linked list, stack, queue, etc).

标准 C 不允许调整其中任何一种类型的数组的大小。您可以创建一个特定大小的新数组，然后将旧数组的内容复制到新数组，或者您可以按照上述建议之一针对不同的抽象数据类型（即：链表、堆栈、队列、等等）。

回答by shuva

Interestingly array is randomly accessible by the index. And removing randomly an element may impact the indexes of other elements as well.

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

    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
    }

Note that memcpywill not work in this case because of the overlapping memory.

请注意，memcpy由于内存重叠，在这种情况下将不起作用。

One of the efficient way (better than memory move) to remove one random element is swapping with the last element.

删除一个随机元素的一种有效方法（比内存移动更好）是与最后一个元素交换。

    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
    }

But the order is changed after the removal.

但是删除后顺序发生了变化。

Again if the removal is done in loop operation then the reordering may impact processing. Memory move is one expensive alternative to keep the order while removing an array element. Another of the way to keep the order while in a loop is to defer the removal. It can be done by validity array of the same size.

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

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

It will create a sparse array. Finally, the sparse array can be made compact(that contains no two valid elements that contain invalid element between them) by doing some reordering.

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

    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
    }

回答by cmaster - reinstate monica

What solution you need depends on whether you want your array to retain its order, or not.

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

Generally, you never only have the array pointer, you also have a variable holding its current logical size, as well as a variable holding its allocated size. I'm also assuming that the removeIndexis within the bounds of the array. With that given, the removal is simple:

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

Order irrelevant

订单无关

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

That's it. You simply copy the last array element over the element that is to be removed, decrementing the logicalSizeof the array in the process.

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

If removeIndex == logicalSize-1, i.e. the last element is to be removed, this degrades into a self-assignment of that last element, but that is not a problem.

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

Retaining order

保留订单

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

A bit more complex, because now we need to call memmove()to perform the shifting of elements, but still a one-liner. Again, this also updates the logicalSizeof the array in the process.

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

回答by Liaquat Hussain

Try this simple code:

试试这个简单的代码：

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

回答by Abel Canizares

I usually do this and works always.

我通常这样做并且总是有效。

---

---

/try this/

/试试这个/

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

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

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