Вставка нескольких элементов

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

Пример

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

Решение

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

Type myarray = Array[1..2*n] Of Integer;

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

Лучше всего просматривать массив, начиная с конца, тогда вставляемый элемент мешать не будет. Кроме того, номер последнего элемента можно будет знать (если знать, сколько элементов вставлено на данный момент), при этом просмотр будет последовательным от N-го до 1-го.

Составим программу.

Program Example-44;

Const n = 10; dd = 51;

Type myarray = Array[1.. 2*n] Of Integer;

Var A: myarray;

x, k, i:Integer; {x - вставляемое число, k - количество вставленных элементов}

Procedure Init2(Var m: myarray); {процедура заполнения (инициализации) массива случайными числами}

...

Procedure Print1(n1: Integer; m: myarray); {процедура вывода (распечатки) массива }

...

Procedure Insert3(k1, x1: Integer; Var m: myarray);

Var i: Integer;

Begin {сдвиг элементов на одну позицию назад, n+k- это номер последнего элемента в данный момент}

For i:= n+k Downto k1+1 Do

m[i+1]:= m[i];

m[k1+1]: = x1; {вставка элемента на место - после k1-го}

Inc(k); {увеличение счётчика вставленных элементов }

End;

Begin

Init2 (A) Print1(n,A);

Writeln(' Введите вставляемое число');

Readln(x);

k: = 0;

For i:= n Downto 1 Do

If A[i] Mod 3=0 Then Insert3 (i,x,A);

Print1 (n+k,A); {вывод массива после вставки в него всех элементов}

Readln;

End.

Рассмотрим выполнение программы в пошаговом режиме. Будем вставлять после всех элементов, кратных 3, число 100, то есть х = 100. Пусть дан массив из 10-ти элементов:

3, -12, 5, 14, 27, -6, 1, 34, 10, -15.

Пусть так же первый вывод массива сделан. Трассировка примера приведена в таблице 5.

Таким образом, массив увеличился на k элементов.

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

3 -12 5 14 27 -6 1 -34 10 -15

3 100 -12 100 5 14 27 100 -6 100 1 -34 10 -15 100

Таблица 5

Просмотр элементов массива
A[i] mod 3 = 0	k	i	массив
да			3, -12, 5, 14, 27, -6, 1, 34, 10, -15
вставляем 100 после i-го (десятого)
			3, -12, 5, 14, 27, -6, 1, 34, 10, -15, 100
нет			3, -12, 5, 14, 27, -6, 1, 34, 10, -15, 100
нет			3, -12, 5, 14, 27, -6, 1, 34, 10, -15, 100
нет			3, -12, 5, 14, 27, -6, 1, 34, 10, -15, 100
да			3, -12, 5, 14, 27, -6, 1, 34, 10, -15, 100
вставляем 100 после i-го (шестого)
			3, -12, 5, 14, 27, -6, 100, 1, 34, 10, -15, -15, 100
да			3, -12, 5, 14, 27, -6, 100, 1, 34, 10, 10, -15, 100
вставляем 100 после i-го (пятого)
			3, -12, 5, 14, 27, 100, -6, 100, 1, 34, 10, -15, 100
нет			3, -12, 5, 14, 27, 100, -6, 100, 1, 34, 10, -15, 100
нет			3, -12, 5, 14, 27, 100, -6, 100, 1, 34, 10, -15, 100
да			3, -12, 5, 14, 27, 100, -6, 100, 1, 34, 10, -15, 100
вставляем 100 после i-го (второго)
			3, -12, 100, 5, 14, 27, 100, -6, 100, 1, 34, 10, -15, 100
да			3, -12, 100, 5, 14, 27, 100, -6, 100, 1, 34, 10, -15, 100
вставляем 100 после i-го (первого) элемента
да			3, 100, -12, 100, 5, 14, 27, 100, -6, 100, 1, 34, 10, -15, 100

Дата добавления: 2015-08-17