ВСТАВКА ЭЛЕМЕНТА В УПОРЯДОЧЕННЫЙ МАССИВ

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

Пример.

Задан упорядоченный по возрастанию массив и произвольное число . Вставить число в массив , не нарушая упорядоченности этого массива.

При этом может иметь место один из трех вариантов:

а)

б)

в)

Пусть массив имеет вид

5 12 18 22 29 31 35 41 47 53 62 77 ( )

Если , т.е. меньше первого элемента , то требуется сдвинуть весь массив вправо на один элемент, а элементу присвоить значение . Если , т.е. , то определяется индекс ближайшего элемента , после чего подмассив сдвигается вправо на один элемент, а элементу присваивается значение . Если , т.е. , то сдвиг элементов массива не производится, а значение переменной присваивается элементу . В любом случае при включении значения в состав массива количество элементов этого массива увеличивается на 1.

{$R+}

Program Insertion;

Const Nmax = 100;

Type Ar = array[1..Nmax] of integer;

VarX : Ar;

i,k,n : integer;

Begin

Ввод и печать n, X, b

k:=0;

For i:=1 ton do { Поиск ближайшего }

If x[i]>b then{ элемента, большего }

Begin { значения b}

k:=i; Break

End;

If k=0 then { b >= x[n] }

x[n+1]:=b

Else

Begin{ Сдвиг подмассива }

For i:=n+1 downto k+1 do { при b<x[n]}

x[i]:=x[i-1];

x[k]:=b { Вставка значения b }

End;

Inc(n); { Увеличение размера массива }

Печать n, X

End.

Примечание 1. Сдвиг части массива X вправо оператором

For i:=k+1 ton+1 do

x[i]:=x[i-1];

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

Примечание 2. Фраза {$R+} означает включение директивы компилятора R.

Примечание 3. Выход за пределы границ массива X будет иметь место при n = Nmax. Следствием этого может быть получение неправильных результатов или зацикливание программы. При включенной директиве R в этом случае будет сгенерировано прерывание 201, что позволит индицировать такую ошибку при отладке программы. Для повышения надежности работы программы целесообразно объявление типа массива выполнить в виде

Ar = array[1..Nmax+1] of integer,

а после ввода массива X проверить условие n £ Nmax и в случае его нарушения выдать соответствующее сообщение на экран.