Удаление элементов из массива в C

Ответ 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;

realloc вернет указатель NULL, если запрашиваемый размер равен 0, или если есть ошибка. В противном случае он возвращает указатель на перераспределенный массив. Временной указатель используется для обнаружения ошибок при вызове realloc, потому что вместо выхода из него также можно просто оставить исходный массив таким, какой он есть. Когда realloc не перераспределяет массив, он не изменяет исходный массив.

Обратите внимание, что обе эти операции будут довольно медленными, если массив большой или если много элементов удалено. Существуют и другие структуры данных, такие как связанные списки и хэши, которые могут использоваться, если приоритетом является эффективное вложение и удаление.

Ответ 2

Вы действительно не хотите перераспределять память каждый раз, когда вы что-то удаляете. Если вы знаете приблизительный размер вашей колоды, выберите подходящий размер для своего массива и сохраните указатель на текущий конец списка. Это stack.

Если вы не знаете размер своей колоды и считаете, что он может стать действительно большим, а также продолжать изменять размер, тогда вам нужно будет сделать что-то более сложное и реализовать связанный список.

В C у вас есть два простых способа объявить массив.

• В стеке, как статический массив

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

• В куче, как динамически выделенный массив

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

Стандарт C не позволяет изменять размеры массива любого из этих типов. Вы можете создать новый массив определенного размера, а затем скопировать содержимое старого массива в новый или вы можете выполнить одно из приведенных выше предложений для другого абстрактного типа данных (т.е. Связанного списка, стека, очереди, и т.д.).

Ответ 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
    }

Но после изменения порядок изменяется.

Опять же, если удаление выполняется в режиме цикла, то переупорядочение может повлиять на обработку. Движение памяти - одна из самых дорогих альтернатив для сохранения порядка при удалении элемента массива. Другой способ сохранить порядок во время цикла - отложить удаление. Это можно сделать с помощью массива validity того же размера.

    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
    }