taocp，顺序分配问题
我在工作 tacop 2.2.2 顺序分配、重新打包第 247 页的内存部分时遇到了一些问题。
主题是有 n 个堆栈共享公共区域位置 L0 < L＜ LX, 最初我们设置 BASE[j] = TOP[j] = L0 为 1 <= j <= n
目标是在插入或删除元素时发生溢出 to stack i，如何重新打包内存。 （通过从堆栈中取出一些来为堆栈 i 腾出空间 尚未填满的表）。
A）。 找到 i < 的最小 k k＜ n 且 TOP[k] ＜ BASE[k+1]，如果有这样的 k 存在。 将事情提升一个档次， 设置内容(L+1)-> CONTENTS(L)，对于 TOP[k] >= L > 基数[i+1] 最后， 设置 BASE[j] -> BASE[j] + 1, TOP[j] -> TOP[j] + 1，对于 i < j＜ k
这是我的问题：
他们如何找到尚未填充的堆栈？ 堆栈 k? 为什么选择最小的k？
i've run into few problems while working tacop 2.2.2 sequential allocations, repacking memory section at page 247.
the subject is there are n stacks sharing a common area locations L0 < L < LX,
initially we set BASE[j] = TOP[j] = L0 for 1 <= j <= n
the goal is when overflow occurs while inserting or deleting elements with respect
to stack i, how to repack memory. (making room for stack i by taking some away from
tables that aren't yet filled).
a). find the smallest k for which i < k < n and TOP[k] < BASE[k+1], if any such k
exists. move things up one notch,
Set CONTENTS(L+1) -> CONTENTS(L), for TOP[k] >= L > BASE[i+1]
finally,
Set BASE[j] -> BASE[j] + 1, TOP[j] -> TOP[j] + 1, for i < j < k
here's my questions:
how do they find the stack that aren't yet to be filled? stack k? and why chose the smallest k?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
要找到尚未填满的堆栈，使用的基本思想是：
算法第一步中的循环从
i+1到n运行k来查找第一个满足此条件的k。另请注意，最初通过设置 BASE[n] = TOP[n] = L0 和 BASE[n，将所有空间分配给最后一个（第 n 个）堆栈+1]=LInfty。 因此，除非所有“更高”的堆栈都已被填满，否则我们将找到这样一个
k。你的第二个问题（为什么选择最小的
k？）更容易回答：第247页的算法只是重新打包的一种方法和简单 一个。 正如 Knuth 在算法文本上方的段落中提到的：后来，Knuth 描述了一种重新打包方法，该方法考虑了早期的重新打包，使该过程具有一定的适应性。
To find the stack that isn't yet filled, the basic idea used is the fact:
The loop in the first step of the algorithm runs
kfromi+1tonto find the firstkthat satisfies this condition.Also note that initially all space is given to the last,
nth, stack by settingBASE[n] = TOP[n] = L0andBASE[n+1]=LInfty. So unless all "higher" stacks have been filled, we will find such ak.Your second question (Why choose the smallest such
k?) is more easily answered: The algorithm on Page 247 is just one way of repacking and a simple one at that. As Knuth mentions in the paragraph just above the text of the algorithm:Later, Knuth describes a repacking approach that takes into account the earlier repacking, making the process somewhat adaptive.