会计学重点:(1)ADT串的设计(shèjì)、实现方法和基本操作；(2)串的简单模式匹配算法，KMP算法。难点:串的模式匹配算法中的KMP算法。4.1串类型的定义4.2串的表示(biǎoshì)和实现4.3串的模式匹配算法4.1串类型(lèixíng)的定义4.1串类型(lèixíng)的定义4.1串类型(lèixíng)的定义ADTString{数据对象(duìxiàng)：数据关系：基本操作：}ADTString基本操作：基本操作：4.2串的表示(biǎoshì)和实现4.2.1定长顺序存储表示(biǎoshì)StatusConcat(SStringS1,SStringS2,SString&T){//用T返回由S1和S2联接而成的新串。若未截断(jiéduàn),则返回TRUE，否则FALSE。……………….returnuncut;}//ConcatStatusConcat(SStringS1,SStringS2,SString&T){//用T返回由S1和S2联接(liánjiē)而成的新串。若未截断,则返回TRUE，否则FALSE。……………….returnuncut;}//ConcatStatusConcat(SStringS1,SStringS2,SString&T){//用T返回由S1和S2联接而成的新串。若未截断(jiéduàn),则返回TRUE，否则FALSE。……………….returnuncut;}//ConcatStatusStrDelete(SSstring&S,intpos,intlen){if(pos<1||pos>S[0]||len<=0)returnerror;if(pos+len-1>=S[0])S[0]=pos-1;else{for(i=pos+len;i<=S[0];i++){S[i-len]=S[i];}S[0]=S[0]-len;}returnOK;}4.2串的表示(biǎoshì)和实现4.2.2堆分配(fēnpèi)存储表示StatusConcat(HString&T,HStringS1,HStringS2){//用T返回由S1和S2联接(liánjiē)而成的新串if(T.ch)free(T.ch);//释放旧空间if(!(T.ch=(char*)malloc((S1.length+S2.length)*sizeof(char))))exit(OVERFLOW);T.ch[0..S1.length-1]=S1.ch[0..S1.length-1];T.length=S1.length+S2.length;T.ch[S1.length…T.length-1]=S2.ch[0...S2.length-1];returnOK;}//ConcatStatusSubString(HString&Sub,HStringS,intpos,intlen){if(pos<1||pos>S.length||len<0||len>S.length-pos+1)returnERROR;if(Sub.ch)free(Sub.ch);//释放旧空间(kōngjiān)if(!len){Sub.ch=NULL;Sub.length=0;}//空子串else{……..}//完整子串returnOK;}//SubStringSub.ch=(char*)malloc(len*sizeof(char));Sub.ch[0..len-1]=S[pos-1..pos+len-2];Sub.length=len;4.2.3串的块链存储(cúnchǔ)表示4.2.3串的块链存储(cúnchǔ)表示#defineCHUNKSIZE80typedefstructChunk{//结点结构charch[CUNKSIZE];structChunk*next;}Chunk;typedefstruct{//串的链表结构Chunk*head,*tail;//串的头和尾指针intcurlen;//串的当前(dāngqián)长度}LString;讨论下面这种情况(qíngkuàng)的时间复杂性，设S串长为n，T串长为m。S：abcdefghjkllkcdeT：jkl讨论下面这种情况(qíngkuàng)的时间复杂性，设S串长为n，T串长为m。S：0000000000000000001T：0000001主串S：子串T：主串S：子串T：主串S：子串T：主串S：子串T：主串S：子串T：假如j滑动到k,如果比较有意义:必须(bìxū)满足:①“t1