0

私はこれを行う方法に本当に戸惑っています...私はどのように始めるかさえ理解できません、私はバイナリツリーのためにそれを行う方法を知っていますが、ネストされたリストの任意の形式でそれを行うことができるようにしたいと思います、誰か助けてくれませんか？

4

2 に答える 2

2

これについては、任意にネストされた要素のリストをトラバースするためのテンプレートを使用する必要があります。たとえば、任意にネストされたリストをコピーする次の手順を調べます。

(define (copy lst)
  (cond ((null? lst)                ; if list is empty
         '())                       ; return the empty list
        ((not (list? (car lst)))    ; if current element is not a list
         (cons (car lst)            ; cons current element
               (copy (cdr lst))))   ; with the rest of the list
        (else                       ; if current element is a list
         (cons (copy (car lst))     ; cons recursive call over current element
               (copy (cdr lst)))))) ; with recursive call over rest of the list

最初にちょっとした慣習。これが基本レベルであり、返されるすべての要素がフラットな出力リストに含まれるとしましょう1（入力リストの元の構造は保持されません）。例えば：

(elements-level '(1 2 3) 1)
; => '(1 2 3)

(elements-level '(1 (2) 3) 2)
; => '(2)

上記のテンプレートを念頭に置いて、目前の問題を解決するためにテンプレートを変更する方法を見てみましょう。質問は宿題のように見えるので、空欄に記入させていただきます。

(define (elements-level lst lvl)
  (cond ((or (null? lst) (< lvl 1))        ; if list is empty or below level
         '())                              ; return the empty list
        ((not (list? (car lst)))           ; if current element is not a list
         (if (= lvl <???>)                 ; if `lvl` is the base level
             (cons <???>                   ; cons current element in list
               (elements-level <???> lvl)) ; and advance recursion over cdr part
             (elements-level <???> lvl)))  ; else advance recursion over cdr part
        (else                              ; if current element is a list
         (append                           ; use `append` for flattening the list
          (elements-level <???> <???>)     ; recur over car, decrease one level
          (elements-level <???> <???>))))) ; recur over cdr, keep the same level

このリストを使用してプロシージャをテストします。'(1)レベル1、'(2)レベルなどに戻る必要があります2。

(elements-level '(1 (2 (3 (4 (5))))) 1)
; => '(1)
于 2012-11-11T20:27:13.660 に答える
0

以下の手順で再帰を使用できると思います。

  1. n番目の深さですべての要素を保持するリストを定義します。
  2. nested listを引数として取る再帰関数を作成しnew listますn
  3. ネストされたループの要素ごとに、子リストと深さをn-1として渡すことにより、再帰関数自体を呼び出します。
  4. n = 0の場合 、 nested listtoのすべての要素を追加します。new list

この方法が完了すると、の深さnのすべての要素になりnew listます。

可能な拡張： 一部のリスト要素がn番目のレベルまで拡張されない可能性がある場合は、再帰メソッドを呼び出す前に要素のタイプを確認することをお勧めします。リーフタイプの場合は、新しいリストに要素を追加するだけです。

于 2012-11-11T20:05:40.063 に答える