По книге Laszlo
"Вычислительная геометрия и компьютерная графика на С++"

Кольцевые списки удобны, например, в геометрии, где многоугольник хранится в виде кольцевого списка вершин в порядке обхода. Узел такого списка является объектом класса Node:

class Node {
protected:
  Node *_next;	// связь к последующему узлу
  Node *_prev;	// связь к предшествующему узлу
public:
  Node (void);
  virtual ~Node (void);
  Node *next(void);
  Node *prev(void);
  Node *insert(Node*);  // вставить узел после текущего
  Node *remove(void);  // удалить узел из списка, возвратить его указатель


  void splice(Node*);
};

Конструктор класса Node формирует новый узел, который имеет двойную ссылку на самого себя — новый узел представляет собой одноузловой связанный список.

Node::Node (void):
_next ( this ) , _prev ( this )
{
}

Внутри компонентной функции переменная this автоматически указывает на принимающий объект, объект, для которого инициируется компонентная функция. В конструкторе переменная this указывает на объект, который подлежит внесению. Соответственно при обсуждении компонентных функций мы будем ссылаться на принимающий объект как на текущий объект (объект с именем this). Деструктор ~Node отвечает за удаление этого объекта. При описании класса он объявлен виртуальным (virtual), так что удаляемый объект (объект класса, полученного из класса Node) будет удален корректно:

Node::-Node (void)
{
}

Компонентные функции next и prev используются для перемещения из этого узла к последователю или предшественнику:

Node *Node::next(void) 
{
  return _next;
}
Node *Node::prev(void) 
{
  return _prev;
}

Компонентная функция insert включает узел b сразу же после текущего (this) узла (рис. 1):

Рис. 1: Включение узла в связанный список

Node *Node::insert(Node *b)
{
  Node *c = _next;
  b->__next = c;
  b->_prev = this ;
  _next = b;
  c->_prev = b;
  return b;
}

Узел можно удалить из списка. Компонентная функция remove удаляет текущий узел из данного связанного списка (рис. 2). При этом возвращается указатель на текущий узел, так что впоследствии он может быть исключен:

Рис. 2: Удаление узла из связанного списка

Node *Node::remove(void)
{
  _prev->_next = _next;
  _next->_prev = _prev;
  _next = _prev = this;
  return  this;
}

Компонентная функция splice используется для соединения двух узлов а и b. Операция соединения приводит к разным результатам, зависящим от принадлежности этих двух узлов к одному и тому же списку. Если принадлежат, то связанный список разделяется на два меньших списка. И наоборот, если узлы а и b принадлежат разным спискам, то оба списка объединяются в один более крупный список.

Для слияния двух узлов а и b мы устанавливаем ссылку из а на b->_next (на последователя узла b) и из b на a->_next (на последователя узла а). Также необходимо изменить и соответствующие ссылки на предшественника. Для этого для нового последователя узла а устанавливаем обратную ссылку на а, а для нового последователя узла b — обратную ссылку на b. Эта операция схематически отображена на рис. 3. Из рисунка очевидно, что операция соединения splice взаимно обратна: соединение узлов а и b на левой схеме приводит к образованию правой схемы, а повторное соединение узлов а и b (на правой схеме) приводит к левой схеме.

Рис. 3: Слияние двух узлов a и b

В следующей реализации компонентной функции splice текущий узел играет роль узла а и в качестве аргумента функции указывается только узел b. Переменная а введена в программу исключительно для отображения симметрии операции: для заданных указателей узлов а и b операции a->splice(b) и b->splice(a) дают одинаковый результат.

void Node::splice (Node *b)
{
  Node *a = this;
  Node *an = a->_next;
  Node *bn = b->_next;
  a->_next = bn;
  b->_next = an;
  an->_prev = b;
  bn->_prev = a;
}

Заметим, что в случаях, когда узел а предшествует узлу b в связанном списке, то операция слияния приводит к удалению узла b. Слияние одноузлового связанного списка b с узлом а некоторого другого связанного списка приводит к фактическому включению узла b после узла а. Это явление приводит к выводу, что операции включения узла в связанный список и удаления узла из связанного списка фактически являются частными случаями операции слияния. Но это только замечание — компонентные функции insert и remove предусмотрены для удобства.

И, наконец, заметим, что слияние узла с самим собой, например, при обращении a->splice (а), не приводит ни к каким изменениям. Это легко проверить по реализации функции splice.

В этом разделе для представления списков введен новый класс List^*.

При нашем подходе каждый элемент списка занимает одну позицию — первый элемент в первой позиции, второй элемент — во второй и т. д. Кроме того существует головная позиция, которая одновременно располагается перед первой и после последней позиции. Объект List обеспечивает доступ к его элементам через окно (window), которое в любой данный момент относится к некоторой позиции в списке. Большинство операций со списками выполняется либо с окном, либо с элементом в окне. Например, мы можем вызвать элемент, находящийся в окне, сдвинуть окно на следующую или предыдущую позицию или передвинуть его на первую или последнюю позицию. Мы также можем выполнить операцию удаления из списка элемента, находящегося в окне, или внести новый элемент в список сразу же после окна. На рис. 4 отражен наш подход к организации списка.

