數(shù)據(jù)結構第4章 串

第四章串和添錦第4章串

4.1基本概念

4.2串的存儲結構

4.3串的基本運算

4.4簡單模式匹配4.5KMP算法4.1基本概念

1、基本概念概念：由有限個合法字符組成一組數(shù)據(jù)表示方法：大寫字母作為串的名稱，串的內(nèi)容使用“”、‘’括起來，中間使用等號（=），例如：S=“abc213%4&*a”其中，引號中的每一個字符是串S的一個元素。2、串的術語串長：一個串中每個元素占一個長度，所有元素的長度和就是串長空串：一個串中不包含任何元素空白串：串中的所有元素均是空格子串：一個串在另一個串中出現(xiàn)，這個串就是另一個串的字串主串：

包含字串的串相對于子串來說就是主串3.案例串長：S=“abcdefg”，這個串的長度為7空串：S=“”，這個串的長度為0，因此是一個空串空白串：S=“”這個串的元素都是空格，也就是一個空格串子串：S1=“abc”，S2=“acbdabc”，因此S1是S2的字串主串：由上一個例子可以得知，S2相對于S1就是它的主串。

4、串相等若串之間的長度相等，且其中的元素相同，對應位置的元素也相等，那么說這些串是相等的。S1=“Kunming”，S2=“KunMing”，S3=“Kunming”，S4=“KUNMING”首先，S1,S2,S3,S4的串長相等，滿足相等的第一個條件；接下來，S1和S3均包含K,u,n,m,i,n,g，S2與之不同的是M和m,S4均為大寫字母，S1和S3滿足包含元素相等；且S1和S3對應位置的元素也相等，因此，S1和S3相等。第4章串

4.1基本概念

4.2串的存儲結構

4.3串的基本運算

4.4簡單模式匹配4.5KMP算法串的定義ClassSeqString(object):def__init__(self,ms):self.ch=[Noneforiinrange(ms)]self.length=0self.MAXSIZE=msProgramming……設ch[100],S=“Programming”,則S的邏輯結構為：012345678910……994.2

串的存儲結構

串是一種線型數(shù)據(jù)結構，之前的課程中線性結構有兩種存儲形式，保證元素之間的邏輯為線型結構即可。順序存儲：不僅元素之間的關系為線型關系，存儲結構也為連續(xù)的線性結構；鏈式存儲：只要求元素之間的邏輯關系保持線性結構，存儲結構不要求連續(xù)。4.2.1串的順序存儲單字節(jié)存儲：在存儲中，一個字符占一個字節(jié)的存儲形式緊縮存儲：串在進行存儲時挨個將內(nèi)存位數(shù)存滿非緊縮存儲：串在進行存儲的時候每個內(nèi)存位只存一個字符單字節(jié)存儲

1單字節(jié)存儲（1）存儲結構要求存儲空間是連續(xù)的，并且能夠將整個串完整的存儲下來（2）基本思想將串中的每一個元素，挨個的存在所分配的存儲空間中，內(nèi)一個元素的存儲位置減去第一個元素的位置+1就是這個元素在串中的位置（3）存儲實例

設存在串S=“Programming”，則這個串的存儲方式為：單字節(jié)存儲Programming012345678910

2緊縮存儲

