Программирование

  Такой список называют двусвязным (doubly-linked list), поскольку в нем существуют предшествующий и последующий узлы. Список, в котором существуют только последующие узлы, называют односвязным (singly-linked list). Мы используем двусвязные узлы, когда хотим облегчить удаление элемента. Узлы списка определяются следующим образом:

struct Link {

  string value;

  Link* prev;

  Link* succ;

  Link(const string& v,Link* p = 0,Link* s = 0)

      :value(v),prev(p),succ(s) { }

};

Иначе говоря, имея объект типа Link, мы можем получить доступ к последующему элементу, используя указатель succ, а к предыдущему элементу — используя указатель prev. Нулевой указатель позволяет указать, что узел не имеет предшествующего или последующего узла. Список норвежских богов можно закодировать так:

Link* norse_gods = new Link("Thor",0,0);

norse_gods = new Link("Odin",0,norse_gods);

norse_gods–>succ–>prev = norse_gods;

norse_gods = new Link("Freia",0,norse_gods);

norse_gods–>succ–>prev = norse_gods;

Мы создали этот список с помощью структуры Link: во главе списка находится Тор, за ним следует Один, являющийся предшественником Тора, а завершает список Фрея — предшественница Одина. Следуя за указателями. можете убедиться, что мы правы и каждый указатель succ и prev ссылается на правильного бога. Однако этот код мало понятен, так как мы не определили явно и не присвоили имя операции вставки.

Link* insert(Link* p, Link* n) // вставка n перед p ( фрагмент )

{

  n–>succ = p;       // p следует после n

  p–>prev–>succ = n; // n следует после предшественника p

  n–>prev = p–>prev; // предшественник p становится

                     // предшественником n

  p–>prev = n;       // n становится предшественником p

  return n;

}

Этот фрагмент программы работает, если указатель p действительно ссылается на объект типа Link и этот объект действительно имеет предшественника. Убедитесь, что это именно так. Размышляя об указателях и связанных структурах, таких как список, состоящий из объектов типа Link, мы практически всегда рисуем на бумаге диаграммы, состоящие из прямоугольников и стрелок, чтобы проверить программу на небольших примерах. Пожалуйста, не пренебрегайте этим эффективным средством.

Приведенная версия функции insert() неполна, поскольку в ней не предусмотрен случай, когда указатели n, p или p–>prev равны 0. Добавив соответствующую проверку, мы получим немного более сложный, но зато правильный вариант функции insert.

Link* insert(Link* p, Link* n) // вставляет n перед p; возвращает n

{

  if (n==0) return p;

  if (p==0) return n;

  n–>succ = p;         // p следует после n

  if (p–>prev) p–>prev–>succ = n;

  n–>prev = p–>prev;   // предшественник p становится

                       // предшественником n

  p–>prev = n;         // n становится предшественником p

  return n;

}

В этом случае мы можем написать такой код:

Link* norse_gods = new Link("Thor");

norse_gods = insert(norse_gods,new Link("Odin"));

norse_gods = insert(norse_gods,new Link("Freia"));

  Теперь все возможные неприятности, связанные с указателями prev и succ, исключены. Проверка корректности указателей очень утомительна и подвержена ошибкам, поэтому ее обязательно следует скрывать в хорошо спроектированных и тщательно проверенных функциях. В частности, многие ошибки в программах возникают оттого, что программисты забывают проверять, не равен ли указатель нулю, — как это было (преднамеренно) продемонстрировано в первой версии функции insert().

Обратите внимание на то, что мы использовали аргументы по умолчанию (см. разделы 15.3.1, A.9.2), чтобы освободить пользователей от необходимости указывать предшествующие и последующие элементы в каждом вызове конструктора.

17.9.4. Операции над списками