Организация взаимосвязей в связанных динамических данных

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

Элемент динамической структуры данных должен состоять как минимум из двух полей: информационного (содержащего заданную условием задачи информацию) и указательного. Поэтому элементы динамической структуры должны иметь тип «запись», который позволяет объединять вместе величины разных типов.

Такую структуру можно представить схемой, на которой Inf – название информационного поля, Link - указательного:

Inf		Inf		Inf
Link		Link		Link

Это самая простая динамическая информационная структура – односвязный список. Особенность списка: указательное поле последнего элемента содержит значение Nil. Это признак конца списка. Элементы его могут быть объявлены так:

Type

TP=^Telem; {тип для объявления указателя}

Telem = record

Inf: integer; {информационное поле}

Link: TP; {указательное поле}

end;

В примере объявлена запись Telem, определяющая элемент списка.

Особенность объявления элемента динамических данных на Pascal’е: запись содержит поле Link, которое является указателем на саму структуру Telem. Для этого поля перед записью объявлен специальный тип TP, которой является указателем на Telem (объявление TP=^Telem;). Получается, что имя Telem используется раньше, чем описывается. Только для указателей сделано такое исключение: перед описанием структуры разрешено описывать тип указателя на эту структуру.

Основные типы связанных динамических структур

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

Кольцевой список – это такие же данные, как и линейный список, но имеющие дополнительную связь между последним и первым элементами списка.

Очередь – частный случай линейного односвязного списка, для которого разрешены только два действия: добавление элемента в конец (хвост) очереди и удаление элемента из начала (головы) очереди.

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

Деревья – это динамические данные иерархической структуры произвольной конфигурации. Элементы дерева называются вершинами (узлами).

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

Рассмотрим работу со списком.

Работа с очередью

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

Type

TP = ^Telem;

Telem = record

inf:integer;

Link:TP;

end;

var

StartP,EndP:TP; {указатель на первый и последний элементы}

k,n,i:integer;

{-----процедура добавление элемента в очередь---------------------}

procedure AddEl(val: integer);

var

p:TP; {указатель на очередной элемент}

begin

1) new(p); {выделяем память под текущий элемент}

2) p^.inf:=val; {присваиваем значение информационному полю}

3) p^.Link:=nil; {"обнуляем" указательное поле}

4) if EndP = nil {если создается первый элемент}

then StartP:=p {то его адрес в указатель на начало очереди}

else {иначе, т.е. создается очередной элемент}

EndP^.Link :=p;{то его адрес в указательное поле предыдущего элемента}

5) EndP:=p; {в указатель на конец списка - адрес добавленного элемента}

end;

{- удаление первого элемента очереди(адрес которого в указателе на начало)-}

function GetDelEl:integer;

var

p:TP; {вспомогательный указатель на текущий элемент}

begin

6) GetDelEl:=StartP^.Inf; {присваиваем функции результат - значение

информационного поля первого элемента }

7) p:=StartP; {адрес этого элемента - в p}

8) StartP:= p^.Link; {первым станет следующий, поэтому его адрес в StartP}

9) if StartP = nil {если следующий - последний }

then EndP:=nil; {сбросить указатель на конец}

10) dispose(p); {удалить элемент}

end;

{--------- ГЛАВНАЯ ПРОГРАММА ------------}

begin

write('Введите количество элементов очереди ');

readln(k);

{---формирование очереди из k элементов---}

StartP:=nil;EndP:=nil; {*}

for i:=1 to k do

begin

write('введите ',i,' число ');readln(n);

AddEl(n); {**}

end;

{---распечатка и удаление очереди из памяти---}

while StartP <> nil do

writeln(GetDelEl); {***}

end.

Рассмотрим процесс выполнения программы:

Начинается работа с ввода количества элементов очереди k. Пусть k=3.

Затем строка {*} :

StartP	Nil	EndP	Nil

Происходит вход в цикл for, вводится первое число в переменную n (пусть n = 5). Начинается формирование первого элемента очереди – вызов процедуры AddEl для значения n.

Строка 1. Выделение памяти под размещение элемента очереди. В памяти выделяется область, размер которой определяется типом Telem. В этой области есть место для поля val и указателя Link (он пока неопределен). Адрес области помещается в указатель p, объявленный в процедуре.

StartP	Nil	EndP	nil	P	Адрес1	.Inf
						.Link	?

Строки 2,3. Заполнение выделенной области информацией: по адресу, содержащемуся в указателе, в поле val заносится 5, в поле Link значение nil (указатель обнуляется)

StartP	Nil	EndP	nil	P	Адрес1	.Inf	5
						.Link	nil

Строка 4: Значение EndP сравнивается с nil. Результат сравнения – TRUE. Это значит, что указатель на конец очереди пока обнулен и, следовательно, созданный только что элемент будет первым. Чтобы он стал первым, нужно его адрес положить в указатель на начало очереди. Поэтому по результатам сравнения происходит переход на then и адрес сформированного элемента присваивается указателю на начало очереди StartP.

StartP	Адрес1	EndP	nil	P	Адрес1	.Inf	5
						.Link	nil

Строка 5. Сформированный только что элемент является последним в очереди. Поэтому его адрес присваивается указателю EndP:

StartP	Адрес1	EndP	адрес1	P	Адрес1	.Inf	5
						.Link	nil

