Реализация L2-списка на основе двух стеков

Интересной реализацией L2-списка является его реализация на основе двух стеков, расположенных `вершиной друг к другу’. Первый из стеков представляет начало списка (часть от начала списка до текущего элемента включительно), а второй – конец (часть после текущего элемента). Текущий элемент списка лежит на вершине первого стека. При необходимости переместиться к следующему элементу, значение вершины второго стека извлекается и помещается на вершину первого стека. При необходимости переместиться к предыдущему элементу, значение вершины первого стека извлекается и помещается на вершину второго стека.

Данная реализация активно применялась, например, при создании текстовых редакторов. Текстовый редактор представляет собой двунаправленный список строк. Работа с каждой строкой может быть представлена как работа с простым вектором символов. Операции вставки, редактирования, удаления символов в строке могут быть реализованы за время = O(N), где N – количество символов в строке.

Список строк реализуется в виде двух стеков, каждый из которых может быть реализован в виде временного файла. Текущая строка (и, возможно несколько соседних строк) хранятся в оперативной памяти, начало файла – в виде одного временного файла, конец (в обратном порядке) – в виде второго временного файла.

Реализация L2-списка с обеспечением выделения/освобождения памяти

При работе со списками может оказаться, что работа функции malloc требует слишком много времени. К тому же, эта функция реально выделяет памяти больше, чем запрошено, что делает ее применение слишком дорогим. Возможна реализация списка, в которой память под весь список выделяется сразу как массив элементов списка. На основе данного массива строятся два списка – основной список и список свободного места. В начальный момент список свободного места объединяет все элементы созданного массива.

Теперь для добавления элемента в список требуется взять его из списка свободного места и добавить в основной список. Для извлечения элемента из списка элемент извлекается из основного списка и добавляется в список свободного места.

Если при добавлении элементов в список место в списке свободного места закончилось, то можно либо выдать сообщение об ошибке, либо выделить еще некоторое количество ячеек памяти для хранения дополнительных свободных элементов и добавить их к списку свободного места.

Итак, для хранения всех данных, относящихся к подобному списку можно использовать следующую структуру

Typedef struct

{

TList2 *array;

TList data, empty;

Int NMax;

} SListMem;

Функция инициализации может выглядеть следующим образом

void SListMemInit(SListMem *list)

{int i;

list->NMax=1000;

list->array=(TList2*)malloc(list->NMax*sizeof(TList2));

ListInit(&(list->data));

list->empty.current=list->empty.temp.next=list->array+0;

list->empty.temp.prev=list->array+ list->NMax-1;

list->array[0].prev=&(list->empty.temp);

for(i=1;i<list->NMax;i++)

{

list->array[i-1].next=list->array+i;

list->array[i].prev=list->array+i-1;

}

list->array[list->NMax-1].next=&(list->empty.temp);

}

Лекция 7

Дата добавления: 2015-10-30