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

 Стандартная библиотека содержит класс 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

    while (n––) {

      if (p–>succ == 0) return 0;

      p = p–>succ;

    }

  }

  else if (n<0) {

    while (n++) {

      if (p–>prev == 0) return 0;

      p = p–>prev;

    }

  }

  return p;

}

Обратите внимание на использование постфиксной инкрементации n++. Она подразумевает, что сначала используется текущее значение переменной, а затем оно увеличивается на единицу.

17.9.5. Использование списков

В качестве небольшого примера создадим два списка

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

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

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

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

Link* greek_gods = new Link("Hera");

greek_gods = insert(greek_gods,new Link("Athena"));

greek_gods = insert(greek_gods,new Link("Mars"));

greek_gods = insert(greek_gods,new Link("Poseidon"));

К сожалению, мы наделали много ошибок: Зевс — греческий бог, а не норвежский, греческий бог войны — Арес, а не Марс (Марс — это его римское имя). Эти ошибки можно исправить следующим образом:

Link* p = find(greek_gods, "Mars");

if (p) p–>value = "Ares";

Обратите внимание на то, что мы проверяем, возвращает ли функция find() значение 0. Мы, конечно, уверены, что этого не может быть (в конце концов, мы только что вставили имя Марса в список greek_gods), но в реальности что-то могло произойти не так, как ожидалось.

Аналогично можем перенести Зевса в правильный список греческих богов.

Link* p = find(norse_gods,"Zeus");

if (p) {

  erase(p);

  insert(greek_gods,p);

}

Вы заметили ошибку? Она довольно тонкая (конечно, если вы не работаете со списками непосредственно). Что, если на опустошенный с помощью функции erase() узел ссылался один из узлов списка norse_gods? Разумеется, на самом деле этого не было, но в жизни бывает всякое, и хорошая программа должна это учитывать.

Link* p = find(norse_gods, "Zeus");

if (p) {

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

  erase(p);

  greek_gods = insert(greek_gods,p);

}

Заодно мы исправили и вторую ошибку: вставляя Зевса перед первым греческим богом, мы должны установить на него указатель списка. Указатели — чрезвычайно полезный и гибкий, но очень тонкий инструмент. В заключение распечатаем наш список.