c语言 - SICP 对指针的描述

Question

这句话来自SICP，我认为它指的是编程语言中的指针/引用。

正如我们所看到的，对提供了一个原始的"胶水"，我们可以用它来构造复合数据对象。图 2.2 显示了可视化货币对的标准方法，在本例中，由 (缺点 1 2( 形成的对。在此表示形式(称为框和指针表示法(中，每个对象都显示为指向框的指针。基元对象的框包含对象的表示形式。例如，数字的框包含一个数字。一对的盒子实际上是一个双盒子，左边的部分包含(指向(这对汽车，右边的部分包含 cdr。

在这种情况下，本书讨论的是配对(例如(缺点1 2((以及它们是如何表示的。但是，我们也可以使用对来构造这样的列表：

(缺点

1 (缺点 2 '(

(((

虽然框和指针表示法只是一个符号并且无用，但我认为这看起来很像链表。据我了解，链表是一种数据结构，其中包含一个值和一个指向另一个链表的指针。话虽如此，我认为缺点可以像链表一样构造。我对以下方面感到困惑：

一对的盒子实际上是一个双盒子，左边的部分包含(指向(这对汽车，右边的部分包含 cdr。

我最初认为指针应该在 cdr 上，因为如果我们通过成对构建列表，这将是下一个列表。

我认为这可能是一种不同类型的指针。在这种情况下，指针到底是什么意思？我唯一知道的指针是 c 中使用的指针。SICP 甚至提到任何关于 c 指针的内容吗？

Answer 1

我最初认为指针应该在 cdr 上，因为如果我们通过成对构建列表，这将是下一个列表。

缺点单元格有两个值，一个汽车值和一个 cdr 值。你投入其中的内容不受约束。你可以把任何东西放进去。

您可以从缺点单元格中构建不同的数据结构。单链表只是一个。它可以是一个二叉树，一个通过键和值提供访问的缺点单元格的assoc列表，一个循环数据结构，等等。

如果我们这样做

(cons
      (cons :foo 10)
      (cons :bar 5))

。然后，如何完成从缺点单元到其汽车值的引用，对程序员来说大多是隐藏的。大多数实现都将具有某种数据结构，其中包含从缺点单元到其汽车和 cdr 组件的指针。通常会对字符和小整数(fixnums(等小对象进行优化 - 这些也可以直接存储在汽车和cdr中，而不是使用指向字符对象的指针。

总结：

缺点单元格有两个值：汽车和 cdr。两者都是完全不受约束的：您可以引用任何其他对象/值。

大多数实现都是隐藏的。在 Lisp 中，你得到的只是以下具有基本函数的接口：

• (consp thing) ：如果谓词是缺点单元格，则谓词返回T thing。
• (car cons-cell)：缺点单元的汽车值
• (cdr cons-cell)：缺点单元的 CDR 值
• (cons thing-0 thing-1) ：创建一个缺点单元格，thing-0和thing-1可以是任何东西。

列表由缺点单元格组成。但是还有其他数据结构可以由缺点单元格组成。

Answer 2

是的，你是对的，缺点单元格用于在 Lisps 中构建链表。

左侧部分包含缺点的值。它是一个指针，因为该值可能是一个数字、一个对象、另一个缺点(例如树(或其他任何东西。

您也是正确的，右侧部分 cdr 包含指向列表中下一个缺点的指针。

因此，列表(54 "foobar" 3)如下所示：

            (car cdr)
             /     
            54      (car cdr)
                     /     
                  "foobar"  (car nil)
                             / 
                            3