SICP习题5.20：列表结构的盒指针与内存向量表示问询

1. 盒指针表示 #

• x 对应的cons单元：

  +---+---+
  | 1 | 2 |
  +---+---+
       ^
       |
       x
  

• y 对应的嵌套cons结构（两个car均指向x的cons单元）：

  +-----+-----+    +-----+-------+
  |  *x |  *→ |→→→ |  *x |  ()   |
  +-----+-----+    +-----+-------+
       ^                   ^
       |                   |
       y                空列表
  

2. 内存向量表示（初始free=p1） #

内存槽位按free指针顺序分配，每个cons占用连续两个槽位：

3. 关键值确定 #

• x对应的指针：p1
• y对应的指针：p3
• 最终free的值：p7

4. 槽位使用原因解析 #

• 槽位1（p1）：分配给(cons 1 2)的car部分，存储数值1
• 槽位2（p2）：分配给(cons 1 2)的cdr部分，存储数值2
• 槽位4（p4）：分配给(list x x)生成的第一个cons的cdr部分，存储指向第二个cons的指针p5
• 槽位5（p5）：分配给(list x x)生成的第二个cons的car部分，存储指向x的指针p1
• 槽位7：所有cons分配完成后，free指针移动到未使用的第一个槽位，即p7

解法合理性验证 #

如果你的推导符合上述逻辑，那么是完全合理的：

• SICP中cons操作会从free指针开始，连续分配两个内存槽位分别存储car和cdr
• list x x等价于(cons x (cons x '()))，会依次分配两组连续槽位
• 空列表()不占用额外内存槽位，仅用特殊标记（如空指针）表示

内容的提问来源于stack exchange，提问作者Enlico