数据结构与算法：Python语言描述-字符串.ppt

《数据结构与算法：Python语言描述-字符串.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、3，字符串字符串的相关概念Python字符串（回顾）字符串匹配和算法进一步的模式匹配问题正则表达式Python的正则表达式应用举例字符串讨论字符串，首先要有一个确定的字符集“字符”是一个抽象概念，字符集是有穷的一组字符构成的集合人们经常考虑在计算机里使用的标准字符集，实际上，完全可以拿任意数据元素的集合作为字符集字符串（简称串）是特殊的线性表，表中元素取自选定的字符集其不同于一般表的特点是支持一组以串为对象的操作长度：串中字符的个数称为串的长度长度为0的串称为空串在任意一个字符集里，只有唯一的一

2、个空串与一般的表类似：字符串里的字符顺序排列，串里的每个字符有其确定位置我们用0开始的自然数表示位置字符串串相等：串的相等基于字符集里的字符定义s1和s2相等，如果其长度相等，而且对应位置的各对字符分别相同假定字符集中的字符有一个全序，串的字典序定义如下：对于串定义s1

3、串显然，s的长度等于s1和s2的长度之和在Python里拼接运算用+表示字符串两个串之间还有一个重要的关系是“子串关系”称s1为s2的一个子串，如果存在两个串s和s'使下式成立s2=s+s1+s'（借用Python的写法）子串也是串。直观看，子串是原串中连续的一段字符序列形成的串。显然，一个串可以是或者不是另一个串的子串如果s1是s2的子串，也说s1在s2里出现，称s2里与s1相同的字符段的第一个字符的位置为s1在s2里出现的位置s2里可能出现多个与s1相同的段，这时说s1在s2里多次出现注意：

4、s1在s2中的多个出现可能不独立，相互重叠。例如babb在babbabbbbabb里有三个出现，前两个有重叠根据定义，很显然，空串是任何字符串的子串；另一方面，任何字符串s也都是该串本身的子串字符串两种特殊子串：如果存在s'使s2=s1+s'，称s1为s2的一个前缀如果存在s使得s2=s+s1，称s1为s2的一个后缀直观说，一个串的前缀就是该串开头的一段字符构成的子串，后缀就是该串最后的一段字符构成的子串显然，空串和s既是s的前缀，也是s的后缀其他有用的串运算：串s的n次幂sn是连续n个s拼接而

5、成的串（在Python语言里用s*n表示）串替换，指将一个串里的一些（互不重叠的）子串代换为另一些串得到的结果（由于可能重叠，需规定代换的顺序，如从左到右）还有许多有用的串运算，可以参考Python的str类型，或其他语言的字符串类型（经典是SNOBOL语言）字符串的理论字符串集合和拼接操作构成了一种代数结构空串是拼接操作的“单位元”（幺元）有结合律，无交换律串集合加上拼接操作，构成一个半群一种典型的非交换半群有单位元，因此是一个幺半群关于串的理论有许多研究工作基于串和串替换，研究者提出了pos

6、t系统这是一种与图灵机等价的计算模型（串）重写系统（rewritingsystem）是计算机理论的一个研究领域，一直非常活跃，有许多重要结果和应用字符串抽象数据类型可以考虑下面的字符串抽象数据类型：ADTString:String(self,sseq)#基于字符序列sseq建立一个字符串is_empty(self)#判断本字符串是否空串len(self)#取得字符串的长度char(self,index)#取得字符串中位置index的字符substr(self,a,b)#取得字符串中[a:b]的子

7、串，左闭右开区间match(self,string)#查找串string在本字符串中第一个出现的位置concat(self,string)#做出本字符串与另一字符串string的拼接串subst(self,str1,str2)#做出将本字符串里的子串str1#都替换为str2的结果串最后两个操作可以实现为变动操作或非变动操作（生成满足需要的新串）这里的大部分操作都很简单，只有match和subst操作比较复杂。易见，subst的基础也是match，因为要找str1在串里的出现子串检索（子串匹配）

8、是字符串的核心操作，后面将详细研究字符串的实现串是字符的线性序列：可采用线性表的实现方式，用顺序表示和链接表示。例如用能动态变化大小的顺序表作为实现方式（如果需要表示可变的字符串）还可以根据串本身的特点和串操作的特点，考虑其他表示方式。当然，无论如何还是基于顺序存储或/和链接关键问题：表示方式应能很好支持串的管理和相关操作的实现字符串表示的两个问题：串内容存储。两个极端：1，连续存储在一块存储区；2，一个字符存入一个独立存储块，链接起来。也可以采用某种中间方式，把串中字符分段保存在一组存储块里，