scheme解决约瑟夫环问题（续)

    sicp的习题3.22，也就是以消息传递的风格重新实现队列，我的解答如下：

(define (make-queue)
  (let ((front-ptr '())
        (rear-ptr '()))
  (define (set-front-ptr! ptr) (set! front-ptr ptr))
  (define (set-rear-ptr! ptr) (set! rear-ptr ptr))
  (define (empty-queue?) (null? front-ptr))
  (define (front-queue)
    (if (empty-queue?)
        (error "FRONT called with an empty queue")
        (car front-ptr)))
  (define (insert-queue! item)
    (let ((new-pair (cons item '())))
      (cond ((empty-queue?)
              (set-front-ptr! new-pair)
              (set-rear-ptr! new-pair))
            (else
               (set-cdr! rear-ptr new-pair)
               (set-rear-ptr! new-pair)))))
  (define (delete-queue!)
      (cond ((empty-queue?)
             (error "DELETE! called with an empty queue" queue))
            (else
               (set-front-ptr! (cdr front-ptr)))))
  (define (dispatch m)
    (cond ((eq? m 'front-queue) (front-queue))
          ((eq? m 'empty-queue?) (empty-queue?))
          ((eq? m 'insert-queue!) insert-queue!)
          ((eq? m 'delete-queue!) delete-queue!)
          (else
             (error "Unknow method" m))))
    dispatch))
(define (front-queue z) (z 'front-queue))
(define (empty-queue? z) (z 'empty-queue?))
(define (insert-queue! z item) ((z 'insert-queue!) item))
(define (delete-queue! z) ((z 'delete-queue!)))

     由此，我才知道自己竟然一直没有想到，scheme完全可以模拟单向循环链表，整整第三章都在讲引入赋值带来的影响，而我却视而不见。在引入了改变函数 后，数据对象已经具有OO的性质，模拟链表、队列、table都变的易如反掌。首先，模拟节点对象，节点是一个序对，包括当前节点编号和下一个节点：

 

(define (make-node n next) (cons n next))
(define (set-next-node! node next) (set-cdr! node next))
(define (set-node-number! node n) (set-car! node n))
(define (get-number node) (car node))
(define (get-next-node node) (cdr node))

    有了节点，实现了下单向循环链表：

(define (make-cycle-list n)
  (let ((head (make-node 1 '())))
    (define (make-list current i)
      (let ((next-node (make-node (+ i 1) '())))
        (cond ((= i n) current)
              (else
                (set-next-node! current next-node)
                (make-list next-node (+ i 1))))))
    (set-next-node! (make-list head 1) head) 
    head))

     make-cycle-list生成一个有N个元素的环形链表，比如(make-cycle-list 8)的结果如下
        #0=(1 2 3 4 5 6 7 8 . #0#)

     Drscheme的输出形象地展示了这是一个循环的链表。那么约瑟夫环的问题就简单了：

 

(define (josephus-cycle n m)
  (let ((head (make-cycle-list n)))
    (define (josephus-iter prev current i)
      (let ((next-node (get-next-node current)))
       (cond ((eq? next-node current) (get-number current))
             ((= 1 i)
              (set-next-node! prev next-node)
              (josephus-iter prev next-node m))
             (else
               (josephus-iter current next-node (- i 1))))))
    (josephus-iter head head m)))

     从head节点开始计数，每到m，就将当前节点删除（通过将前一个节点的next-node设置为current的下一个节点），最后剩下的节点的编号就是答案。