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

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

список. Когда нам потребуется новый узел, то возьмем его из вершины стека. Операция вставки иллюстрируется рис. 20.

Рис 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. Удалённый узел помещается в вершину стека свободного пространства.

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

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

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

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

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

NODE *X;

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

p->Next=X->Next;

X->Next=s;

s=X;

}

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

Дата добавления: 2014-12-08