使用方案将元素插入循环列表

Question

我有一个循环列表，例如：#0=(1 2 3 4 . #0#)。

我想做的是在这个列表中插入一个新元素 (x)，这样结果就是 #0=(x 1 2 3 4 . #0#)。我一直在尝试使用此代码（x 是循环列表）：

(define (insert! elm)
  (let ((temp x))
    (set-car! x elm)
    (set-cdr! x temp)))

不过，我觉得set-cdr！没有像我想要的那样工作。我在这里错过了什么？也许我跑题了？

Answer 1

由于您要将元素添加到循环列表中，因此需要做两件事：

在包含附加元素的列表的前面插入一个新的 cons 单元格。这很容易，因为您只需执行一个简单的 (cons elm x).
您还需要修改循环列表的递归部分，使其指向新创建的cons cell，否则循环部分将只包含列表的旧部分。

要执行后者，您需要一种方法来确定循环列表的 "end" 在哪里。这实际上并不存在，因为列表当然是循环的，但是可以通过对列表的每个元素执行 eq? 检查直到找到等于列表头部的元素来确定。

创建一个辅助函数来执行此操作，insert! 的简单实现如下所示：

(define (find-cdr v lst)
  (if (eq? v (cdr lst)) lst
      (find-cdr v (cdr lst))))

(define (insert! elm)
  (set! x (cons elm x))
  (set-cdr! (find-cdr (cdr x) (cdr x)) x))

Answer 2

将元素添加到列表中的最简单方法是修改列表中的汽车，并将列表的 cdr 设置为新的 cons，其汽车为原始汽车列表的第一个元素，其 cdr 是列表的原始尾部：

(define (prepend! x list)                      ; list = (a . (b ...)) 
  (set-cdr! list (cons (car list) (cdr list))) ; list = (a . (a . (b ...)))
  (set-car! list x))                           ; list = (x . (a . (b ...)))

(let ((l (list 1 2 3)))
  (prepend! 'x l)
  (display l))
;=> (x 1 2 3)

现在，这仍然适用于循环列表，因为列表开头的 cons 单元（即对）保持不变，所以 "final" cdr 仍将指向对象是开始。不过，为了测试这一点，我们需要一些函数来创建循环列表并从中采样，因为它们不包含在语言中（据我所知）。

(define (make-circular list)
  (let loop ((tail list))
    (cond
      ((null? (cdr tail))
       (set-cdr! tail list)
       list)
      (else
       (loop (cdr tail))))))

(define (take n list)
  (if (= n 0)
      '()
      (cons (car list)
            (take (- n 1)
                  (cdr list)))))

(display (take 10 (make-circular (list 1 2 3))))
;=> (1 2 3 1 2 3 1 2 3 1)

现在我们可以检查如果我们在循环列表前面添加会发生什么：

(let ((l (make-circular (list 1 2 3))))
  (prepend! 'x l)
  (display (take 15 l)))
;=> (x 1 2 3 x 1 2 3 x 1 2 3 x 1 2)

使用方案将元素插入循环列表

Insert element to circular list using scheme

scheme

list

insert

circular-list