Главная | Обратная связь | Поможем написать вашу работу!
МегаЛекции

Структуры на основе списков. Работа со стеком и очередью.




Пусть S – стек, а – элемент стека. Основные операции при работе со стеком:

Empty(S): Boolean проверка стека на пустоту

a:=Pop(S) получить верхний элемент стека

Push(S,a) добавить элемент в стек

 

Для работы с очередью используются те же операции. Особенности их применения обсуждались выше

 

19)

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

В теории графовдерево — связанный ациклический граф (иногда его называют направленным ациклическим графом, у которого каждая вершина имеет степень 0 или 1). Ациклический граф без жесткого условия связывания иногда называется лесом (так как он состоит из деревьев).

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

Терминология и свойства

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

Линии, связывающие элементы называются «ветвями», а сами элементы называются узлами. Узлы без потомков называются «конечными узлами» или «листьями».

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

· Узел является «родителем» другого узла, если он расположен на один шаг выше в иерархии дерева, то есть находится ближе к корневому узлу.

· «Дети» («брат» или «сестра») имеют общий родительский узел.

· Узел, связанный со всеми нижележащими узлами называется «предком» или «предшественником».

В приведенном выше примере, «энциклопедия» является родителем по отношению к «науке» и «культуре», которые соответственно, являются ее «детьми». «Искусство» и «ремесло» являются братьями по отношению друг к другу и детьми по отношению к «культуре».

Древовидные структуры используются для отображения все видов информации из области таксономии, как например, генеалогическое древо, филогенетическое дерево, грамматическая структура языка (например, в английском языке, хорошим примером является схема S → NP VP, означающая, что предложение (sentence) является именной группой (noun phrase) и глагольной группой (verb phrase), способ логического упорядочивания веб-страниц на сайте и так далее.

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

Древовидные структуры широко используются в информатике (смотри Дерево (структура данных) и Связь (техника)).

 

24) Топологическая сортировка — упорядочивание вершин бесконтурного ориентированного графа согласно частичному порядку, заданному ребрами орграфа на множестве его вершин. Пример

Для графа

Бесконтурный ориентированный граф

существует несколько согласованных последовательностей его вершин, которые могут быть получены при помощи топологической сортировки, например:

·

·

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

[править]Алгоритм

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

пока выбрать любую вершину такую, что и удалить из всех

Наличие хотя бы одного контура в графе приведёт к тому, что на определённой итерации цикла не удастся выбрать новую вершину .

[править] Пример работы алгоритма

Пусть задан граф . В таком случае алгоритм выполнится следующим образом:

шаг
 
 
 
 
 
 

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

 

 

Поделиться:





Воспользуйтесь поиском по сайту:



©2015 - 2024 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...