数据结构与算法：Python语言描述-字符串教学课件

B。宮唱字符串的相关概念令Python字符串(回顾)令字符串匹配和算法令进一步的模式匹配问题令正则表达式☆Python的正则表达式◆应用举例数据结构和算法(Python语言版):字符串裘宗燕,2019323-1字符串■讨论字符串,首先要有一个确定的字符集口“字符”是一个抽象概念,字符集是有穷的一组字符构成的集合口人们经常考虑在计算机里使用的标准字符集,实际上,完全可以拿任意数据元素的集合作为字符集字符串(简称串)是特殊的线性表,表中元素取自选定的字符集其不同于一般表的特点是支持一组以串为对象的操作长度:串中字符的个数称为串的长度口长度为0的串称为空串口在任意一个字符集里,只有唯一的一个空串■与一般的表类似口字符串里的字符顺序排列,串里的每个字符有其确定位置口我们用0开始的自然数表示位置数据结构和算法(Python语言版):字符串裘宗燕,20193/23-2字符串■串相等:串的相等基于字符集里的字符定义s1和s2相等,如果其长度相等,而且对应位置的各对字符分别相同■假定字符集中的字符有一个全序,串的字典序定义如下对于串S1=a(41定义s1<s2,如果存在一个k使a;=b,(=0,1,…k-1)而且ak<b或者n<m而且对i=0,1,…,n-1都有a2=b显然,字典序是字符串集合上的一个全序■串与串的最重要运算是拼接(concatenate)上面1和2的拼接是串S=aoa1…anb…bn1显然,s的长度等于s1和s2的长度之和在Python里拼接运算用+表示数据结构和算法(Python语言版):字符串裘宗燕,2019323-3字符串两个串之间还有一个重要的关系是“子串关系称s1为s2的一个子串,如果存在两个串s和s使下式成立s2=s+S1+S'(借用Python的写法)口子串也是串。直观看,子串是原串中连续的一段字符序列形成的串。显然,一个串可以是或者不是另一个串的子串口如果S1是S2的子串,也说S1在S2里出现,称S2里与S1相同的字符段的第一个字符的位置为S1在S2里出现的位置口S2里可能出现多个与S1相同的段,这时说S1在S2里多次出现■注意:s1在s2中的多个出现可能不独立,相互重叠。例如babb在babbabbbbabb里有三个出现,前两个有重叠■根据定义,很显然,空串是任何字符串的子串;另一方面,任何字符串s也都是该串本身的子串数据结构和算法(Python语言版):字符串裘宗燕,2019323-4字符串两种特殊子串:口如果存在S使S2=S1+s,称S1为s2的一个前缀口如果存在s使得S2=S+S1称S1为s2的一个后缀直观说,一个串的前缀就是该串开头的一段字符构成的子串,后缀就是该串最后的一段字符构成的子串显然,空串和s既是s的前缀,也是s的后缀其他有用的串运算口串s的n次幂s是连续n个s拼接而成的串(在Python语言里用s*n表示)口串替换,指将一个串里的一些(互不重叠的)子串代换为另一些串得到的结果(由于可能重叠,需规定代换的顺序,如从左到右)口还有许多有用的串运算,可以参考Python的st类型,或其他语言的字符串类型(经典是SNOBOL语言)数据结构和算法(Python语言版):字符串裘宗燕,2019323-5字符串的理论■字符串集合和拼接操作构成了一种代数结构口空串是拼接操作的“单位元”(幺元)有结合律,无交换律口串集合加上拼接操作,构成一个半群一种典型的非交换半群口有单位元,因此是一个幺半群关于串的理论有许多研究工作口基于串和串替换,研究者提出了post系统这是一种与图灵机等价的计算模型口(串)重写系统(rewritingsystem)是计算机理论的一个研究领域,一直非常活跃,有许多重要结果和应用数据结构和算法(Python语言版):字符串裘宗燕,2019323-6字符串抽象数据类型可以考虑下面的字符串抽象数据类型:ADTStringString(sef,sseq)#基于字符序列sseq建立一个字符串is_empty(self)#判断本字符串是否空串len(sef)#取得字符串的长度char(selfindex)#取得字符串中位置index的字符substr(sef,a,b)#取得字符串中[ab的子串,左闭右开区间match(sef,string)#查找串srng在本字符串中第一个出现的位置concat(sef,string)#做出本字符串与另一字符串srng的拼接串subs(slf,str1,str2)#做出将本字符串里的子串str1#都替换为str2的结果串最后两个操作可以实现为变动操作或非变动操作(生成满足需要的新串)这里的大部分操作都很简单,只有match和subst操作比较复杂。易见,subst的基础也是match,因为要找str1在串里的出现子串检索(子串匹配)是字符串的核心操作,后面将详细研究数据结构和算法(Python语言版):字符串裘宗燕,2019323字符串的实现■串是字符的线性序列口可采用线性表的实现方式,用顺序表示和链接表示。例如用能动态变化大小的顺序表作为实现方式(如果需要表示可变的字符串)口还可以根据串本身的特点和串操作的特点,考虑其他表示方式。当然,无论如何还是基于顺序存储或和链接口关键问题:表示方式应能很好支持串的管理和相关操作的实现■字符串表示的两个问题口串内容存储。两个极端:1,连续存储在一块存储区;2,一个字符存入一个独立存储块,链接起来。也可以采用某种中间方式,把串中字符分段保存在一组存储块里,链接起这些存储块口串结束的表示,不同字符串长度可能不同,必须表示串到哪里结束。两种基本方式:1,用专门数据域记录字符串长度;2,用一个特殊符号表示串结束(例如C语言的字符串采用这种方式)数据结构和算法(Python语言版):字符串裘宗燕,20193/23-8字符串的实现现在考虑字符串的操作许多串操作是线性表操作的具体实例,包括串拼接下面考虑一个特殊的操作串替换口牵涉到三个串:被处理的主串s,作为被替换对象需要从s中替换掉的子串t,以及用于代换t的口由于t可能在s中出现多次,因此需要通过一系列具体的子串代换完成整个替换口由于多次出现可能重叠(回忆前面的例子),只能规定一种代换顺序(例如从左到右),一次代换破坏的子串不应再代入新串次子串代换后,应该从代入的新串之后继续工作。即使代入新串之后形成的部分能与t匹配,也不应在本次替换中考虑口很容易看到:串替换的关键是找到匹配数据结构和算法(Python语言版):字符串裘宗燕,2019323-9实际语言里的字符串■许多语言提供了标准的字符串功能,如口c语言标准库有一组字符串函数(string.h),一些C语言系统提供的扩展的字符串库;C++语言标准库里的字符串库<tring口Java标准库的字符串库口许多脚本语言(包括Python)提供了功能丰富的字符串库■许多实际字符串库用动态顺序表结构作为字符串的表示方式口这样既能支持任意长的字符串口又能比较有效地实现各种重要的字符串操