进行破坏性的逆转！计划中的功能 [英] Make a destructive reverse! function in scheme

问题描述

我需要创建一个程序，该程序将破坏性地反转列表.例如说..

I need to create a program that will reverse a list destructively. For example lets say..

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

其中L成为反向列表的最后一个元素.我知道我应该使用set-cdr！以某种方式但无法弄清楚如何实现它.

Where L becomes the last element of the reversed list. I know I am supposed to use set-cdr! somehow but cannot figure out how to implement it.

推荐答案

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

Because this looks like homework, I can't give you a straight answer. I'll show you the general structure of the solution, so you can figure out the details and fill-in the blanks:

(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参数，用作反向列表的累加器
• 递归结束后，将返回累加器中的答案

• The original list is traversed using a named let for simplicity, given that another parameter is needed
• A new acc parameter is defined, to serve as the accumulator for the reversed list
• When the recursion ends, the answer in the accumulator is returned

现在，对于递归步骤:

• 在<?1?>中，我们需要获取对列表其余部分的引用并将其保存，因为我们打算对其进行修改
• 关键点位于(set-cdr! <?2?> <?3?>)行中.您必须将当前列表的 next 元素设置为先前累积的，反向列表
• 最后，递归以新的累加值进行

• In <?1?> we need to obtain a reference to the rest of the list and save it, given that we're going to modify it
• The key point lies in the line (set-cdr! <?2?> <?3?>). You'll have to set the next element of the current list to the previously accumulated, reversed list
• Finally, the recursion proceeds with the new accumulated values

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

Notice that in the end, the lst reference got modified in-place and now is pointing to the last element of the list. If you need lst to point to the reversed list, then simply do this:

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

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

所描述的过程破坏性地反转了列表，并且不会创建新列表(不使用cons操作.)

The procedure described reverses a list destructively and doesn't create a new list (no cons operations are used.)

这篇关于进行破坏性的逆转！计划中的功能的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！