taocp，顺序分配问题

Question

我在使用tacop 2.2.2顺序分配时遇到了一些问题，重新打包了第247页的内存部分。

主题是有n个堆栈共享一个公共区域位置L0

目标是当相对于堆栈i插入或删除元素时发生溢出时，如何重新包装内存。(从尚未填满的表中取走一些，为堆栈I腾出空间)。

a)。找到i CONTENTS(L)设置为TOPk >= L> BASEi+1最后，为i BASEj + 1，TOPj -> TOPj +1

以下是我的问题：

它们如何找到尚未填充的堆栈？堆栈k？为什么选择最小的k？

Answer 1

要查找尚未填充的堆栈，使用的基本思想是：

堆栈k不是完整的<==> TOP[k] < BASE[k+1]

算法第一步中的循环从i+1运行k到n，以查找满足此条件的第一个k。

还请注意，通过设置BASE[n] = TOP[n] = L0和BASE[n+1]=LInfty，最初所有空间都被分配给最后一个堆栈，即nth。因此，除非所有“更高”的堆栈都已填满，否则我们将找到这样的k。

你的第二个问题(为什么选择最小的k?)更容易回答:第247页上的算法只是重新打包的一种方式，而且是一种简单的方式。正如Knuth在算法文本上方的段落中提到的那样：

建议了几种重新打包的方法；...我们将从最简单的方法开始，然后考虑一些替代方法。

后来，Knuth描述了一种重新打包的方法，该方法考虑了早期的重新打包，使该过程在某种程度上具有适应性。