3. Способы организации связных ддс
Для реализации некоторой динамической структуры на языке программирования Паскаль необходимо:
отобразить ее на одну из структур языка программирования Паскаль;
написать на Паскаль процедуры выполнения типовых операций.
Рассмотрим первую операцию.
Как уже отмечалось выше, ДДС представляют собой отдельные элементы, связанные с помощью ссылок. Каждый элемент хранит определенную информацию (данные) и указатель связи с другими элементами структуры, то есть каждый элемент (узел) состоит из двух областей памяти: поля данных и ссылок:
Ссылки представляют собой адреса других узлов этого же типа, с которыми данный элемент логически связан. В языке Паскаль для организации ссылок используются указатели.
Из рассмотренного выше представления следует, что в качестве элементов таких структур необходимо использовать записи, которые могут объединять в единое целое разнородные элементы.
В простейшем случае элемент ДДС должен состоять из двух полей: информационного и указательного.
При добавлении нового узла в такую структуру выделяется новый блок памяти и с помощью ссылок устанавливаются связи этого элемента с уже существующими. Для обозначения конечного элемента в цепи используются нулевые или пустые ссылки (nil в языке Паскаль).
Схематично такую структуру данных можно показать следующим образом:
В общем случае запись может содержать не один, а несколько указателей и несколько полей данных.
4. Описание односвязной дсд
Правило последовательности описаний в Паскаль требует, чтобы каждый идентификатор был описан, прежде чем он будет использоваться для других объявлений.
Для описания типов элементов динамических структур данных сделано исключение: тип указателя на элемент динамической структуры данных может и должен быть описан перед описанием типа этого элемента.
Соответствующее ей объявления будут иметь такой вид:
tуре <имя_типа>=^ <имя_элемента>;
<имя_элемента>=record
<имя_информационной части>: <тип информац. части>;
<имя_указатель>: <имя_типа>
end;
Тип информационной части может быть любым простым типом, массивом, множеством или записью.
Пример: Динамическая структура, содержащая вещественные числа, описывается так:
type ukaz=^element;
element = record
inf: real;
next: ukaz
end;
var sp: ukaz;
Начнем рассмотрение основных принципов построения и работы с ДСД с частных случаев линейного односвязного списка.
5. Стек
Образно стек представляет собой “трубу” с одним запаянным концом, куда помещаются “бочонки” – элементы.
Правило стека:
«первым пришел – последним вышел»
или
«последний пришел – первым уйдешь».
Использование стека является непременным атрибутом любой вычислительной машины, так как стек необходим для организации вызовов подпрограмм и обработки прерываний.
Над стеком можно реализовывать следующие операции:
создание (инициализация) стека;
добавление элемента в стек;
удаление элемента из стека;
уничтожение стека.
Рассмотрим общую схему формирования стека.
Для создания стека и работы с ним необходимо иметь один основной указатель на вершину стека (возьмем идентификатор Beg).
Для удобства работы часто используют временный (рабочий) указатель (возьмем р).