资源描述：
《串类型的定义串的表示和实现串的模式匹配算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、4.1串类型的定义4.2串的表示和实现4.3串的模式匹配算法第4章串重点:(1)ADT串的设计、实现方法和基本操作；(2)串的简单模式匹配算法，KMP算法。难点:串的模式匹配算法中的KMP算法。本章重点难点4.1串类型的定义4.2串的表示和实现4.3串的模式匹配算法第4章串4.1串类型的定义串是由零个或多个字符组成的有限序列。记为：s=”a1a2…an”(n≥0)其中，s是串的名，用双引号括起来的字符序列是串的值。(1)串的长度:串中字符的数目n。(2)空串(Nullstring):长度为零的串。
2、(3)子串:串中任意个连续的字符组成的子序列。串的有关术语串(String)的定义4.1串类型的定义(4)主串包含子串的串相应地称为主串。(5)串相等只有当两个串的长度相等，并且各个对应位置的字符都相等，称两串相等。(6)空格串(空白串)(blankstring)由一个或多个空格组成的串。要和“空串”区别，空格串有长度就是空格的个数。串的有关术语4.1串类型的定义(1)串数据对象约束为字符集。(2)基本操作的对象不同，线性表以“单个元素”为操作对象；串以“串的整体”为操作对象，操作的一般都是子串。
3、串与一般线性表的区别ADTString{数据对象：数据关系：基本操作：}ADTString串的ADT定义见下页D＝{ai
4、ai∈CharacterSet,i=1,2,...,n,n≥0}R1＝{
5、ai-1,ai∈D,i=2,...,n}4.1串类型的定义基本操作：StrAssign(&T,chars)//根据串常量chars生成串TStrCopy(&T,S)//把串S中内容拷贝到T串DestroyString(&S)//销毁串SStrEmpty(S)//判断串是否空StrComp
6、are(S,T)//比较串S和TStrLength(S)//求串长Concat(&T,S1,S2)//连接串4.1串类型的定义基本操作：SubString(&Sub,S,pos,len)//求子串Index(S,T,pos)//子串定位ClearString(&S)//清空串SStrDelete(&S,pos,len)//删除子串Replace(&S,T,V)//把串S中符合T的子串替换StrInsert(&S,pos,T)//插入子串4.1串类型的定义4.2串的表示和实现4.2.1、定长顺序存储
7、表示4.2.2、堆分配存储表示4.2.3、串的块链存储表示4.2.1定长顺序存储表示#defineMAXSTRLEN255//用户可在255以内定义最大串长typedefunsignedcharSstring[MAXSTRLEN+1];//0号单元存放串的长度SstringS;串的顺序存储C语言实现StatusConcat(SStringS1,SStringS2,SString&T){//用T返回由S1和S2联接而成的新串。若未截断,则返回TRUE，否则FALSE。……………….returnunc
8、ut;}//ConcatT[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;}if(S1[0]+S2[0]<=MAXSTRLEN){//未截断4.2.1定长顺序存储表示串的连接算法StatusConcat(SStringS1,SStringS2,SString&T){//用T返回由S1和S2联接而成的新串。若未截断,则返回TRUE，否则FALSE。……………….retur
9、nuncut;}//Concatelseif(S1[0]10、.returnuncut;}//Concatelse{//截断(仅取S1)T[0..MAXSTRLEN]=S1[0..MAXSTRLEN];//T[0]==S1[0]==MAXSTRLENuncut=FALSE;}4.2.1定长顺序存储表示串的连接算法StatusStrDelete(SSstring&S,intpos,intlen){if(pos<1
11、
12、pos>S[0]
13、
14、len<=0)returnerror;if(pos+len-1>=S[0])S[0]=pos-1;else{f
