Как реализовать компактный связанный список с массивом?

Вот вопрос упражнения CLRS 10.3-4 Я пытаюсь решить

It is often desirable to keep all elements of a doubly linked list compact in storage, using, for example, the first m index locations in the multiple-array representation. (This is the case in a paged, virtual-memory computing environment.) Explain how to implement the procedures ALLOCATE OBJECT and FREE OBJECT so that the representation is compact. Assume that there are no pointers to elements of the linked list outside the list itself. (Hint: Use the array implementation of a stack.)

Вот мой раствор до сих пор

int free; 
int allocate()
{
    if(free == n+1)
        return 0;
    int tmp = free;
    free = next[free];
    return tmp;
}
int deallocate(int pos)
{

    for(;pos[next]!=free;pos[next])
    {
        next[pos] = next[next[pos]];
        prev[pos] = prev[next[pos]];
        key[pos] = key[next[pos]];
    }
    int tmp = free;
    free = pos;
    next[free] = tmp;
}

Теперь проблема в том, что если это так, нам не нужен связанный список. Если удаление равно O(n), мы можем реализовать его, используя обычный массив. Во-вторых, я тоже не использовал реализацию массива стека. Так где подвох? Как мне начать?


c++ algorithm linked-list clrs
person Unbound    schedule 22.03.2014    source источник
comment
Разве это не связанный список, который вы там реализовали?   -  person Niklas B.    schedule 22.03.2014
comment
Да, это компактная реализация связанного списка.   -  person Unbound    schedule 22.03.2014
comment
тогда наверное я не понял вопроса   -  person Niklas B.    schedule 22.03.2014
comment
Вопрос состоит в том, чтобы реализовать связанный список таким образом, что если есть n элементов и m - размер связанного списка, то выделенные объекты должны быть от 1 до n, а свободная память должна быть n+1. ..m .Вот что я думаю. Я действительно не знаю о подкачке виртуальной памяти. Так что я не могу понять лучше.   -  person Unbound    schedule 22.03.2014
comment
Вероятно, вам не следует создавать переменную с именем free, так как это важное слово в языке C (следовательно, C++).   -  person John Zwinck    schedule 22.03.2014
comment
Одним из основных преимуществ двусвязных списков является возможность вставлять элементы в случайные места. Наличие блоков элементов, реализованных в массивах, как бы убивает это, поскольку массивы хороши только для конечной вставки. Однако: возможно, эта задача требует, чтобы вы просто хранили элементы в смежных блоках памяти. В этом случае вам нужно создать отдельный класс для элемента списка, а затем реализовать распределитель, который будет выделять один блок памяти для n элементов, а затем отслеживать пустые места в таких выделенных блоках. Так что мы просто говорим о стандартном пользовательском распределителе.   -  person velis    schedule 22.03.2014
comment
Но он сказал использовать стек. Итак, где я буду использовать стек?   -  person Unbound    schedule 22.03.2014

Ответы (1)


arrow_upward
-1
arrow_downward

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

Затем введите другой метод для pack вашего списка, т.е. удалите все дыры. Имейте в виду, что после вызова метода pack все «ссылки» становятся недействительными.

person alzaimar    schedule 22.03.2014