练习 3.23

关于双端结构的更多信息,可以参考维基百科的 Double-ended queue 词条 或者任何一本算法/数据结构书籍。

以下是双端队列的实现:

;;; 23-deque.scm

; ptr selector

(define (front-ptr deque)
    (car deque))

(define (rear-ptr deque)
    (cdr deque))

; ptr setter

(define (set-front-ptr! deque item)
    (set-car! deque item))

(define (set-rear-ptr! deque item)
    (set-cdr! deque item))

; deque constructor

(define (make-deque)
    (cons '() '()))

; deque selector

(define (empty-deque? deque)
    (null? (front-ptr deque)))

(define (front-deque deque)
    (if (empty-deque? deque)
        (error "FRONT-DEQUE called with an empty deque" deque)
        (car (front-ptr deque))))

(define (rear-deque deque)
    (if (empty-deque? deque)
        (error "REAR-DEQUE called with an empty deque" deque)
        (car (rear-ptr deque))))

; deque setter

(define (insert-rear-deque! deque item)
    (let ((new-pair (cons item '())))
        (cond ((empty-deque? deque)
                (set-front-ptr! deque new-pair)
                (set-rear-ptr! deque new-pair)
                deque)
              (else
                (set-cdr! (rear-ptr deque) new-pair)
                (set-rear-ptr! deque new-pair)
                deque))))

(define (delete-front-deque! deque)
    (cond ((empty-deque? deque)
            (error "DELETE-FRONT-DEQUE! called with an empty deque" deque))
          (else
            (set-front-ptr! deque (cdr (front-ptr deque)))
            deque)))

(define (insert-front-deque! deque item)
    (cond ((empty-deque? deque)
            (insert-rear-deque! deque item))
          (else
            (set-front-ptr! deque (cons item (front-ptr deque)))
            deque)))

(define (delete-rear-deque! deque)
    (define (iter deque lst)
        (cond ((null? (cdr (cdr lst)))
                (set-cdr! lst '())
                (set-rear-ptr! deque lst)
                deque)
              (else
                (iter deque (cdr lst)))))
    (cond ((empty-deque? deque)
            (error "DELETE-REAR-DEQUE! called with an empty deque" deque))
          ((null? (cdr (front-ptr deque)))      ; 长度等于 1
            (set-front-ptr! deque '())
            deque)
          (else
            (iter deque (front-ptr deque)))))   ; 长度大于 1

;

(define (print-deque deque)
    (car deque))

测试:

1 ]=> (load "23-deque.scm")

;Loading "23-deque.scm"... done
;Value: delete-rear-deque!

1 ]=> (define q (make-deque))       ; 创建队列

;Value: q

1 ]=> (insert-front-deque! q 2)     ; 插入三个元素

;Value 11: ((2) 2)

1 ]=> (insert-front-deque! q 1)

;Value 11: ((1 2) 2)

1 ]=> (insert-rear-deque! q 3)

;Value 11: ((1 2 3) 3)

1 ]=> (print-deque q)

;Value 12: (1 2 3)

1 ]=> (delete-front-deque! q)       ; 从前端删除

;Value 11: ((2 3) 3)

1 ]=> (print-deque q)

;Value 13: (2 3)

1 ]=> (delete-rear-deque! q)        ; 从后端删除

;Value 11: ((2) 2)

1 ]=> (print-deque q)

;Value 13: (2)

1 ]=> (empty-deque? q)              ; 空队列测试

;Value: #f

1 ]=> (delete-rear-deque! q)

;Value 11: (() 2)

1 ]=> (empty-deque? q)

;Value: #t

双端队列的双链表实现

前面的双端队列实现虽然能满足功能上的目的,但是它不符合题目『所有操作都必须在 \(\Theta(1)\) 步内完成』的要求,因为在 delete-rear-deque! 过程中,使用了一个 \(\Theta(n)\) 步的遍历操作。

为了让所有操作的复杂度都能达到 \(\Theta(1)\) ,需要修改双端队列的底层实现,从原来的单链表(single linked list)表示改为双链表(double linked list)表示。

首先实现双链表:

;;; 23-double-linked-list.scm

(define (make-double-linked-list)
    '())

(define (empty-double-linked-list? lst)
    (null? lst))

(define (insert-double-linked-list! lst item)
    (cond ((empty-double-linked-list?)
            (set! lst (make-node item '() '()))
            lst)
          (else
            

测试:

:wq

讨论

blog comments powered by Disqus