第7章时空权衡.pptVIP

第7章 时空权衡 最重要的事情永远不能受次要事情的支配。 ———Johann Wolfgang von Goethe(1749—1832 三种类型: 1、对问题的部分或全部输入做预处理，然而对获得的额外信息进行存储，以加速后面问题的求解。我们把这个方法称为输入增强。如计数法排序(7．1节)、BoyepMoo贮串匹配算法和HoRpool提出的简化版本(7．2节) 预构造:简单地使用额外空间来实现更快和(或)更方便的数据存取(涉及存取结构)。如散列法(7．3节)、以D树作索引(7．4节) 动态规划: 这个策略的基础是把给定问题中重复于问题的解记录在表中，然后求得所讨论问题的解。 7.1 计数排序 针对待排序列表中的每一个元素，算出列表中小于该元素的元素个数并把结果记录在一张表中。这个“个数”指出了该元素在有序列表中的位置。 7.2 串匹配中的输入增强技术 串匹配中使用了输入增强思想：对模式进行预处理以得到它的一些信息，然后在给定文本中实际查找模式的时候使用这些信息。 最著名的两种算法的基本思路：Knuth-Morris-Pratt算法和Boyer-Moore算法 7.2 串匹配中的输入增强技术 蛮力法: 简单地从左到右比较模式和文本中每一对相应的字符 Boyer-Moore算法 Horspool算法 7.2.1 Horspool算法 考虑在某些文本中查找模式BARBER: 情况1:模式中不存在C(在例子中,C就是S),模式安全移动的幅度就是它的全部长度. 情况2:模式中存在C,但它不是模式的最后一个字母(在例子中,C就是B), 移动时应该把模式中最右边的C和文本中的C对齐. 情况3:如果C正好是模式中的最后一个字符，但是在模式的其它m-1个字符中不包含C，移动的情况类似于情况1：移动的幅度等于模式的全部长度m。 情况4:如果C正好是模式中的最后一个字符，并且在模式的前m-1个字符中也包含C，移动的情况类似于情况2:移动时应该把模式中前m-1个字符中的C和文本中的C对齐。 7．3 散 列 法 词典（广义索引）结构：通过关键码的索引对元素进行访问，如索引表和散列表。 这节讨论散列法的实现 词典在讨论词典抽象数据类型时，把词典定义为名字-属性对的集合。根据问题的不同，可以为名字和属性赋予不同的含义。 例如，在图书馆检索目录中，名字是书名，属性是索书号及作者等信息；在计算机活动文件表中，名字是文件名，属性是文件地址、大小等信息；而在编译程序建立的变量表中，名字是变量标识符，属性是变量的属性、存放地址等信息。 在实际应用中，字典最重要的一种类型是可看作记录的集合，如前面的图书记录。 在词典的所有操作中，最基本的只有3种： Find (有哪些信誉好的足球投注网站) Insert (插入) Remove (删除)。在选择词典的表示时，必须确保这几个操作的实现。 通常，用文件 (表格) 来表示实际的对象集合，用文件记录 (表格的表项) 来表示单个对象。这样，词典中的名字-属性对将被存于记录 (表项) 中，通过表项的关键码 ( 名字-属性对的名字) 来标识该表项，称为键。 表项的存放位置及其关键码之间的对应关系可以用一个二元组表示：(关键码key，表项位置指针addr) 这个二元组构成有哪些信誉好的足球投注网站某一指定表项的索引项。考虑到有哪些信誉好的足球投注网站效率，可以用顺序表的方式组织词典，也可以用二叉有哪些信誉好的足球投注网站树或多路有哪些信誉好的足球投注网站树的方式组织词典，还有另一种有哪些信誉好的足球投注网站效率很高的组织词典的方法，即散列表结构。 散列法的基本思想是把键分布在一个称为散列表的一维数组 H[0,1,…,m-1]中。我们可以通过对每个键计算某些被称为散列函数的预定义函数h的值，来完成这种分布。该函数为每个键指定一个称为散列地址的位于0到m-1之间的整数。例如，如果键K是一个非负整数，它的散列函数可以是这种形式：h(K)=Kmod m.如果是字符串，…如果是字符串，… 一般来说，一个散列函数需要满足两个多少有些冲突的要求： 1) 一个散列函数需要把镶在散列表的单元中尽可能均匀地分布; 2) —个散列函数必须容易计算。 7．3．1 开散列(分离键) 根据散列函数解决碰撞的机制不同，分为开散列（分离键）和闭散列(开式寻址) 在开散列中，键被储存在附着于散列表单元上的链表中。每个链表包含着所有散列到该单元的键。作为一个例子，下面这个词的列表： 在开散列中，查找实现：键-散列值-链表单元碰撞后比较。 7．3．2 闭散列(开式寻址) 在闭散列中，所有的链都存储在散列表本身、而没有使用