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

{

    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);

}

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

void print_all(Link* p)

{

  cout << "{ ";

  while (p) {

    cout << p–>value;

    if (p=p–>succ) cout << ", ";

  }

  cout << " }";

}

print_all(norse_gods);

cout<<"n";

print_all(greek_gods);

cout<<"n";

Результат должен быть следующим:

{ Freia, Odin, Thor }

{ Zeus, Poseidon, Ares, Athena, Hera }

17.10. Указатель this

Обратите внимание на то, что каждая из функций, работающих со списком, получает в качестве первого аргумента указатель Link* для доступа к данным, хранящимся в этом объекте. Такие функции обычно являются членами класса. Можно ли упростить класс Link (или использование списка), предусмотрев соответствующие члены класса?

Может быть, сделать указатели закрытыми, чтобы только функции-члены класса могли обращаться к ним? Попробуем.

class Link {

public:

  string value;

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

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

  Link* insert(Link* n);   // вставляет n перед данным объектом

  Link* add(Link* n);      // вставляет n после данного объекта

  Link* erase();           // удаляет данный объект из списка

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

  Link* advance(int n) const;  // удаляет n позиций

                               // из списка

  Link* next() const { return succ; }

  Link* previous() const { return prev; }

private:

  Link* prev;

  Link* succ;

};

Этот фрагмент выглядит многообещающе. Мы определили операции, не изменяющие состояние объекта класса Link, с помощью константных функций-членов. Мы добавили (не модифицирующие) функции next() и previous(), чтобы пользователи могли перемещаться по списку, — поскольку непосредственный доступ к указателям succ и prev теперь запрещен. Мы оставили значение узла в открытом разделе класса, потому что (пока) у нас не было причины его скрывать; ведь это просто данные.

Попробуем теперь реализовать функцию Link::insert(), скопировав и модифицировав предыдущий вариант.

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

{

  Link* p = this;     // указатель на данный объект

  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::insert()? Без помощи языка это сделать невозможно. Однако в каждой функции-члене существует идентификатор this, являющийся указателем на объект, для которого она вызывается. A в качестве альтернативы мы могли бы просто писать this вместо p.

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

{

  if (n==0) return this;

  if (this==0) return n;

  n–>succ = this;       // этот объект следует за n

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

  n–>prev = this–>prev; // предшественник этого объекта

                        // становится

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

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

                        // объекта

  return n;

}

Это объяснение выглядит немного многословным, но мы не обязаны упоминать, что указатель this обеспечивает доступ к члену класса, поэтому код можно сократить.

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

{

  if (n==0) return this;

  if (this==0) return n;

  n–>succ = this;   // этот объект следует за n

  if (prev) prev–>succ = n;

  n–>prev = prev;   // предшественник этого объекта

                    // становится

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

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

                    // объекта

  return