1

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

主题是有 n 个堆栈共享一个公共区域位置 L0 < L < LX，最初我们设置 BASE[j] = TOP[j] = L0 为 1 <= j <= n

目标是在插入或删除关于堆栈 i 的元素时发生溢出时，如何重新打包内存。（通过从尚未填满的桌子上拿走一些来为堆栈 i 腾出空间）。

一个）。如果存在任何这样的 k，则找到 i < k < n 且 TOP[k] < BASE[k+1] 的最小 k。将事情提升一个档次，设置 CONTENTS(L+1) -> CONTENTS(L)，对于 TOP[k] >= L > BASE[i+1] 最后，设置 BASE[j] -> BASE[j] + 1 , TOP[j] -> TOP[j] + 1, 对于 i < j < k

这是我的问题：

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

4

1 回答 1

2

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

堆栈k未满 <==>TOP[k] < BASE[k+1]

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

另请注意，最初通过设置和将所有空间分配给最后一个nth 堆栈。所以除非所有“更高”的栈都被填满，否则我们会找到这样一个.BASE[n] = TOP[n] = L0BASE[n+1]=LInftyk

您的第二个问题（为什么选择最小的这样k？）更容易回答：第 247 页上的算法只是一种重新包装的方法，而且是一种简单的方法。正如 Knuth 在算法文本上方的段落中提到的：

建议自己进行重新包装的几种方法；...我们将从给出最简单的方法开始，然后考虑一些替代方法。

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

于 2009-07-21T11:20:56.647 回答