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)