Город бешаных рефератиков
.

.

РАЗДЕЛЫ

РЕКОМЕНДУЕМ

КАТАЛОГ РЕФЕРАТОВ

Реферат Алгоритм

Список - конечная последовательность, состоящая из нуля или более атомов или Списков.


Рассмотрим Список L = (a: N, b, c: (d: N), e: L), N = (f: ( ), g: (h: L, j: N)) а соответствующей диаграммой для него будет





Существует много способов для представления Списочных структур в памяти машины. Обычно все они являются вариациями на одну и ту же основную тему, согласно которой для представления общих лесов деревьев используются бинарные деревья: одно поле, скажем RLINK, используется для указания на следующий элемент Списка, а другое поле DLINK можно использовать для указания на первый элемент под-Списка.


Тогда Список можно представить в виде:





Но эта простая идея не вполне пригодна для наиболее часто встречающихся приложений, включающих обработку Списков.

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





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

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

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



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




ГОРОДСКИЕ ЗАКОНЫ

Рефераты и/или содержимое рефератов предназначено исключительно для ознакомления, без целей коммерческого использования. Все права в отношении рефератов и/или содержимого рефератов принадлежат их законным правообладателям. Любое их использование возможно лишь с согласия законных правообладателей. Администрация сайта не несет ответственности за возможный вред и/или убытки, возникшие или полученные в связи с использованием рефератов и/или содержимого рефератов.

РЕКЛАМА









© ReferatCity.ru, рефераты, курсовые, дипломы, 2007-2018
При копирование материалов ссылка на сайт приветствуется.