Шрифт:
struct Link {
string value;
Link* prev;
Link* succ;
Link(const string& v,Link* p = 0,Link* s = 0)
:value(v),prev(p),succ(s) { }
};
Иначе говоря, имея объект типа
Link
, мы можем получить доступ к последующему элементу, используя указатель succ
, а к предыдущему элементу — используя указатель prev
. Нулевой указатель позволяет указать, что узел не имеет предшествующего или последующего узла. Список норвежских богов можно закодировать так:
Link* norse_gods = new Link("Thor",0,0);
norse_gods = new Link("Odin",0,norse_gods);
norse_gods–>succ–>prev = norse_gods;
norse_gods = new Link("Freia",0,norse_gods);
norse_gods–>succ–>prev = norse_gods;
Мы создали этот список с помощью структуры
Link
: во главе списка находится Тор
, за ним следует Один, являющийся предшественником Тора, а завершает список Фрея — предшественница Одина. Следуя за указателями. можете убедиться, что мы правы и каждый указатель succ
и prev
ссылается на правильного бога. Однако этот код мало понятен, так как мы не определили явно и не присвоили имя операции вставки.
Link* insert(Link* p, Link* n) // вставка n перед p ( фрагмент )
{
n–>succ = p; // p следует после n
p–>prev–>succ = n; // n следует после предшественника p
n–>prev = p–>prev; // предшественник p становится
// предшественником n
p–>prev = n; // n становится предшественником p
return n;
}
Этот фрагмент программы работает, если указатель
p
действительно ссылается на объект типа Link
и этот объект действительно имеет предшественника. Убедитесь, что это именно так. Размышляя об указателях и связанных структурах, таких как список, состоящий из объектов типа Link
, мы практически всегда рисуем на бумаге диаграммы, состоящие из прямоугольников и стрелок, чтобы проверить программу на небольших примерах. Пожалуйста, не пренебрегайте этим эффективным средством. Приведенная версия функции
insert
неполна, поскольку в ней не предусмотрен случай, когда указатели n
, p
или p–>prev
равны 0
. Добавив соответствующую проверку, мы получим немного более сложный, но зато правильный вариант функции insert
.
Link* insert(Link* p, Link* n) // вставляет n перед p; возвращает n
{
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* norse_gods = new Link("Thor");
norse_gods = insert(norse_gods,new Link("Odin"));
norse_gods = insert(norse_gods,new Link("Freia"));
prev
и succ
, исключены. Проверка корректности указателей очень утомительна и подвержена ошибкам, поэтому ее обязательно следует скрывать в хорошо спроектированных и тщательно проверенных функциях. В частности, многие ошибки в программах возникают оттого, что программисты забывают проверять, не равен ли указатель нулю, — как это было (преднамеренно) продемонстрировано в первой версии функции insert
.