Стек свободного пространства

До сих пор мы не заботились о том, куда деваются освобождаемые узлы списков, перекладывая это на алгоритмы работы с "кучей". Это было возможно, потому, что наши списки располагались в оперативной памяти и в нашем распоряжении имелись операторы new и delete. Существуют ситуации, когда программа сама должна заботиться об "утилизации" осво­бож­даемых узлов списков. Такая ситуация возникнет, если отказаться от кучи как поставщика узлов или список находится на внешнем носителе. Просто бросать освободившиеся узлы было бы слишком расточительно. Мы будем помещать их в стек свободного пространства, организованный как линейный односвязный

Рис 20. Вставка узла в список.

Текст функции приведен ниже.

NODE *InsertNode(NODE *p, NODE *s){

// Вставка узла вслед за p

// s – указатель на вершину стека свободного пространства

// возвращает указатель на новый узел

NODE *X;

X=s;

s=s->Next;

X->Next=p->Next;

p->Next=X;

return X;

}

Рис 21. Удаление узла из списка.

Текст функции, выполняющей операцию удаления, приведен ниже.

void DeleteNode(NODE *p, NODE *s){

// узел, следующий за p удаляется и помещается

// в вершину стека свободного пространства s

NODE *X;

X=p->Next; // X-удаляемый узел

p->Next=X->Next;

X->Next=s;

s=X;

}

Для списочных структур на внешнем носителе роль указателя играет смещение узла относительно начала файла.