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

你注意到图案了吗？andd之间的每个都是 a 的简写，and之间的每个是 a 的简写，按从左到右的顺序排列。crcdracrcar

关于您问题的第二部分，在书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。其中包括诸如红黑树之类的东西，当将值插入到树中时，它们可能对如何维护树的结构有特殊的规则。Racket并没有具体说明它是如何发生的：它只是我们需要遵循的一般要求才能使平衡发挥作用。

Matt Might 写了一篇关于在 Racket 中实现的红黑树的非常好的文章。

于 2012-10-31T18:32:16.770 回答