Saturday, June 12, 2010

Ex 3.19 of SICP - use constant amount of space to find if a list contains a cycle

We can set a mark of a list,e.g. the address of the
head of a list and to see if this mark is accessed twice.
リストの頭のアドレスを記憶し、2回目アクセスされるときに、ロープが
あると判断できる。

可以记录一下list的头地址,如果此地址第二次被访问说明有循环在里面。
不是很确定是否为正解。因为要求使用一定量的空间。而记录头地址实际上
要记录整个list。但不须记录嵌套的list。

(define (loop? x)
  (define (iter y mk)
    (if (null? y) #f
      (if (eq? y mk) #t
(iter (cdr y) mk))))
  
  (if (null? x) #f
    (let ((mark x))
      (iter (cdr x) mark))))
loop?

gosh> loop?
gosh> (loop? '( 1 2 3))
#f
gosh> (define s '( 1 2 3))
s
gosh> (set-cdr! (cddr s) s)
#
gosh> 
#t
gosh> (loop? s)
#t

No comments:

Post a Comment