VC编程教程 第4章 串

《VC编程教程 第4章 串》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第4章串本章主要介绍下列内容：串的定义、存储结构和基本运算退出[本章学习要求]掌握：串的基本概念和基本运算。掌握：串的顺序存储结构以及定长串的基本运算。了解：串的简单的模式匹配以及KMP模式匹配算法。了解：串的堆存储结构和基于堆结构的基本运算。掌握：串的链式存储结构表示。了解：串在文本编辑中处理方法。4.1串的定义及其基本运算4.2串的定长顺序存储及基本运算4.3串的堆存储结构4.1.1串的定义定义：串(string)是一种在数据元素的组成上具有一定约束条件的线性表，即要求组成线性表的所有数据元素都是字符，所以，人们经常又这样定义串：串

2、是一个有穷字符序列，一般记为:4.1串的定义及其基本运算s=〝a1a2a3…an〞说明:1)其中s是串名，用双引号括起来的字符序列是串的值。2)ai(1<=i<=n)可以是字母、数字或其他字符；n为串中字符的个数，称为串的长度,i是序号。3)一个长度为零的串称为空串，表示为s=“”或Φ。4)空格也是合法字符，空格串是字符,为空格的串。几个术语空串：长度为0的字符串；空格串：由空格字符组成的字符串，长度>1.子串:字符串中任意个连续的字符构成的序列;母串:包含该子串的字符串;两串相等:两个字符串的长度相等且各对应位置上的字符都相同.字符的

3、位置：从1开始子串的位置：该子串第一个字符的位置例如，有下列几个串a，b，c，d，e，f：a=“WelcometoBeijing”b=“Welcome”c=“Bei”d=“welcometo”e=“Welcome”f=“welcome”4.1.2串的基本运算1.求串的长度StrLength(s)；2.串赋值StrAssign(s1,s2);3.两个串的连接StrConcat(s1,s2,s)或StrConcat(s1,s2)4.求某串的子串SubStr(s,i,len)；5.串比较StrCmp(s1,s2)；6.子串定位StrIndex

4、(s,t);7.插入子串StrInsert(s,i,t)；8.删除子串StrDelete(s,i,len)；9.置换StrRep(s,t,r)。4.2串的存储结构1.顺序存储结构串的顺序存储结构与线性表的顺序存储类似，用一组连续的存储单元依次存储串中的字符序列。(1)第一种是事先定义字符串的最大长度，字符串存储在一个定长的存储区中。类型定义如下所示：#defineMAXSIZE256typedefstruct{chardata[MAXSIZE];intcurlen;}SeqString;第一种：abefi0256s.curlencdgh

5、13478s.dataMAXSIZE-1(2)第二种是在串尾存储一个不会在串中出现的特殊字符作为串的终结符，以此表示串的结尾。比如C语言中处理定长串的方法就是这样的，它是用’’来表示串的结束。这种存储方法不能直接得到串的长度，是用判断当前字符是否是’’来确定串是否结束，从而求得串的长度。第二种：#defineMAXSIZE256chars[MAXSIZE];abefi0256cdgh134789MAXSIZE-1(3)设定长串存储空间：chars[MAXSIZE+1];用s[0]存放串的实际长度，串值存放在s[1]~s[MA

6、XSIZE]，字符的序号和存储位置一致，应用更为方便。第三种：#defineMAXSIZE256chars[MAXSIZE+1];abefi0256cdgh1347899MAXSIZE2、定长串的基本运算本小节主要讨论定长串联接、求子串、串比较算法，顺序串的插入和删除等运算基本与顺序表相同，在此不在赘述。设串结束用‘’来标识。（1）求串长intstrLength(chars[]){inti=0;while(s[i]!=’’)i++;return(i);}（2）串联接把两个串s1和s2首尾连接成一个新串s，即：s<=s1+s2。i

7、ntStrConcat1(chars1[],chars2[],chars[]){inti=0,j,len1,len2;len1=StrLength(s1);len2=StrLength(s2);if(len1+len2>MAXSIZE-1)return0;/*s长度不够*/j=0;while(s1[j]!=’’){s[i]=s1[j];i++;j++;}j=0;while(s2[j]!=’’){s[i]=s2[j];i++;j++;}s[i]=’’;return1;}（3）求子串intStrSub(char*t,char*s

8、,inti,intlen)/*用t返回串s中第个i字符开始的长度为len的子串1≤i≤串长*/{intslen;slen=StrLength(s);if(i<1

9、

10、i>slen

11、

12、len<0

13、

14、len>sl