Материал: Мансуров. Основы программирования в среде Lazarus. 2010

4.3 Динамические структуры данных

____________________________________________________________________

мент, помещенный в него последним. Стек работает по принципу «последним

пришел, первым ушел» ("Last In – First Out", LIFO).

Лицам мужского пола, возможно, будет легче понять принцип работы сте-

ка, если они представят себе обойму пистолета. Патрон, помещенный в обойму последним, первым уйдет в цель. Особам женского пола более приятно будет ассоциировать стек со стопкой тарелок. Тарелка, помещенная в стопку послед-

ней, первой пойдет в "дело".

Рассмотрим процесс помещения в стек трех элементов a, b, c. Первона-

чально стек пусть будет пустым. На рисунке 4.22 показаны последовательные

c верхушка

b

a

Рис. 4.22. Последовательные состояния стека при добавлении элементов

Таким образом, последний добавленный в стек элемент с оказывается в верхушке стека. Применение стека рассмотрим на примере составления алго-

ритма обхода двоичного дерева слева.

336

Глава 4 Типовые алгоритмы обработки информации

____________________________________________________________________

Дерево:=правое поддерево

Рис. 4.23 Алгоритм обхода двоичного дерева слева

4.3.1 Представление в памяти компьютера динамических структур.

Память компьютера состоит из ячеек, называемых байтами. Каждый байт имеет свой номер или иначе адрес. Нумерация идет от 0 до N-1. Где N объем оперативной памяти. Если мы хотим записать в память компьютера значение некоторой переменной, то мы не указываем конкретный адрес, куда должно быть записано значение переменной. Мы просто даем этой переменной имя, т.е.

обозначаем ее, например А. Компилятор отведет этой переменной нужное ко-

личество байтов. Каждая переменная в памяти занимает в зависимости от ее типа определенное количество байтов, расположенных подряд. При этом, адре-

337

4.3 Динамические структуры данных

____________________________________________________________________

сом переменной считается адрес ее первого байта. Таким образом, под А мы подразумеваем не само значение переменной, а ее адрес (адрес первого байта).

Хотя в программе мы пишем, например А:= 28; на самом деле мы говорим компьютеру: запиши в байты памяти начиная с номера А число 28. Перемен-

ной А компилятор отведет четыре подряд расположенных байта, поскольку число 28 является целым.

Если мы хотим представить в памяти некоторый массив, то под этот мас-

сив компилятор также отведет группу подряд расположенных байтов. Пусть этому массиву присвоено имя M, количество элементов массива 20, тип массива

– целый, т.е. каждый его элемент это целые числа.

Тогда компилятор отведет под этот массив 20*4=80 байтов. Причем для обращения к отдельным элементам массива используется индекс M[1], M[I],B[I+K], т.е. в этом случае адрес состоит из двух частей: одна часть ука-

зывает на начало всей совокупности, отводимой для массива, а другая – адрес байта относительно начала совокупности. Обычно адрес начала совокупности называют базовым адресом, а адрес байта относительно начала совокупности – смещением.

Таким образом:

Полный адрес = базовый адрес + смещение

338

Глава 4 Типовые алгоритмы обработки информации

____________________________________________________________________

Байты памяти

0

Переменной А отведено 4 байта.

Массиву М отведено

20х4 = 80 байтов.

N-1

Рис. 4.24. Схема распределения памяти переменной А и массиву М

Такая совокупность называется вектором памяти. В языке Pascal масси-

вы (как одномерные, так и многомерные) представляются векторами.

Но можно использовать и другой способ представления информации.

Как известно, последовательности байтов памяти мы можем интерпрети-

ровать как угодно, в частности их можно интерпретировать как адрес некото-

рой другой совокупности байтов. Например, значение переменной A: <А> = 2000← можно считать адресом

Переменная, значением которой является некоторый адрес памяти, назы-

вается указателем, а адрес, на который указывает указатель, называется звеном.

Если имеется некоторая последовательность указателей и звеньев, то ее назы-

вают цепочкой или сцеплением звеньев.

Рассмотрим простейшую структуру сцепления – связанный список. Пред-

ставим, например, с помощью связанного списка строку символов "МАМА".

339

4.3 Динамические структуры данных

____________________________________________________________________

Признак конца списка

Рис. 4.25. Связанный список

Как видно из рисунка связанный список состоит из двух полей. Первое по-

ле содержит непосредственно сам элемент списка. Второе поле – указатель на следующий элемент списка. Причем поле указателя последнего элемента спи-

ска содержит специальный признак конца списка – nil.

Тип nil означает "пустой" адрес, т.е. этот адрес не может быть адресом ни одной переменной, он является "ничейным", фиктивным адресом. В списках nil обозначает конец списка.

Связанные списки еще называют линейными списками.

Стек и деревья можно реализовать как с помощью векторов памяти (мас-

сивов), так и с помощью линейных списков, используя указатели.

4.3.2 Реализация стека с помощью массивов

Напишем программу работы со стеком. Существует всего две операции со стеком – поместить элемент в стек и извлечь элемент из стека. Используются также термины втолкнуть (затолкнуть) элемент в стек и вытолкнуть элемент из стека. Процедуру, реализующую операцию помещения элемента в стек назовем

Put_Stack, а процедуру, реализующую процесс извлечения элемента из стека

– Take_Stack. Вполне можно было бы назвать эти процедуры и Push_Stack,

340