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

       

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


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


//------------------------------------------------------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 также интерпретируются как указатели на следующий и предыдущий элементы списка в доступном через указатель. Тогда смыл присваивания указателей " один в один" переводится в словесное описание, как это было в приводимых выше комментария.
Например, если p - указатель на новый элемент, а q - указатель на текущий, то
выражение q -&#62pred-&#62next=p формально интерпретируется как " указателю на следующий элемент списка в предыдущем от текущего присвоить указатель на новый" .


2. Графическая интерпретация присваивания указателя :


-операция перемещения указателя реализуется через операцию присваивания одному указателю значения другого. На рисунке это соответствует перенесению (копированию) требуемого указателя из одной ячейки (2) в другую (1) ;


-в левой части операции присваивания должно находиться обозначение ячейки, в которую
заносится новое значение указателя (2). Причем она может быть достижима только через имеющиеся рабочие указатели. На рисунке этому соответствует цепочка операций q -&#62pred-&#62next ;


-в правой части операции присваивания должно находиться обозначение ячейки, из которой берется значение указателя (1) - на рисунке - p.


3. . Адресная интерпретация присваивания указателя . Содержимым указателя является адрес указуемой переменной. В свете этой фразы предыдущая картинка может стать более понятной.





Содержание раздела