第十四章 再论自引用数据的定义
最后更新于:2022-04-02 04:14:31
[TOC]
## 概述
![UTOOLS1582097470535.png](http://yanxuan.nosdn.127.net/f5eb7d559f2b618d9876398cb1ad52b3.png)
### BT 二叉树
binary-tree (简称 BT) 是下列两者之一
1. false
2. (make-node soc pn lft rgt)
其中 soc 是数, pn 是符号 ,lft 与 rgt 是 bt
### BST 二插搜索树(带排序的二叉树)
二插搜索树(binary-search-tree,简称 BST) 是 BT
1. false 总是 BST
2. (make-node soc pn lft rgt) 是 BST 如果
a. lft 和 rgt 是 BST
b. lft 中所有的 ssn 数都比 soc 小
c. rgt 中所有的 ssb 数都比 soc 大
## 14.2.1 二叉树查数
按照图144的方法,给出上述的两棵树的形象表示。然后开发 contains-bt,该函数读入一个数和一棵BT,判断这个数是否在树中出现。
```
;; 判断数是否在二叉树中
;; node 定义
(define-struct node (soc pn lft rgt))
;; contains-bt:number,bt->boolean
;; 15,node1->true
;; 13,node2->false
(define (contains-bt n bt)
(cond
[(= n (node-soc bt)) true]
[(node? (node-rgt bt)) (contains-bt n (node-rgt bt))]
[(node? (node-lft bt)) (contains-bt n (node-lft bt))]
[else false]))
(define node1
(make-node 15 'd false
(make-node 24 'i false false)))
(define node2
(make-node 15 'd
(make-node 87 'h false false)
false))
;(contains-bt 15 node1) ; #true
;(contains-bt 24 node1) ; #true
;(contains-bt 23 node1) ; #false
(contains-bt 87 node2) ; #true
```
## 14.2.2 二叉树通过数查找symbol
开发 search-bt,该函数读入数n和一棵BT。如果这棵树中包含一个node,其soc字段值为n,函数就返回这个节点的pn字段的值;否则,函数返回 false
```
;; 判断数soc是否在二叉树中,存在则返回 pn
;; node 定义
(define-struct node (soc pn lft rgt))
;; contains-bt:number,bt->boolean
;; 15,node1->pn
;; 13,node2->false
(define (contains-bt n bt)
(cond
[(= n (node-soc bt)) (node-pn bt)]
[(node? (node-rgt bt)) (contains-bt n (node-rgt bt))]
[(node? (node-lft bt)) (contains-bt n (node-lft bt))]
[else false]))
(define node1
(make-node 15 'd false
(make-node 24 'i false false)))
(define node2
(make-node 15 'd
(make-node 87 'h false false)
false))
;(contains-bt 87 node2) ; 'h
(contains-bt 88 node2) ; #false
```
## 14.2.2 二插搜索树 查找值
search-bt,该函数读入数n和一棵BT。如果这棵树中包含一个node,其soc字段值为n,函数就返回这个节点的pn字段的值;否则,函数返回 false
```
;; 判断数soc是否在二叉搜索树中,存在则返回 pn
;; node 定义
(define-struct node (soc pn lft rgt))
;; contains-bst:number,bst->boolean | pn
;; 15,node1->pn
;; 13,node2->false
(define (search-bst n bst)
(cond
[(node? bst)
(cond
[(= n (node-soc bst)) (node-pn bst)]
[(> n (node-soc bst)) (search-bst n (node-rgt bst)) ]
[(< n (node-soc bst)) (search-bst n (node-lft bst)) ]) ]
[else false]))
(define node1
(make-node 15 'd
(make-node 9 'k false false)
(make-node 24 'i false false)))
;(search-bst 25 node1 );false
;(search-bst 8 node1 );false
(search-bst 9 node1 );'k
(search-bst 24 node1 );'i
```
## 14.3 表中的表
教程案例, 计算网页中单词个数
```
;; szie : wp ->number
;; 案例
;; (= (size empty) 0)
;; (= (size (cons 'One empty)) 1)
;; (= (size (cons (cons 'One empty) empty)) 1)
;; 当 cons 第一个元素是非empty时,返回为一
;; 模版
;;第二和第三个 cond 子句中包含了表的第一个元素和其余部分的选择器表达
;;式。因为(rest a-wp)总是网页,而在第三个子句中,(first a-wp)也是网页,所以我们还为这些选择器表达式
;;加上 size 的递归调用
;;(define (size a-wp)
;; (cond
;; [(empty? a-wp) 0]
;; [(symbol? (first a-wp)) ... (first a-wp) .. (size (rest a-wp))]
;; [else ... (size (first a-wp)) ... (size (rest a-wp)]))
(define (size a-wp)
(cond
[(empty? a-wp) 0]
[(symbol? (first a-wp)) (+ 1 (size (rest a-wp)))]
[else (+ (size (first a-wp)) (size (rest a-wp)))]))
(= (size empty) 0)
(= (size (cons 'One empty)) 1)
(= (size (cons (cons 'One empty) empty)) 1)
(= (size (list 'a 'b 'c (list 'z 'e))) 5)
```
## 14.3.2 字符出现次数
开发函数 occurs1,该函数读入一个网页和一个符号,返回该符号在网页中出现的次数,忽略
嵌入的网页
```
;; occurs1 : sym,wp->number
;; 读入一个网页和一个符号,返回该符号在网页中出现的次数,忽略嵌入的网页
;; 解析,如果元素为表就跳过,
;; 例子
;;(= (occurs1 'a empty) 0)
;;(= (occurs1 'a (list 'a)) 1)
;;(= (occurs1 'a (list 'a (list 'a))) 1)
;;(= (occurs1 'a (list 'b 'a)) 1)
;; 模版
;;(define (occurs1 sym wp)
;; (cond
;; [(empty? wp) ...]
;; [(cons? (first wp)) ...]
;; [(eq? sym (fits wp)) ... (first wp) ... (occurs1 sym (rest wp))]
;; [else ...(occurs1 sym (rest wp))...]))
(define (occurs1 sym wp)
(cond
[(empty? wp) 0]
[(cons? (first wp)) 0]
[(eq? sym (first wp)) (+ 1 (occurs1 sym (rest wp)))]
[else (occurs1 sym (rest wp))]))
;;测试
(= (occurs1 'a empty) 0)
(= (occurs1 'a (list 'a)) 1)
(= (occurs1 'a (list 'a (list 'a))) 1)
(= (occurs1 'a (list 'b 'a)) 1)
```
## 14.3.3 字符替换
该函数读入符号 new 和 old,以及网页 a-wp,返回一个网页,该网页在结
构上和 a-wp 相同,但其中所有 old 的出现都被替换成 new
```
;; occurs2 : new,old,wp->wp
;; 该函数读入符号 new 和 old,以及网页 a-wp,返回一个网页,该网页在结
;; 构上和 a-wp 相同,但其中所有 old 的出现都被替换成 new
;; 例子
;;(replace 'a 'b empty) ;'()
;;(replace 'a 'b (list 'b )) ; (cons 'a '())
;;(replace 'a 'b (list 'b (list 'b) )) ; (cons 'a (cons (cons 'a '()) '()))
;;(replace 'a 'b (list 'b 'c )) ; (cons 'a (cons 'c '()))
;; 模版
;;(define (replace new old wp)
;; (cond
;; [(empty? wp) ...]
;; [(cons? (first wp)) ... (replace new old (first wp)) ... (replace new old (rest wp)) ...]
;; [(eq? old (first wp)) ... new ... ((replace new old(rest wp))) ...]
;; [else ... (first wp) ... (replace new old (rest wp)) ...)]))
(define (replace new old wp)
(cond
[(empty? wp) empty]
[(cons? (first wp)) (cons (replace new old (first wp)) (replace new old (rest wp)) )]
[(eq? old (first wp)) (cons new (replace new old (rest wp)))]
[else (cons (first wp) (replace new old (rest wp)) )]))
;;测试
(replace 'a 'b empty)
(replace 'a 'b (list 'b ))
(replace 'a 'b (list 'b (list 'b) ))
(replace 'a 'b (list 'b 'c ))
```
## 14.3.4 获取最深嵌入页网页深度
```
;; depth : wp->number
;; 获取最深嵌入页网页深度
;; 例子
;;(= (depth empty) 0)
;;(= (depth (list 'a)) 1)
;;(= (depth (list 'a (list 'a))) 2)
;;(= (depth (list 'a (list 'a 'a) (list 'a 'a 'a))) 4)
;; 模版
;;(define (depth wp)
;; (cond
;; [(empty? wp ) ...]
;; [(symbol? (first wp)) ... (first wp) ... (depth (rest wp)) ...]
;; [(cons? (first wp )) (cond
;; [(> (depth (first wp)) (depth (rest wp))) (depth (first wp))]
;; [else (depth (rest wp))])]))
(define (depth wp)
(cond
[(empty? wp ) 0]
[(symbol? (first wp)) (+ 1 (depth (rest wp)))]
[(cons? (first wp )) (cond
[(> (depth (first wp)) (depth (rest wp))) (depth (first wp))]
[else (depth (rest wp))])]))
;;测试
(= (depth empty) 0)
(= (depth (list 'a)) 1)
(= (depth (list 'a (list 'a))) 2)
(= (depth (list 'a (list 'a 'a) (list 'a 'a 'a))) 4)
```
';