Вставка элементов в одномерный массив

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

С заданным номером

Пример

Вставить число 100 после пятого элемента массива.

Решение

Пусть k − номер элемента, после которого мы дол­жны вставить элемент х (k и х будем вводить с клави­атуры). Вставка осуществляется следующим образом:

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

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

¨ элементу с номером (k+1) присваиваем значение х.

Рассмотрим конкретный пример. Пусть дан следу­ющий одномерный массив из 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 элементов, и это надо учесть при описании типа myarray:   

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

Будем выводить массив два раза − до и после встав­ки нового элемента, используя уже известную процеду­ру Print1.

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

Program Example_105;

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(А);

Print1(n, А); {Вывод начального массива

из n элементов}

Writeln('Номер элемента, после которого

вставлять, ');

Writeln('и значение нового элемента');

Readln(k, x);

Insert1(k, x, A);

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

Readln;

End.

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

Данным номером

Пример

Вставить число 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_106;

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(А);

Print1(n,А); {вывод начального массива}

Writeln('Номер элемента, перед которым

вставлять, ');

Writeln('и значение нового элемента');

Readln(k,x);

Insert2(k, x, A);

Print1(n+1, A); {Вывод массива после

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

Readln;

End.

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

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

Пример

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

Решение

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

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

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

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

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

Program Example_107;

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(А);

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.

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

Перестановка двух элементов

Пример

Поменять местами значения двух элементов с номе­рами k1 и k2 (где k1 и k2 вводятся с клавиатуры).

Решение

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

Program Example_108;

Procedure Swap(k1, k2: Integer;

Varm: myarray);

Var x: Integer;

Begin

x:=m[k1]; m[k1]:=m[k2]; m[k2]:=x;

End;

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

Перестановка нескольких

Элементов (части) массива

Пример

Дан одномерный массив А, состоящий из 2n эле­ментов. Поменять местами его половины.

Решение

Пусть массив А состоит из 10 элементов, то есть n=5: 1, 12, 23, 3, 7, 13, 27, 6, 9, 11. Тогда если мы поменяем местами его половины, то получим такой массив А: 13, 27, 6, 9, 11, 1, 12, 23, 3, 7. Заметим, что мы меняем местами элементы с номерами 1 и n+1, 2 и n+2 и так далее; последняя пара − n и 2n. Легко заметить и то, что элемент с номером i меняется местами с элементом с номером n+i. Поэтому, исполь­зуя процедуру Swap из примера, можно в основной про­грамме применить цикл:

Program Example_109;

...

For i:=1 To n div 2 Do

Swap(i, i+n div 2, A);

ДВУХМЕРНЫЕ МАССИВЫ