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

 

 

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

 

            Кольцевой список представляет собой обобщение линейного списка. Этот список характеризуется тем, что не имеет конца - элемента с пустой ссылкой; от каждого элемента здесь достижим каждый. Доступ к кольцевому списку происходит через единственный указатель на условно “головной” элемент.

            Включить элемент в циклический список можно “слева” от “головного”. Схема такого включения показана на рис.1.7.

            Рис. 1.7. Схема включения элемента в кольцевой список.

            Искусственным образом можно произвести и включение “справа”. Для этого элемент сначала включают “слева”, а затем его делают “головным”. Исключают элементы из кольцевого списка только “слева”.

            Если включение и исключение элементов производится “слева”, то кольцевой список моделирует стек. Если же включение элементов производится “справа”, а удаление “слева”, то в этом случае кольцевой список моделирует очередь.

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

            Кольцевые списки удобно использовать при работе с многочленами; каждый элемент списка при этом соответствует одночлену, представляя коэффициент при нем и степени аргументов. Например, многочлен x4-9xy2+7y-4 можно задать четырьмя элементами: (1,4,0), (-9,1,2), (7,0,1), (-4,0,0). Так как результатом сложения или умножения многочленов является многочлен, который содержит неизвестное заранее количество слагаемых, то самым удобным способом представления результата является именно список.

            В качестве примера работы с кольцевым списком рассмотрим сложение многочленов - операцию над их представлениями, а не значениями. Д. Кнут предлагает степени аргументов представлять единым полем degree по правилу: слагаемому xayb соответствует degree=a*256+b. Другими словами, каждому аргументу отводится отдельный разряд  в специфической системе счисления. Если упорядочить элементы списка по значению degree, алгоритмы операций упрощаются, а сами операции становятся быстрее. В “голову” списка заносят значение

degree=-1.

            Программа, представленная на рис. 1.8, находит сумму T(x,y)=2x4y2-xy3-xy+7y многочленовP(x,y)=-xy3+3xy и Q(x,y)=2x4y2-4xy3 +7y. В результате работы программы сначала формируются два списка - (p) и (q). Затем список-результат создается на месте списка (q) следующим образом: на каждом шаге c помощью просмотра всего списка (q) определяется нужное место для очередного элемента списка (p). В табл. 1.1 показано пошаговое формирование результата.

 

 

 

 

 

 

 

Таблица 1.1.

№ шага

Список (p)

Список (q)

0

¬(0,-1)¬(3,257)¬(-1,259)¬

¬(0,-1)¬(7,1)¬(-4,257)¬(2,1026)¬

1

¬(0,-1)¬(3,257)¬(-1,259)¬

¬(0,-1)¬(7,1)¬(-4,257)¬(-1,259)¬ ¬(2,1026)¬

2

¬(0,-1)¬(3,257)¬(-1,259)¬

¬(0,-1)¬(7,1)¬(-1,257)¬(-1,259)¬ ¬(2,1026)¬