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


Проблема концов списка и циклические списки


Основной сложностью при работе со списками является необходимость проверки множества вариантов при выполнении операций над элементом списка, в том числе:



-список пустой;



-элемент единственный;



-элемент в начале списка;



-элемент в конце списка;



-элемент в середине списка.

Особенно это заметно при работе с двусвязными списками. Для решения проблемы " концов списка" удобно бывает сделать его циклическим, то есть вместо указателей NULL записывать:



-указатель на последний элемент в качестве указателя на предыдущий в первом элементе списка;



-указатель на первый элемент в качестве указателя на последующий в последнем элементе списка.

Тогда единственный элемент в циклическом списке будет иметь указатели на самого себя, а в процессе просмотра конец списка определяется фактом возвращения на его начало. В качестве примера рассмотрим функции просмотра циклического списка и включения элемента в его конец.


//------------------------------------------------------bk53-06.cpp


// Просмотр циклического списка


void scan(list2 *ph)
{
list2 *p;
if (ph ==NULL) return;
p = ph;
do { /* ... */
p = p-&#62next;
}
while (p != ph); // возврат к началу списка


}
// ------------------------- Включение в конец списка


list2 *insert(list2 *ph, int v)
{
list2 *p = new list;
p-&#62val = v;
p-&#62next = p-&#62pred = p; // указатели на самого себя


if (ph ==NULL)
return p; // включение в пустой список


list2 *pr; // текущий и предыдущий элементы списка


pr = ph-&#62pred; // в циклическом списке l предыдущий


// l от первого - последний


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


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


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


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


return ph;
}

При выполнении операций над циклическим списком необходимо следить за его заголовком. Например, операция включения в начало списка будет отличаться от включения в конец списка только перемещением заголовка на новый элемент:


ph = p;




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



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