CommonLisp中的双链表

html5 • • 问答

我想在SBCL中实现一个简单的双链表，其关键结构如下

(defstruct element
  (value 0 :type fixnum)
  (next nil :type element)
  (prev nil :type element))

问题是，不可能实例化第一个元素，因为 next 和 prev 都可能为零。它们的类型是元素，所以它们必须是一个实例。

如果我删除 type 属性，这个问题基本上很容易解决。但事实是，这部分程序需要非常快，所以我想给优化器一个充分利用它的机会。

有没有其他方法可以指定成员的类型并使它们为零？或者更好：有没有办法创建一个带有 next 和 prev 引用实例本身的启动实例？

回答

还可以设置层次结构：

(defstruct element)

(defstruct (null-element (:include element)))

(defstruct (link-element (:include element))
  (value 0                   :type fixnum)
  (next  (make-null-element) :type element)
  (prev  (make-null-element) :type element))

使用它：

* (compile-file "linked-list.lisp")
; compiling file "/Users/joswig/Desktop/linked-list.lisp"
;   (written 08 APR 2021 12:58:56 PM):
; processing (DEFSTRUCT ELEMENT)
; processing (DEFSTRUCT (NULL-ELEMENT #))
; processing (DEFSTRUCT (LINK-ELEMENT #) ...)

; wrote /Users/joswig/Desktop/linked-list.fasl
; compilation finished in 0:00:00.032
#P"/Users/joswig/Desktop/linked-list.fasl"
NIL
NIL
* (load *)
T
* (make-link-element)
#S(LINK-ELEMENT :VALUE 0
                :NEXT #S(NULL-ELEMENT)
                :PREV #S(NULL-ELEMENT))

回答

(defstruct element
  (value 0 :type fixnum)
  (next nil :type (or element null))
  (prev nil :type (or element null)))

回答

让 NIL 表示空元素并没有错，但如果你真的想强制执行类型，你可以按如下方式进行。

该ALLOCATE-INSTANCE泛型函数（但不是INITIALIZE-INSTANCE很明显）被指定为工作用的实例STRUCTURE-CLASS。

函数空元素的前向声明

此函数返回 type 的空值element。使用 SBCL，如果您一次编译所有定义（即使用compile-file），则不是绝对必要的。

(declaim (ftype function null-element))

定义结构

values 的 initform 是对 的调用null-element，以便在形成新结构时该值满足类型。没有为这个结构定义构造函数，这使得手动构建它变得更加困难（并避免命名问题）。

(defstruct (element (:constructor nil))
  (value 0 :type fixnum)
  (next (null-element) :type element)
  (prev (null-element) :type element))

实例化一个元素

这里的代码分配结构，但不初始化它。这避免了 sbcl 可能会自动检查其插槽类型的问题。在这里，插槽的内容在分配后未定义，但随后它们被设置为适当类型的值（元素本身）。

(defun make-element (value)
  (let ((element (allocate-instance (find-class 'element))))
    (prog1 element
      (setf (element-value element) value
            (element-next  element) element
            (element-prev  element) element))))

使用类，我会initialize-instance改为调用，但我认为这不会适用于所有实现。使用setf 直接设置插槽工作。

在这里，我将回答您的问题，并让元素具有指向自身的链接。

或者更好：有没有办法创建一个带有 next 和 prev 引用实例本身的启动实例？

您也可以让字段为(null-element)，但这只是设计选择的问题。

单例空元素值

该调用(null-element)返回一个表示空元素的标记值。在这里，我element在加载时分配一个实例，并在每次调用时返回相同的实例。存储在节点中的实际值并不重要。正如 RainerJoswig 所指出的，空元素可能是一个没有这样值的结构体的实例。

(defun null-element ()
  (load-time-value (make-element 0)))

(defun null-element-p (element)
  (eq element (null-element)))

以上是CommonLisp中的双链表的全部内容。
THE END
分享
二维码
< <上一篇
下一篇>>