Программирование. Принципы и практика использования C++ Исправленное издание - Бьёрн Страуструп

Shape, поскольку класс Shape является открытым базовым классом по отношению к классу Circle. Рассмотрим пример.

void rotate(Shape* s, int n); // поворачиваем фигуру *s на угол n

Shape* p = new Circle(Point(100,100),40);

Circle c(Point(200,200),50);

rotate(&c,45);

Это можно сделать и с помощью ссылок.

void rotate(Shape& s, int n); // поворачиваем фигуру *s на угол n

Shape& r = c;

rotate(c,75);

Этот факт является чрезвычайно важным для большинства объектно-ориентированных технологий программирования (см. разделы 14.3, 14.4).

17.9.3. Пример: списки

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

 

 Такой список называют двусвязным (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. Операции над списками

 Стандартная библиотека содержит класс list, который будет описан в разделе 20.4. В нем реализованы все необходимые операции, но в данном разделе мы самостоятельно разработаем список, основанный на классе Link, чтобы узнать, что скрывается “под оболочкой” стандартного списка, и продемонстрировать еще несколько примеров использования указателей.

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

• Конструктор.

• insert: вставка перед элементом.

• add: вставка после элемента.

• erase: удаление элемента.

• find: поиск узла с заданным значением.

• advance: переход к n-му последующему узлу.

Эти операции можно написать следующим образом:

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

{

  // напоминает insert (см. упр. 11)

}

Link* erase(Link* p) // удаляет узел *p из списка; возвращает

                     // следующий за p

{

  if (p==0) return 0;

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

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

  return p–>succ;

}

Link* find(Link* p,const string& s) // находит s в списке;

                                    // если не находит, возвращает 0

{

  while(p) {

    if (p–>value == s) return p;

    p = p–>succ;

  }

  return 0;

}

Link* advance(Link* p,int n) // удаляет n позиций из списка

 // если не находит, возвращает 0

 // при положительном n переносит указатель на n узлов вперед,

 // при отрицательном — на n узлов назад

{

  if (p==0) return 0;

  if (0<n)