Работа процедуры завершается, происходит возврат в основную программу. Продолжает работать цикл for, выполняется ввод второго элемента (пусть это число 10). Снова происходит вызов процедуры добавления элемента в очередь (строка **). Этой процедуре в качестве параметра передается значение 10. Процедура начинает работать.

Строка 1. Выделение памяти под следующий элемент:

StartP	Адрес1	EndP	адрес1	P	Адрес2	.Inf	5	.Inf
						.Link	nil	.Link	?

Строки 2,3. Заполнение выделенной области информацией: по адресу, содержащемуся в указателе: в поле val заносится 10, в поле Link значение nil (указатель обнуляется)

StartP	Адрес1	EndP	адрес1	P	Адрес2	.Inf	5	.Inf	10
						.Link	nil	.Link	nil

Строка 4: Значение EndP сравнивается с nil. Результат сравнения – FALSE. Это значит, что созданный элемент будет продолжать очередь. Поэтому его адрес помещается в указательное поле Link предыдущего элемента, который пока является последним. По результатам сравнения происходит переход на ветку else. По адресу последнего элемента EndP^ (у нас пока всего один, который и первый и последний) происходит обращение к полю Link и ему присваивается значение указателя P. Оператор EndP^.Link :=p;

StartP	Адрес1	EndP	адрес1	P	Адрес2	.Inf	5	.Inf	10
						.Link	адрес2	.Link	nil

Строка 5. Сформированный только что элемент является последним в очереди. Поэтому его адрес помещается в указатель EndP:

StartP	Адрес2	EndP	адрес2	P	Адрес2	.Inf	5	.Inf	10
						.Link	адрес2	.Link	nil

Завершается работа процедуры. Происходит возврат в основную программу. Продолжает работать цикл for, выполняется ввод второго элемента (пусть это число 20). Снова происходит вызов процедуры добавления элемента в очередь (строка **). Этой процедуре в качестве параметра передается значение 20. Процедура начинает работать.

Строка 1. Выделение памяти под следующий элемент:

StartP	Адрес1	EndP	адрес2	P	Адрес3	.Inf	5	.Inf	10	.Inf
						.Link	адрес2	.Link	nil	.Link	?

Строки 2,3. Заполнение выделенной области информацией: по адресу, содержащемуся в указателе: в поле val заносится 20, в поле Link значение nil (указатель обнуляется)

StartP	Адрес1	EndP	адрес2	P	Адрес3	.Inf	5	.Inf	10	.Inf	20
						.Link	адрес1	.Link	nil	.Link	nil

Строка 4: Значение EndP сравнивается с nil. Результат сравнения – ЛОЖЬ. Это значит, что созданный только что элемент будет продолжать очередь. Для этого его адрес должен быть помещен в указательное поле Link элемента, который пока является последним. По результатам сравнения происходит переход на ветку else. По адресу последнего элемента EndP^ (у нас это второй элемент) происходит обращение к полю Link и ему присваивается значение указателя P. Оператор EndP^.Link :=p; Затем устанавливается указатель на конец.

StartP	Адрес1	EndP	адрес3	P	адрес3	.Inf	5	.Inf	10	.Inf	20
						.Link	адрес2	.Link	адрес 3	.Link	nil

Завершается работа процедуры, происходит возврат в основную программу. Цикл for завершает работу. Начинается вывод информации очереди на экран. При этом одновременно происходит ее удаление из памяти.

Начинает работу цикл While, т.к. значение указателя StartP не равно Nil.

Вызывается процедура GetDelEl.

Строка 6. Функции GetDelEl присвается результат - значение, находящееся по адресу StartP в поле inf. Это число 5.

Строка 7. Указателю p присваивается адрес начала очереди – значение, хранящееся в StartP.

StartP	Адрес1	EndP	адрес3	P	Адрес1	.Inf	5	.Inf	10	.Inf	20
						.Link	адрес2	.Link	адрес 3	.Link	nil

Строка 8. После удаления первого элемента очереди на его место станет второй. Поэтому адрес второго нужно положить в StartP (указатель на начало очереди). Обращение к этому значению записывается в виде p^.Link:

StartP	Адрес2	EndP	адрес2	P	Адрес1	.Inf	5	.Inf	10	.Inf	20
						.Link	адрес2	.Link	адрес 3	.Link	nil

Строка 9. Проверяется, достигнут ли конец очереди. Для этого значение StartP сравнивается с nil. Результат – False (значит, удаляется не последний элемент очереди), поэтому оператор EndP:=nil не выполняется.

Строка 10. Освобождается область памяти, адрес которой записан в р, т.е. удаляется первый элемент очереди.

StartP	Адрес2	EndP	адрес2	P	?			.Inf	10	.Inf	20
								.Link	адрес 3	.Link	nil

Завершается работа функции. Происходит возврат в основную программу, результат функции (число 5) выводится на экран.

Начинается новый проход цикла While. StartP не равен nil, поэтому снова повторяется цикл и вызывается функция удаления элемента. Выполнение ее происходит аналогично предыдущему вызову. Результат функции - 10, состояние памяти перед выходом из функции:

StartP	Адрес2	EndP	адрес2	P	?					.Inf	20
										.Link	nil

Действия повторяются, снова происходит вызов функции. Действия похожи, но в строке 9 обнуляется StartP. Результат функции – 20. Состояние перед выходом из функции:

StartP

Nil

EndP

Nil

Это же состояние сохраняется и перед завершением работы программы.