了解深度反转

问题描述

假设我有列表‘(1233(456)789)。它应该使用以下代码返回(987(654)321)。我试图理解这个迭代过程是如何工作的。一步一步地展示如何做到这一点将是非常有帮助的。

我最困惑的部分是此时调用了两次Deep-Reverse
(追加(深反转(Cdr Lst))(list(Deep-verse(Car Lst)

我不知道接下来会发生什么。

(define (deep-reverse lst)
   (cond ((null? lst) '() )
         ((pair? (car lst))
          (append
           (deep-reverse (cdr lst))
           (list (deep-reverse (car lst)))))
         (else
          (append
           (deep-reverse (cdr lst))
           (list (car lst))))))

推荐答案

嗯，我刚才回答了这样的问题here，但是我并没有真正详细介绍深度反转。

发生的情况是，在将恰好是列表的每一项追加到列表末尾之前，它会颠倒该列表中的每一项。想象一下，如果它没有对列表中的Car调用Deep-Reverse会发生什么：(reverse '(a (b c d) e)is

(list
   'e
   '(b c d)
   'a
)

使用深度反转时，它看起来类似

(list
    'e
    (deep-reverse '(b c d))
    'a
)

哪个是

(list
    'e
    '(d c b)
    'a
)

这里是深度反转的另一个版本，如果这样写得更清楚的话会有所不同。

(define (deep-reverse ls)
  (define (deep-reverse-2 ls acc)
    (if (null? ls)
        acc
        (if (list? (car ls))
            (deep-reverse-2 (cdr ls) (cons (deep-reverse (car ls)) acc));  If adding  a list, reverse it first
            (deep-reverse-2 (cdr ls) (cons (car ls) acc)))))
  (deep-reverse-2 ls '()))

此版本的深度复制使用累加器，并且是尾部递归的。

这将在将元素添加到列表之前检查元素是否为列表，如果是，则首先将其反转。由于它调用自身来反转内部列表，因此可以处理任意嵌套。

(deep-reverse '(a (b c d) e)) -> '(e (d c b) a)

，尽管存在嵌套列表，但它是按相反的字母顺序排列的。评估结果如下：

(deep-reverse-2 '(a (b c d) e) '()); Which calls
(deep-reverse-2 '((b c d) e)  '(a)); which is the same as
(deep-reverse-2 '(e) (cons (deep-reverse-2 '(b c d) '()) '(a))); it calls deep-reverse on the list '(b c d) before consing it on.
(deep-reverse-2 '(e) (cons (deep-reverse-2 '(c d)  '(b)) '(a)))
(deep-reverse-2 '(e) (cons (deep-reverse-2 '(d)  '(c b)) '(a)))
(deep-reverse-2 '(e) (cons '(d c b) '(a)))
(deep-reverse-2 '(e)  '((d c b) a))
(deep-reverse-2 '() '(e (d c b) a))
'(e (d c b) a)

这篇关于了解深度反转的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！