Уроки 69 - 70
Динамические массивы
(§40. Динамические массивы)

Содержание урока

Что это такое?

Размещение в памяти

Использование в подпрограммах

Расширение массива

Как это работает?

Вопросы и задания

Задачи

Расширение массива

Задача 2. С клавиатуры вводятся натуральные числа, ввод заканчивается числом 0. Нужно вывести на экран эти числа в порядке возрастания.

Как и в предыдущей задаче, для сортировки нужно предварительно сохранить все числа в оперативной памяти (в массиве). Но проблема в том, что размер этого массива становится известен только тогда, когда будут введены все числа. Что же делать?

В первую очередь приходит в голову такой вариант: при вводе каждого следующего ненулевого числа расширять массив на 1 элемент и записывать введённое число в последний элемент массива:

read(х);
while х<>0 do begin
	SetLength(A,Length(А)+1);
	A[High(А)]:=х;
	read(х)
end;

Здесь х — это целая переменная. К счастью, при таком расширении массива значения всех существующих элементов сохраняются.

Чем плох такой подход? Дело в том, что память в «куче» выделяется блоками. Поэтому при каждом увеличении длины массива последовательно выполняются три операции:

1) выделение блока памяти нового размера;
2) копирование в этот блок всех «старых» элементов;
3) удаление «старого» блока памяти из «кучи».

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

Ситуацию можно немного исправить, если увеличивать массив не каждый раз, а, скажем, после каждых 10 введённых элементов. То есть когда все свободные элементы массива заполнены, к нему добавляется ещё 10 новых элементов. При этом нужно считать фактическое количество записанных в массив значений, потому что определить их, как в предыдущей программе, через функцию Length (А), будет невозможно:

N: =0 ; 
read(х);
while х<>0 do begin
	if N>High(A) then
		SetLength(A, Length(A)+10);
	A[N]:=x;
	N:=N+1;
	read (x)
end;

Здесь целая переменная N — это счётчик введённых чисел.

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

Следующая страница Как это работает?

Cкачать материалы урока