北邮算法与数据结构4

《北邮算法与数据结构4》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、数据结构---第四章串1第四章串串是特殊的线性表，数据元素是单个字符。线性表的操作通常以“数据元素”为操作对象；串的操作主要以“子串”为操作对象。4.1串类型的定义4.2串的存储结构和操作的实现4.3串的模式匹配算法4.4串应用示例——文本编辑本章学习要点及习题数据结构---第四章串24.1串类型的定义4.1.1串的概念串（字符串）：是由零个或多个字符组成的有限序列。记作：s=‘a1a2…an’(n0)串长：串中字符的个数n。子串和主串：串中任意个连续的字符组成的子序列称为该串的子串。包含子串的串称为主串。串相等：两个串长度相等，且对应位置的字符都相等。空串和空白串：空串不包含任何字符,表示

2、为；空白串由一个或多个空格组成，如‘’。数据结构---第四章串34.1.2串的常用基本操作(1)用串常量赋值StrAssign(&T,chars)用串变量赋值StrCopy(&T,S)(2)判定空串StrEmpty(S)(3)两串比较StrCompare(S,T)(4)求串长StrLength(S)(5)串清空ClearString(&S)(6)两串连接Concat(&T,S1,S2)(7)求子串SubString(&Sub,S,pos,len)(8)子串定位Index(S,T,pos)(9)子串置换Replace(&S,T,V)(10)插入子串StrInsert(&S,pos,T)(11)

3、删除子串StrDelete(&S,pos,len)(12)串销毁DestroyString(&S)串类型的最小操作子集数据结构---第四章串4[例]设s=‘Iamastudent.’t=‘OK!’p=‘student’q=‘nurse’r=‘good’(1)Concat(newstr,s,t)newstr=‘Iamastudent.OK!’(2)Replace(s,p,q);s=‘Iamanurse.’(3)StrInsert(s,8,r)s=‘Iamagoodnurse.’数据结构---第四章串54.2串的存储结构和操作的实现4.2.1串的顺序存储结构（1）定长顺序存储表示7student0

4、12345678MAXSTRLEN#defineMAXSTRLEN255//予定义最大串长typedefunsignedcharSString[MAXSTRLEN+1];存放串的长度[存储定义]BOOKC语言本身的串表示方式：不便于求串长等操作数据结构---第四章串6[基本操作实现示例]约定：串值长度上溢时，用“截尾法”处理，即“截断”超过予定义长度的部分。intStrCompare(SStringS,SStringT)//S>T,返回值>0；S=T，返回0；S

5、[i]);returnS[0]-T[0]}//StrCompare操作基于“字符序列复制”i数据结构---第四章串7StatusConcat(SString&T,SStringS1,SStringS2)//用T返回串s1和s2联接而成的新串。//若未截断，返回TRUE，否则返回FALSE{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]

6、1[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];uncut=FALSE;}returnuncut;}//Concat数据结构---第四章串8StatusSubString(SString&Sub,SStringS,intpos,intlen)//用Sub返回串S从第pos个字符起长度为len的子串{if((pos<1

7、

8、pos>S[0]

9、

10、len<0

11、

12、len>S[0]-pos+1)returnER

13、ROR;Sub[1..len]=S[pos..pos+len-1];Sub[0]=lenreturnOK;}//SubString01poslenSSub数据结构---第四章串9（2）堆分配存储表示动态分配串值存储空间，避免定长结构的截断现象。typedefstruct{char*ch;//串空间基址，按串长申请intlength;//串长度}HString;[存储定义]数据结构---第四章串10