這種存儲方式與單字節(jié)存儲是一回事，存儲形式有所區(qū)別。設串S=“Programming”，串的緊縮存儲方式為：(32位系統(tǒng)，存儲單元為4字節(jié)）緊縮存儲Prohramming

3非緊縮存儲（1）存儲要求按照系統(tǒng)位數(shù)和存儲位數(shù)分配存儲空間，但是內(nèi)一個存儲位數(shù)只存儲一個字符。（2）基本思想將存儲空間的位數(shù)進行存儲時，不再挨個存，而是挨位存。非緊縮存儲（3）實例設S=“abcde”，則S進行非緊縮存儲的示意圖為：非緊縮存儲abcde4.2.2

串的鏈式存儲在線性表的學習中，我們知道，線性結構的數(shù)據(jù)還可以使用地址和數(shù)據(jù)兩個域合作的形式完成非連接存儲區(qū)域的線性存儲，在串的存儲中主要有以下兩個鏈式存儲方法：多字符域鏈式存儲單字符域鏈式存儲

定義4.2classLString(object):def__init__(self,ms):self.ch=[Noneforiinrange(ms)]self.length=0self.MAXSIZE=msself.next=None1、多字符域節(jié)點鏈表結構由定義4.2可以看出，如果按照這樣的存儲方式進行存儲，串的每一個節(jié)點可以存儲串長不高于MAXSIZE的一個串。這樣的存儲類似于定義了一個串組，每一個節(jié)點可以作為一個串，也可以作為一個字符。

例如：對于串S=“Programming”，多字符域鏈式存儲結構示意圖為：Programming^2、單字符域節(jié)點鏈表結構這種存儲方式每一個節(jié)點只存一個字符，串S的單字符域節(jié)點存儲示意圖如下：

Progrg^ammin第4章串

4.1基本概念

4.2串的存儲結構

4.3串的基本運算

4.4簡單模式匹配4.5KMP算法4.4串的基本運算1、求串長length(S):統(tǒng)計串S中所包含的合法字符的個數(shù)。如：S=“abcde”,則length(S)=5

Slength(s)算法4.1求串長deflength(self）：

returnself.length2、串連接concat（S,T）：將一個串T連接在另一個串S的后面。如：S=“abcd”，T=“efgh”，則concat(S,T)=“abcdefg”STS.MaxSize算法4.2串連接defconcat(s,t):slen=s.lengthtlen=t.lengthifslen+tlen>s.MAXSIZE:returnFalse#空間不夠

foriinrange(slen,slen+tlen):s.ch[i]=t.ch[i-slen]s.length=slen+tlenreturnTrue#連接成功3、串比較strcmp(S,T):比較S和T的大小，將其中的元素分別挨個進行對比，得出兩個串的大小值。S>T=1，S=T=0，S<T=-1。S=“abcDE”,T=“abcde”,則strcmp(S,T)=-1。

ST是否相等算法4.3串比較defstrcmp(s,t):slen=s.lengthtlen=t.lengthifslen==tlen:i=0whilei<slenandi<tlen:ifs.ch[i]>t.ch[i]:return1ifs.ch[i]<t.ch[i]:return-1i=i+1return0elifslen>tlen:return1else:return-1T1T2T4T5T34、子串查詢index（S,T）:查找子串T在主串S中第一次出現(xiàn)的位置。S=“abcdcbad”，T=“bad”，則index(S,T)=7。T能否找到T5、求子串substr(S,i,k):從串S的第i個位置開始，取k個字符作為S串的子串。S=“Programming”，則T=substr(S,3,3)=“ogr”

ST算法4.4求子串defsubstr(s,i,j):

n=s.lengthifi<1ori>nori+j>n+1:print("iorjisinvalid.")returnFalsesbs=String(j)sbs.length=jforkinrange(i,i+j):sbs.ch[k-i]=s.ch[k-1]returnsbs6、插入子串insert(S,T,i):在主串S的第i個位置插入子串TS=“aefg”，T=“bcd”，則insert（S,T,2）=“abcdefg”算法4.5插入子串definsert(s,t,i):#在的第i個位置插入tn=s.lengthm=t.lengthifi<1ori>n+1orm+n>s.MAXSIZE:returnFalse#出錯結束插入操作

j=n-1whilej>=i-1:s.ch[m+j]=s.ch[j]j=j-1j=i-1whilej<i+m-1:s.ch[j]=t.ch[j-i+1]j=j+1s.length=m+n7、刪除子串delete(S,i,k):在主串S中刪除從第i位開始的連續(xù)k個字符。S=“Programming”，則delete（S,3,4）=“Prmming”

算法4.6刪除子串defdelete(s,i,j):#刪除s中第i個位置開始的j個字符

n=s.lengthifi<1ori>nori+j>s.MAXSIZE+1:returnFalse#出錯結束刪除操作

forkinrange(i-1+j,n):s.ch[k-j]=s.ch[k]s.length=s.length-j8、復制串strcpy（S,T）：將串S的所有元素復制給串T。S=“Kunming”，T=“”,運行strcpy(S,T)后，T=“Kunming”ST算法4.7復制串defstrcopy(s,t):#將字符串t的值，賦值給s1n=t.lengthforiinrange(0,n):s.ch[i]=t.ch[i]s.length=n第4章串

4.1基本概念

4.2串的存儲結構

4.3串的基本運算

4.4簡單模式匹配4.5KMP算法4.5串的簡單模式匹配1、基本概念字符串匹配是串的基本運算的一種操作，主要是指在一個串中，查找另一個串，查找成功后返回首次出現(xiàn)的位置，查找失敗直接返回錯誤。

2、基本思路將子串的元素挨個取出來，并與主串的元素進行比較。從主串的第一個位置開始對比，失敗以后對比順序往后移動一位，直到對比到主串長-子串長的位置。ST現(xiàn)在需要在主串S中尋找子串T，如果找到了就返回T[0]==S[i]時候的i的值，若直到最后都沒有找到，則返回-1。（在數(shù)據(jù)結構中，順序結構的下標是從0開始的，因此，即便在計算機中可以使用0表示邏輯否，但是這里不能返回0）？若這里的“？”是相等若這里的“？”是不相等繼續(xù)判斷”？”的邏輯k3、簡單算法defindex(t,p):#在t中查找p是否存在

i=0whilei<t.length:j=0whilej<p.length:ift.ch[i+j]!=p.ch[j]:break;j=j+1ifj==p.length:returni#匹配成功，返回ii=i+1return-1#匹配不成功，返回-1第4章串

4.1基本概念

4.2串的存儲結構

4.3串的基本運算

4.4簡單模式匹配4.5KMP算法

4.6KMP算法1、基本思路

CDABADABCABADABABABADABABs=p=4.6KMP算法1、基本思路

CDABADABCABADABABABADABABs=p=根據(jù)對比我們可以看到。KMP算法在進行匹配時，出現(xiàn)失敗了，并不會每一次都是移動一位進行二次匹配，而是移動到下一個有用的匹配的位置繼續(xù)匹配2、算法描述在進行模式匹配時，如果執(zhí)行s[i](1≤i≤m)與p[j](1≤j≤n)的試配，可能出現(xiàn)的情況如下：（1）如果s[i]=p[j]，則繼續(xù)進行試配，進行s[i+1]與p[j+1]的試配；（2）如果s[i]≠p[j]，則①如果j=1，把模式p右移一位再從頭開始進行試配。②如果2≤j≤n，選擇一個適當?shù)奈恢胣ext[j],進行si與p[next(j)]的試配，把模式串的位置移動到j-next[j]。next[j]稱為“失效函數(shù)”。算法4.9defindexKMP(t,p,next):#KMP算法,由于數(shù)組下標是從0開始,所以請注意文中描述的i,j值與下標之間的換算關系。

i=0j=0whilei<t.lengthandj<p.length:

ifj==-1ort.ch[i]==p.ch[j]: i=i+1 j=j+1 else: j=next[j]ifj==p.length:returni-jels