瞭解深度反轉

假設我有'（1 2 3（4 5 6）7 8 9）'列表。它應該返回（9 8 7（6 5 4）3 2 1），使用下面的代碼。我試圖瞭解這個迭代過程如何工作。顯示如何一步一步完成將是非常有益的。瞭解深度反轉

我感到困惑的最的部分是，當深相反在此時叫了兩聲
（追加（深反向（CDR LST））（名單（深反向（汽車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))))))

來源

2010-11-05 Joe

嗯，我剛纔已經回答這樣的事情here，但我並沒有真正進入細節上深相反。

會發生什麼，它會顛倒每個恰好是列表的項目，然後將其附加到列表的末尾。試想一下，如果它沒有呼籲名單的汽車深反轉會發生什麼：(reverse '(a (b c d) e)是

(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)

來源

2010-11-05 02:10:36

容易，你不知道頭部是否爲整數或列表，所以你必須在其應用deep-reverse還，然後將其附加到當前列表的尾部逆轉。

所以：

((1 2) 3 4)

有可能成爲

(4 3 (2 1))

注意，我們必須扭轉頭部和尾部。

來源

2010-11-05 02:10:44 Blindy

瞭解深度反轉

回答

相關問題