3

現在、DrRacket を使用してラケットの値を見つける関数を作成しようとしています。いくつかの助けを借りて、私はこれを以下に思いつきました。cadrただし、との違いは何かを説明してくれる人が必要caddrです。また、DrRacket で BST を作成するにはどうすればよいですか? リストを作るのと似ていますか？

(define (find-val bst elt)
    (cond ((null? bst) #f)
          ((< elt (car bst))
           (find-val (cadr bst) elt))
          ((> elt (car bst))
           (bst (caddr bst) elt))
          ((equal? elt (car bst))
           #t)))
4

2 に答える 2

3

あなたの質問の最初の部分については、

(cadr x)

と同等です：

(car (cdr x))

と

(caddr x)

と同等です：

(car (cdr (cdr x)))

パターンに気づきましたか？とdの間のそれぞれは、の省略形であり、との間のそれぞれは、左から右の順序で、の省略形です。crcdracrcar

あなたの質問の2番目の部分に関しては、本SICPのセクション§2.3.3のタイトルセットの下に二分木としてBSTを表す方法の非常に詳細な説明があります。そこには、ツリーを作成および操作するために必要な手順があります。

于 2012-10-31T04:14:54.673 に答える
0

Racketでは、structを使用して構造化された値の形状を定義できます。例えば：

(struct person (name age))

構造を定義しpersonます。これにより、次のような2フィールドの構造化された値を作成できます。

(define p1 (person "danny" 33))
(define p2 (person "richie" 31))

セレクター関数を使用して、構造化値の個々のフィールドにアクセスできます。

;; p: person -> void
(define (say-hi p)
  (printf "hi, my name is ~a, and I am ~a years old\n"
          (person-name p)
          (person-age p)))

(say-hi p1)
(say-hi p2)

プレーンリスト構造を使用するなど、構造化された値を作成する方法は他にもあります。ただし、Racketのほとんどのアプリケーションでは、structを使用することをお勧めします。理由は次のとおりです。

  1. 構造体のフィールドへのアクセスは高速です-単一の間接参照。リスト表現では、フィールドアクセスにはリスト構造のウォークが含まれますが、これは多少コストがかかります。

  2. 構造体セレクターの型チェックにより、間違った種類のデータを渡す際の間違いをより迅速に検出し、適切なエラーメッセージを生成できます。

次に、二分探索木を作成するには、ツリーの個々のノードを表す構造を定義する必要があります。また、ノードは特殊な方法で順序付けられているため、構造を検索する際にシーケンシャルリストよりも高速になる可能性があるため、構築中はかなり厳格なルールに従う必要があります。

アルゴリズムの教科書は、ノード間の良好なバランスを保証するBSTを作成するために従うことができる潜在的なルールセットのいくつかを検討する必要があります。これらには、赤黒木などが含まれます。これには、挿入によって値がツリーにプッシュされるときに、ツリーの構造を維持する方法に固有のルールがあります。それがどのように発生するかについて、実際にはラケットは何もありません。バランスをうまく機能させるために従う必要があるのは、一般的な要件だけです。

Matt Mightは、Racketに実装された赤黒木に関する非常に優れた記事を書いています。

于 2012-10-31T18:32:16.770 に答える