Подраздел FAQ (ЧАВО, ЧАстые ВОпросы) предназначен для размещения готовых рабочих программ, реализаций алгоритмов. Это нечто вроде справочника, он наполнялся в течение 2000х годов. Ваши вопросы, особенно просьбы решить задачу, не пройдут предмодерацию. Те, кто наполнял раздел, уже не заходят на форум, а с теми, кто на форуме сейчас, лучше начинать общение в других разделах. В частности, решение задач — здесь.
Во многом эти списки похожи на обычные двухсвязные, за одним исключением: они закольцованы, т.е., последний элемент в таком списке ссылается на первый. Это вносит свои коррективы в алгоритм добавления элемента к кольцевому списку.
Для описания элемента списка будем пользоваться следующей структурой:
type myType = integer; Ring = ^TRing; TRing = record info: myType; next: Ring; prev: Ring; end;
Добавление элемента
Добавляться новые элементы будут перед элементом, помеченным как first (то есть, перед "головой" списка) по следующему алгоритму:
Поскольку выделение памяти под новый элемент должно производиться независимо от того, пуст список или в нем уже есть элементы, то сделаем это в самом начале процедуры добавления, еще перед проверкой на пустоту списка.
В зависимости от того, пуст наш кольцевой список или уже частично заполнен, дальнейшее выполнение процедуры пойдет по одному из двух путей:
2а) список пуст - устанавливаем указатели prev и next на новый элемент и "помечаем" его как первый (First)
2б) список не пуст - действовать нужно по-другому:
поскольку добавляем в "конец" списка (перед элементом first), то поле next нового элемента указывает на "голову" списка, а поле prev - туда, куда раньше указывал prev "головы";
не забываем про "бывший последним" элемент (элемент на который раньше указывал first^.prev). Поле next этого элемента должно указывать на добавляемый элемент, поскольку новый добавляется после "последнего" (перед "первым");
ну, и наконец, "голова" списка должна теперь указывать prev-ом на новый элемент, он ведь находится в списке ПЕРЕД "головой"...
.
procedure Append(var First: Ring; value: myType); var p: Ring; begin { 1 } new(p); p^.info := value;
if first = nil then begin { 2а } p^.next := p; p^.prev := p; first := p; end else begin { 2б } p^.next := first; p^.prev := first^.prev; first^.prev^.next := p; first^.prev := p; end; end;
Удаление элемента
При удалении элемента из кольцевого списка также рассматриваем два случая:
Список содержит один элемент: проверяем, нужно ли удалять этот элемент, и если нужно - просто удаляем его, и обнуляем First, нет элементов - нет "головы" списка.
Список содержит несколько элементов: переназначаем указатели prev^.next и next^.prev удаляемого элемента так, чтобы ни предыдущий ни последующий элементы больше на P не указывали. После этого проверяем, не удаляется ли "головной" элемент (First), и в случае положительного ответа "продвигаем" First на один элемент вперед (если этого не сделать, то после удаления элемента P указатель на "голову" станет невалидным и его использование приведет к получению неправильных результатов). И только после того, как все вышесказанное выполнено, можно удалять элемент списка, на который указывает P...
{ Удалить из списка, начинающегося с First, элемент, на который указывает P } procedure RemoveItem(var First: Ring; p: Ring); begin if (first^.next = first) and (p = first) then begin dispose(first); first := nil; exit; end;
p^.prev^.next := p^.next; p^.next^.prev := p^.prev; if p = first then first := p^.next; dispose(p); p := nil; end;