问题标签 [taocp]

我一直在阅读 Donald Knuth 第二版的计算机编程艺术第 3 卷中的排序和搜索算法。我在第 95 页遇到了 Knuth 称之为“列表插入”（传统插入排序的一种修改）的算法。

在该页面上，Knuth 得出结论，“直接插入的正确数据结构是单向链接线性列表。”并且“链接分配（第 2.2.3 节）非常适合插入，因为只需要几个链接要改变。” 但是，第 97 页的 MIXAL 程序（程序 L）似乎没有利用传统的链表结构（一系列由地址链接的节点）。相反，键和链接似乎一起存储在一个类似结构的结构中，这些结构存储在一个名为INPUT.

我决定尝试在 C 中实现这个算法。我提供了 Knuth 对算法的描述，以及他在 MIXAL 汇编语言中的实现作为参考。我决定让键成为data数组中的元素本身，并将链接放在一个类似并行的数组中，称为links. 我说“类并行数组”是因为数组的大小links比数组的大小data大一。我这样做是为了可以data通过将其存储为数组中的第一个元素来轻松确定数组最小元素的索引links。由于 中的这个额外索引links，数组的索引 0 - (n - 1)data对应于数组的索引 1 - n links。links数组中的每个元素对应于data排序列表中下一个元素的数组。

我的问题是，根据他的描述，这个算法应该如何实现，还是我遗漏了什么？

在The Art of Computer Programming Volume 1, third edition一书中，我很难理解以下 MIX 汇编语言指令的含义：ENT1 *，它出现在本书的第 189 页。

(p.189) 例如，如果我们想让MAXNbe的调用序列

那么子程序可以写成如下：

到目前为止我发现的是以下行

将存储常量的内存地址n存储到存储指令的内存位置的 [0:2] 字段中ENT1 *。

因此，我在这里猜测以下行

应该将存储指令的内存位置的 [0:2] 字段的值加载ENT1 *到 register I1。

*但是，如教科书所述，星号（）的含义是：

(p.146) 星号（读作“self”）指的是它出现的行的位置。

那么，不应该 ENT1 *只将存储指令的内存位置的地址ENT1 *存储到寄存器I1吗？

我似乎记得曾经阅读过 tAOCP 分册之一 Knuth 关于计算整数商和余数的讨论。我的记忆是，他声称没有另一个就不可能计算一个，并且他认为结果都应该提供给程序员。问题是大多数编程语言都强制程序员计算 q = a/b 然后 r = a%b 之类的东西，但实际上 CPUB 做了两次相同的计算，这是一种浪费。

我刚刚在 MMIX Volume Fascicle 1 在第 1.3.1 节中对 DIV 的描述中进行了搜索，但我没有找到我似乎记得的讨论。

有人可以告诉我他们是否记得类似的讨论，我可以在哪里找到它？

我正在阅读 Donald Knuth 的 TAOCP：第 4 卷，第 6 卷，第 18 页。

他提到了gigam这个词。他什么意思？什么是千斤顶？

在 MIX STA 中，将 A 寄存器的内容存储在给定的内存位置。

我看不出 TAOCP 是如何涵盖标志周围的行为的。MIX 在以下示例中的行为方式：

位置 2000 包含：+ 5 4 6 2 1

A 寄存器包含： - 7 8 1 3 2

STA 2000 (0:1) 有什么作用？

这是否被认为是从 A 寄存器中获取值 3 2 并将它们放入内存位置 2000 的字段 0:1 中？如果是这样，是否有任何非符号值到 + 的隐式转换？或者字段规范中的 0 是否意味着“获取 A 寄存器的符号以及任何剩余字节并将这些值放入该位置”？

解释 1：2000 -> + 2 4 6 2 1

解释 2：2000 -> - 2 4 6 2 1

还是有第三种选择？

这是程序：

到目前为止我所知道的：

• STZ 1 将下一条指令设置为 NOP，因此可以忽略第二条指令
• 根据答案 - ADD 函数应该触发溢出。
• ADD 函数应该将内存 1 的内容添加到寄存器 A

使用第一个命令将存储器 1 设置为零 - ADD 功能应该简单地将零添加到寄存器 A。

如果 Mem1 设置为零，这如何将溢出切换设置为打开？

REF：计算机编程的艺术第 1 卷第 142 页问题 18