数据结构课件(部分6).ppt

1、1234基本操作的功能说明基本操作的功能说明567上述上述13种基本操作中种基本操作中,下面下面5种操作构成最小操作子集种操作构成最小操作子集: 串赋值串赋值 StrAssign; 串比较串比较 StrCompare; 求串长求串长 StrLength; 串联结串联结 Concat; 求子串求子串 Substring;其它操作可以用其实现其它操作可以用其实现例如定位函数例如定位函数Index(S,T,pos)的算法如右的算法如右:int Index(String S, String T, int pos) int i,n,m; String sub; if(pos 0) n = StrLeng

2、th(S); m = StrLength(T); i = pos; while(i=n-m+1) SubString(sub,S,i,m); if(StrCompare(sub,T)!=0)+i; else return i; /while / if return 0; / Index84.2 4.2 串的表示和实现串的表示和实现#define MAXSTRLEN 255 / 串的长度最大为串的长度最大为255typedef unsigned char SStringMAXSTRLEN+1; / 0号单元存放串的长度号单元存放串的长度, 其最大值刚好是其最大值刚好是255.当超出当超出2552

3、55个字符时个字符时, ,串的多余内容被舍去串的多余内容被舍去, ,叫做叫做“截断截断”以下用串联结和求子串为例介绍这种存储以下用串联结和求子串为例介绍这种存储9S1S2T0 maxstrlen0 maxstrlenS10+S20 MAXSTRLEN 时截断部分10status Concat(SString &T, SString S1, SString S2)/用用T T返回由返回由串串S1S1和和S2S2联结而成的新串。若未被截断联结而成的新串。若未被截断, ,则返回则返回1;1;否则返回否则返回0 0。 if ( S10+S20 = MAXSTRLEN) /未被截断未被截断 T1.S10

4、 = S11.S10; TS10+1. S10+S20 = S21.S20; T0 = S10+S20; uncut = 1; elseif (S10 MAXSTRLEN) / 截断截断 T1.S10 = S11.S10; TS10+1. MAXSTRLEN = S21. MAXSTRLEN-S10; T0 = MAXSTRLEN; uncut = 0; else / 截断截断(仅取仅取S1) T0. MAXSTRLEN = S10. MAXSTRLEN; uncut = 0; / if return uncut; / Concat112.2.求子串求子串SubString(&Sub,S,po

5、s,len)的算法的算法status SubString(SString &Sub, SString S, int pos, int len)/用用SubSub返回串返回串S S的第的第pospos个字符起长度为个字符起长度为lenlen的子串的子串。 其中其中,1=pos=StrLength(S) 且且 0=len=StrLength(S) -pos + 1 。 if ( pos s0 | len s0 - pos +1 ) return ERROR; Sub1.len = Spos.pos+len-1; Sub0 = len; return OK; / SubStringSSub1 pos

6、len12 也是用一组连续的存储单元存储串值的字符序列也是用一组连续的存储单元存储串值的字符序列. .但存储空间是在程序执行过程中动态分配得到的但存储空间是在程序执行过程中动态分配得到的. . 在在C C语言中语言中, ,用字符用字符“0”0”表示串的终结表示串的终结,“0”,“0”不计入串不计入串长长. .typedef struct char *ch; / 若是非空串若是非空串,则按实际长度分配则按实际长度分配,否则为否则为NULL; int length; / 串长度串长度 HString; 以下用串插入操作以下用串插入操作 StrInsert(&S,pos,TStrInsert(&S,

7、pos,T) )为例介绍这种存储为例介绍这种存储13串插入串插入StrInsert(&S,pos,T)的算法的算法1415161718194.2.3 4.2.3 串的块链存储结构串的块链存储结构20 typedef structtypedef struct / / 串的链表结构串的链表结构 Chunk Chunk * *head, head, * *tail; / tail; / 串的串的头和尾指针头和尾指针 int curlenint curlen; / ; / 串的串的当前长度当前长度 LString LString; ;2122例：主串例：主串S=ababcabcacbab，模式，模式T

