乐正

Actions speak louder than words.

Sicp-ex3-18

问题

请写出一个过程检查一个表,确定其中是否包含环,也就是说,如果某个程序打算通过不断的做cdr去找到这个表的结尾,是否会陷入无穷循环。练习3.13构造了这种表。

解答

练习3.18 (ex3-18.scm) download
1
2
3
4
5
6
7
8
9
10
(define (ring? x)
  (define (in? item lst)
    (cond ((null? lst) #f)
          ((eq? item (car lst)) #t)
          (else (in? item (cdr lst)))))
  (define (iter y checked)
    (cond ((null? y) #f)
          ((in? y checked) #t)
          (else (iter (cdr y) (cons y checked)))))
  (iter x '()))

测试

1
2
3
4
5
6
7
8
9
10
11
(define a (list 'a 'b 'c))
;Value: a

(set-cdr! (last-pair a) a)
;Unspecified return value

(ring? a)
;Value: #t

(ring? (list 'a 'b 'c))
;Value: #f

draft

« sicp-ex3-17 sicp-ex3-19 »

Comments