乐正

Actions speak louder than words.

Sicp-ex3-23

问题

双端队列(deque)也是一种数据项的序列,其中的数据项可以从前端或后端插入和删除。双端队列的操作包括构造函数make-deque,谓词empty-deque?,选择函数front-dequerear-dequerear-deque,改变函数front-insert-deque!rear-insert-deque!front-delete-deque!rear-delete-deque!。请说明如何用序对表示双端队列,并给出各个操作的实现。所有的操作都应该在$\Theta (1)$步骤内完成。

解答

为了满足所有操作都是$\Theta (1)$步骤内完成,需要使用一个双向链表实现。

练习3.23 (ex3-23.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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
(define (make-deque) (cons '() '()))

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

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

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

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

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

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

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

(define (front-delete-deque! deque)
  (if (empty-deque? deque)
      (error "FRONT DELETE! with an empty deque." deque)
      (begin
        (set-car! deque (cdr (front-ptr deque)))
        (set-car! (car (front-ptr deque)) '()))))

(define (rear-delete-deque! deque)
  (if (empty-deque? deque)
      (error "REAR DELETE! with an empty deque." deque)
      (begin
        (set-cdr! deque (car (car (rear-ptr deque))))
        (set-cdr! (rear-ptr deque) '()))))

(define (print-deque deque)
  (define (print-iter items)
    (if (not (null? items))
      (begin
        (display (cdr (car items)))
        (display " ")
        (print-iter (cdr items)))))
  (display ";(")
  (print-iter (front-ptr deque))
  (display ")")
  (newline))

测试

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
36
37
38
39
40
41
42
43
44
45
(print-deque q)
;()
;Unspecified return value

(front-insert-deque! q 'a)
;Unspecified return value

(print-deque q)
;(a )
;Unspecified return value

(front-insert-deque! q 'b)
;Unspecified return value

(print-deque q)
;(b a )
;Unspecified return value

(rear-insert-deque! q 'c)
;Unspecified return value

(print-deque q)
;(b a c )
;Unspecified return value

(rear-insert-deque! q 'd)
;Unspecified return value

(print-deque q)
;(b a c d )
;Unspecified return value

(front-delete-deque! q)
;Unspecified return value

(print-deque q)
;(a c d )
;Unspecified return value

(rear-delete-deque! q)
;Unspecified return value

(print-deque q)
;(a c )
;Unspecified return value

draft

« sicp-ex3-22 sicp-ex3-24 »

Comments