Вставка элементов в одномерный массив
Вставка одного элемента
Вставлять элемент можно до или после данного элемента, номер этого элемента можно вводить с клавиатуры или искать при определённых условиях. Рассмотрим вставку элемента после элемента с данным номером, номер этого элемента будем вводить с клавиатуры.
Вставка элемента после элемента с заданным номером.
Пример
Вставить число 100 после пятого элемента массива.
Решение
Пусть k - это номер элемента, после которого мы должны вставить элемент х (k и х будем вводить с клавиатуры). Тогда вставка осуществляется следующим образом:
 | первые k элементов массива остаются без
изменений;
| все элементы, начиная с (k+1)-го,
необходимо сдвинуть на один назад;
| на место (k+1)-го элемента записываем
значение х, то есть после k-го элемента
массива. | |
Рассмотрим на конкретном примере. Пусть дан следующий одномерный массив из N (N = 10) элементов: 3, -12, 5, 14, 27, -6, 1, -34, 10, -15.
Надо вставить 100 после пятого элемента массива. Тогда получим следующий массив:
3, -12, 5, 14, 27, 100, -6, 1, -34, 10, -15.
Таким образом, в массиве стало 11 элементов, то есть массив надо определять на N+1 элемент:
Type myarray = Array[1..n+1] Of Integer.
Кроме того, в программе необходимо выводить массив два раза, сначала первые N элементов массива, а затем все N+1 элементы. Поэтому будем использовать уже известную процедуру Print1.
Составим теперь основную программу с использованием новой процедуры Insert1 (k1, x1, m), которой передаются: k1 - номер элемента, после которого надо вставить, х1 - число, которое вставляем, m - массив, в котором делаем преобразования. Кроме того, сдвиг элементов будем начинать с последнего элемента.
Program Example_42;
Const n = 10; dd = 51;
Type myarray = Array[1.. n+1] Of Integer;
Var A : myarray;
x, k : Integer; {x - вставляемое число, k - номер
элемента, после которого вставляем}
Procedure Init2 (Var m: myarray); {процедура
заполнения (инициализации) массива
случайными числами}
...
Procedure Print1 (n1: Integer; m: myarray); {процедура
вывода (распечатки) массива}
...
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;
Begin
Init2(A);
Print1(n,A) {первый вывод начального массива из n
элементов}
Writeln (' Номер элемента, после которого
вставлять,');
Writeln ('и вставляемое число');
Readln (k,x); {ввод номера и вставляемого
элемента}
Insert1(k,x,A);
Print1(n+1,A); {вывод массива после вставки в него}
Readln;
End.
Рассмотрим выполнение программы по шагам выполнения. Пусть начальное заполнение массива сделано и имеется массив из десяти целых чисел:
3, -12, 5, 14, 27, -6, 1, 34, 10, -15.
Кроме того, пусть первый вывод массива тоже уже сделан и на экране появились 10 целых чисел. Введём номер элемента, после которого будем вставлять новый элемент и сам этот новый элемент:
k = 5 - будем вставлять после пятого элемента;
x = 100 - вставлять будем число 100.
| Сдвиг элементов | |||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| i | m[1] | m[2] | m[3] | m[4] | m[5] | m[6] | m[7] | m[8] | m[9] | m[10] | m[11] |
| - | 3 | -12 | 5 | 14 | 27 | -6 | 1 | 34 | 10 | -15=> | - |
| 10 | 3 | -12 | 5 | 14 | 27 | -6 | 1 | 34 | 10=> | -15 | -15 |
| 9 | 3 | -12 | 5 | 14 | 27 | -6 | 1 | 34=> | 10 | 10 | -15 |
| 8 | 3 | -12 | 5 | 14 | 27 | -6 | 1=> | 34 | 34 | 10 | -15 |
| 7 | 3 | -12 | 5 | 14 | 27 | -6=> | 1 | 1 | 34 | 10 | -15 |
| 6 | 3 | -12 | 5 | 14 | 27 | -6 | -6 | 1 | 34 | 10 | -15 |
| на (k1+1)-ое место записываем значение x1 - m[k1+1] := 100 | |||||||||||
| - | 3 | -12 | 5 | 14 | 27 | 100 | -6 | 1 | 34 | 10 | -15 |
Итак, получили новый массив, который уже имеет N+1 элемент, его и будем выводить на экран. На экране всё это будет выглядеть следующим образом:
3 -12 5 14 27 -6 1 34 10 -15
Номер элемента, после которого вставлять, и вставляемое число
5 100
3 -12 5 14 27 100 -6 1 34 10 -15
Вставка элемента перед данным
Пример
Вставить число 100 перед пятым элементом массива.
Решение
Эта вставка немногим отличается от предыдущей: в первой сдвигали назад все элементы, стоящие после k-го, то есть с (k+1)-го, а на его место записывали новый элемент, в этой - сдвигаем все элементы с 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.
Изменим программу для этой вставки:
Program Example_43;
Const n = 10; dd = 51;
Type myarray = Array[1..n+1] Of Integer;
Var A : myarray;
x, k : Integer; {x - вставляемое число; k - номер
элемента, после которого вставляем}
Procedure Init2(Var m: myarray); {процедура
заполнения (инициализации) массива
случайными числами}
Procedure Print1(n1: Integer; m: myarray ); {процедура
вывода (распечатки) массива}
Procedure Insert2(k1, x1: Integer; Var m: myarray );
Var i : Integer;
Begin {сдвиг на одну позицию назад}
For i:=n Downto k1 Do
m[i+1]:=m[i];
m[k1]:=x1; {вставка x1 на место k1-го}
End;
Begin
Init2(A);
Print1 (n,A); {первый вывод начального массива }
Writeln ('Номер элемента, перед которым
вставлять,');
Writeln (' u вставляемое число ');
Readln (k,x); {ввод номера и вставляемого
элемента}
Insert2(k,x,A);
Print1(n+1,A); {выводмассива после вставки в него}
Readln;
End.
Рассмотрим на том же примере пошаговое выполнение программы. Пусть начальное заполнение массива сделано и имеется массив из десяти целых чисел:
3, -12, 5, 14, 27, -6, 1, -34, 10, -15.
Кроме того, пусть первый вывод мвссива тоже уже сделан и на экране появились 10 целых чисел. Введём номер элемента, перед которым будем вставлять новый элемент и сам этот новый элемент:
| k = 5 - будем вставлять перед пятым
элементом;
| x = 100 - вставляемое число 100. | |
| Сдвиг элементов | |||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| i | m[1] | m[2] | m[3] | m[4] | m[5] | m[6] | m[7] | m[8] | m[9] | m[10] | m[11] |
| - | 3 | -12 | 5 | 14 | 27 | -6 | 1 | 34 | 10 | -15=> | - |
| 10 | 3 | -12 | 5 | 14 | 27 | -6 | 1 | 34 | 10=> | -15 | -15 |
| 9 | 3 | -12 | 5 | 14 | 27 | -6 | 1 | 34=> | 10 | 10 | -15 |
| 8 | 3 | -12 | 5 | 14 | 27 | -6 | 1=> | 34 | 34 | 10 | -15 |
| 7 | 3 | -12 | 5 | 14 | 27 | -6=> | 1 | 1 | 34 | 10 | -15 |
| 6 | 3 | -12 | 5 | 14 | 27=> | -6 | -6 | 1 | 34 | 10 | -15 |
| 5 | 3 | -12 | 5 | 14 | 27 | 27 | -6 | 1 | 34 | 10 | -15 |
| на k1-ое место записываем значение x1 - m[k1] := 100 | |||||||||||
| - | 3 | -12 | 5 | 14 | 100 | 27 | -6 | 1 | 34 | 10 | -15 |
Итак, получили новый массив, который уже имеет N+1 элемент, его и будем выводить на экран. На экране всё это будем выглядеть следующим образом:
3 -12 5 14 27 -6 1 -34 10 -15
Номер элемента, перед которым вставлять, и вставляемое число
5 100
3 -12 5 14 100 27 -6 1 -34 10 -15
Вставка нескольких элементов
Предположим, что необходимо вставлять не один элемент в массив, а по одному элементу после всех элементов с заданным свойством. Рассмотрим эту вставку на примере вставки после всех элементов с заданным свойством.
Пример
Вставить число после всех элементов массива, кратных 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
| Просмотр элементов массива | |||||||||
|---|---|---|---|---|---|---|---|---|---|
| A[i] mod 3 = 0 | k | i | массив | ||||||
| да | 0 | 10 | 3, -12, 5, 14, 27, -6, 1, 34, 10, -15 | ||||||
| вставляем 100 после i-го (десятого) | |||||||||
| 1 | 10 | 3, -12, 5, 14, 27, -6, 1, 34, 10, -15, 100 | |||||||
| нет | 1 | 9 | 3, -12, 5, 14, 27, -6, 1, 34, 10, -15, 100 | ||||||
| нет | 1 | 8 | 3, -12, 5, 14, 27, -6, 1, 34, 10, -15, 100 | ||||||
| нет | 1 | 7 | 3, -12, 5, 14, 27, -6, 1, 34, 10, -15, 100 | ||||||
| да | 1 | 6 | 3, -12, 5, 14, 27, -6, 1, 34, 10, -15, 100 | ||||||
| вставляем 100 после i-го (шестого) | |||||||||
| 2 | 6 | 3, -12, 5, 14, 27, -6, 100, 1, 34, 10, -15, -15, 100 | |||||||
| да | 2 | 5 | 3, -12, 5, 14, 27, -6, 100, 1, 34, 10, 10, -15, 100 | ||||||
| вставляем 100 после i-го (пятого) | |||||||||
| 3 | 5 | 3, -12, 5, 14, 27, 100, -6, 100, 1, 34, 10, -15, 100 | |||||||
| нет | 3 | 4 | 3, -12, 5, 14, 27, 100, -6, 100, 1, 34, 10, -15, 100 | ||||||
| нет | 3 | 3 | 3, -12, 5, 14, 27, 100, -6, 100, 1, 34, 10, -15, 100 | ||||||
| да | 3 | 2 | 3, -12, 5, 14, 27, 100, -6, 100, 1, 34, 10, -15, 100 | ||||||
| вставляем 100 после i-го (второго) | |||||||||
| 4 | 2 | 3, -12, 100, 5, 14, 27, 100, -6, 100, 1, 34, 10, -15, 100 | |||||||
| да | 4 | 1 | 3, -12, 100, 5, 14, 27, 100, -6, 100, 1, 34, 10, -15, 100 | ||||||
| вставляем 100 после i-го (первого) элемента | |||||||||
| да | 5 | 1 | 3, 100, -12, 100, 5, 14, 27, 100, -6, 100, 1, 34, 10, -15, 100 | ||||||
