Программирование в среде Турбо Паскаль (Поляков, Круглов) - страница 137

for i:=1 to 200 do New( D[i] );

как и освобождение:

for i:=1 to 200 do Dispose( D[i] );

Обращение к элементу массива D (разыменование) имеет вид D[i]^[j], где i — номер строки, a j — номер столбца.

Описанный прием достаточно эффективен для многомерных массивов и записей. Таким образом, можно заменять части структуры ссылками на них и забыть про предел в 64K. Но с одномерным массивом так поступить уже нельзя. Придется искать какие-либо обходные пути.

Существует несколько способов хранения данных и их структур, которые ограничены лишь свободным объемом памяти (ОЗУ). К ним относятся списочные структуры, деревья (графы). Отдельно можно выделить структуры типа «стек».

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

- 214 -

ки* nil, т.е. уже ни на что не ссылается. Списки легко создаются, добавляются с любого конца; их можно размыкать для вставки нового элемента, исключать элементы и т.д.

* Так напечатано. Видимо при печати пропущена часть текста.— Ю. Ш.

Мы не будем здесь рассматривать работу со списками. Большинство учебных и справочных изданий по языку Паскаль содержит основные принципы работы с ними.

Вместо этого мы предлагаем пример модуля, реализующего процедуры работы со стеком. Стек, или магазин, иногда называется списком LIFO (последним вошел — первым вышел). Это структура данных, при которой элемент, первым помещенный в стек, будет извлечен оттуда последним. И наоборот, доступнее всех последний положенный в стек элемент. Аналог стека — детская разборная пирамидка из дисков на штырьках. Надеть диск сверху — значит поместить в стек очередное значение. Снять диск (а снять можно только верхний диск) — значит вытолкнуть значение из стека. Доступ к содержимому стека всегда последователен, причем порядок выгрузки элементов из стека обратен порядку их загрузки в стек.

Организация стека основана на связном списке, и поэтому стек занимает в памяти только необходимый на данный момент объем. Наглядно структура стека представлена на рис. 11.9.

Рис. 11.9

- 215 -

Сумма размеров всех хранимых в стеке данных ограничена только размером свободной памяти в куче, хотя элемент данных по-прежнему не должен превышать 64K. Стек оптимален для случаев, когда требуется просчитать и запомнить большое число структур данных, а потом обработать их в обратном порядке (в других случаях он мало полезен). К недостатку стека и списков, вообще, надо отнести расход памяти под узлы (здесь — 2x4 байта на каждый узел). Но если элемент хранимых данных имеет размер, например, 16K, с восемью байтами можно примириться.