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

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