《数据结构教程》第4章串

《《数据结构教程》第4章串》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第4章串4.1串的基本概念4.2串的存储结构本章小结4.3串的模式匹配串(或字符串),是由零个或多个字符组成的有穷序列。含零个字符的串称为空串,用Ф表示。串中所含字符的个数称为该串的长度(或串长)。通常将一个串表示成"a1a2…an"的形式。其中,最外边的双引号本身不是串的内容,它们是串的标志,以便将串与标识符(如变量名等)加以区别。每个ai(1≤i≤n)代表一个字符。4.1串的基本概念当且仅当两个串的长度相等并且各个对应位置上的字符都相同时,这两个串才是相等的。一个串中任意个连续字符组成的子序列(含空串,但不含串本身)

2、称为该串的子串。例如,“a”、“ab”、“abc”和“abcd”等都是“abcde”的子串（平凡子串不包括自身）。例4.1问题:“abcde”有多少个平凡子串?解:空串数:1含1个字符的子串数:5含2个字符的子串数:4含3个字符的子串数:3含4个字符的子串数:2共有1+2+3+4+5=15个子串。串的基本运算如下:(1)StrAssign(&s,chars):将一个字符串常量赋给串s,即生成一个其值等于chars的串s。(2)StrCopy(&s,t):串复制:将串t赋给串s。(3)StrEqual(s,t):判串相等:

3、若两个串s与t相等则返回真；否则返回假。(4)StrLength(s):求串长:返回串s中字符个数。(5)Concat(s,t):串连接:返回由两个串s和t连接在一起形成的新串。(6)SubStr(s,i,j):求子串:返回串s中从第i(1≤i≤StrLength(s))个字符开始的、由连续j个字符组成的子串。(7)InsStr(s1,i,s2):将串s2插入到串s1的第i(1≤i≤StrLength(s)+1)个字符中,即将s2的第一个字符作为s1的第i个字符,并返回产生的新串。(8)DelStr(s,i,j):从串s

4、中删去从第i(1≤i≤StrLength(s))个字符开始的长度为j的子串,并返回产生的新串。(9)RepStr(s,i,j,t):替换:在串s中,将第i(1≤i≤StrLength(s))个字符开始的j个字符构成的子串用串t替换,并返回产生的新串。(10)DispStr(s):串输出:输出串s的所有元素值。4.2.1串的顺序存储及其基本操作实现串是一种特殊的线性表,在非紧缩格式中,它的每个结点仅由一个字符组成,因此存储串的方法也就是存储线性表的一般方法。存储串最常用的方式是采用顺序存储,即把串的字符顺序地存储在内存一片

5、相邻的空间,这称为顺序串。4.2串的存储结构顺序存储采用一般顺序表的存储结构,其类型定义如下:#defineMaxSize100typedefstruct{chardata[MaxSize];intlen;}strtype;其中,ch域用来存储字符串,len域用来存储字符串的当前长度,MaxSize常量表示允许所存储字符串的最大长度。在C语言中每个字符串以''标志结束。顺序串中实现串的基本运算如下:(1)StrAssign(str,cstr)将一个字符串常量赋给串str,即生成一个其值等于cstr的串s。voidSt

6、rAssign(SqString&str,charcstr[]){inti;for(i=0;cstr[i]!='';i++)str.data[i]=cstr[i];str.len=i;}(2)StrCopy(s,t)将串t复制给串s。voidStrCopy(SqString&s,SqStringt)/*引用型参数*/{inti;for(i=0;i

7、则返回假(0)。intStrEqual(SqStrings,SqStringt){intsame=1,i;if(s.len!=t.len)same=0;/*长度不相等时返回0*/elsefor(i=0;i

8、由两个串s和t连接在一起形成的新串。SqStringConcat(SqStrings,SqStringt){SqStringstr;inti;str.len=s.len+t.len;for(i=0;istr*/str.data[i]=s.data[i]