Название: Алгоритмическое мышление при решении задач (Шамшев А. Б.) Жанр: Информационные системы и технологии Просмотров: 1435 |
Задача 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; } |
|