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

Пример 3.14. Удалить из массива, в котором все элементы различны, наибольший элемент. После удаления массив уплотнить, сдвинув все следующие за ним элементы, влево.

Дано: n – размер массива; A[n] – массив вещественных чисел.

Найти новый массив А размера n – 1.

Для решения задачи необходимо:

1) найти номер k наибольшего элемента массива. Эта задача решена в примере 3.5.

2) сдвинуть все элементы массива, начиная с k–го на один элемент влево.

Для того чтобы разработать алгоритм, рассмотрим конкретный пример. Пусть дан одномерный массив, состоящий из 10 элементов: А(6, 3, 7, 11, 2, 8, 1, 5). Номер наибольшего элемента равен 7 (k = 7), то есть, начиная с седьмого элемента, будем сдвигать элементы на один влево: седьмому элементу присвоим значение восьмого, восьмому элементу присвоим значение девятого, а девятому присвоим значение десятого элемента. На этом сдвиг заканчивается. Таким образом, сдвиг начинается с k–го элемента и заканчивается элементом с номером n – 1, где n –количество элементов в массиве. После этого количество элементов в массиве станет на один элемент меньше. Массив примет вид: А(6, 3, 4, 7, 11, 8, 1, 5).

Фрагмент алгоритма решения задачи:

Нахождение максимального элемента и его номера max = а[1] k = 1 нц Для i от 2 до n повторять Если а[i] > max то max = а[i] k = i Все если кц Сдвиг элементов массива нц Для i от = k до n – 1 повторять а[i] = а[i+1] кц Уменьшение количества элементов массива n = n – 1

Мы уже рассматривали подробно алгоритм нахождения максимального элемента массива и его номера. Покажем, как выполняется вторая часть алгоритма (сдвиг элементов массива) для тестового примера.

Тест

В массиве номер наибольшего элемента k = 4. Удаляем этот элемент.

Пример 3.15. Решить предыдущую задачу, считая, что максимальных элементов может быть несколько.

Дано n – размер массива; A[n] – массив вещественных чисел.

Найти: Новый массив А размера n – k, где k – количество удаленных элементов массива.

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

нц

Для i от i_кон до i_нач шаг –1 повторять

<тело цикла>

кц

Значение переменной i уменьшается на единицу, начиная от i_кон до i_нач.

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

Amax = a[1];

нц

Для i от 2 до n повторять {Нахождение максимального элемента}

Если a[i] > Amax то Amax = a[i];