8、=abcaca b a b c a b c a c b a bi=3，j=3失败；失败；i回溯到回溯到2，j回溯到回溯到1ijijij第第 1趟趟a b c a c 23例：主串例：主串S=ababcabcacbab，模式，模式T=abcaca b a b c a b c a c b a bi=3，j=3失败；失败；i回溯到回溯到2，j回溯到回溯到1ji第第 1趟趟a b c a c 24例：主串例：主串S=ababcabcacbab，模式，模式T=abcaca b a b c a b c a c b a bi=2，j=1失败失败i回溯到回溯到3，j回溯到回溯到1第第 2趟趟ija b c a

9、 c 25例：主串例：主串S=ababcabcacbab，模式，模式T=abcaca b a b c a b c a c b a bi=2，j=1失败失败i回溯到回溯到3，j回溯到回溯到1第第 2趟趟ija b c a c 26例：主串例：主串S=ababcabcacbab，模式，模式T=abcaca b a b c a b c a c b a ba b c a c i=7，j=5失败失败i回溯到回溯到4，j回溯到回溯到1第第 3趟趟ijijijijij27例：主串例：主串S=ababcabcacbab，模式，模式T=abcaca b a b c a b c a c b a ba b c a

10、c i=7，j=5失败失败i回溯到回溯到4，j回溯到回溯到1第第 3趟趟ij28例：主串例：主串S=ababcabcacbab，模式，模式T=abcaca b a b c a b c a c b a ba b c a c i=4，j=1失败失败i回溯到回溯到5，j回溯到回溯到1第第 4趟趟ij29例：主串例：主串S=ababcabcacbab，模式，模式T=abcaca b a b c a b c a c b a ba b c a c i=4，j=1失败失败i回溯到回溯到5，j回溯到回溯到1第第 4趟趟ij30例：主串例：主串S=ababcabcacbab，模式，模式T=abcaca b a

11、b c a b c a c b a ba b c a c i=5，j=1失败失败i回溯到回溯到6，j回溯到回溯到1第第 5趟趟ij31例：主串例：主串S=ababcabcacbab，模式，模式T=abcaca b a b c a b c a c b a ba b c a c i=5，j=1失败失败i回溯到回溯到6，j回溯到回溯到1第第 5趟趟ij32例：主串例：主串S=ababcabcacbab，模式，模式T=abcaca b a b c a b c a c b a ba b c a c i=11，j=6，T中全部中全部字符都比较完毕，字符都比较完毕，匹配成功。匹配成功。第第 6趟趟ijiji

12、jijij3334BF算法算法的复杂度分析的复杂度分析设设n = StrLength(S);m = StrLength(Tn = StrLength(S);m = StrLength(T););设匹配成功发生在设匹配成功发生在s si i处，则字符比较次数在前面处，则字符比较次数在前面i-1i-1趟匹配中共趟匹配中共比较了比较了i-1i-1次，第次，第i i趟成功的匹配共比较了趟成功的匹配共比较了m m次，所以总共比较了次，所以总共比较了i-1+mi-1+m次，所有匹配成功的可能共有次，所有匹配成功的可能共有n-m+1n-m+1种，设从种，设从s si i开始与开始与t t串串匹配成功的概率为

13、匹配成功的概率为p pi i，在等概率情况下，在等概率情况下p pi i=1/(n-m+1)=1/(n-m+1)，因此最好，因此最好情况下平均比较的次数是：情况下平均比较的次数是：2)()1()1(111111mnmimipmnimnmnii35最坏情况最坏情况, ,T = “00000001”T = “00000001”S = S = “00000000000000000000000000000000000000000000000001”“00000000000000000000000000000000000000000000000001”设匹配成功发生在设匹配成功发生在s si i处，则在前面处，则在前面i-1i-1趟匹配中共比较了趟匹配中共比较了(i-1)(i-1)* *m m次，第次，第i i趟成功的匹配共比较了趟成功的匹配共比较了m m次，所以总共比较了次，所以总共比较了i i* *m m次，因次，因此最坏情况下平均比较的次数是：此最坏情况下平均比较的次数是：即最坏情况下的时间复杂度是即最坏情况下的时间复杂度是O(nO(n* *m)m)。而而0101串是计算机应用中最串是计算机应用中最普遍的一种，所以有必要改进该模式匹配算法。普遍的一种，所以有必要改进该模式匹配算法。 2) 2()()(111111mnmmimipmnimnmnii