《算法：C语言实现（第1-4部分）基础知识、数据结构、排序及搜索（》

编辑推荐

内容简介

作者简介

精彩书评

目录

精彩书摘

　　还有一个例子出现在某种程序设计环境中，连通性可用来断言两个变量名是否等价。问题是在经过这样的断言序列之后，能够确定两个给定的名字是否等价。这个应用激发了我们打算考虑的几个算法的研制。它直接将我们的问题与一种简单抽象关联起来，为使算法具有广泛应用而提供了一种方法。我们即将看到这一点。
　　像上一段描述的变量名等价问题这样的应用程序要求我们把每个不同的变量名与一个整数关联起来。这种关联关系也隐含在前面描述的网络连接和电路连接的应用中。在第10章至第16章，我们将会以一种更高效的方法考虑提供这种连接关系的大量算法。因此，不失一般性，本章假设有N个对象，每个都与0一N一1之间的一个整数名对应。
　　我们正在寻求完成特定和良定义任务的程序，可能还想要解决其他许多相关的问题。在研制算法时我们面对的首要任务之一是确信我们已经以合理的方式指定了问题。我们要求算法的越多，它完成任务所需要的时间和空间越多。不可能量化这个关系，并且我们在发现一个问题难以求解或是求解代价昂贵，或是在好的情况下，发现算法可以比原始说明提供更多有用的信息时，我们常常修改这个问题的说明。
　　例如，我们的连通问题的说明只要求我们的程序知道任意给定对p—q是否是连通的，并不能够表明连接那个对的任何方式。添加这样一个说明的要求会使问题更加困难，会涉及其他的算法，我们将在第5章简略讨论，并在第7章详细讨论。
　　前面这段提到的说明要比原始说明要求更多的信息，我们也可以要求更少的信息。例如，我们可能只想回答这样的问题：“M个连接足以把Ⅳ个对象都连接起来吗？”这个问题表明，要研制一个高效的算法，常常需要我们对正在处理的抽象对象进行高级推理。在这种情况下，由图论基本结果可以得出所有Ⅳ个对象是连通的，当且仅当连通算法输出的对的个数恰好为N一1（见5．4节）。换句话说，连通算法永远不会输出多于N一1个对，这是因为一旦它输出N一1个对，则它从那个时刻遇见的任何对将会是连通的。因此，我们可以修改求解连通问题的程序，增加一个计数器就可以得到一个回答yes-no问题的程序，而不输出那些前面不连通的每个对，当计数器的值为N-1时，程序回答“yes”，否则回答“no”。这个问题只是我们希望回答关于连通性的许多问题中的一个例子。输入对的集合称为图（graph），输出对的集合称为图的生成树，它连接了所有对象。我们在第七部分考察图、生成树以及所有相关算法的性质。
　　……

前言/序言