CH4串市公开课一等奖省赛课获奖课件

CH4串4.1串类型定义4.2串表示和实现4.3串模式匹配算法CH4串第1页教学目标熟悉串相关概念，串和线性表关系。掌握串各种存放结构，比较它们优、缺点，从而学会在何时选取何种存放结构为宜。熟练掌握串七种基本运算，并能利用这些基本运算实现串其它各种运算。教学难点串运算实现，尤其是次序串上子串定位运算（又称串模式匹配或串匹配）。CH4串第2页4.1串类型定义一、串基本概念串(String)定义

s＝’a1a2…an’其中：s为串名字，串值ai(1≤i≤n)能够是字母、数字或其它字符。串长度n。空串和空白串：长度为零串称为空串(EmptyString)，它不包含任何字符。空格（白）串:仅由一个或多个空格组成串称为空白串(BlankString)CH4串第3页子串和主串eg:

A＝’Thisisastring’B＝’is’尤其地：空串是任意串子串，任意串是其本身子串。注意:串值必须用一对单引号括起来，但单引号本身不属于串串相等字符串与普通线性表区分：串数据元素约束为字符集；串基本操作通常针对串整体或串一个部分进行。CH4串第4页二、串抽象数据类型定义ADTString{数据对象：D＝{ai|ai∈CharacterSet,i＝1,2,…,n;n≥0}数据关系：S＝{<ai-1,ai>|ai-1，ai∈D,i＝2,…,n}基本操作：StrAssign(&T,chars)StrLength(S)SubString(&Sub,S,pos,len)StrCopy(&T,S) Index(S,T,pos)StrEmpty(S) Replace(&S,T,V)StrCompare(S,T) StrInsert(&S,pos,T)Concat(&T,S1,S2) StrDelete(&S,pos,len)}ADTStringCH4串第5页4.2串表示和实现4.2.1定长次序存放表示定长次序存放表示,也称为静态存放分配次序表。它是用一组连续存放单元来存放串中字符序列。CH4串第6页串结束标志设置普通可使用一个不会出现在串中特殊字符在串值尾部来表示串结束。比如，C语言中以字符‘\0’表示串值终止。缺点：串长隐含，不便于计算直接使用定长字符数组来定义，数组上界预先给出#defineMAXSTRLEN255typedefcharSString[MAXSTRLEN+1];SStrings;//s是一个可容纳255个字符次序串。//0号单元存放串长度CH4串第7页 算法4.2（串连接算法）StatusConcat(SString&T,SStringS1,SStringS2){if(S1[0]+S2[0]<=MAXSTRLEN){//未截断T[1…S1[0]]=S1[1…S1[0]];T[S1[0]+1…S1[0]+S2[0]]=S2[1…S2[0]];T[0]=S1[0]+S2[0];uncut=TRUE;}elseif(S1[0]<MAXSTRLEN){//截断，取S2部分T[1…S1[0]]=S1[1…S1[0]];T[S1[0]+1…MAXSTRLEN]=S2[1…MAXSTRLEN-S1[0]];T[0]=MAXSTRLEN;uncut=FALSE;} else{ T[0..MAXSTRLEN]=S1[0…MAXSTRLEN];//S1[0]=T[0]==MAXSTRLENuncut=FALSE;}//截断，只取S1returnOK;}CH4串第8页Concat(&T,S1,S2)算法示意图S1S2T0maxstrlen0maxstrlenS1[0]+S2[0]<=MAXSTRLEN时S1S2T0maxstrlen0maxstrlenS1[0]+S2[0]>MAXSTRLEN时截断部分S1S2T0maxstrlenS1[0]==MAXSTRLEN时CH4串第9页算法4.3（取子串）StatusSubString(SString&Sub,SStringS,intpos,intlen){if(pos<1||pos>S[0]||len<0||len>S[0]-pos+1)returnERROR;Sub[1…len]=S[pos…pos+len-1]Sub[0]=len;returnOK;}//SubStringCH4串第10页小结：1.串定长次序存放结构又称为串静态存放结构，即用一段连续存放单元来存放串字符序列。其基本操作为“字符序列复制” 2.串存放结构必须预先定义允许存放串最大字符个数，轻易造成系统空间浪费或运行犯错。3.串一些操作（如：串连接、串替换等）受到限制(如超长需截尾处理）。CH4串第11页4.2.2堆分配存放表示存放特点也是用一组连续存放单元存放串值字符序列.但存放空间是在程序执行过程中动态分配得到存放表示（类似于次序表存放）

typedefstruct{char*ch;intlength;}HString;

CH4串第12页StatusConcat(HString&T,HStringS1,HStringS2){//用T返回由S1和S2联接而成新串

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;}//ConcatCH4串第13页

StatusSubString(HString&Sub,HStringS,

intpos,intlen){//用Sub返回串S第pos个字符起长度为len子串

if(pos<1||pos>S.length

||len<0||len>S.length-pos+1)

returnERROR;

if(Sub.ch)free(Sub.ch);//释放旧空间

if

(!len)

{

Sub.ch=NULL;Sub.length=0;

}//空子串

else{}//

完整子串

return

OK;}//SubString……CH4串第14页

Sub.ch=(char*)malloc(len*sizeof(char));Sub.ch[0..len-1]=S[pos-1..pos+len-2];Sub.length=len;CH4串第15页4.2.3串链式存放结构次序串上插入和删除操作不方便，需要移动大量字符。所以，我们可用单链表方式来存放串值，串这种链式存放结构简称为链串。