Рис. 4: Структура списка длиной в семь элементов. Элементы в списке располагаются с 1 по 7 позицию. Головная позиция 0 располагается между первой и последней позициями. Окно, изображенное в виде квадрата, в данный момент находится в положении 2.

Для реализации класса List будем использовать связанные списки. Каждый узел соответствует позиции в списке и содержит элемент, сохраняемый в этой позиции (узел, соответствующий головной позиции, называется головной узел). Узел представляется объектом класса ListNode, который получается из класса Node. Класс ListNode обладает компонентом данных _val, который указывает на фактический элемент.

Список является коллекцией элементов некоторого заданного типа. Однако нет необходимости встраивать специфический тип элемента в описание класса ListNode или List, поскольку операции над списками действуют совершенно независимо от типа элемента. По этой причине мы определим эти классы как шаблоны класса. Тип элемента задается в виде параметра шаблона класса. Впоследствии, когда нам потребуется список элементов некоторого специфичного типа, мы обратимся к шаблону класса с заданным типом элемента, и тогда шаблон класса будет использован для создания фактического класса с этим типом элемента.

Шаблон класса ListNode определяется следующим образом:

template<class T> class ListNode : public Node  {
 public :
  Т _val;
  ListNode (Т val);
  friend class List<T>;
};

Здесь через Т обозначен параметр типа. Для объявления конкретной реализации ListNode вместо параметра Т необходимо подставить название типа. Например, объявление

ListNode <int *> а,  b;

определяет а и b как объекты ListNode, каждый из них содержит указатель_на_целое (pointer_to_int).

Конструктор ListNode может быть определен подобно

template<class T> ListNode::ListNode (Т val) :
   _val(val)
{
}

Конструктор ListNode неявно инициирует конструктор для базового класса Node, поскольку последний конструктор не имеет аргументов.

Мы не определяем здесь деструктора класса ListNode. Как только удаляется объект ListNode, автоматически инициируется деструктор базового класса Node::~Node, объявленный как виртуальный. Заметим, что элемент, указанный элементом данных ListNode::_val не разрушается. Было бы безопасно разрушить элемент только в том случае, если бы было известно, что он создан как новый (new), но нет никакой гарантии такой ситуации.

Вернемся к определению шаблона класса List. Класс List содержит три компонента данных: header указывает на головной узел, соответствующий головной позиции; win указывает на узел, который находится в позиции текущего окна; параметр _length содержит длину списка. Шаблон класса определяется следующим образом:

template<class T> class List {
 private:
  ListNode<T> *header;
  ListNode<T> *win;
  int _length;
 public :
  List (void);
  ~List (void);
  Т insert (T);
  T append (Т);
  List *append(List *);
  Т prepend(T);
  Т remove (void);
  void val (T);
  Т val (void);
  T next (void);
  T prev(void);
  T first (void);
  T last (void);
  int length (void);
  bool isFirst (void);
  bool isLast (void);
  bool isHead(void);
};

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

List<Polygon *> р;

определяет, что р будет списком указателей_на_полигоны (Polygons), тогда как объявление

List<Polygon> q;

будет ошибочным.

Конструкторы и деструкторы

Конструктор List создает и инициализирует пустой список, представленный одним головным узлом, со ссылками на самого себя:

template<class T> List<T>::List(void) : 
  _length(0)
{
  header = new ListNode<T> (NULL);
  win = header;
}

Деструктор класса разрушает узлы связанного списка:

template<class T> List<T>::~List (void)
{
  while (length() > 0) {
    first();
	remove ();
  }
  delete header;
}

Заметим, что деструктор не разрушает сами элементы данных.

Изменение списков

Компонентные функции insert, prepend и append используются для включения в список новых элементов. Ни одна из этих трех функций не изменяет позиции окна. Функция insert заносит новый элемент после окна и возвращает указатель на новый элемент:

template<class T> T List<T>::insert(T val)
{
  win->insert(new ListNode<T>(val) );
  ++_length;
  return val;
}

Компонентные функции prepend и append вставляют новый элемент в начало или в конец списка соответственно и возвращают указатель на новый элемент:

template<class Т> Т List<T>::prepend(T val)
{
  header->insert (new ListNode<T> (val));
  ++_length;
  return val;
}

template<class T> Т List<T>::append (T val)
{
  header->prev()->insert (new ListNode<T> (val) );
  ++_length;
  return val;
}

Вторая версия компонентной функции append используется для добавления списка 1 в конец текущего списка — первый элемент списка 1 помещается после последнего элемента текущего списка. В процессе выполнения список 1 становится пустым. Возвращается указатель на текущий список:

