欢迎来到天天文库
浏览记录
ID:43084377
大小:375.00 KB
页数:28页
时间:2019-09-29
《北邮算法与数据结构4》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库。
1、数据结构---第四章串1第四章串串是特殊的线性表,数据元素是单个字符。线性表的操作通常以“数据元素”为操作对象;串的操作主要以“子串”为操作对象。4.1串类型的定义4.2串的存储结构和操作的实现4.3串的模式匹配算法4.4串应用示例——文本编辑本章学习要点及习题数据结构---第四章串24.1串类型的定义4.1.1串的概念串(字符串):是由零个或多个字符组成的有限序列。记作:s=‘a1a2…an’(n0)串长:串中字符的个数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];存放串的长度[存储定义]BOOK C语言本身的串表示方式:不便于求串长等操作数据结构---第四章串6[基本操作实现示例]约定:串值长度上溢时,用“截尾法”处理,即“截断”超过予定义长度的部分。intStrCompare(SStringS,SStringT)//S>T,返回值>0;S=T,返回0;S5、[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<17、8、pos>S[0]9、10、len<011、12、len>S[0]-pos+1)returnER13、ROR;Sub[1..len]=S[pos..pos+len-1];Sub[0]=lenreturnOK;}//SubString01poslenSSub数据结构---第四章串9(2)堆分配存储表示动态分配串值存储空间,避免定长结构的截断现象。typedefstruct{char*ch;//串空间基址,按串长申请intlength;//串长度}HString;[存储定义]数据结构---第四章串10
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<17、8、pos>S[0]9、10、len<011、12、len>S[0]-pos+1)returnER13、ROR;Sub[1..len]=S[pos..pos+len-1];Sub[0]=lenreturnOK;}//SubString01poslenSSub数据结构---第四章串9(2)堆分配存储表示动态分配串值存储空间,避免定长结构的截断现象。typedefstruct{char*ch;//串空间基址,按串长申请intlength;//串长度}HString;[存储定义]数据结构---第四章串10
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
此文档下载收益归作者所有