《方案与编程艺术》一书中的练习 12.10

问题描述 投票:0回答:1

面向对象编程章节中的练习12.10 我们通过创建一个函数queue-maker来构建一个队列数据结构。 在此函数中,我们处理发送到对象的消息 例如,当我们发送对象时,消息“enqueue”和操作数“a”=>“a”将被推送到队列

(define q (queue-maker))
(q 'enqueue 'a)

需要做的是为消息“enqueue-list”添加处理程序,操作数将是一个列表。这会将列表中的所有项目添加到队列中

(q 'enqueue-list '(b c d))

这里的问题是为什么我们不使用追加!修改队列的函数?

scheme lisp
1个回答
0
投票

使用

append!
对于书中给出的队列的

实现来说都是一场灾难。

练习 12.10 要求您使用程序 12.15 中定义的版本。这是使用尾指针来提高 
enqueue!
 效率的版本。在此实现中,您可以通过两种方式使用 
append!

  1. 您可以直接
    append!进入队列列表。 (a) 不使用尾指针,因此必须遍历整个队列,更糟糕的是,(b) 不会 update
     尾指针,从而破坏数据结构,因此下次调用 
    enqueue!
     您将丢失刚刚添加的所有内容。您可以通过更新尾部指针以指向新的最后一个缺点来修复此问题,这否定了使用 
    append! 的任何假定的性能优势。但这无论如何都不安全
  2. ,请参见下文。
  3. 您可以
    append!指向指向队列最后一个cons的尾指针。这更好,但您仍然必须记住更新尾指针以指向新的最后一个 cons,因此您“仍然”必须遍历要附加的列表。然而,这仍然不安全,请参见下文。
方法(1)既否定了使用尾指针的优点,而且实现起来很痛苦。方法(2)看起来好一些。但是,再次请参阅下文,

两者都都不安全。

如果您使用早期的队列实现(程序 12.13 中的实现),看起来使用

append!

 会起作用:现在无需担心尾指针。但这
是不安全的。

这就是为什么所有这些方法都不安全。

考虑这段代码:

(define (enqueue-list-twice q l) (q 'enqueue-list! l) (q 'enqueue-list! l) ;or just enqueue! anything l)
如果使用 

append!

 来实现 
enqueue!
 会发生什么?好吧,第一次这样做时,您最终会得到一个尾部 
l
 的队列。这不是 
l
 的副本,它是
l
。第二次执行此操作时,
append!
将粉碎此列表中的最后一个缺点,
因此l
的最后一个缺点将是...
l

因此,这种方法为您设置了一个令人讨厌的陷阱:它将其参数之一作为队列的一部分隐藏起来,

然后将被破坏性地修改。太恶心了。

您甚至可以通过制作列表的显式副本来解决此问题,这再次否定了使用

append!

 的优势,因为无论如何您都必须遍历它才能复制它。当您完成所有这些工作时,最好只是实施该事情,而不必自始至终事后猜测
append!
。最明显、安全的方法就是通过重复调用 
enqueue-list!
 来实现 
enqueue!

© www.soinside.com 2019 - 2024. All rights reserved.