Название: Алгоритмическое мышление при решении задач (Шамшев А. Б.)

Жанр: Информационные системы и технологии

Просмотров: 1394


Задача 6. удаление элементов из массива по значению (2 способ решения)

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

1. Подсчет   количества   элементов,   которые   надо   удалить   (что подразумевает под собой проход по всем элементам).

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

Таким образом, общее количество проходов по массиву всегда равно 2, вне

зависимости от количества удаляемых элементов.

В псевдокоде алгоритм первого этапа имеет вид:

 

Объявить и инициализировать счетчик удаляемых элементов нулем.

Для каждого элемента массива

НачалоЦикла

Если текущий элемент массива надо удалить, то

НачалоЕсли

Увеличить счетчик удаляемых элементов на 1.

ОкончаниеЕсли

ОкончаниеЦикла

 

В псевдокоде алгоритм второго этапа имеет вид:

 

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

Для каждого элемента исходного массива

НачалоЦикла

Если текущий элемент исходного массива не надо удалять, то

НачалоЕсли

Скопировать  текущий  элемент  в  свободный  элемент  результирующего массива

ОкончаниеЕсли

ОкончаниеЦикла

 

Однако операция «скопировать текущий элемент в свободный элемент результирующего массива» подразумевает под собой нахождение свободного элемента. Поэтому детализируем псевдокодовый алгоритм.

 

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

Объявить        и          инициализировать    нулем  номер  свободного     элемента         в результирующем массиве.

Для каждого элемента исходного массива

НачалоЦикла

Если текущий элемент исходного массива не надо удалять, то

НачалоЕсли

Скопировать текущий элемент в элемент результирующего массива, индекс которого равен номеру свободного элемента.

Увеличить номер свободного элемента на 1.

ОкончаниеЕсли

ОкончаниеЦикла

 

Реализация данного алгоритма будет иметь следующий вид:

public static void delByValue(ref int[] data, int delValue) {

int countDel = 0;

for (int i = 0; i < data.Length; i++) {

if (data[i] == delValue) {

countDel++;

}

}

int[] newData = new int[data.Length - countDel];

int curPos = 0;

for (int i = 0; i < data.Length; i++) {

if (data[i] != delValue) {

newData[curPos++] = data[i];

}

}

data = newData;

}