Двусвязные списки
Список, в котором каждый элемент имеет указатели на последующий и предыдущий, называется двусвязным. Его основное отличие от односвязного -возможность просмотра его в обоих направлениях. Основное применение двусвязных списков - создание упорядоченных последовательностей элементов при достаточно частых операциях включения и исключения. В качестве примера рассмотрим включение в список нового элемента с сохранением упорядоченности значений.
//------------------------------------------------------bk53-05.cpp
struct list2
{
list2 *next, *pred;
int val;
};
list *InsertSort(list2 *ph, int v)
{
list2 *q , *p=new list;
p->val = v;
p->pred = p->next = NULL;
if (ph == NULL) return p; // включение в пустой список
for (q=ph; q !=NULL && v > q->val; q=q->next) ;
// поиск места включения - q
if (q == NULL) // включение в конец списка
{ // восстановить указатель на
for (q=ph; q->next!=NULL; q=q->next) ;
p->pred = q; // последний
q->next = p;
return ph;
} // включить перед текущим
p->next=q; // l следующий за новым = текущий
p->pred=q->pred; // l предыдущий нового = предыдущий
// l текущего
if (q->pred == NULL) // включение в начало списка
ph = p;
else // включение в середину
q->pred->next = p; // l следующий за предыдущим l =l новый
q->pred=p; // l предыдущийl l текущего = новый
return ph;
}
Наибольшие проблемы при работе со списками возникают при перемещении указателей в процессе перестановки элементов списков. Эти операции можно интерпретировать несколькими способами .
1. . Смысловая интерпретация присваивания указателя. При работе со списками каждый указатель имеет определенный смысл - первый, текущий, следующий, предыдущий и т.п. элементы списка. Поля pred,next также интерпретируются как указатели на следующий и предыдущий элементы списка в доступном через указатель. Тогда смыл присваивания указателей " один в один" переводится в словесное описание, как это было в приводимых выше комментария.
Например, если p - указатель на новый элемент, а q - указатель на текущий, то выражение q ->pred->next=p формально интерпретируется как " указателю на следующий элемент списка в предыдущем от текущего присвоить указатель на новый" .
2. Графическая интерпретация присваивания указателя :
-операция перемещения указателя реализуется через операцию присваивания одному указателю значения другого. На рисунке это соответствует перенесению (копированию) требуемого указателя из одной ячейки (2) в другую (1) ;
-в левой части операции присваивания должно находиться обозначение ячейки, в которую заносится новое значение указателя (2). Причем она может быть достижима только через имеющиеся рабочие указатели. На рисунке этому соответствует цепочка операций q ->pred->next ;
-в правой части операции присваивания должно находиться обозначение ячейки, из которой берется значение указателя (1) - на рисунке - p.
3. . Адресная интерпретация присваивания указателя . Содержимым указателя является адрес указуемой переменной. В свете этой фразы предыдущая картинка может стать более понятной.
