华北水利学院数据结构第章(陈波).ppt

第4章 特殊的线性表——串 问题的提出 查毒程序 有哪些信誉好的足球投注网站引擎 1. 串的逻辑结构 串：由零个或多个任意字符组成的有限序列。 串长度：串中所包含的字符个数。 空串：长度为0的串，记为： 。 非空串通常记为：S=“a1 a2…an”其中：S是串名，双引号是定界符，双引号引起来的部分是串值 ，ai（1≤i≤n）是一个任意字符。 1. 串的逻辑结构 两个串相等：如果两个串的长度相等且对应字符都相等。 子串：串中任意连续的字符组成的子序列称为该串。 主串：包含子串的串。 子串的第一个字符在主串中的序号称为子串的位置。 2. 串的存储结构——顺序串 2. 串的存储结构——顺序串 2. 串的存储结构——顺序串 2. 串的存储结构——链接串 3. 串的基本操作 串的链接 串的比较 串的复制 习题4.4、4.5、4.6 习题4.7。编写一个函数来颠倒单词在字符串里的出现顺序。【《程序员面试攻略(第2版)》p81】 例如，把字符串“Do or do not, there is no try. ”转换为“try. no is there not, do or Do”。假设所有单词都以空格为分隔符，标点符号也当做字母来对待。 请对你的设计思路做出解释，并对你的解决方案的执行效率进行评估。 3. 串的基本操作 删除特定字符。 【《程序员面试攻略(第2版)》p78】 用C语言编写一个高效率的函数来删除字符串里的给定字符。这个函数的调用模型如下所示：void RemoveChars(char str[],char remove[]); 注意，remove中的所有字符都必须从str中删除干净。比如说，如果str是“Battle of the Vowels: Hawaii VS. Grozny”，remove是“aeiou”，这个函数将把str转换为“Bttl f th Vwls: Hw vs. Grzny”。 请对你的设计思路做出解释，并对你解决方案的执行效率进行评估。 4. 串的应用——模式匹配 模式匹配：给定主串S=s1s2…sn和模式T=t1t2…tm，在S中寻找T 的过程称为模式匹配。如果匹配成功，返回T 在S中的位置，如果匹配失败，返回0。 4. 串的应用——BF模式匹配算法 基本思想：从主串S的第一个字符开始和模式T 的第一个字符进行比较，若相等，则继续比较两者的后续字符；否则，从主串S的第二个字符开始和模式T 的第一个字符进行比较，重复上述过程，直到T 中的字符全部比较完毕，则说明本趟匹配成功；或S中字符全部比较完，则说明匹配失败。 4. 串的应用——BF模式匹配算法 4. 串的应用——BF模式匹配算法 4. 串的应用——BF模式匹配算法 4. 串的应用——BF模式匹配算法 4. 串的应用——BF模式匹配算法 4. 串的应用——BF模式匹配算法 4. 串的应用——BF模式匹配算法 4. 串的应用——BF模式匹配算法 4. 串的应用——BF模式匹配算法 4. 串的应用——BF模式匹配算法 4. 串的应用——BF模式匹配算法 4. 串的应用——BF模式匹配算法 4. 串的应用——BF模式匹配算法 4. 串的应用——BF模式匹配算法 设串s长度为n，串t长度为m，在匹配成功的情况下，考虑两种极端情况： 最好情况：不成功的匹配都发生在串t的第一个字符。 例如：s=aaaaabcd t=bcd 设匹配成功发生在si处，则在i-1趟不成功的匹配中共比较了i-1次，第i趟成功的匹配共比较了m次，所以总共比较了i-1+m次，所有匹配成功的可能情况共有n-m+1种，则：设从si开始与t串匹配成功的概率为pi，在等概率情况下pi=1/(n?m+1)，平均比较的次数是 因此最好情况下的时间复杂度是O(n+m)。 4. 串的应用——BF模式匹配算法 设串s长度为n，串t长度为m，在匹配成功的情况下，考虑两种极端情况： 最坏情况：不成功的匹配都发生在串t的最后一个字符。 例如：s=aaaaab t= aaab“ 设匹配成功发生在si处，则在i-1趟不成功的匹配中共比较了(i-1)×m次，第i趟成功的匹配共比较了m次，所以总共比较了i×m次，因此平均比较的次数是 一般情况下，mn，因此最坏情况下的时间复杂度是O(nm)。 4. 串的应用——BF模式匹配算法 为什么BF算法时间性能低？ 在每趟匹配不成功时存在大量回溯，没有利用已经部分匹配的结果。 如何在匹配不成功时主串不回溯？ 主串不回溯，模式就需要向右滑动一段距离。 如何确定模式的滑动距离？ 4. 串的应用——KMP模式匹配算法 4. 串的应用——KMP模式匹配算法 4. 串的应用——KMP模式匹配算法 4. 串的应用——KMP模式匹配算法 4. 串的应用——KMP模式匹配算法 4. 串的应用