Циклические (кольцевые) списки

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

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

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

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

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

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

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

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

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

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

Сначала создается список с ключами от 1 до N. Затем программа проходит по этому циклическому списку, пропуская M–1 элементом и уничтожая следующий после них узел до тех пор, пока в списке не останется один единственный элемент.

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

Статья на Хабре - http://habrahabr.ru/post/65617/

Часть 2 - http://habrahabr.ru/post/66926/

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

Для практических целей обычно используют два подвида бинарных деревьев — двоичное дерево поиска и двоичная куча.