《华北水利学院数据结构第四章(陈波).ppt》由会员分享，可在线阅读，更多相关《华北水利学院数据结构第四章(陈波).ppt（44页珍藏版）》请在三一办公上搜索。
1、第4章 特殊的线性表串,问题的提出,查毒程序搜索引擎,1.串的逻辑结构,串：由零个或多个任意字符组成的有限序列。串长度：串中所包含的字符个数。空串：长度为0的串，记为：。非空串通常记为：S=“a1 a2an”其中：S是串名，双引号是定界符，双引号引起来的部分是串值，ai（1in）是一个任意字符。,1.串的逻辑结构,两个串相等：如果两个串的长度相等且对应字符都相等。子串：串中任意连续的字符组成的子序列称为该串。主串：包含子串的串。子串的第一个字符在主串中的序号称为子串的位置。,顺序串：用数组来存储串中的字符序列。,（1）用一个变量来表示串的长度。,2.串的存储结构顺序串,如何表示串的长度？,顺序
2、串：用数组来存储串中的字符序列。,（2）在串尾存储一个不会在串中出现的特殊字符作为串的终结符。,2.串的存储结构顺序串,如何表示串的长度？,顺序串：用数组来存储串中的字符序列。,（3）用数组的0号单元存放串的长度，串值从1号单元开始存放。,2.串的存储结构顺序串,如何表示串的长度？,链接串：用链接存储结构来存储串。p55,2.串的存储结构链接串,3.串的基本操作,串的链接串的比较串的复制习题4.4、4.5、4.6习题4.7。编写一个函数来颠倒单词在字符串里的出现顺序。【程序员面试攻略(第2版)p81】例如，把字符串“Do or do not,there is no try.”转换为“try.n
3、o 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
4、转换为“Bttl f th Vwls:Hw vs.Grzny”。请对你的设计思路做出解释，并对你解决方案的执行效率进行评估。,4.串的应用模式匹配,模式匹配：给定主串S=s1s2sn和模式T=t1t2tm，在S中寻找T 的过程称为模式匹配。如果匹配成功，返回T 在S中的位置，如果匹配失败，返回0。,4.串的应用BF模式匹配算法,基本思想：从主串S的第一个字符开始和模式T 的第一个字符进行比较，若相等，则继续比较两者的后续字符；否则，从主串S的第二个字符开始和模式T 的第一个字符进行比较，重复上述过程，直到T 中的字符全部比较完毕，则说明本趟匹配成功；或S中字符全部比较完，则说明匹配失败。,例：
5、主串S=ababcabcacbab，模式T=abcac,i=3，j=3失败；i回溯到2，j回溯到1,第 1趟,a b c a c,4.串的应用BF模式匹配算法,i=3，j=3失败；i回溯到2，j回溯到1,j,i,第 1趟,a b c a c,例：主串S=ababcabcacbab，模式T=abcac,4.串的应用BF模式匹配算法,i=2，j=1失败i回溯到3，j回溯到1,第 2趟,a b c a c,例：主串S=ababcabcacbab，模式T=abcac,4.串的应用BF模式匹配算法,i=2，j=1失败i回溯到3，j回溯到1,第 2趟,i,j,a b c a c,例：主串S=ababcab
6、cacbab，模式T=abcac,4.串的应用BF模式匹配算法,a b c a c,i=7，j=5失败i回溯到4，j回溯到1,第 3趟,例：主串S=ababcabcacbab，模式T=abcac,4.串的应用BF模式匹配算法,a b c a c,i=7，j=5失败i回溯到4，j回溯到1,第 3趟,i,j,例：主串S=ababcabcacbab，模式T=abcac,4.串的应用BF模式匹配算法,a b c a c,i=4，j=1失败i回溯到5，j回溯到1,第 4趟,例：主串S=ababcabcacbab，模式T=abcac,4.串的应用BF模式匹配算法,a b c a c,i=4，j=1失败i回
7、溯到5，j回溯到1,第 4趟,i,j,例：主串S=ababcabcacbab，模式T=abcac,4.串的应用BF模式匹配算法,a b c a c,i=5，j=1失败i回溯到6，j回溯到1,第 5趟,例：主串S=ababcabcacbab，模式T=abcac,4.串的应用BF模式匹配算法,a b a b c a b c a c b a b,a b c a c,i=5，j=1失败i回溯到6，j回溯到1,第 5趟,i,j,例：主串S=ababcabcacbab，模式T=abcac,4.串的应用BF模式匹配算法,a b a b c a b c a c b a b,a b c a c,i=11，j=6
8、，T中全部字符都比较完毕，匹配成功。,第 6趟,例：主串S=ababcabcacbab，模式T=abcac,4.串的应用BF模式匹配算法,1.在串S和串T中设比较的起始下标i和j；2.循环直到S或T的所有字符均比较完；2.1 如果Si=Tj，继续比较S和T的下一个字符；2.2 否则，将i和j回溯，准备下一趟比较；3.如果T中所有字符均比较完，则匹配成功，返回匹配的起始比较下标；否则，匹配失败，返回0；,4.串的应用BF模式匹配算法,int BFmatching(char s,char t)i=1;j=1;while(it0)return(i-j+1);else return 0;,4.串的应用
9、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/(nm+1)，平均比较的次数是因此最好情况下的时间复杂度是O(n+m)。,4.串的应用BF模式匹配算法,设串s长度为n，串t长度为m，在匹配成功的情况下，考虑两种极
10、端情况：最坏情况：不成功的匹配都发生在串t的最后一个字符。例如：s=aaaaab t=aaab“设匹配成功发生在si处，则在i-1趟不成功的匹配中共比较了(i-1)m次，第i趟成功的匹配共比较了m次，所以总共比较了im次，因此平均比较的次数是一般情况下，mn，因此最坏情况下的时间复杂度是O(nm)。,4.串的应用BF模式匹配算法,为什么BF算法时间性能低？在每趟匹配不成功时存在大量回溯，没有利用已经部分匹配的结果。如何在匹配不成功时主串不回溯？主串不回溯，模式就需要向右滑动一段距离。如何确定模式的滑动距离？,i=3，j=3失败；s2=t2;t1t2t1s2,第 1趟,a b c a c,4.串
11、的应用KMP模式匹配算法,i=3，j=3失败；s2=t2;t1t2t1s2,i,j,第 1趟,a b c a c,a b c a c,第 3趟,4.串的应用KMP模式匹配算法,a b c a c,第 3趟,i=7，j=5失败s4=t2;t1t2t1s4,4.串的应用KMP模式匹配算法,a b c a c,第 3趟,i=7，j=5失败s5=t3;t1t3t1s5,4.串的应用KMP模式匹配算法,a b c a c,第 3趟,i=7，j=5失败s5=t3;t1t3t1s5,匹配成功,4.串的应用KMP模式匹配算法,4.串的应用KMP模式匹配算法,结论：i可以不回溯，模式向右滑动到的新比较起点k，并
12、且k 仅与模式串T有关！需要讨论两个问题：如何由当前部分匹配结果确定模式向右滑动的新比较起点k？模式应该向右滑多远才是最高效率的?,请抓住部分匹配时的两个特征：,（1）设模式滑动到第k个字符，则T1Tk-1 Si-(k-1)Si-1,4.串的应用KMP模式匹配算法,请抓住部分匹配时的两个特征：,两式联立可得：T1Tk-1Tj-(k-1)Tj-1,（2）则Tj-(k-1)Tj-1 Si-(k-1)Si-1,（1）设模式滑动到第k个字符，则T1Tk-1 Si-(k-1)Si-1,4.串的应用KMP模式匹配算法,T1Tk-1Tj-(k-1)Tj-1说明了什么？（1）k 与 j 具有函数关系，由当前失
13、配位置 j，可以计算出滑动位置 k（即比较的新起点）；（2）滑动位置k 仅与模式串T有关。,从第1位往右经过k-1位,从j-1位往左经过k-1位,kmax k|1kj 且T1Tk-1Tj-(k-1)Tj-1,T1Tk-1Tj-(k-1)Tj-1的物理意义是什么？,模式应该向右滑多远才是最高效率的?,4.串的应用KMP模式匹配算法,next j,0 当j1时/不比较max k|1kj 且T1Tk-1=Tj-(k-1)Tj-1 1 其他情况,令k=next j，则：,nextj函数表征着模式T中最大相同首子串和尾子串（真子串）的长度。可见，模式中相似部分越多，则nextj函数越大，它既表示模式 T
14、 字符之间的相关度越高，模式串向右滑动得越远，与主串进行比较的次数越少，时间复杂度就越低。,4.串的应用KMP模式匹配算法,4.串的应用KMP模式匹配算法,计算nextj的方法：当j=1时，nextj=0；/nextj=0表示根本不进行字符比较当j1时，nextj的值为：模式串的位置从1到j-1构成的串中所出现的首尾相同的子串的最大长度加1。当无首尾相同的子串时nextj的值为1。nextj=1表示从模式串头部开始进行字符比较,j=1时,next j 0；j=2时,next j 1；,j=3时,t1t2，因此，k=1；,j=4时,t1t3，因此，k=2；,j=5时,t1t4，因此，k=2；,以
15、此类推。,4.串的应用KMP模式匹配算法,void GetNext(char t)next1=0;j=1;k=0;while(jt0)if(k=0)|(tj=tk)j+;k+;nextj=k;else k=nextk;,求模式串t的next函数值算法,4.串的应用KMP模式匹配算法,1.在串s和串t中分别设比较的起始下标i和j；2.循环直到s中所剩字符长度小于t的长度或T中所有字符均比较完毕 2.1 如果si=tj，继续比较S和T的下一个字符；否则 2.2 将j向右滑动到nextj位置，即j=nextj；2.3 如果j=0，则将i和j分别加1，准备下一趟比较；3.如果t中所有字符均比较完毕，则
16、返回匹配的起始下标；否则返回0；,4.串的应用KMP模式匹配算法,例：设主串s=abcabcabd，模式串p=abcabd，按KMP算法进行模式匹配，当s0s1s2s3s4=p0p1p2p3p4，且s5p5时，应进行 比较。A、s5和p2 B、s5和p3 C、s1和p0D、s8和p5,4.串的应用KMP模式匹配算法,特殊线性表,栈,队 列,串,栈的定义操作特性ADT定义,队列定义操作特性ADT定义,串的定义基本概念ADT定义,顺序栈,链栈,循环队列,链队列,顺序存储,链接存储,逻辑结构,存储结构,逻辑结构,逻辑结构,存储结构,存储结构,比 较,模式匹配,比较,比较,基本操作的实现时间性能,基本操作的实现时间性能,特殊线性表串,
