数据结构及应用算法教程（修订版） 第5章 串和数组.ppt

《数据结构及应用算法教程（修订版） 第5章 串和数组.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、主要内容5.1串的定义和操作5.2串的表示和实现5.3正文模式匹配5.4正文编辑----串操作应用举例5.5数组5.6矩阵的压缩存储5.1串的定义和操作1.基本概念从串的定义找出串与线性表的相似与区别?串的表示方法?子串、主串的概念串长度、子串在主串中的位置，位置的取值范围？什么叫串相等？空格串与空串的区别？1）串（string或字符串）的定义：由零个或多个字符组成的有限序列。一般记为：s=“a0a1a2...an-1”(n≥0，下标从0开始)，其中s是串的名，用双引号括起来的字符序列是串的值。2）串的长度：串中字符的数目n（

2、n≥0）。3）空串（nullstring）：零个字符的串，它的长度为零。4）空格串：由一个或多个空格组成的串,与空串不同。用Φ表示空字符。5）子串：串中任意个连续的字符组成的子序列。6）主串：包含子串的串相应地称为主串。7）字符在串中的位置：字符在序列中序号。8）子串在主串中的位置：子串的第0个字符在主串中的位置。例如：a="BEI",b="JING",c="BEIJING",d="BEIJING"//串长分别为3,4,7,8,且a,b都是c,d的子串。9）两串相等：两个串对应位置的字符相等且长度相等。10）两个串的比较：从第

3、一个字符开始，每个字符按照ASCII比较，整体按照英语字典的顺序（前小，后大）。2.基本操作1）串赋值：StrAssign(&T,chars)初始条件：chars是字符串常量操作结果：把chars赋为T的值2）串复制：StrCopy(&T,S)初始条件：串S存在操作结果：由串S复制得串T3）判断串是否是空串：StrEmpty(S)初始条件：串S存在操作结果：若S为空串，则返回TRUE，否则返回FALSE4）销毁串：DestroyString(&S)初始条件：串S存在操作结果：串S被销毁5）字符串比较：StrCompare(S,

4、T)初始条件：串S和T存在操作结果：若ST，则返回值0；若ST，则返回值0；若ST，则返回值0。例如：StrCompare(“data”,“state”)StrCompare(“cat”,“case”)6）串长度：StrLength(S)初始条件：串S存在操作结果：返回S的元素个数，称为串的长度。7）串连接：Concat(&T,S1,S2)初始条件：串S1和S2存在。操作结果：用T返回由S1和S2连接而成的新串。8）求子串：SubString(&Sub,S,pos,len)初始条件：串S存在，0≤pos

5、Length(S)且0≤len≤StrLength(S)-pos。操作结果：用Sub返回串S的第pos个字符起长度为len的子串例如：SubString(sub,commander,3,3)求得sub=?SubString(sub,commander,0,9)求得sub=?SubString(sub,commander,8,1)求得sub=?SubString(sub,student,5,0)=长度为0的子串为“合法”串9）求子串位置：Index(S,T,pos)初始条件：串S和T存在，

6、T是非空串，0≤pos

7、，则经置换后得到S=?11）插入子串：StrInsert(&S,pos,T)初始条件：串S和T存在，0≤pos≤StrLength(S)。操作结果：在串S的第pos个字符之前插入串T。例如：S=chater，T=rac，则执行StrInsert(S,3,T)之后得到S=?12）删除子串：StrDelete(&S,pos,len)初始条件：串S存在，0≤pos≤StrLength(S)-len。操作结果：从串S中删除第pos个字符起长度为len的子串。13）清空串：ClearString(&S)初始条件：串S存

8、在。操作结果：将S清为空串。串赋值StrAssign、串比较StrCompare、求串长StrLength、串连接Concat以及求子串SubString等五种操作构成串类型的最小操作子集（不可由其它操作构成），其他函数可以由最小操作子集中的函数构成。C语言中的串函数gets