И коммуникаций республики узбекистан

8. Кольцевые списки.
Списки могут быть не только линейными, но и кольцевыми. В кольцевом списке для последнего элемента следующим является первый, а если список двунаправленный, то для первого предыду­щим является последний (рис.5.8).
К ак и линейный, кольцевой список определяется указателем на свой первый элемент. Из процедур обработки кольцевого списка принципиально от­личается от процедур линейного только просмотр списка. Так, при просмотре линейного списка мы переходили от одного элемента к другому, пока рабочий указатель не стал равен Nil. При просмотре кольцевого списка, очевидно, надо переходить к следующему эле­менту до тех пор, пока рабочий указатель не совпадет с указателем на первый элемент. Однако, если мы начнем просмотр с первого элемента, то мы сразу же выйдем из цикла просмотра. Поэтому пер­вый элемент должен обрабатываться отдельно, а просмотр при по­мощи цикла следует начинать со второго элемента.


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


Древовидная структура (дерево)
Вершина, располагающаяся в нулевом уровне, называется корнем дерева (нумерация уровней может начинаться с 1). В корень не входит ни одного ребра. Вершины, из которых не выходит ни одного ребра, называются листьями (вершины 8, 9, 5, 6, 7). Дерево, из каждой вершины которого выходит только по два ребра, называется бинарным (рисунок 7).
Графы представляют собой совокупность двух множеств: вершин и ребер. Граф - это сложная нелинейная многосвязная динамическая структура, отображающая свойства и связи сложного объекта

Бинарное дерево

Примеры графовых структур
Многосвязная структура обладает следующими свойствами:

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

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

Многосвязный список (сплетение)

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