Вход/Регистрация
Программирование. Принципы и практика использования C++ Исправленное издание
вернуться

Страуструп Бьерн

Шрифт:

Обратите внимание на то, что мы использовали аргументы по умолчанию (см. разделы 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) {

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
), но в реальности что-то могло произойти не так, как ожидалось.

  • Читать дальше
  • 1
  • ...
  • 264
  • 265
  • 266
  • 267
  • 268
  • 269
  • 270
  • 271
  • 272
  • 273
  • 274
  • ...

Ебукер (ebooker) – онлайн-библиотека на русском языке. Книги доступны онлайн, без утомительной регистрации. Огромный выбор и удобный дизайн, позволяющий читать без проблем. Добавляйте сайт в закладки! Все произведения загружаются пользователями: если считаете, что ваши авторские права нарушены – используйте форму обратной связи.

Полезные ссылки

  • Моя полка

Контакты

  • chitat.ebooker@gmail.com

Подпишитесь на рассылку: