1

我需要创建一个会破坏性地反转列表的程序。例如让我们说..

scm> (define L (list 1 2 3 4))
scm> (reverse! L)
(4 3 2 1)
scm> L
(1)

其中 L 成为反向列表的最后一个元素。我知道我应该使用 set-cdr！不知何故，但无法弄清楚如何实现它。

4

4 回答 4

4

因为这看起来像家庭作业，所以我不能给你一个直接的答案。我将向您展示解决方案的一般结构，以便您了解详细信息并填写空白：

(define (reverse! lst)
  (let loop ((lst lst)
             (acc '()))
    (if (null? lst)
        acc
        (let ((tail <?1?>))
          (set-cdr! <?2?> <?3?>)
          (loop tail lst)))))

(define lst (list 1 2 3 4))
lst
> (1 2 3 4)

(reverse! lst)
> (4 3 2 1)

lst
> (1)

在上面的代码中：

  • 为简单起见，使用命名遍历原始列表let，因为需要另一个参数
  • 定义了一个新acc参数，作为反向列表的累加器
  • 当递归结束时，返回累加器中的答案

现在，对于递归步骤：

  • 我们<?1?>需要获取对列表其余部分的引用并保存它，因为我们要修改它
  • 关键在于线(set-cdr! <?2?> <?3?>)。您必须将当前列表的下一个元素设置为先前累积的反向列表
  • 最后，递归继续使用新的累加值

请注意，最后，lst引用已就地修改，现在指向列表的最后一个元素。如果您需要lst指向反向列表，那么只需执行以下操作：

(define lst (list 1 2 3 4))
lst
> (1 2 3 4)

(set! lst (reverse! lst))
lst
> (4 3 2 1)

描述的过程破坏性地反转列表并且不创建新列表（不cons使用任何操作。）

于 2012-04-22T14:53:02.343 回答
0

您应该阅读The Scheme Programming Language书中关于 mutators 的部分。另外，查看Scheme 中的函数。本质上，您可以使用该函数从根本上更改定义并提供另一个输出。caseset!

于 2012-04-22T16:31:55.267 回答
0

UCB 好家伙。

这是我为您的 HilAcke 提供的解决方案。

(define (reverse! L)
     (define (helper prev cur)
           (if (null? cur)
               prev
               (let ((next (cdr cur)))
                   (set-cdr! cur prev)
                   (helper cur next))))
     (helper '() L))

然后在定义后你可以用通常的方式检查

 (define L (list 1 2 3 4))
 (define LR (reverse! L))
 LR
 > (4 3 2 1)
于 2012-04-23T17:15:09.447 回答
0

所以我想知道今天如何做到这一点，因为我需要它进行测试。对于每个包含超过 1 个元素的列表，我将cons参数中的第一个作为结果中的第一个。我做了一个新的缺点，用一个虚拟值保存新的最后一个值，然后我反转元素 2..n-1 的链接。最后我设置了第一cons和新的车last。结果是最后的结果set-cdr!。

(define (reverse! lst)
  (if (or (null? lst)
          (null? (cdr lst)))
      'soup ; an undefined value. You may use something else
      (let ((last (list 1)))
        (let loop ((prev last) (cur (cdr lst)))
          (let ((next (cdr cur)))
            (if (pair? next)
                (begin
                  (set-cdr! cur prev)
                  (loop cur next))
                (begin
                  (set-car! last (car lst))
                  (set-car! lst (car cur))
                  (set-cdr! lst prev))))))))

例子：

(define test '(() (2) (3 4) (5 6 7) (8 9 10 11 12 13 14 16)))
(for-each reverse! test)
test ; ==> (() (2) (4 3) (7 6 5) (16 14 13 12 11 10 9 8))
于 2014-03-30T20:08:01.377 回答