Линейные структуры данных. Стэк и дэк.

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

SELECT DISTINCT T_Base.Node FROM T_Base, T_Helper

WHERE T_Base.ID=T_Helper.UID and T_Helper.UID NOT IN (

SELECT DISTINCT ParentID FROM T_Helper);

Проблемы, возникающие при работе со списками. Способы их преодоления.

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

Первая проблема – проблема «концов списка»: при каждом обращении к элемента необходимо

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

Но циклические списки в свою очередь несут за собой ряд проблем.

Проблема – возможна потеря данных. Способы решения:

Кольцо с указателями на заголовок. При входе в кольцо не через его начало можно быстро получить информацию из заголовка.

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

«Коралловое» кольцо для повышения устойчивости. Левые коэф. у нечетных, правые у всех, ссылка на заголовок у четных.

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

3) Понятие кольца. Типы организации колец. Особенности «коралловой» организации кольца.

Кольцо –включение идет по одному, а выключение по-другому. Может быть потеря данных. Кольцо с указателями на заголовок. При входе в кольцо не через его начало можно быстро получить информацию из заголовка. Кольцо с двунаправленными указателями. Если какая-нибудь запись цепи будет разрушена, все остальные записи останутся доступными. Если будет испорчен один указатель – его можно восстановить. «Коралловое» кольцо для повышения устойчивости. Если разрушена запись с четным номером, любая другая запись может быть найдена. Если потеряна запись с нечетным номером, то некоторые записи могут стать недоступными.

Линейные структуры данных. Стэк и дэк.

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

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