scheme 用变动数据模拟

练习3.13 考虑下面的make-cycle过程，并画出盒子指针图形。

点击查看代码

(define (make-cycle x)(set-cdr! (last-pair x) x)x)

这是一个循环结构，会使得指针无限循环

练习3.14
下面的过程相当有用，但也有些费解：

点击查看代码

(define (mystery x)(define (loop x y)(if (null? x)y(let ((temp (cdr x)))(set-cdr! x y)(loop temp x))))(loop x '()))

这是个倒叙的结构。

练习3.16 ben决定写一个过程，用来统计任何一个表结构中序对的数量

点击查看代码

(define (count-pairs x)(if (not (pair? x))0(+ (count-pairs (car x))(count-pairs (cdr x))1)))

这个过程会出现重复计数的问题。

点击查看代码

> (define a1 (list 'a 'b 'c))
> (define a2 (list 'c (list 'a 'b)))
> (define x1 (cons 'a 'b))
> (define y1 (cons x1 x1))
> (define z1 (cons y1 y1))
> (count-pairs a1)
3
> (count-pairs a2)
4
> (count-pairs z1)
7

练习3.17 修正count-pairs过程

点击查看代码

;增加一个对比内容，剔除重复计数的部分
(define (element-of-set set x)(cond ((null? set) #f)((eq? (car set) x) #t)(else(element-of-set (cdr set) x))))
(define (adjoin-set set x)(cons x set))
(define (count-pair x)(let ((visited '()))(define (count-pair-set x)(cond ((not (pair? x)) 0)((element-of-set visited x) 0)(else(set! visited (adjoin-set visited x))(+ (count-pair-set (car x))(count-pair-set (cdr x))1))))(count-pair-set x)))

练习3.18 请写一个过程去检查一个表，确定其中是否有环（类似3.13中的无限循环结构）

点击查看代码

(define (cycle-pair? x)(let ((visited '()))(define (cycle-pair-set? x)(cond ((not (pair? x) #f))((element-of-set visited x) #t)(else(set! visited (adjoin-set visited x))(cycle-pair-set? (cdr x)))))(cycle-pair-set? x)))

练习3.19 采用一种只需要常量空间的算法解决3.18

点击查看代码

;无法使用表的遍历确认是否进入循环
;通过异步，通过cdr取x1，cddr取x2，如果进入循环则x2会追上x1
;由于x2肯定在x1前面，所以只用考虑x2是否会跳出
(define (cycle-pairs? x)(define (cycle? x1 x2)(cond ((not (pair? x2)) #f)((not (pair? (cdr x2))) #f)((eq? x1 x2) #t)(else(cycle? (cdr x1) (cddr x2)))))(if (not (pair? x)) #f(cycle? x (cdr x))))