數(shù)據(jù)結(jié)構(gòu)與算法：Python語言描述-字符串教學(xué)課件

B。宮唱字符串的相關(guān)概念令Python字符串(回顧)令字符串匹配和算法令進(jìn)一步的模式匹配問題令正則表達(dá)式☆Python的正則表達(dá)式◆應(yīng)用舉例數(shù)據(jù)結(jié)構(gòu)和算法(Python語言版):字符串裘宗燕,2019323-1字符串■討論字符串,首先要有一個確定的字符集口“字符”是一個抽象概念,字符集是有窮的一組字符構(gòu)成的集合口人們經(jīng)?？紤]在計算機(jī)里使用的標(biāo)準(zhǔn)字符集,實(shí)際上,完全可以拿任意數(shù)據(jù)元素的集合作為字符集字符串(簡稱串)是特殊的線性表,表中元素取自選定的字符集其不同于一般表的特點(diǎn)是支持一組以串為對象的操作長度:串中字符的個數(shù)稱為串的長度口長度為0的串稱為空串口在任意一個字符集里,只有唯一的一個空串■與一般的表類似口字符串里的字符順序排列,串里的每個字符有其確定位置口我們用0開始的自然數(shù)表示位置數(shù)據(jù)結(jié)構(gòu)和算法(Python語言版):字符串裘宗燕,20193/23-2字符串■串相等:串的相等基于字符集里的字符定義s1和s2相等,如果其長度相等,而且對應(yīng)位置的各對字符分別相同■假定字符集中的字符有一個全序,串的字典序定義如下對于串S1=a(41定義s1<s2,如果存在一個k使a;=b,(=0,1,…k-1)而且ak<b或者n<m而且對i=0,1,…,n-1都有a2=b顯然,字典序是字符串集合上的一個全序■串與串的最重要運(yùn)算是拼接(concatenate)上面1和2的拼接是串S=aoa1…anb…bn1顯然,s的長度等于s1和s2的長度之和在Python里拼接運(yùn)算用+表示數(shù)據(jù)結(jié)構(gòu)和算法(Python語言版):字符串裘宗燕,2019323-3字符串兩個串之間還有一個重要的關(guān)系是“子串關(guān)系稱s1為s2的一個子串,如果存在兩個串s和s使下式成立s2=s+S1+S'(借用Python的寫法)口子串也是串。直觀看,子串是原串中連續(xù)的一段字符序列形成的串。顯然,一個串可以是或者不是另一個串的子串口如果S1是S2的子串,也說S1在S2里出現(xiàn),稱S2里與S1相同的字符段的第一個字符的位置為S1在S2里出現(xiàn)的位置口S2里可能出現(xiàn)多個與S1相同的段,這時說S1在S2里多次出現(xiàn)■注意:s1在s2中的多個出現(xiàn)可能不獨(dú)立,相互重疊。例如babb在babbabbbbabb里有三個出現(xiàn),前兩個有重疊■根據(jù)定義,很顯然,空串是任何字符串的子串;另一方面,任何字符串s也都是該串本身的子串?dāng)?shù)據(jù)結(jié)構(gòu)和算法(Python語言版):字符串裘宗燕,2019323-4字符串兩種特殊子串:口如果存在S使S2=S1+s,稱S1為s2的一個前綴口如果存在s使得S2=S+S1稱S1為s2的一個后綴直觀說,一個串的前綴就是該串開頭的一段字符構(gòu)成的子串,后綴就是該串最后的一段字符構(gòu)成的子串顯然,空串和s既是s的前綴,也是s的后綴其他有用的串運(yùn)算口串s的n次冪s是連續(xù)n個s拼接而成的串(在Python語言里用s*n表示)口串替換,指將一個串里的一些(互不重疊的)子串代換為另一些串得到的結(jié)果(由于可能重疊,需規(guī)定代換的順序,如從左到右)口還有許多有用的串運(yùn)算,可以參考Python的st類型,或其他語言的字符串類型(經(jīng)典是SNOBOL語言)數(shù)據(jù)結(jié)構(gòu)和算法(Python語言版):字符串裘宗燕,2019323-5字符串的理論■字符串集合和拼接操作構(gòu)成了一種代數(shù)結(jié)構(gòu)口空串是拼接操作的“單位元”(幺元)有結(jié)合律,無交換律口串集合加上拼接操作,構(gòu)成一個半群一種典型的非交換半群口有單位元,因此是一個幺半群關(guān)于串的理論有許多研究工作口基于串和串替換,研究者提出了post系統(tǒng)這是一種與圖靈機(jī)等價的計算模型口(串)重寫系統(tǒng)(rewritingsystem)是計算機(jī)理論的一個研究領(lǐng)域,一直非?；钴S,有許多重要結(jié)果和應(yīng)用數(shù)據(jù)結(jié)構(gòu)和算法(Python語言版):字符串裘宗燕,2019323-6字符串抽象數(shù)據(jù)類型可以考慮下面的字符串抽象數(shù)據(jù)類型:ADTStringString(sef,sseq)#基于字符序列sseq建立一個字符串is_empty(self)#判斷本字符串是否空串len(sef)#取得字符串的長度char(selfindex)#取得字符串中位置index的字符substr(sef,a,b)#取得字符串中[ab的子串,左閉右開區(qū)間match(sef,string)#查找串srng在本字符串中第一個出現(xiàn)的位置concat(sef,string)#做出本字符串與另一字符串srng的拼接串subs(slf,str1,str2)#做出將本字符串里的子串str1#都替換為str2的結(jié)果串最后兩個操作可以實(shí)現(xiàn)為變動操作或非變動操作(生成滿足需要的新串)這里的大部分操作都很簡單,只有match和subst操作比較復(fù)雜。易見,subst的基礎(chǔ)也是match,因?yàn)橐襰tr1在串里的出現(xiàn)子串檢索(子串匹配)是字符串的核心操作,后面將詳細(xì)研究數(shù)據(jù)結(jié)構(gòu)和算法(Python語言版):字符串裘宗燕,2019323字符串的實(shí)現(xiàn)■串是字符的線性序列口可采用線性表的實(shí)現(xiàn)方式,用順序表示和鏈接表示。例如用能動態(tài)變化大小的順序表作為實(shí)現(xiàn)方式(如果需要表示可變的字符串)口還可以根據(jù)串本身的特點(diǎn)和串操作的特點(diǎn),考慮其他表示方式。當(dāng)然,無論如何還是基于順序存儲或和鏈接口關(guān)鍵問題:表示方式應(yīng)能很好支持串的管理和相關(guān)操作的實(shí)現(xiàn)■字符串表示的兩個問題口串內(nèi)容存儲。兩個極端:1,連續(xù)存儲在一塊存儲區(qū);2,一個字符存入一個獨(dú)立存儲塊,鏈接起來。也可以采用某種中間方式,把串中字符分段保存在一組存儲塊里,鏈接起這些存儲塊口串結(jié)束的表示,不同字符串長度可能不同,必須表示串到哪里結(jié)束。兩種基本方式:1,用專門數(shù)據(jù)域記錄字符串長度;2,用一個特殊符號表示串結(jié)束(例如C語言的字符串采用這種方式)數(shù)據(jù)結(jié)構(gòu)和算法(Python語言版):字符串裘宗燕,20193/23-8字符串的實(shí)現(xiàn)現(xiàn)在考慮字符串的操作許多串操作是線性表操作的具體實(shí)例,包括串拼接下面考慮一個特殊的操作串替換口牽涉到三個串:被處理的主串s,作為被替換對象需要從s中替換掉的子串t,以及用于代換t的口由于t可能在s中出現(xiàn)多次,因此需要通過一系列具體的子串代換完成整個替換口由于多次出現(xiàn)可能重疊(回憶前面的例子),只能規(guī)定一種代換順序(例如從左到右),一次代換破壞的子串不應(yīng)再代入新串次子串代換后,應(yīng)該從代入的新串之后繼續(xù)工作。即使代入新串之后形成的部分能與t匹配,也不應(yīng)在本次替換中考慮口很容易看到:串替換的關(guān)鍵是找到匹配數(shù)據(jù)結(jié)構(gòu)和算法(Python語言版):字符串裘宗燕,2019323-9實(shí)際語言里的字符串■許多語言提供了標(biāo)準(zhǔn)的字符串功能,如口c語言標(biāo)準(zhǔn)庫有一組字符串函數(shù)(string.h),一些C語言系統(tǒng)提供的擴(kuò)展的字符串庫;C++語言標(biāo)準(zhǔn)庫里的字符串庫<tring口Java標(biāo)準(zhǔn)庫的字符串庫口許多腳本語言(包括Python)提供了功能豐富的字符串庫■許多實(shí)際字符串庫用動態(tài)順序表結(jié)構(gòu)作為字符串的表示方式口這樣既能支持任意長的字符串口又能比較有效地實(shí)現(xiàn)各種重要的字符串操