Сжатие массива

Пример. 3.2. Написать программу, которая «сжимает» целочисленный массив из 10 элементов, удаляя из него элементы, меньшие заданной величины. Освободившиеся в конце массива элементы заполнить нулями.

Исходный массив:

6 -8 15 9 -1 3 5 -10 12 2

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

6 15 9 5 12 0 0 0 0 0

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

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

Рис. 3.2. Сжатие с использованием дополнительного массива

program compress_l;

const n = 10;

type mas = array [1 .. n] of integer;

var

a, b : mas;

i : integer; { номер текущего элемента в массиве а }

j : integer; { номер текущего элемента в массиве b }

x : integer; { заданное число}

begin

writeln('Введите число');

readln(x);

writeln('Введите элементы массива');

for i := 1 to n do read(a[i]);

j :=0;

for i:=1 to n do

if a[i] >= x then begin

inc(j); b[j] := a[i];

end;

a := b;

writeln('Преобразованный массив:');

for i := 1 to n do write(a[i]:4);

end.

Обнуление «хвоста» массива происходит естественным образом, поскольку в Паскале глобальные переменные обнуляются.

Однако для массивов большой размерности выделение двойного объема памяти может оказаться слишком расточительным. Поэтому далее приводится вариант программы, в которой преобразование массива выполняется «на месте».

Алгоритм работы этой программы выглядит следующим образом:

1. Просматривая массив, определить номер самого первого из удаляемых элементов.

2. Если таковой есть, сдвигать каждый последующий элемент массива на первое «свободное» место, обнуляя оставшуюся часть массива.

Иллюстрация алгоритма приведена на рис. 3.3.

Рис. 3.3. Сжатие массива «на месте»

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

program compress_2;

const n = 10;

type mas = array [1 .. n] of integer;

var

a : mas;

i : integer; { номер текущего элемента }

j : integer; { номер элемента, в который помещается текущий }

x : integer; { заданное число }

begin

writeln('Введите число');

readln(x);

writeln('Введите элементы массива');

for i := 1 to n do read(a[i]);

j := 0;

for i := 1 to n do { поиск номера первого удаляемого элемента }

if a[i] < x then begin j := i; break end;

if j <> 0 then begin { если есть, что удалять, }

for i := j + 1 to n do { просмотреть оставшуюся часть массива }

if a[i] >=x then begin { такие элементы надо оставить в массиве }

a[j] := a[i]; inc(j); end;

for i := j to n do a[i] := 0; { обнуление "хвоста" массива }

end;

writeln('Преобразованный массив:');

for i := 1 to n do write(a[i]:4);

end.

Для тестирования этой программы попробуйте использовать несколько значений переменной х – таких, чтобы из массива:

§ не был удален ни один элемент;

§ были удалены все элементы;

§ была удалена часть элементов.