typedefstructnode{chardata;structnode*next;}*LString;

特点：一个链串由头指针唯一确定。这种结构便于进行插入和删除运算，但存放空间利用率太低。CH4串第16页串块链结构为了提升存放密度，可使每个结点存放多个字符。通常将结点数据域存放字符个数定义为结点大小，显然，当结点大小大于1时，串长度不一定恰好是“结点大小”整数倍，所以要用特殊字符来填充最终一个结点，以表示串终止。CH4串第17页

#defineCHUNKSIZE80

//可由用户定义块大小

typedefstructChunk{

//

结点结构

charch[CUNKSIZE];

structChunk*next;

}Chunk;

typedefstruct{//串链表结构

Chunk*head,*tail;//串头和尾指针

intcurlen;//串当前长度

}LString;CH4串第18页这是串一个主要操作，很多软件，若有“编辑”菜单项话，则其中必有“查找”子菜单项。4.3 串模式匹配算法CH4串第19页初始条件：串S和T存在，T是非空串，

1≤pos≤StrLength(S)。操作结果：若主串S中存在和串T值相同子串返回它在主串S中第pos个字符之后第一次出

现位置；不然函数值为0

首先，回想一下串匹配(查找)定义:INDEX(S,T,pos)CH4串第20页1趟ababcabcacbababc3趟ababcabcacbababcac2趟ababcabcacbabaCH4串第21页6趟ababcabcacbababcac4趟ababcabcacbaba5趟ababcabcacbab

aCH4串第22页下面以定长次序串类型作为存放结构，给出详细串匹配算法。intIndex(SStringS,SStringT,intpos){i=pos;j=1;while(i<=S[0]&&j<=T[0])if(s[i]==T[j]){++i;++j;}else{i=i-j+2;j=1;}if(j>T[0])returni-T[0];elsereturn0;}显然，该算法在最坏情况下时间复杂度为O((n-m)*m)。CH4串第23页小结BF（Brute-Force）算法特点：简单，易于了解，效率较高；算法时间复杂度O((n-m)*m)。(其中n,m分别为主串和模式串长度）

实际运行中，时间近似于O（n+m)。注意：当碰到一次si≠tj,主串要回退到i-j+2位置，而模式串要回到第一个位置（即j=1位置)；但当一次比较出现si≠tj时，则应该有：

"si-j+1si-j+2……si-1"="t1t2……tj-2tj-1"改进：每当一趟匹配过程出现si≠tj时，主串指示器i不用回溯，而是利用已经得到“部分匹配”结果，将模式串向右“滑动”尽可能远一段距离后，继续进行比较。CH4串第24页4.3.2模式匹配改进算法（KMP算法）一、分析与示例1趟ababcabcacbababc2趟ababcabcacbababcac3趟ababcabcacbababcacCH4串第25页二、讨论普通情况设:主串S="s1s2…si…sn"，

模式串T

="p1p2…pj…pm"问：当某趟比较发生“失配”（即si≠pj）时，模式串应该向“右”滑动可行距离为多长？(不需要回溯i指针）CH4串第26页解：设某趟匹配发生si≠pj时，

si应该与pk（k＜j）继续比较。依据："p1p2…pk-1"＝"si-k+1si-k+2…si-1"

"pj-k+1pj-k+2…pj-1"＝"si-k+1si-k+2…si-1"能够推出：“p1p2…pk-1”＝“pj-k+1pj-k+2…pj-1”示意图以下：主串Sikj模式串TCH4串第27页令next(j)＝knext(j)＝0当j=1Max{k|1＜k＜j且"p1p2…pk-1"＝"pj-k+1pj-k+2…pj-1"}

当此集合非空1其它情况j12345Pjabcacnext(j)01112例1：计算以下模式串next函数值。j12345678Pjabaabcacnext(j)01122312例2：计算以下模式串next函数值。CH4串第28页KMP算法（算法4.6）intIndex_KMP(SStringS,SStringT,intpos){i=pos;j=1;while(i<=S[0]&&j<=T[0]){if(j=0||S[i]==T[j]){++i,;++j;}elsej=next[j];}if(j>T[0])returni-T[0];elsereturn0;}//Index_KMPCH4串第29页三、模式串next函数值求解由定义知：next[1]=0，

设next[j]=k,表明"p1p2…pk-1"="pj-k+1pj-k+2…pj-1"

①（其中1＜k＜j,且不存在k’(k’＞k)满足上式）问：next[j+1]=k’=?

解：情况1：若pK=

Pj,即"p1p2…pk-1pk"="pj-k+1pj-k+2…pj-1pj" ②

则next[j+1]=next[j]+1=k+1；

情况2：若pK≠Pj,即"p1p2…pk-1pk“≠"pj-k+1pj-k+2…pj-1pj", 但"p1p2…pk-1“="pj-k+1pj-k+2…pj-1",

则应将模式向右滑动至模式中next[k]=k’个字符比较，重复 上述过程直至Pj和模式中某个字符匹配 成功或不存在任何 k’(1<k’<j)满足②，则令next[j+1]=1。CH4串第30页算法4.7voidget_next(SStringT,int&next[]){i=1;next[1]=0;j=0;while(i<T[0]){if(j==0||T[i]==T[j]){++i;++j;nex