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


Односвязные списки - часть 2



// элемент - pr


for ( p=ph,pr=NULL; n!=0 &#38&#38 p!=NULL; n--, pr=p, p =p-&#62next);
if (p==NULL) return ph;
if (pr==NULL)
{ q=ph; ph=ph-&#62next; } // Исключить первый


else // Исключить из середины


{ q=p; pr-&#62next=p-&#62next; }
delete q; // Уничтожить элемент списка


return ph;
}

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



-в качестве заголовка можно использовать " фиктивный" элемент без данных. Тогда все рабочие указатели в списке могут ссылаться не на текущие элементы списка, а на предыдущие ;



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


//------------------------------------------------------bk53-02.cpp


// Поиск и удаление элемента списка с минимальным значением


// Заголовок списка - " фиктивный" элемент без данных


// Используется указатель на предыдущий элемент от искомого


int remove_min(list *ph)
{ // pmin - предыдущий перед минимальным


list *pmin,*p;
for (pmin=p=ph; p-&#62next!=NULL; p=p-&#62next)
if (pmin-&#62next-&#62val &#60 p-&#62next-&#62val)
pmin=p;
list *q=pmin-&#62next;
pmin-&#62next = q-&#62next;
int vv=q-&#62val;
delete q;
return vv;
}
void main()
{list PH={0,NULL};} // Заголоков пустого списка в программе


Другим способом возвращения измененного заголовка списка является передача формального параметра по ссылке (использование ссылки на указатель ссылки на заголовок списка).


//------------------------------------------------------bk53-03.cpp


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


// Используется ссылка на указатель на переменную-заголовок




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



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