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

Урок из серии: «Программирование на языке Паскаль»
Продолжим знакомиться с алгоритмами обработки одномерных массивов. Сегодня рассмотрим алгоритмы для вставки элементов в массив. Как и в алгоритмах с удалением элементов, будем различать два случая: вставку одного элемента и вставку нескольких элементов. Алгоритмы получаются разные.

Вставка одного элемента

Вставить элемент можно до или после данного элемента, номер этого элемента можно вводить с клавиатуры или искать при определённых условиях.
Рассмотрим вставку элемента после элемента с данным номером, номер этого элемента будем вводить с клавиатуры.

Рассмотрим несложную задачу.

Пример 1. В массив, состоящий из n элементов, вставить число b после k-го элемента.

Решение

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

Вставим число 100 после 5 элемента (b=100, k = 5)

Алгоритм вставки элемента в массив:

Первые 5 элементов массива остаются без изменений.
Сдвинуть все элементы, начиная с шестого, на один назад. Но чтобы не потерять соседнее значение, сдвиг будем начинать с последнего элемента — сдвинуть сначала десятый на один вправо, затем девятый, восьмой и т. д. до шестого (m[i+1]:=m[i], i=n..k).
На место шестого элемента записываем значение 100, то есть после 5-го элемента массива (m[k+1]:=b;).

Получим следующий массив:

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

Таким образом, в массиве стало 11 элементов, то есть массив надо определять на N+1 элемент:

Type myarray = Array[1..n+1] Of Integer.

Составим теперь новую процедуру Insert1 (k1, x1, m), которой передаются: k 1 — номер элемента, после которого надо вставить, х1 — число, которое вставляем, m — массив, в котором делаем преобразования.

Procedure Insert1 (k1,x1: Integer; Var m: myarray);
{процедура вставка одного элемента в массив }
Var i: Integer;
Begin

   For i:=n Downto k1+1 Do {сдвиг элементов на одну позицию назад}   m[i+1]:= m[i];
   m[k1+1]:= x1; {вставка элемента на место после k1-го}
End;

Составим основную программу с использованием новой процедуры Insert1 (k1, x1, m).

Program Primere_1;
Const n = 10; dd = 51;
Type myarray = Array[1.. n+1] Of Integer;
Var m : myarray;
    x, k : Integer; {x - вставляемое число, k - номер элемента, после которого вставляем}

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

Procedure Insert1 (k1,x1: Integer; Var m: myarray);
{процедура вставки одного элемента в массив }
...

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

Begin {main}
   Init2(-25, 25, m); {заполнение массива и вывод на экран}
   Writeln ('Введите номер элемента, после которого вставлять,');
   Writeln ('и вставляемое число');
   Readln (k,x);   Insert1(k,x,m);
   Print(n+1,m); {вывод массива после вставки элемента}
   Readln;
End.

Мы рассмотрели алгоритм вставки одного элемента в массив. Рассмотрим следующий случай.

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

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

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

Решение

Первое, на что необходимо обратить внимание — это описание массива: на сколько элементов может увеличиться массив?

Максимальное количество элементов, после которых может быть вставлен новый элемент, совпадает с количеством элементов массива. Так как может случиться, что все элементы массива отвечают заданному свойству. Поэтому массив может увеличиться в два раза (это его самая большая размерность), а значит, соответствующее ему описание будет следующим:
Type myarray = Array[1..2*n] Of Integer;

Второе. Если мы будем просматривать элементы массива с начала и вставлять новый после элемента с заданным свойством, то следующим просматриваемым элементом будет новый (вставленный) элемент и его необходимо будет пропускать («перепрыгивать»). Поэтому решение будет не очень эффективным.
Поэтому лучше всего просматривать массив, начиная с конца, тогда вставляемый элемент мешать не будет. При этом просмотр будет последовательным от N-го до 1-го.

И последнее, на что нужно обратить внимание, это то, что номер последнего элемента после каждой вставки будет меняться. Его нужно будет переопределять. Для этого нужно вести подсчет количества вставленных элементов на данный момент.

Для вставки нескольких элементов в массив составим новую процедуру Insert2 (k1, x1, m), в которой будет вестись подсчет количества вставленных элементов и корректироваться номер последнего элемента.
Номер последнего элемента необходим для того, чтобы знать, сколько элементов необходимо сдвинуть при освобождении места для нового элемента, так как количество элементов в этой части массива увеличивается.
Ниже представлен текст процедуры с учетом изменений. Параметры у процедуры оставим прежние.

Procedure Insert2(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;

Теперь можно написать программный код основной программы. Он будет следующий:

Program Primer_2;
Const n = 10;
Type myarray = Array[1.. 2*n] Of Integer;
Var m : myarray;
    x, k, i :Integer; {x - вставляемое число, k - счетчик вставленных элементов}

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

Procedure Insert2(k1, x1: Integer; Var m: myarray);
{процедура вставки нескольких элементов в массив}...

Procedure Print(n1: Integer; m: myarray);
{процедура вывода массива }
...
Begin {main}
   Init2 (-25, 25, M); {заполнение массива и вывод на экран}
   Writeln(' Введите число для вставки: ');
   Readln(x);
   k: = 0;
   For i:= n Downto 1 Do
      If M[i] Mod 3 = 0 Then
            Insert2(i,x,M);
   Print(n+k,M); {вывод массива после вставки всех элементов}
End.

Вы познакомились с алгоритмами вставки элементов в одномерный массив. На следующем уроке рассмотрим алгоритмы сортировки одномерных массивов.

Урок 27. Вставка элементов в массив

Вставка одного элемента

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