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

テストのために必要だったので、今日これを行う方法を考えていました。複数の要素を持つすべてのリストについて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 に答える
0

The Scheme Programming Language bookのミューテーターに関するセクションを読む必要があります。また、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 に答える