Все о динамических структурах данных. Опции

[Altair]

Содержание:

• Указатели
• Списки
  + Модуль для работы со списками. + Двусвязные списки
  
• Стеки
  + Модуль для работы со стеками.
• Очереди
  + Модуль для работы с очередями.
• Деки (двусторонние очереди)
  + Модуль для работы с деками.
• Деревья
  + Модуль для работы с деревьями.
• Сортировка стека
• Сортировка очереди
• Демонстрационные программы с ДСД
• Двусвязные списки

Есть материал по теме? высылайте! ваша информация будет размещена здесь!

[volvo]

Кольцевые (циклические) двухсвязные списки

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

Для описания элемента списка будем пользоваться следующей структурой:

type
   myType = integer;
   Ring = ^TRing;
   TRing = record
      info: myType;
      next: Ring;
      prev: Ring;
  end;

Добавление элемента

Добавляться новые элементы будут перед элементом, помеченным как first (то есть, перед "головой" списка) по следующему алгоритму:

1. Поскольку выделение памяти под новый элемент должно производиться независимо от того, пуст список или в нем уже есть элементы, то сделаем это в самом начале процедуры добавления, еще перед проверкой на пустоту списка.
2. В зависимости от того, пуст наш кольцевой список или уже частично заполнен, дальнейшее выполнение процедуры пойдет по одному из двух путей:
   
   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;

Удаление элемента

При удалении элемента из кольцевого списка также рассматриваем два случая:

1. Список содержит один элемент: проверяем, нужно ли удалять этот элемент, и если нужно - просто удаляем его, и обнуляем First, нет элементов - нет "головы" списка.
2. Список содержит несколько элементов: переназначаем указатели 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;

Продолжение следует...