1 (define (front-ptr queue) (car queue)) 2 (define (rear-ptr queue) (cdr queue)) 3 4 (define (set-front-ptr! queue item) (set-car! queue item)) 5 (define (set-rear-ptr! queue item) (set-cdr! queue item)) 6 7 (define (empty-queue? queue) (null? (front-ptr queue))) 8 9 (define (make-queue) (cons '() '())) 10 11 (define (front-queue queue) 12 (if (empty-queue? queue) 13 (error "FRONT called with an empty queue" queue) 14 (car (front-ptr queue)))) 15 16 (define (insert-queue! queue item) 17 (let ((new-pair (cons item '()))) 18 (cond ((empty-queue? queue) 19 (set-front-ptr! queue new-pair) 20 (set-rear-ptr! queue new-pair) 21 queue) 22 (else (set-cdr! (rear-ptr queue) new-pair) 23 (set-rear-ptr! queue new-pair) 24 queue)))) 25 26 (define (delete-queue! queue) 27 (if (empty-queue? queue) 28 (error "DELETE called with an empty queue" queue) 29 (begin 30 (set-front-ptr! queue (cdr (front-ptr queue))) 31 queue))) 32 33 ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; 34 35 (define q1 (make-queue)) 36 37 (insert-queue! q1 'q) 38 (insert-queue! q1 'b) 39 (insert-queue! q1 'c) 40 (delete-queue! q1) 41 42 ;;;;;;;;;;;;;;;;3.21 43 44 (define (print-queue queue) 45 (car queue)) 46 47 (print-queue q1) 48 (rear-ptr q1) 49 (front-ptr q1) 50 (set-cdr! (rear-ptr q1) '(m)) 51 ;(set-cdr! q1 '(m)) 52 53 (set-rear-ptr! q1 '(m)) 54 q1 55 56 ;;;;;;;;;;;;;;;;3.22 57 (define (make-queue2) 58 (let ((front-ptr '()) 59 (rear-ptr '())) 60 (define (set-front-ptr! item) 61 (set! front-ptr item)) 62 (define (set-rear-ptr! item) 63 (set! rear-ptr item)) 64 (define (empty-queue?) 65 (null? front-ptr)) 66 (define (insert-queue! item) 67 (let ((new-pair (list item))) 68 (cond ((empty-queue?) 69 (set-front-ptr! new-pair) 70 (set-rear-ptr! new-pair) 71 front-ptr) 72 (else 73 (set-cdr! rear-ptr new-pair) 74 (set-rear-ptr! new-pair) 75 front-ptr)))) 76 (define (delete-queue!) 77 (cond ((empty-queue?) 78 (error "DELETE! called with an empty queue" front-ptr)) 79 (else 80 (set-front-ptr! (cdr front-ptr)) 81 front-ptr))) 82 (define (dispatch m) 83 (cond ((eq? m 'insert-queue!) insert-queue!) 84 ((eq? m 'delete-queue!) delete-queue!) 85 ((eq? m 'empty-queue?) empty-queue?) 86 (else (error "Undefined operation" m)))) 87 dispatch)) 88 89 (define (make-queue3) 90 (let ((front-ptr '()) 91 (rear-ptr '())) 92 (define (insert-queue! item) 93 (cond ((empty-queue?) 94 (let ((init-list (list item))) 95 (set! front-ptr init-list) 96 (set! rear-ptr init-list) 97 front-ptr)) 98 (else 99 (let ((new-item (list item))) 100 (set-cdr! rear-ptr new-item) 101 (set! rear-ptr new-item) 102 front-ptr)))) 103 (define (delete-queue!) 104 (cond ((empty-queue?) 105 (error "DELETE! called with an empty queue" front-ptr)) 106 (else 107 (set! front-ptr (cdr front-ptr)) 108 front-ptr))) 109 (define (empty-queue?) 110 (null? front-ptr)) 111 (define (dispatch m) 112 (cond ((eq? m 'insert-queue!) 113 insert-queue!) 114 ((eq? m 'delete-queue!) 115 (delete-queue!)) 116 ((eq? m 'empty-queue?) 117 (empty-queue?)) 118 (else 119 (error "Unknow operation -- DISPATCH" m)))) 120 dispatch)) 121 122 ;(define q2 (make-queue3)) 123 ;((q2 'insert-queue!) 3) 124 ;((q2 'insert-queue!) 4) 125 126 ;(define q2 '(1)) 127 ;(set-cdr! q2 (list 2)) 128 ;q2
这几题的理解花了几天，发现自己是想多了点，然后还有一个原因是理解错误
126-128 的结果为（1 2）不是 （1 （2））