Алгоритм: удаление элемента массива

  • В этой теме 0 ответов, 1 участник, последнее обновление 2 недели, 3 дня назад сделано Васильев Владимир Сергеевич.
Просмотр 0 веток ответов
  • Автор
    Сообщения
    • #7037
      @admin
      StudLance.ru

      Есть массив arr из n элементов, надо удалить элемент с номером k.

      Массив — это цельный кусок памяти, который интерпретируется программой как набор элементов некоторого типа (все элементы имеют одинаковый размер). Так как кусок цельный, то «просто так» удалить из середины ничего нельзя. однако, можно удалить с конца — для этого достаточно изменить размер массива. При этом физически ничего удалено не будет, но программа будет значть что в массиве не стало одного элемента. Удаление элемента из середины выполнятся с помощью сдвига — при этом удаляемый элемент сдвигается в конец массива как показано на рисунке:

      Удаляемый элемент (число 2) выделен красным цветом. На первом шаге на его место записывается элемент, стоящий следом (8) — после этого двойки в массиве уже нет (миссия выполнена), но в массиве оказывается две восьмерки. На место восьмерки записывается девятка, оказывается две девятки… Процесс продолжается пока не будет обработан последний элемент массива. В нашем случае девятка — это последний элемент поэтому мы можем удалить ее изменив размер на единицу. Блок-схема соответствующего алгоритма:

      Вычислительная сложность такого алгоритма — O(n).

      StudLance.ru

Просмотр 0 веток ответов
  • Для ответа в этой теме необходимо авторизоваться.
×