1

这是我要解决的练习CLRS的问题 10.3-4

通常希望在存储中保持双向链表的所有元素紧凑，例如使用多数组表示中的前 m 个索引位置。（在分页的虚拟内存计算环境中就是这种情况。）解释如何实现过程 ALLOCATE OBJECT 和 FREE OBJECT 以使表示紧凑。假设在链表本身之外没有指向链表元素的指针。（提示：使用堆栈的数组实现。）

到目前为止，这是我的解决方案

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)，我们可以使用普通数组来实现它。其次，我也没有使用堆栈的数组实现。那么问题在哪里呢？我应该如何开始？

4

1 回答 1

-1

您不必立即缩小列表。只需留下一个洞并将该洞链接到您的免费​​列表。一旦你分配了内存，它就是你的了。因此，假设您的页面大小为 1K。即使列表为空，您的初始分配列表大小也将为 1K。现在您可以非常有效地添加和删除项目。

然后在您的列表中引入另一种方法pack，即删除所有孔。请记住，调用 pack-method 后，所有“引用”都将变为无效。

于 2014-03-22T07:00:30.887 回答