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