Какие операции необходимы пользователю, чтобы избежать ошибок, связанных с указателями? В некотором смысле это дело вкуса, но мы все же приведем полезный набор.
• Конструктор.
•
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++
. Она подразумевает, что сначала используется текущее значение переменной, а затем оно увеличивается на единицу.
сожалению, мы наделали много ошибок: Зевс — греческий бог, а не норвежский, греческий бог войны — Арес, а не Марс (Марс — это его римское имя). Эти ошибки можно исправить следующим образом:
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
(или использование списка), предусмотрев соответствующие члены класса?