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))
转载于:https://www.cnblogs.com/tclan126/p/6624561.html