1. 设计模式¶
1.1. 设计模式¶
比 ADT 更高一层的抽象，是用于描述程序设计的抽象—也就是 对象与类之间的交互。 有经验的软件设计者会学习并复用用于组合软件组件的模式。 这些模式被称为 设计模式 。
设计模式针对反复出现的问题，把重要的设计概念加以具体化并推广。 设计模式的一个主要目标，是把专家设计者获得的知识迅速传递给 较新的程序员。 另一个目标是让程序员之间能够高效地交流。 当你与别人共享与该主题相关的技术词汇时，讨论设计问题会容易得多。
具体的设计模式源于这样一种认识：某个特定的设计问题会在许多场景中 反复出现。 它们旨在解决实际问题。 设计模式描述设计解决方案的结构，而细节则针对具体问题来填充。 设计模式有点像是数据结构： 每一种都带来代价与收益，这意味着可能存在权衡。 因此，一个给定的设计模式在应用时可能有多种变体， 以匹配特定情境中固有的各种权衡。
本模块余下部分介绍几个在数据结构与算法学习中经常出现的简单设计模式。
1.1.1. 享元¶
享元 旨在解决下面这个问题： 你有一个包含许多对象的应用程序。 其中一些对象在所包含的信息和所扮演的角色上完全相同。 但它们必须能从不同地方访问，而从概念上说它们又确实是不同的对象。 由于相同信息存在大量重复， 我们希望能利用这个机会通过共享该空间来降低内存开销。 一个例子来自文档版面的表示。 字母 "C" 可以合理地用一个对象来表示，该对象描述这个字符的笔画 和包围盒。 然而，我们并不想在文档中每个出现 "C" 的地方都创建一个单独的 "C" 对象。 解决办法是为 "C" 对象分配共享表示的单独一份副本。 这样，文档中每一处需要给定字体、字号和字型的 "C" 的地方， 都会引用这一份副本。 对特定形式 "C" 的引用的各种实例被称为享元。
我们可以用树结构来描述页面上文字的版面。 树的根表示整个页面。 页面有多个子结点，每一列对应一个子结点。 列结点有对应每一行的子结点。 而行又有对应每个字符的子结点。 这些字符的表示就是享元。 享元包含对共享形状信息的引用， 还可能包含特定于该实例的附加信息。 例如， "C" 的每个实例都会包含一个对笔画和形状共享信息的引用， 还可能包含该字符实例在页面上的确切位置。
在用于存储点对象集合的 PR 四叉树 和 bintree 的实现中都用到了享元。 在 PR 四叉树中，许多 叶结点 表示空区域， 它们存储的唯一信息就是自己是空的这一事实。 这些完全相同的结点可以通过引用享元的单个实例来实现， 以降低内存开销。
1.1.2. 访问者¶
给定一棵用于描述页面版面的对象树，我们可能希望对树中的每个结点 执行某种活动。 树的遍历 是按照某种 确定的顺序访问树中每个结点的过程。 对于我们的文字排版应用，一个简单的例子可能是统计表示页面的树中 结点的数目。 另一些时候，我们可能希望为了调试而打印所有结点的清单。
我们可以为打算在树上执行的每一种此类活动分别编写一个遍历函数。 更好的做法是编写一个通用的遍历函数， 并把要在每个结点处执行的活动作为参数传入。 这种组织方式构成了 访问者 设计模式。 访问者设计模式也可以用于 图遍历 。
1.1.3. 组合¶
处理一组动作与一个对象类型层次结构之间的关系，有两种基本方法。 首先考虑典型的 过程式 方法。 假设我们有一个用于页面版面实体的基类， 并有一个子类层次结构来定义具体的子类型（页面、列、行、图形、字符等）。 再假设有一些要对这样一组对象执行的动作（例如把对象渲染到屏幕上）。 过程式设计方法是：把每个动作实现为一个方法， 该方法以一个指向基类类型的指针作为参数。 每个这样的动作方法都会遍历对象集合，依次访问每个对象。 每个动作方法都包含类似 switch 语句的东西， 为集合中的每个子类（例如页面、列、行、字符）定义动作的细节。 我们可以通过使用 访问者 设计模式来减少一些代码， 这样只需编写一次遍历，然后为可能应用于该对象集合的每个动作 编写一个访问者子例程。 但每个这样的访问者子例程仍然必须包含处理每一种可能子类的逻辑。
在我们的页面排版应用中，只有少数几种活动是我们希望对该页面表示执行的。 我们可能以完整细节渲染对象。 或者我们可能想要一种"草稿"渲染，只打印对象的包围盒。 如果我们想出一个要应用于对象集合的新活动， 并不需要修改任何实现现有活动的代码。 但对这个应用而言，新增活动并不常发生。 相比之下，对象类型可能有很多， 而我们可能经常向实现中添加新的对象类型。 遗憾的是，添加一种新的对象类型要求我们修改每一个活动， 而实现这些活动的子例程会得到相当长的 switch 语句， 用来区分众多子类的行为。
另一种设计是让层次结构中的每个对象子类都体现各种可能活动的动作。 每个子类都会有执行每种活动（例如完整渲染或包围盒渲染）的代码。 这样，如果我们想把这个活动应用于集合， 只需调用集合中的第一个对象并指定该动作（作为对该对象的方法调用）。 对于我们的页面版面及其层级式对象集合， 那些包含其他对象的对象（例如包含字母的行对象） 会为每个子结点调用相应的方法。 如果采用这种组织方式，我们想添加一个新活动，就必须修改每个子类的代码。 但对我们的文字排版应用来说，这种情况相对少见。 相比之下，向子类层次结构中添加一个新对象（对这个应用而言， 这远比添加一个新渲染函数更可能发生）则很容易。 添加一个新的子类不需要修改任何现有子类。 它只要求我们定义可以在新子类上执行的每个活动的行为。
第二种设计方法把功能活动埋藏在子类中， 称为 组合设计模式 。 使用组合设计模式的详细示例可以在关于 表达式树 的讨论中看到。
1.1.4. 策略¶
我们最后一个设计模式示例，让我们能够把一组可能作为某个更大活动一部分 执行的备选动作封装起来并使之可以互换。 还是继续我们的文字排版例子，我们希望渲染到的每个输出设备都需要 有自己执行实际渲染的函数。 也就是说，对象会被分解成组成它们的像素或笔画， 但渲染一个像素或笔画的实际机制取决于输出设备。 我们不想把这种渲染功能构建到对象子类中。 相反，我们想把为该输出设备执行适当渲染细节的方法或类 传递给执行渲染动作的子例程。 也就是说，我们想把恰当的 策略 交给对象， 以完成渲染任务的细节。 因此，这种方法被称为 策略 设计模式。
策略设计模式可以用来创建通用的排序函数。 排序函数可以带一个额外的参数来调用。 这个参数是一个类，它知道如何为待排序的记录提取和比较键值。 这样，排序函数就不需要知道其记录类型是如何实现的任何细节。
理解设计模式的最大挑战之一在于，有时一个模式与另一个模式只有细微差别。 例如，你可能会对组合模式与访问者模式之间的区别感到困惑。 它们的区别在于：组合设计模式关心的是把遍历过程的控制权 交给树的结点还是交给树本身。 两种做法都可以利用访问者设计模式，通过封装在每个结点处执行的活动， 来避免多次重写遍历函数。
但策略设计模式不是在做同样的事吗？ 访问者模式与策略模式之间的差别更为细微。 这里的差别主要是意图和侧重点的不同。 在策略设计模式和访问者设计模式中，活动都是作为参数传入的。 策略设计模式侧重于封装属于某个更大过程一部分的活动， 以便可以替换执行该活动的不同方式。 访问者设计模式侧重于封装将要对集合所有成员执行的活动， 以便可以在一个访问集合所有成员的通用方法中替换完全不同的活动。
