Представляющий очереди как процедура с местными государственными


Из SICP:

Упражнение 3.22. Вместо представляющий очереди как пара указатели, мы можем построить очередь как процедуры с местными государственными. Местные государство будет состоять из указателей на начало и конец обычный список. Таким образом, на очереди процедура будет иметь форму

(define (make-queue)
  (let ((front-ptr ...)
        (rear-ptr ...))
    <definitions of internal procedures>
    (define (dispatch m) ...)
    dispatch))

Полное определение сделать-очереди и обеспечить реализацию операции очереди с помощью этого представление.

Я написал следующее решение:

(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?) (null? front-ptr))
    (define (front-queue) 
      (if (empty?)
          (error "FRONT called with an empty queue" front-ptr)
          (car front-ptr)))
    (define (insert! item)
      (let ((new-pair (cons item '())))
        (cond ((empty?)
               (set-front-ptr! new-pair)
               (set-rear-ptr! new-pair)
               dispatch)
              (else
               (set-cdr! rear-ptr new-pair)
               (set-rear-ptr! new-pair)
               dispatch))))
    (define (delete!)
      (cond ((empty?)
             (error "DELETE! called with an empty queue" first-ptr))
            (else
             (set-front-ptr! (cdr front-ptr))))
      dispatch)
    (define (print) front-ptr)
    (define (dispatch m)
      (cond ((eq? m 'insert!) insert!)
            ((eq? m 'front-ptr) front-ptr)
            ((eq? m 'rear-ptr) rear-ptr)
            ((eq? m 'empty?) empty?)
            ((eq? m 'delete!) delete!)
            ((eq? m 'print) print)
            (else (error "No such procedure: dispatch" m))))
    dispatch))

(define q1 (make-queue))
((((q1 'insert!) 'a) 'print))
((((q1 'insert!) 'b) 'print))
((((q1 'delete!)) 'print))
((((q1 'delete!)) 'print))

Как его можно улучшить?



247
4
задан 20 мая 2011 в 07:05 Источник Поделиться
Комментарии