Глава 3. Алгоритмы, использующие одномерные массивы - 3.7. Удаление и вставка элементов массива

E-mail Печать PDF
Рейтинг пользователей: / 10
ХудшийЛучший 
Индекс материала
Глава 3. Алгоритмы, использующие одномерные массивы
3.2 Задачи заполнения массива
3.3. Задачи анализа массива
3.4. Нахождение элементов, обладающих определенным свойством
3.5. Изменение значений некоторых элементов
3.6. Обмен значений элементов
3.7. Удаление и вставка элементов массива
3.8. Алгоритмы, реализуемые с помощью циклов с предусловием
3.9. Использование вложенных циклов
Все страницы

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

Пример 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 отдо n повторять 

         Если а[i] > max то

   max = а[i]

   k = i

         Все если

кц

Сдвиг элементов массива

нц

Для i от = k до n - 1 повторять

         а[i] = а[i+1]

кц

Уменьшение количества элементов массива

 n = n - 1

 

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

Тест

Данные

Результат

N = 8

A = (6, 3, 7, 11, 2, 8, 1,  5)

A = (6, 3, 7, 2, 8, 1, 5)  N = 7

     

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

i

Массив

4; 4 ? 7? Да

А = (6, 3, 7, 2, 2, 8, 1, 5)

5; 5 ? 7? Да

А = (6, 3, 7, 2, 8, 8, 1, 5)

6; 6 ? 7? Да

А = (6, 3, 7, 2, 8, 1, 1, 5)

7; 7 ? 7? Да

А = (6, 3, 7, 2, 8, 1, 5, 5)

8; 8 ? 7? Нет

Конец цикла. n = 8 - 1 = 7

Пример 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];

   Все если

кц

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

нц

Для  i от n до 1 шаг -1 повторять

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

a[i] = a[i + 1]

k = k + 1

  Все если

кц

n = n - k

 

 

Задачи для самостоятельного решения

1. Удалите все отрицательные элементы массива.

2. Удалите все элементы, большие данного числа А (значение числа А вводится с клавиатуры).

3. Удалите все четные элементы, стоящие на нечетных местах.

4. Удалите все повторяющиеся элементы, оставив их первые вхождения, то есть в массиве должны остаться только различные элементы.

5. Удалите последний четный элемент массива.

6. Удалите все элементы, кратные 3 или 5.

Пример 3.16. Вставить произвольное число в одномерный массив A[n] после элемента с заданным номером.

Дано: n - размер массива; A[n] - числовой вещественный массив; k - номер элемента, после которого вставляется число, равное m.

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

Словесное описание алгоритма.

Вставка нового элемента осуществляется следующим образом:

1) первые k элементов массива остаются без изменения;

2) все элементы, начиная с (k + 1)-го необходимо сдвинуть вправо;

3) элементу с номером (k + 1) присвоить значение m. Количество элементов массива увеличить на 1.

Рассмотрим пример. Пусть дан массив из n = 5 элементов: A(3, -12, 5, 14, 27). Надо вставить элемент со значением 10 после второго элемента массива. Мы получим массив A(3, -12, 10, 4, 14, 27). Количество элементов n = 6.

Запишем фрагмент алгоритма.

{Сдвиг элементов массива}

нц

Для i от n до k+1 шаг -1 повторять

    a[i+1] = a[i]

кц

{Вставляем новый элемент}

a[k+1] = m

{Количество элементов в массиве увеличиваем}

n = n + 1

Тест

Данные

Результат

N = 5; k = 2; m=10

A = (3, -12, 5, 14, 27)

A = (3, -12, 10, 5, 14, 27); N=6

     

Покажем, как выполняется этот алгоритм для тестового примера.

 

i

Массив

5; 5 ? 3? Да

A = (3, -12, 5, 14, 27, 27)

4; 4 ? 3? Да

A = (3, -12, 5, 14, 14, 27)

3; 3 ? 3? Да

A = (3, -12, 5, 5, 14, 27)

2; 2 ? 3? Нет

Конец цикла

 

A[3] = 10; n = 5 + 1 = 6

 

A = (3, -12, 10, 5, 14, 27)

Пример 3.17. Вставить произвольное число в одномерный массив A[n] перед элементом с заданным номером.

