[scheme]求教一个Sheme操作队列的问题

Question

本帖最后由 白云深 于 2010-03-21 22:54 编辑

下面这段代码是“The Scheme Programming Language"上面的，是描述如何操作队列的：

1. (define make-queue
2.   (lambda ()
3.     (let ((end (cons 'ignored '())))
4.       (cons end end))))
6. (define putq!
7.   (lambda (q v)
8.     (let ((end (cons 'ignored '())))
9.       (set-car! (cdr q) v)
10.       (set-cdr! (cdr q) end)
11.       (set-cdr! q end))))
13. (define getq
14.   (lambda (q)
15.     (car (car q))))
17. (define delq!
18.   (lambda (q)
19.     (set-car! q (cdr (car q)))))

复制代码我用的是PLT Scheme，下面是测试代码及输出

> (define myq (make-queue))(putq! myq 'a)
> (putq! myq 'b)
> myq
((a b ignored) ignored)
> (delq! myq)
> myq
((b ignored) ignored)
> (delq! myq)
> myq
((ignored) ignored)
>

这段代码基本上看懂了，但有些细节理解的还不是很透彻，尤其是putq!，所以我在plt的交互环境下，试着按照putq!的定义，一步一步执行，并查看myq的内容，但得到的结果却是这样：

> (define end (cons 'ignored '()))
> (define myq (cons end end))
> myq
((ignored) ignored)
> (set-car! (cdr myq) 'a)
> myq
((a) a)
> (set-cdr! (cdr myq) end)
> myq
(#0=(a . #0#) . #0#)
> (set-cdr! myq end)
> myq
(#0=(a . #0#) . #0#)
> (set-car! (cdr myq) 'b)
> myq
(#0=(b . #0#) . #0#)
> (set-cdr! (cdr myq) end)
> myq
(#0=(b . #0#) . #0#)
> (set-cdr! myq end)
> myq
(#0=(b . #0#) . #0#)
>

上面的操作步骤，原想是要在myq中做两次putq操作，让a, b先后进队列，然后得到的输出却完全不是我原先想象的那样。上面的操作，我在MIT/GNU Scheme上也做了一下，得到的结果又是另外一种样子，这里就不贴了。不知道错在什么地方，或许我这种思路就有问题。初学Scheme，请各位前辈指点一二，先行谢过。

Answer 1

回复 2# win_hate

多谢版主指点，确实如您所说。感觉有点像C/CPP里面指针的深复制，浅复制，不知道我这样理解对不对。

Answer 2

自己动手画个图可能会更清楚一些。

Answer 3

putq! 里的 end 每次都是新构造出来的，你模拟时，每插入一个新项，就要新建一个 end.

guile> (define new-end
  (lambda ()
    (cons 'ignored '())))

guile> (define end (new-end))
guile> (define myq (cons end end))
guile> myq
((ignored) ignored)
guile> (set-car! (cdr myq) 'a)
guile> myq
((a) a)
guile> (define end2 (new-end))
guile> (set-cdr! (cdr myq) end2)
guile> myq
((a ignored) a ignored)
guile> (set-cdr! myq end2)
guile> myq
((a ignored) ignored)
guile> (set-car! (cdr myq) 'b)
guile> myq
((a b) b)
guile> (define end2 (new-end))
guile> (set-cdr! (cdr myq) end2)
guile> myq
((a b ignored) b ignored)
guile> (set-cdr! myq end2)
guile> myq
((a b ignored) ignored)