template<class T> List<T>* List<T>::append (List<T> *1)
{
  ListNode<T> *a = (ListNode<T>*) header->prev() ;
  a->splice(l->header);
  _length += l-> _length;
  l->header->remove();
  l->_length = 0;
  l->win = header;
  return this;
}

Компонентная функция remove удаляет элемент, находящийся в окне, перемещает окно в предыдущую позицию и возвращает указатель на только что удаленный элемент. Если окно находится в головной позиции, то таких действий не производится:

template<class T> T List<T>::remove (void)
{
  if (win == header) return NULL;
  void *val = win->_val;
  win = (ListNode<T>*) win->prev();
  delete (ListNode<T>*) win->next()->remove();
  -— _length ;
  return val;
}

Если вызывается компонентная функция val с именем некоторого элемента v, то происходит замена элемента, находящегося в текущем окне, на элемент v. Если окно находится в головной позиции, то никаких действий не производится.

void List<T>::val (T v)
{
  if (win != header) 
    win->_val = v;
}

Доступ к элементам списка

Если обращение к компонентной функции val происходит без аргументов, то возвращается элемент, находящийся в окне, или нуль NULL, если окно располагается в головной позиции:

template<class T> T List<T>::val(void)
{
  return win->_val;
}

Компонентные функции next и prev перемещают окно в следующую или предыдущую позиции соответственно. Каждая из них возвращает указатель на элемент, расположенный в новой позиции окна. Заметим, что класс List обеспечивает операцию "заворачивания". Например, если окно находится в последней позиции, то выполнение операции next переместит окно в головную позицию, еще одно обращение к next переместит окно в первую позицию.

template<class T> T List<T>::next(void)
{
  win = (ListNode<T>*) win->next();
  return win->_val;
}

template<class T> T List<T>::prev(void)
{
  win = (ListNode<T>*) win->prev();
  return win->_val;
}

Компонентные функции first и last переносят окно в первую и последнюю позиции соответственно, они не производят никаких действий, если лист пустой. Каждая из этих функций возвращает указатель на элемент, записанный в новом положении окна:

template<class T> T List<T>::first (void)
{
  win = (ListNode<T>*) header->next();
  return win->_val;
}

template<class T> T List<T>::last (void)
{
  win = (ListNode<T>*) header->prev();
  return win->_val;
}

Компонентная функция length возвращает значение длины списка:

template<class T> int List<T>::length (void)
{
  return _length;
}

Компонентные функции isFirst, isLast и isHead возвращают значение TRUE (истина) только в случаях, если окно находится в первой, последней или головной позициях соответственно.

template<class T> bool List<T>::isPirst(void)
{
  return ( (win == header->next() ) && (_length > 0) );
}

template<class T> bool List<T>::isLast (void)
{
  return ( (win == header->prev() ) && (_length > 0) );
}

template>class T> bool List<T>::isHead(void)
{
  return (win == header);
}

Примеры списков

Два простых примера иллюстрируют использование списков. В первом примере шаблон функции arrayToList загружает n элементов массива а в список и возвращает указатель на этот список:

template<class T> List<T> *arrayToList(Т а[], int n)
{
  List<T> *s = new List<T>;
  for (int i = 0; i < n; i++)
    s->append(a[i]);
  return s;
}

Например, если а представляет собой массив строк, то следующий фрагмент программы преобразует массив а в список строк s :

char *a[20];
  .
  .
// здесь должен быть определен массив а
  .
  .
List<char*> *s = arrayToList(a, 20);

Шаблон функции arrayToList мы будем впоследствии использовать как утилиту в некоторых программах.

В качестве второго примера рассмотрим шаблон функции leastltem, которая возвращает наименьший элемент в списке s. Два элемента сравниваются с помощью функции стр, в результате работы которой возвращаются значения -1, 0 или 1, если первый аргумент соответственно меньше, равен или больше второго аргумента:

template<class Т> Т leastltem(List<T> &s, int(*cmp) (Т,Т) )
{
  int i;
  if (s.length() == 0)
    return NULL;
   Т v = s.first();
   for (s.next(); !s.isHeadO; s.next() )
     if (cmp(s.val(), v) < 0)
       v = s.val();
   return v;
}

Для определения, какой из списков строк появляется раньше в алфавитном порядке, следует обратиться к функции leastltem с функцией сравнения strcmp. Это стандартная библиотечная функция языка C++, которая при обработке двух строк выдает значения -1, 0 или 1 в зависимости от того, будет ли первая строка меньше, равна или больше второй строки в алфавитном порядке. Например, в результате работы следующего фрагмента программы будет напечатана строка ant:

List<char*> s;
s.append("bat");
s.append("ant");
s.append("cat");
cout << leastltem(s, strcmp);