Дано: n - размер массива; A[n] - числовой вещественный массив; k - номер элемента, перед которым вставляется число, равное m.

Найти: Новый массив A размера n+1.

В этой задаче, в отличие от предыдущей, мы сдвигаем все элементы с k-го и на место k-го элемента записываем новый.

Пусть задан следующий одномерный массив из n (n =10) элементов: 3, -12, 5, 14, 27, -6, 1, 34, 10, -15. Надо вставить элемент со значением 100 перед пятым элементом массива. Получим следующий массив: 3, -12, 5, 14, 100, 27, -6, 1, 34, 10, 15.

Сдвиг элементов на одну позицию вправо и вставка элемента на место k-го элемента:

нц

Для  i от n до k шаг -1 повторять

a[i + 1] = a[i]

кц

a[k] = x;

Тест

Данные

Результат

N = 10; k = 5;
m=100

A = (3, -12, 5, 14, 27, -6, 1, 34, 10, -15)

A = (3, -12,  5, 14, 100, 27, -6, 1, 34, 10, 15); N=6

     

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

Пример 3.18. Вставить данное число после всех элементов массива, кратных трем.

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

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

Удобнее просматривать массив с конца, тогда вставляемый элемент мешать не будет.

Дано: n - размер массива; A[n] - вещественный массив; k - номер элемента, перед которым вставляется число, равное m.

Найти: Новый массив A размера 2n.

Фрагмент алгоритма:

Количество сдвигаемых элементов k = 0.

 

Цикл по всем элементам массива от n-го до
1-го. Параметр цикла i меняется с шагом -1. Внешний цикл.

 

Проверка деления каждого числа a[i] на 3.

Если число делится на 3 без остатка, то выполняем сдвиг элементов на одну позицию вправо.

n + k - это в данный момент номер последнего элемента.

Во внутреннем цикле параметр цикла j меняется от n + k до i + 1 с шагом -1.

 

После окончания сдвига вставляем элемент на место после i-го и увеличиваем количество вставленных элементов.

Тест

Данные

Результат

N = 5; х=10

A = (1, -12, 5, 14, 27)

A = (1, 10, -12, 10, 5, 14, 27, 10) ; N=7

     

Покажем выполнение алгоритма для тестового примера.

k

i

A[i] mod 3 = 0?

j

Массив после сдвига

Массив после вставки

0

5

27 mod 3 = 0? Да

5

1, -12, 5, 14, 27, 27

 

 

4

1, -12, 5, 14, 14, 27

 

 

кц

 

1, -12, 5, 14, 10, 27

1

4

14 mod 3 = 0? Нет

 

 

 

3

5 mod 3 = 0? Нет

 

 

 

2

-12 mod 3 = 0? Нет

6

1, -12, 5, 14, 10, 27, 27

 

 

5

1, -12, 5, 14, 10, 10, 27

 

 

4

1, -12, 5, 14, 14, 10, 27

 

 

3

1, -12, 5, 5, 14, 10, 27

 

 

кц

 

1, -12, 10, 5, 14, 10, 27

2

1

1 mod 3 = 0? Нет

кц

 

 

Задачи для самостоятельного решения

1. Вставьте элемент с данным значением после первого отрицательного элемента массива.

2. Вставьте элемент с данным значением перед последним положительным элементом массива.

3. Вставьте в массив два элемента с данным значением: первый - после максимального элемента, второй - перед максимальным элементом.

4. Вставьте по одному элементу с данным значением перед всеми элементами массива, кратными заданному числу.

5. Вставьте по одному элементу с заданным значением перед всеми нулевыми элементами данного массива.

6. Дан произвольный массив. Вставьте два элемента с данными значениями: первый - после всех элементов, больших данного числа Р , а второй - перед всеми элементами, большими данного числа Р (Р вводится с клавиатуры).

7. Дан произвольный массив. Вставьте элемент со значением А перед всеми элементами, большими А, а элемент со значением В - после всех элементов, меньших В.



 

Добавьтe Ваш комментарий

Ваше имя (псевдоним):
Ваш адрес почты:
Заголовок:
Комментарий:

Комментарии

Интересное




Похожие материалы

Партнёры