资源描述：
《串的定义及基本运算》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、4.1串的定义及基本运算4.2串的存储结构4.3模式匹配算法的实现4.4小结与习题第四章串1串（字符串）是一种特殊的线性表，它的数据元素仅由一个字符组成，计算机非数值处理的对象经常是字符串数据，在事物处理程序中，一般也是作为字符串处理的。4.1串的定义及基本运算一、串和基本概念串(String)是零个或多个字符组成的有限序列。一般记作：S=“a1a2a3…an”其中S是串名，双引号括起来的字符序列是串值；ai(1≦i≦n)可以是字母、数字或其它字符；串中所包含的字符个数称为该串的长度。长度为零的串称为空串(EmptyString)，它不包含任何字符。2通常将仅由一个或多个空格组成的串称为
2、空白串(BlankString)。注意：空串和空白串的不同。二、串的术语1.主串和子串：串中任意个连续字符组成的子序列称为该串的子串，包含子串的串相应地称为主串。通常将子串在主串中首次出现时的该子串的首字符对应的主串中的序号，定义为子串在主串中的序号（或位置）。例如，设A和B分别为A=“Thisisastring”B=“is”则B是A的子串，A为主串。32.子串的位置：子串的第一个字符在主串中的序号称为子串的位置。B在A中出现了两次，首次出现所对应的主串位置是3。因此，称B在A中的序号（或位置）为3。特别地，空串是任意串的子串，任意串是其自身的子串。3.串相等：称两个串是相等的，是指两个
3、串的长度相等且对应字符都相等。4三、串的基本运算1.求串长StrLength(s)：操作条件：串s存在；操作结果：求出串s的长度。2.串赋值StrAssign(s1,s2)操作条件：s1是一个串变量，s2或者是一个串常量，或者是一个串变量（通常s2是一个串常量时称为串赋值，是一个串变量称为串拷贝）。操作结果：将s2的串值赋值给s1，s1原来的值被覆盖掉。53.连接操作：StrConcat(s1,s2,s)或StrConcat(s1,s2)操作条件：串s1,s2存在。操作结果：两个串的联接就是将一个串的串值紧接着放在另一个串的后面，连接成一个串。前者是产生新串s，s1和s2不改变;后者是在
4、s1的后面联接s2的串值，s1改变，s2不改变。4.求子串SubStr(s,i,len)：操作条件：串s存在，1≤i≤StrLength(s)，0≤len≤StrLength(s)-i+1。操作结果：返回从串s的第i个字符开始的长度为len的子串。len=0得到的是空串。65.串比较StrCmp(s1,s2)操作条件：串s1,s2存在。操作结果：若s1==s2，操作返回值为0；若s1s2,返回值>0。6.子串定位StrIndex(s,t)：找子串t在主串s中首次出现的位置操作条件：串s,t存在。操作结果：若t∈s，则操作返回t在s中首次出现的位置，否则返回值为
5、-1。78.串删除StrDelete(s,i,len)操作条件：串s存在，1≤i≤StrLength(s)，0≤len≤StrLength(s)-i+1。操作结果：删除串s中从第i个字符开始的长度为len的子串，s的串值改变。7.插入StrInsert(s,i,t)操作条件：串s,t存在，1≤i≤StrLength(s)+1。操作结果：将串t插入到串s的第i个字符位置上。9.串替换StrRep(s,t,r)操作条件：串s,t,r存在，t不为空。操作结果：用串r替换串s中出现的所有与串t相等的不重叠的子串，s的串值改变。84.2串的存储结构4.2.1串的定长顺序存储类似于顺序表，用一组地址
6、连续的存储单元存储串值中的字符序列，所谓定长是指按预定义的大小，为每一个串变量分配一个固定长度的存储区，如：1.类似顺序表，用一个指针来指向最后一个字符，这样表示的串描述如下：typedefstruct{chardata[MAXSIZE];intcurlen;}SeqString;9nedutSMAXSIZE-1…543210s.datas.curlen2.在串尾存储一个不会在串中出现的特殊字符作为串的终结符，以此表示串的结尾。比如C语言中处理定长串的方法就是这样的，它是用＇ ＇来表示串的结束。3.设定长串存储空间：chars[MAXSIZE+1];用s[0]存放串的实际长度，串值存放
7、在s[1]~s[MAXSIZE]，字符的序号和存储位置一致，应用更为方便。104.2.2定长顺序串的基本运算1.串联接：把两个串s1和s2首尾连接成一个新串s。intStrConcat1(s1,s2,s){inti=0,j,len1,len2;len1=StrLength(s1);len2=StrLength(s2)if(len1+len2>MAXSIZE-1)return0;j=0;while(s1[j]!=’ ’){s[i]=
