;08/6/28
;ex 3.23
;deque
;rear-delete-deque!是四个过程中比较特殊的，因为删除之后需要寻址队列的倒数第二个节点。
;又题目要求时间复杂度为O(1)，所以采用双向链表。
;与以前不同是front-delete-deque!和rear-delete-deque!需要确保两端的一致性
;另外写了个print过程用来做显示输出
;--------deque-node------------
(define (make-deque-node former-ptr data next-ptr)
  (list former-ptr data next-ptr))
(define (former-ptr node)
  (car node))
(define (data node)
  (cadr node))
(define (next-ptr node)
  (caddr node))
(define (set-former-ptr! node new-ptr)
  (if (null? node)
      '()    ;do nothing
      (set-car! node new-ptr)))
(define (set-data! node new-data)
  (if (null? node)
      '()  ;do nothing
      (set-car! (cdr node) new-data)))
(define (set-next-ptr! node new-ptr)
  (if (null? node)
      '()    ;do nothing
      (set-car! (cddr node) new-ptr)))
 
;--------deque--------
(define (front-ptr deque) (car deque))
(define (rear-ptr deque) (cdr deque))
(define (set-front-ptr! deque item)
  (set-car! deque item))
(define (set-rear-ptr! deque item)
  (set-cdr! deque item))

(define (empty-deque? deque)
  (null? (rear-ptr deque)))
(define (make-deque) (cons '() '()))
(define (front-deque deque)      ;队列前端的数据项
  (if (empty-deque? deque)
      (error "FRONT called by empty deque" deque)
      (data (front-ptr deque))))
(define (rear-deque deque)      ;队列前端的数据项
  (if (empty-deque? deque)
      (error "REAR called by empty deque" deque)
      (data (rear-ptr deque))))

