乐正

Actions speak louder than words.

Sicp-ex3-22

问题

除了可以用一对指针表示队列外,我们也可以将队列构造成一个带有局部状态的过程。这里的局部状态由指向一个常规表的开始和结束指针组成。这样,过程make-queue将具有下面的形式:

1
2
3
4
5
6
(define (make-queue)
  (let ((front-ptr ...)
        (rear-ptr ...))
    <内部过程定义>
    (define (dispatch m) ...)
    dispatch))

请完成make-queue的定义,进而采用这一表示提供队列操作的实现。

解答

练习3.22 (ex3-22.scm) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
(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 (front-queue)
      (if (empty-queue?)
          (error "FRONT called with 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)
              front-ptr)
              (else
                (set-cdr! rear-ptr new-pair)
                (set-rear-ptr! new-pair)
                front-ptr))))
    (define (delete-queue!)
      (cond ((empty-queue?)
             (error "DELETE! called with an empty queue."))
            (else
              (set-front-ptr! (cdr front-ptr))
              front-ptr)))
    (define (dispatch m)
      (cond ((eq? m 'front-ptr) front-ptr)
            ((eq? m 'rear-ptr) rear-ptr)
            ((eq? m 'empty-queue?) empty-queue?)
            ((eq? m 'front-queue) front-queue)
            ((eq? m 'insert-queue!) insert-queue!)
            ((eq? m 'delete-queue!) delete-queue!)
            (else (error "Unrecognized message" m))))
    dispatch))

测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
(define q1 (make-queue))
;Value: q1

(q1 'front-ptr)
;Value: ()

(q1 'rear-ptr)
;Value: ()

((q1 'empty-queue?))
;Value: #t

((q1 'insert-queue!) 'a)
;Value 14: (a)

((q1 'insert-queue!) 'b)
;Value 14: (a b)

((q1 'delete-queue!))
;Value 15: (b)

((q1 'delete-queue!))
;Value: ()

draft

« sicp-ex3-21 sicp-ex3-23 »

Comments