Информатика и технология программирования


Двусвязные списки


Список, в котором каждый элемент имеет указатели на последующий и предыдущий, называется двусвязным. Его основное отличие от односвязного -возможность просмотра его в обоих направлениях. Основное применение двусвязных списков - создание упорядоченных последовательностей элементов при достаточно частых операциях включения и исключения. В качестве примера рассмотрим включение в список нового элемента с сохранением упорядоченности значений.


//------------------------------------------------------bk53-05.cpp


struct list2
{
list2 *next, *pred;
int val;
};
list *InsertSort(list2 *ph, int v)
{
list2 *q , *p=new list;
p-&#62val = v;
p-&#62pred = p-&#62next = NULL;
if (ph == NULL) return p; // включение в пустой список


for (q=ph; q !=NULL &#38&#38 v &#62 q-&#62val; q=q-&#62next) ;
// поиск места включения - q


if (q == NULL) // включение в конец списка


{ // восстановить указатель на


for (q=ph; q-&#62next!=NULL; q=q-&#62next) ;
p-&#62pred = q; // последний


q-&#62next = p;
return ph;
} // включить перед текущим


p-&#62next=q; // l следующий за новым = текущий


p-&#62pred=q-&#62pred; // l предыдущий нового = предыдущий


// l текущего


if (q-&#62pred == NULL) // включение в начало списка


ph = p;
else // включение в середину


q-&#62pred-&#62next = p; // l следующий за предыдущим l =l новый


q-&#62pred=p; // l предыдущийl l текущего = новый


return ph;
}

Наибольшие проблемы при работе со списками возникают при перемещении указателей в процессе перестановки элементов списков. Эти операции можно интерпретировать несколькими способами .



1. . Смысловая интерпретация присваивания указателя. При работе со списками каждый указатель имеет определенный смысл - первый, текущий, следующий, предыдущий и т.п. элементы списка. Поля pred,next также интерпретируются как указатели на следующий и предыдущий элементы списка в доступном через указатель. Тогда смыл присваивания указателей " один в один" переводится в словесное описание, как это было в приводимых выше комментария.


Начало  Назад  Вперед



Книжный магазин