首页 文章

在O（n）中的球拍中的反向列表

提问于
浏览 次
0

我需要在Scheme中编写一个递归函数，它接受一个原子列表并在线性时间内反转它 . 我只允许使用define，lambda，cons，car，cdr，cond，let和null？ . 这是我到目前为止：

(define reverse
  (lambda (lat)
    (cond
      ((null? lat) lat)
      (else (cons (reverse (cdr lat)) (cons (car lat) '()))))))

所以当我调用函数时：

(reverse '(a b c d))

我得到以下输出：

'(() (((() 4) 3) 2) 1)

任何帮助将非常感谢 .

scheme lisp racket

1 回答

  • 1

    问题是，如果 (reverse (cdr lat)) 返回一个列表，例如 (3 2) ，那么 (cons '(3 2) (1)) 将变为 ((3 2) 1) .

    执行此操作的经典方法是创建一个本地过程，该过程采用累加器以及全局过程的参数 . 当您从开头到结尾迭代列表时，您会从结尾到开头累积一个列表，使其与参数完全相反 . 当迭代列表为空时，您的答案在累加器中 . 当你注意到你迭代每个元素时，当你点击空列表时你返回累加器它是一个完美的 O(n)

    作为提示：

    (define (myreverse lst)
  (define (myreverse-aux lst acc)
    (if (null? <??>)
        <??>
        (myreverse-aux <??> (cons <??> <??>))))
  (myreverse-aux <??> <??>))

    这是一个使用 foldl 的版本

    (define (myreverse lst)
  (foldl cons '() lst))
    回复于

相关问题