(define (rear-insert-deque! deque item)
  (let ((new-node (make-deque-node '()
                                   item
                                   '())))
    (cond ((empty-deque? deque)
           (set-front-ptr! deque new-node)
           (set-rear-ptr! deque new-node)
           deque)
          (else
           (set-former-ptr! new-node (rear-ptr deque))
           (set-next-ptr! (rear-ptr deque) new-node)
           (set-rear-ptr! deque new-node)
           deque))))
(define (front-insert-deque! deque item)
  (let ((new-node (make-deque-node '() item '())))
    (cond ((empty-deque? deque)
           (set-front-ptr! deque new-node)
           (set-rear-ptr! deque new-node)
           deque)
          (else
           (set-next-ptr! new-node (front-ptr deque))
           (set-former-ptr! (front-ptr deque) new-node)
           (set-front-ptr! deque new-node)
           deque))))
(define (front-delete-deque! deque)
  (cond ((empty-deque? deque)
         (error "DELETE an empty deque " deque))
        (else (set-front-ptr! deque
                              (next-ptr (front-ptr deque)))
              (if (null? (front-ptr deque))         ;保持front-ptr和rear-ptr一致
                  (begin (set-rear-ptr! deque '())
                         deque)
                  deque))))
(define (rear-delete-deque! deque)
  (cond ((empty-deque? deque)
         (error "DELETE an empty deque " deque))
        (else (set-rear-ptr! deque (former-ptr (rear-ptr deque)))
              (set-next-ptr! (rear-ptr deque) '())
              (if (null? (rear-ptr deque))         ;保持front-ptr和rear-ptr一致
                  (begin (set-front-ptr! deque '())
                         deque)
                  deque))))
(define (print deque)
  (define (print-helper ptr)
    (if (null? ptr)
        'Done
        (begin
          (display (data ptr))
          (display "   ")
          (print-helper (next-ptr ptr)))))
  (print-helper (front-ptr deque)))

才明白一点，这样的方法类似面向对象的类，其中的成员front-ptr/rear-ptr不需要用cons联系起来...
(define (make-queue)
  (let ((front-ptr '())
        (rear-ptr '()))
    (define (set-front-ptr! item) (set! front-ptr item))
    (define (set-rear-ptr! item) (set! rear-ptr item))
    (define (empty-queue?) (null? front-ptr))
    (define (insert-queue! item)
      (let ((new-pair (cons item '())))
        (cond ((empty-queue?)
               (set-front-ptr! new-pair)
               (set-rear-ptr! new-pair)
               (cons front-ptr rear-ptr))
              (else
               (set-cdr! rear-ptr new-pair)
               (set-rear-ptr! new-pair)
               (cons front-ptr rear-ptr)))))
    (define (delete-queue!)
      (cond ((empty-queue?)
             (error "DELETE an empty queue " (cons front-ptr rear-ptr)))
            (else (set-front-ptr! (cdr front-ptr))
                  (cons front-ptr rear-ptr))))
    (define (dispatch m)
      (cond ((eq? m 'front-ptr) front-ptr)
            ((eq? m 'rear-ptr) rear-ptr)
            ((eq? m 'set-front-ptr!) set-front-ptr!)
            ((eq? m 'set-rear-ptr!) set-rear-ptr!)
            ((eq? m 'empty-queue?) empty-queue?)
            ((eq? m 'insert-queue!) insert-queue!)
            ((eq? m 'delete-queue!) delete-queue!)
            (else (error "UNKNOWN operation" m))))
    dispatch))
(define (front-ptr queue) (queue 'front-ptr))
(define (rear-ptr queue) (queue 'rear-ptr))
(define (insert-queue! queue item)
  ((queue 'insert-queue!) item))
(define (delete-queue! queue)
  ((queue 'delete-queue!)))

(define (print-queue queue)
  (print-list (front-ptr queue)))
(define (print-list item)
  (if (null? item)
      'Done
      (begin (display (car item))
             (display "  ")
             (print-list (cdr item)))))

 

临走那天宿舍一帮哥们忙里忙外的搬东西，前一分钟还跟出租车司机有说有笑，之后关上车门就走了。我这边也才明白过来，丫们不是出去办事了，以后来学校才是过来办事了。不过随之而来的感觉不是伤离别，而是马上想出他们还在北京我也还在北京，都没跑多远呢，别那么做作的伤感了。然后像之前几天一样，借着毕业的理由，去吃烤肉。回来也不能闲着，DOTA、GGXX照常进行，赶紧把自己折腾累了好睡觉。
没睡好，做梦都是楼管带着刷墙队过来清宿舍的场面。醒来的时候宿舍剩的几个哥们的行李都卷起来了，一个电话之后，宿舍就留下我跟一地的乱七八糟，有用的和没用的。我是三个宿舍最后一个走的，在宿舍里一个人转悠了一个钟头，心里堵的慌，但脑子里是空的，脸上是木的。“毕业了，关好宿舍的门”，关什么阿，楼管阿姨还得进去收拾收拾呢。
到了家，蛋疼的时候想，为啥咱的毕业就这么土呢？可能是因为手机、E-mail到处都是，该联系的又没分开，毕业并没改变什么。多喝点酒，应该就有气氛了，就算不能放大感情，至少让人专心点感受毕业的气氛，而不会想以后还能联系这些混帐理由，这样才不会像个三流演员演戏那样一副欠打的样子。

这半年毕设做的马马虎虎，也学了些以后基本用不到的东西，而且知道了学校里面的实验室不都是那么正规的。

这段时间就忙着写论文编论文改论文了。要求是两万字左右——什么概念，原来的800字作文还要给你90分钟吧，然后老师提些建议“题目不好”“格式不对 ”“内容太少”，或者说“我很忙，没时间”。然后打印装订成册，上交。据说答辩完毕后统一销毁——估计差不多的，要不这种东西都留在图书馆作索引，要浪费很多资源的。现在才知道很多称之为论文的东西都是这样搞出来的，而且还在这样顺理成章的继续着。

毕设答辩还要过两天，又是个费心的活计。然后这半年的过渡就彻底结束了。