Информатика и технология программирования
Двусвязные списки
Список, в котором каждый элемент имеет указатели на последующий и предыдущий, называется двусвязным. Его основное отличие от односвязного -возможность просмотра его в обоих направлениях. Основное применение двусвязных списков - создание упорядоченных последовательностей элементов при достаточно частых операциях включения и исключения. В качестве примера рассмотрим включение в список нового элемента с сохранением упорядоченности значений.
//------------------------------------------------------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 также интерпретируются как указатели на следующий и предыдущий элементы списка в доступном через указатель. Тогда смыл присваивания указателей " один в один" переводится в словесное описание, как это было в приводимых выше комментария.
