数据结构与算法Python语言描述字符串课件.ppt
时间反复无常，鼓着翅膀飞逝,数据结构与算法：Python语言描述 字符串,B。宮唱字符串的相关概念令 Python字符串(回顾)令字符串匹配和算法令进一步的模式匹配问题令正则表达式 Python的正则表达式应用举例数据结构和算法(Python语言版):字符串裘宗燕,2017323-1,字符串讨论字符串,首先要有一个确定的字符集口“字符”是一个抽象概念,字符集是有穷的一组字符构成的集合口人们经常考虑在计算机里使用的标准字符集,实际上,完全可以拿任意数据元素的集合作为字符集字符串(简称串)是特殊的线性表,表中元素取自选定的字符集其不同于一般表的特点是支持一组以串为对象的操作长度:串中字符的个数称为串的长度口长度为0的串称为空串口在任意一个字符集里,只有唯一的一个空串与一般的表类似口字符串里的字符顺序排列,串里的每个字符有其确定位置口我们用0开始的自然数表示位置数据结构和算法(Python语言版):字符串裘宗燕,20173/23-2,字符串串相等:串的相等基于字符集里的字符定义s1和s2相等,如果其长度相等,而且对应位置的各对字符分别相同假定字符集中的字符有一个全序,串的字典序定义如下对于串S1=a(41定义s1s2,如果存在一个k使a;=b,(=0,1,k-1)而且akb或者nm而且对i=0,1,n-1都有a2=b显然,字典序是字符串集合上的一个全序串与串的最重要运算是拼接(concatenate)上面1和2的拼接是串S=aoa1anbbn1显然,s的长度等于s1和s2的长度之和在 Python里拼接运算用+表示数据结构和算法(Python语言版):字符串裘宗燕,2017323-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语言版):字符串裘宗燕,2017323-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语言版):字符串裘宗燕,2017323-5,字符串的理论字符串集合和拼接操作构成了一种代数结构口空串是拼接操作的“单位元”(幺元)有结合律,无交换律口串集合加上拼接操作,构成一个半群一种典型的非交换半群口有单位元,因此是一个幺半群关于串的理论有许多研究工作口基于串和串替换,研究者提出了post系统这是一种与图灵机等价的计算模型口(串)重写系统(rewriting system)是计算机理论的一个研究领域,一直非常活跃,有许多重要结果和应用数据结构和算法(Python语言版):字符串裘宗燕,2017323-6,字符串抽象数据类型可以考虑下面的字符串抽象数据类型:ADT StringString(sef,sseq)#基于字符序列sseq建立一个字符串is_empty(self)#判断本字符串是否空串len(sef)#取得字符串的长度char(self index)#取得字符串中位置 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语言版):字符串裘宗燕,2017323,字符串的实现串是字符的线性序列口可采用线性表的实现方式,用顺序表示和链接表示。例如用能动态变化大小的顺序表作为实现方式(如果需要表示可变的字符串)口还可以根据串本身的特点和串操作的特点,考虑其他表示方式。当然,无论如何还是基于顺序存储或和链接口关键问题:表示方式应能很好支持串的管理和相关操作的实现字符串表示的两个问题口串内容存储。两个极端:1,连续存储在一块存储区;2,一个字符存入一个独立存储块,链接起来。也可以采用某种中间方式,把串中字符分段保存在一组存储块里,链接起这些存储块口串结束的表示,不同字符串长度可能不同,必须表示串到哪里结束。两种基本方式:1,用专门数据域记录字符串长度;2,用一个特殊符号表示串结束(例如C语言的字符串采用这种方式)数据结构和算法(Python语言版):字符串裘宗燕,20173/23-8,字符串的实现现在考虑字符串的操作许多串操作是线性表操作的具体实例,包括串拼接下面考虑一个特殊的操作串替换口牵涉到三个串:被处理的主串s,作为被替换对象需要从s中替换掉的子串t,以及用于代换t的口由于t可能在s中出现多次,因此需要通过一系列具体的子串代换完成整个替换口由于多次出现可能重叠(回忆前面的例子),只能规定一种代换顺序(例如从左到右),一次代换破坏的子串不应再代入新串次子串代换后,应该从代入的新串之后继续工作。即使代入新串之后形成的部分能与t匹配,也不应在本次替换中考虑口很容易看到:串替换的关键是找到匹配数据结构和算法(Python语言版):字符串裘宗燕,2017323-9,实际语言里的字符串许多语言提供了标准的字符串功能,如口c语言标准库有一组字符串函数(string.h),一些C语言系统提供的扩展的字符串库;C+语言标准库里的字符串库 tring口Java标准库的字符串库口许多脚本语言(包括 Python)提供了功能丰富的字符串库许多实际字符串库用动态顺序表结构作为字符串的表示方式口这样既能支持任意长的字符串口又能比较有效地实现各种重要的字符串操作实际上,支持不同的字符串操作,可能需要不同的实现,例如口有些计算工作需要记录和处理极长的字符串,如支持操作MB(大约为10)或更长的字符串,采用连续存储可能带来管理问题口被编辑文本也是字符串,实现编辑器操作要考虑专门的字符串表示数据结构和算法(Python语言版):字符串裘宗燕,2017323-/10,67,26、要使整个人生都过得舒适、愉快，这是不可能的，因为人类必须具备一种能应付逆境的态度。卢梭27、只有把抱怨环境的心情，化为上进的力量，才是成功的保证。罗曼罗兰28、知之者不如好之者，好之者不如乐之者。孔子29、勇猛、大胆和坚定的决心能够抵得上武器的精良。达芬奇30、意志是一个强壮的盲人，倚靠在明眼的跛子肩上。叔本华,谢谢！,
