Удаление всего списка с освобождением памяти.

Procedure Delete_List(Var First : el);

Var

P, q : el;

Answer : string;

Begin

If First <> Nil Then

Begin{ список не пуст }

writeln ( 'Вы хотите удалить весь список ? (да/нет)' );

readln ( answer );

if answer = 'да' then

Begin

q:=First;

p:=nil;

While ( q <> nil ) do

Begin

p:=q;

q:=q^.Next;

Dispose(p);

End;

First:=Nil;

End;

End

Else

writeln ('список пуст');

End;

Задачи на замену элементов в линейном однонаправленном списке без головного элемента.

Операция замены элемента в списке практически представляет собой комбинацию удаления и вставки элемента. Читателю дается возможность, используя представленные ранее графические приемы и примеры программ, самому написать процедуры замены элементов. Перед выполнением операции замены элемента желательно запрашивать у пользователя подтверждение замены.

Действуя аналогично, можно построить графические схемы и программы задач действий с двунаправленными списками.

Стеки, деки, очереди.

Одной из важных концепций в программировании является концепция стека. Стеком называется упорядоченный набор элементов, в котором добавление новых элементов и удаление существующих выполняется только с одного его конца, который называется вершиной стека. Бытовой иллюстрацией стека может служить стопка книг. Добавить к ней очередную книгу можно, положив новую поверх остальных. Верхняя книга (элемент стека) и есть вершина стека. Просматривать книги можно только по одной, снимая их с вершины. Чтобы получить книгу из середины стека, надо задать критерий отбора и удалять элементы-книги из стека до тех пор, пока не будет найдена нужная книга. Элементы из стека могут удаляться, пока он не станет пустым. Таким образом, над стеком выполняются следующие операции:

1) добавление в стек нового элемента;

2) определение пуст ли стек;

3) доступ к последнему включенному элементу, вершине стека;

4) исключение из стека последнего включенного элемента.

Отсюда ясно виден принцип работы со стеком: «пришел последним - ушел первым» (last in - first out, LIFO).

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

Другим специальным видом использования списка является очередь. Существуют различные разновидности очередей, здесь будет рассмотрена простая бесприоритетная очередь. При этом добавление элементов производится в конец очереди, а выборка и удаление элементов - из начала. Принцип доступа к очереди – «первым пришел - первым ушел» (first in - first out, FIFO). Принцип обработки как для стека, так и для очереди определяет набор соответствующих процедур. Для реализации очереди необходим список, для которого известны адрес первого и адрес последнего элементов. Таким образом, над очередью выполняются следующие операции:

1) добавление в конец очереди нового элемента;

2) определение пуста ли очередь;

3) доступ к первому элементу очереди;

4) исключение из очереди первого элемента.

Эти операции могут быть взяты из стандартного набора действий со списком.

Кроме рассмотренных очереди и стека есть ещё и третий вариант структуры данных - дек, очередь с двойным доступом, или, как ещё его называют, - двухконечный стек. Для дека добавление элементов, доступ к «вершине» и удаление элемента возможны с обоих концов списка.

Использование рекурсии при работе со списками.

Рекурсия является одним из удобнейших средств при работе с линейными списками. Она позволяет сократить код программы и сделать алгоритмы обхода узлов деревьев и списков более понятными.

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

Хотя рекурсии в списках не являются настолько очевидным решением, как в деревьях, все же они позволяют оптимизировать обработку линейных списков. В списках возможны два варианта прохода: из начала в конец и из конца в начало. Эти методы реализуются очень легко в случае с двунаправленными списками.

Рекурсию в линейных списках демонстрирует следующий пример: подсчет числа элементов в линейном однонаправленном списке.

Procedure Count_El (var q : El; var count : integer);

Begin

if q< >nil { ограничитель рекурсии } then

Begin

inc(count);

Count_El( q^.next , count);

End

End;

При входе в процедуру count = 0,а q=first (указатель на первый элемент списка).Далее рекурсивная процедура работает так. Анализируется значение указателя, переданного в процедуру. Если он не равен Nil (список не закончился), то счетчик числа элементов увеличивается на 1. Далее происходит очередной вызов рекурсивной процедуры уже с адресом следующего элемента списка, а «текущая» рекурсивная процедура приостанавливается до окончания вызванной процедуры. Вызванная процедура работает точно так же: считает, вызывает процедуру и переходит в состояние ожидания. Формируется как бы последовательность из процедур, каждая из которых ожидает завершения вызванной процедуры. Этот процесс продолжается до тех пор, пока очередное значение адреса не станет равным Nil (признак окончания списка). В последней вызванной рекурсивной процедуре уже не происходит очередного вызова, так как не соблюдается условие q<>nil, срабатывает «ограничитель рекурсии». В результате процедура завершается без выполнения каких-либо действий, а управление возвращается в «предпоследнюю», вызывающую процедуру. Точкой возврата будет оператор, стоящий за вызовом процедуры, в данном тексте - End, и «предпоследняя» процедура завершает свою работу, возвращая управление в вызвавшую её процедуру. Начинается процесс «сворачивания» цепочки ожидающих завершения процедур. Счетчик count, вызывавшийся по ссылке, сохраняет накопленное значение после завершения всей цепочки вызванных рекурсивных процедур.

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

Бинарные деревья.

Кроме линейных структур существуют и нелинейные, при помощи которых задаются иерархические связи данных. Для этого используются графы, а среди них сетевые и древовидные структуры. Рассмотрим один вид деревьев - бинарное дерево.

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

Рис. 23 Двоичное дерево

На рис. 23 показан наиболее часто встречающийся способ представления бинарного дерева. Оно состоит из девяти узлов. Корнем дерева является узел А. Левое поддерево имеет корень В, а правое поддерево - корень С. Они соединяются соответствующими ветвями, исходящими из А. Отсутствие ветви означает пустое поддерево. Например, у поддерева с корнем С нет левого поддерева, оно пусто. Пусто и правое поддерево с корнем Е. Бинарные поддеревья с корнями D, G, H и I имеют пустые левые и правые поддеревья. Узел, имеющий пустые правое и левое поддеревья, называется листом. Если каждый узел бинарного дерева, не являющийся листом, имеет непустые правое и левое поддеревья, то дерево называется строго бинарным

Уровень узла в бинарном дереве определяется следующим образом: уровень корня всегда равен нулю, а далее номера уровней при движении по дереву от корня увеличиваются на 1 по отношению к своему непосредственному предку. Глубина бинарного дерева - это максимальный уровень листа дерева, иначе говоря, длина самого длинного пути от корня к листу дерева. Узлы дерева могут быть пронумерованы по следующей схеме (см. рис. 24)

Рис. 24 Схема нумерации узлов двоичного дерева

Номер корня всегда равен 1, левый потомок получает номер 2, правый - номер 3. Левый потомок узла 2 должен получить номер 4, а правый - 5, левый потомок узла 3 получит номер 6, правый - 7 и т.д. Несуществующие узлы не нумеруются, что, однако, не нарушает указанного порядка, так как их номера не используются. При такой системе нумерации в дереве каждый узел получает уникальный номер.

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

Почти полное бинарное дерево определяется как бинарное дерево, для которого существует неотрицательное целое k такое, что:

1) каждый лист в дереве имеет уровень k или k+1;

2) если узел дерева имеет правого потомка уровня k+1, тогда все его левые потомки, являющиеся листами, также имеют уровень k+1.

Не нашли, что искали? Воспользуйтесь поиском по сайту: