УДАЛЕНИЕ ЭЛЕМЕНТОВ ИЗ МАССИВА

Чтобы удалить элемент из массива , необходимо сдвинуть элементы на один "шаг" влево и уменьшить значение на 1. Если , то в этом случае достаточно выполнить .

Пример 1. Из массива Х удалить минимальный элемент.

Program DelMin;

Const Nmax = 200;

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

Var i,imin,n : byte;

xmin : integer;

X : Ar;

Begin

В в о д n, X

Xmin:=x[1]; imin:=1; { Определение положения }

For i:=2 to n do { (индекса) минимального}

If x[i]<xmin then{ элемента }

Begin

Xmin:=x[i]; imin:=i

End;

For i:=imin ton-1 do{ Удаление элемента }

x[i]:=x[i+1]; { с индексом imin }

Dec(n); { Уменьшение размера массива }

П е ч а т ь n, X

End.

Если imin = n, то второй цикл For не работает (начальное значение параметра i больше его конечного значения), но размер массива n уменьшается на 1.

Пример 2. Из массива Х удалить все нулевые элементы.

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

Program Mas;

Const Nmax = 500;

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

Var i,j,n : integer;

X : Ar;

Begin

Ввод n, X

Fori:=1 to n do

If x[i]=0 then

Begin

Forj:=i ton-1 do

x[j]:=x[j+1];

Dec(n);

End;

Вывод n, X

End.

По поводу программы Mas можно сделать три замечания.

1. При i = n, когда анализируется последний элемент массива, параметр j изменяется от n до n-1, т.е. начальное значение параметра цикла больше его конечного значения. Как известно из описания оператора For, цикл в этом случае не выполняется, т.е. оператор цикла эквивалентен пустому оператору. Следовательно, при происходит лишь уменьшение значения n, что соответствует алгоритму решения задачи.

2. Начальное и конечное значения параметра цикла вычисляются до начала цикла и в процессе его выполнения не изменяются. Следовательно, уменьшение значения переменной n при = 0 не изменяет количество повторений цикла по параметру i. Это приводит к избыточной работе программы, но не отражается на правильности решения задачи.

3. Предположим, что в массиве X имеются подряд идущие нулевые элементы и . При i = k будет удален элемент , а на его место перемещается элемент , также равный нулю. Поскольку при новом повторении цикла Forпараметр цикла принимает очередное значение k+1, то новый нулевой элемент не будет анализироваться повторно и, как следствие, не будет удален из массива. Поэтому при наличии в массиве подряд идущих нулевых элементов программа Mas работает неправильно.

Для корректного решения поставленной задачи нужно, чтобы программа после удаления нулевого элемента повторно анализировала этот же элемент и переходила к рассмотрению элемента лишь при ¹ 0. Для этого нужно в программе вместо цикла Forиспользовать цикл While:

Program DelZero1;

ConstNmax = 500;

TypeAr = array[1..Nmax] ofinteger;

Var i,j,n : integer;

X : Ar;

Begin

Ввод n, X

i:=1;

While i<=n do

If x[i]=0 then

Begin

Forj:=i to n-1 do

x[j]:=x[j+1];

Dec(n);

End

Else

Inc(i);

End.

Тот же эффект можно достичь с помощью оператора For, если просмотр массива выполнять справа налево.

ProgramDelZero2;

Const Nmax = 500;

TypeAr = array[1..Nmax] of integer;

Var i,j,n : integer;

X : Ar;

Begin

Ввод n, X

For i:=n downto1 do

If x[i]=0 then

Begin

Forj:=i ton-1 do

x[j]:=x[j+1];

Dec(n);

End;

End.

Обнаружение нулевого элемента во внешнем цикле и, как следствие, его удаление из массива приводит к перемещению уже обработанных элементов в "хвосте" массива и не влияет ни на количество повторений внешнего цикла, ни на анализ оставшихся элементов.

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

ProgramDelZero3;

Const Nmax = 500;

TypeAr = array[1..Nmax] of integer;

Var i,k,n : integer;

X : Ar;

Begin

Ввод n, X

For i:=1 ton do

If x[i]<>0 then

Begin

Inc(k);

If k<>i then

x[k]:=x[i];

End;

n:=k;

End.

Компьютерный эксперимент, проведенный по отношению к программам удаления однотипных элементов из массива (в данном случае нулей), показал, что быстродействие (время обработки одного и того же массива) программами DelZero1, DelZero2 и DelZero3 пропорционально численным значениям 7, 3 и 1.