數(shù)據(jù)結(jié)構(gòu)4串4完整版

第四章串數(shù)據(jù)結(jié)構(gòu)一.串的抽象數(shù)據(jù)類型的定義二.串的表示和實現(xiàn)三.串的模式匹配算法串是字符串的簡稱。它是一種特殊的線性表，線性表的每個元素僅由一個字符組成。串是由零個或多個字符組成的有限序列。一般記為：s=“

a1a2…an”

串名串值串的長度：串中字符的數(shù)目?？沾洪L度為零的串。用“”來表示空串。4.1串的基本概念子串：串中任意個連續(xù)的字符組成的子序列稱為該串的子串。主串：包含子串的串相應(yīng)地稱為主串。例：s1=“12ab3AB45ABC”-------主串

s2=“AB”-------子串字符在串中的位置：字符在字符串序列中的序號子串在主串中的位置：子串在主串中的第一次出現(xiàn)時，子串中的第一個字符在主串中的位置。串相等：兩個串的長度相等，并且各個對應(yīng)位置的字符都相等。4.2串的基本操作(1)判等函數(shù)：EQUAL(s，t)(2)求長函數(shù)：LENGTH(s)(3)連接函數(shù)：CONCAT(s，t)(4)求子串函數(shù)：SUBSTR(s，start，len)

若1≤start≤length(s)

且

0<len

≤length(s)-start+1，則返回從串s中第start個字符起，長度為len的字符序列，否則返回一個特殊的串常量。(5)INDEX(s，t)定位函數(shù)。t<>

若在主串s

中存在和

t

相等的子串，則函數(shù)值為s

中第一個這樣的子串在主串s

中的位置，否則函數(shù)值為零。(6)REPLACE(

s，t，v)

置換操作：以串v替換串s中所有和t相等的不重疊的子串。例如：設(shè)s=“BBABBABBA”，

t

=“AB”，v=“A”

則REPLACE(s，t，v)的操作結(jié)果為:“BBABABA”(7)INSERT(s，pos，t)插入操作:

當1≤pos≤length(s)+1時，在串s的第pos個字符之前插入串t。(8)DELETE(s，pos，len)刪除操作當1≤pos≤length(s)

且

0<len

≤length(s)-pos+1時，從串s中刪去從第pos個字符起長度為len的子串。(9)CREAT(s，ss)：

設(shè)定一個串s，其值為字符序列ss。(10)ASSIGN(s

，t)：將t的值賦給s。一.定長順序存儲方式

4.3串的存儲結(jié)構(gòu)#defineMAXLEN255//預(yù)定義長度typedef

charSString[MAXLEN+1]

//0號單元存放串長按這種串的表示方法實現(xiàn)的串的運算時，其基本操作為

“字符序列的復(fù)制”串的實際長度可在這個預(yù)定義長度的范圍內(nèi)隨意設(shè)定，超過予定義長度的串值則被舍去，稱之為“截斷”特點:定長順序存儲方式下串操作的實現(xiàn)n

t1t2…tnt

ms1s2…smsMAXLEN

s1s2…sm

t1t2…tnlm+n例1：串聯(lián)接concat(s，t)；SString

concat(SStrings1，SStrings2，int

&overflow)

//設(shè)局部變量t用于函數(shù)的返回值，overflow=0為正常聯(lián)接{if(

s1[0]+s2[0]≤MAXLEN

){t[1..s1[0]]=s1[1..s1[0]]；t[s1[0]+1..s1[0]+s2[0]]=s2[1..s2[0]]；t[0]=s1[0]+s2[0]；overflow=0；}；

elseif

(s1[0]<MAXLEN)

//截斷s2串

{t[1..s1[0]]=s1[1..s1[0]]；t[s1[0]+1..MAXLEN]=s2[1..MAXLEN–s1[0]]；t[0]=MAXLEN；overflow=1；}；

else{

//s1[0]==MAXLENt[0..MAXLEN]=s1[0..MAXLEN];overflow=1；}

return(t);}//concat

(2)求子串SUBSTR(s，start，n)SString

substr(SString

s，int

start，

int

n){

//返回在s串中從start位置起長度為n的子串if(start<1||start>s[0]||n<1||n>s[0]-start+1)return空串；

else{

sub[1..n]=s[start..start+n-1]；sub[0]=n；

return(sub)；

}}以一組地址連續(xù)的存儲單元存放串值字符序列，但它們的存儲空間是在程序執(zhí)行中從堆中(Heap)動態(tài)分配而得。所以也稱為動態(tài)存儲分配的順序表。在C語言中，利用動態(tài)存儲管理函數(shù)，來根據(jù)實際需要動態(tài)分配和釋放字符數(shù)組空間typedef

struct{

char*ch；

//若是非空串，則按串長分配存儲空間，否則ch為NULL

intlength；

//串的長度}HString；HString

S；二.堆分配順序存儲方式(1)串聯(lián)接函數(shù)CANCAT(S1，S2，&T)statusconcat(HString

S1,HString

S2,HString

&T){

//用參數(shù)T返回連接S1和S2后的新串if(T.ch)

free(T.ch)；

//釋放舊的空間

T.ch=(char*)malloc((S1.length+S2.length)*sizeof(char)

)

T.length=S1.length+S2.length；T.ch[0..S1.length-1]=S1[0..S1.length-1]；T.ch[S1.length..T.length-1]=S2[0..S2.length-1]；

returnOK；}//concat

(2)求子串SUBSTR(s，start，n)HSstring

substr(HString

s，int

start，

int

n){//用sub返回在s串中從start位置起長度為n的子串if(start<1||start>s.length||n<1||n>s.length-start+1)

return空串；else{

sub.ch=(char

*)malloc(n*sizeof(char))；sub.ch[0..n-1]=s[start-1..start+n-2]；

sub.length=n；

return(sub)；}}為了便于進行串的操作，除頭指針外還可附設(shè)一個尾指針指示鏈表中的最后一個結(jié)點，并給出當前串的長度。稱這種結(jié)構(gòu)為塊鏈結(jié)構(gòu)。三.串的塊鏈存儲方式例如:

在編輯系統(tǒng)中，整個文本編輯區(qū)可以看成是一個串，每一行是一個子串，構(gòu)成一個結(jié)點。即:同一行的串用定長結(jié)構(gòu)(80個字符),行和行之間用指針相聯(lián)接。abcdefghi###/\Headabc…i/\Head#define

CHUNKSIZE

80

//

可由用戶定義的塊大小typedef

struct

BNode

{chardata[CHUNKSIZE]；//塊內(nèi)連續(xù)字符結(jié)點成員

struct

BNode*next；}typedef

struct{

struct

BNode*head，*tail；//串的頭和尾指針

int

curlen；

//串的當前長度

}LString；

//串的類型是一個結(jié)構(gòu)

LString

s；abcdefghi###/\headtail9例：主串s=“ababcabcacbab”,

模式串t=“abcac”的匹配過程。

第一趟：ababcabcacbab

abc

ac

i=1

j=1i=2j=2i=3j=3

第二趟：ababcabcacbab

abc

aci=2j=14.4子串的模式匹配

第三趟：ababcabcacbab

abc

a

c

i=3j=1i=4j=2i=6j=4i=5j=3i=7j=5

第四趟：ababcabcacbab

abc

aci=4j=1

第五趟：ababcabcacbab

abc

aci=5j=1

第六趟：ababcabcacbab

abc

aci=6j=1i=7j=2i=8j=3i=9j=4i=10j=5i=11j=6定長順序存儲方式

下INDEX(S，T)算法如下：int

index(SStringS，SString

T){//返回子串T在主串S中首次出現(xiàn)的位置i=1；j=1；//S[0],T[0]為串長while(i≤S[0]&&j≤

T[0])

if(S[i]==T[j])

{i++；j++};else{i=i-j+2；j=1}；if(j>T[0])

return(i-T[0]);elsereturn(0)；}//index模式匹配的一種改進算法(KMP算法)

第三趟：ababcabcacbab

abc

a

ci=3j=1i=4j=2i=6j=4i=5j=3i=7j=5

在index(s，t)的回溯法中，第三趟如下：第四趟：讓i回溯到4?；厮莘椒ǖ膯栴}：改進：

每一趟匹配過程中出現(xiàn)字符比較不等時，不需回溯i指針，而是利用已經(jīng)得到的“部分匹配”的結(jié)果，將模式串向右“滑動”盡可能遠的一段距離后，繼續(xù)進行比較。0000000000000000000000000000000000000000000000001000000010000000100000001

第一趟：ababcabcacbab

abc

ac

i=1

j=1i=2j=2i=3j=3

第二趟：ababcabcacbab

abc

aci=3j=1i=4j=2i=5j=3i=6j=4i=7j=5

第三趟：ababcabcacbab

(a)bc

aci=7j=2i=8j=3i=9j=4i=10j=5i=11j=6S1S2……Si-j+1……Si-j+k-1……Si-k+1……Si-1

Si…

≠

P1P2……Pk-1

Pk

……Pj-k+1……Pj-1

Pj

?

k=next[j]

P1……Pk-1

Pk假設(shè)主串為“s1s2…sn”，模式串為“p1p2…pm”，如在匹配過程中產(chǎn)生“失配”(si

≠pj)，模式串應(yīng)向右滑動多遠，即si

應(yīng)與模式串中哪個字符再比較？假設(shè)應(yīng)與第k(k<j)個字符pk繼續(xù)比較，“p1p2…pk-1”=“Si-k+1Si-k+2…Si-1”

(1)“pj-k+1

pj-k+2…pj-1

”=“Si-k+1Si-k+2…Si-1”

(2)由(1)、(2)得到：

“p1p2…pk-1”=“pj-k+1pj-k+2…pj-1”

若令next[j]=k，則模式串的next函數(shù)如下定義：0，j=1next[j]=max

{k|1<k<j且

“p1…pk-1”=“pj-k+1…pj-1”}1，其它

j12345678模式串

abaabcacnext[j]j=1:

next[1]=0j=2:

滿足1<k<j的k不存在，next[2]=1j=3

:滿足1<k<j的k=2:“p1”=“a”不等于“p2”=“b”,next[3]=1j=4

:滿足1<k<的k=2，3；

k=2

:“p1”=“a”等于“p3”=“a”k=3

:“p1p2”=“ab”不等于“p2p3”=“ba”,

next[4]=2

0

1

1

2j=5

滿足1<k<j的有k=2，3，4；

k=2:“p1”=“a”等于“p4”=“a”

k=3:“p1p2”=“ab”不等于“p3p4”=“aa”,

k=4:

“p1p2p3”=“aba”不等于“p2p3p4”=“baa”,next[5]=2

j12345678模式串

abaabcacnext[j]0112

2

3j=6

滿足1<k<j的有k=2，3,4，5；

k=2:“p1”=“a”不等于“p5”=“b”

k=3:

“p1p2”=“ab”等于“p4p5”=“ab”,

k=4：“p1p2p3”=“aba”不等于“p3p4p5”=“aab”,

k=5:

“p1p2p3p4”=“abaa”不等于“p2p3p4p5”=“baab”,

next[6]=3j=7

時滿足1<k<j的有k=2，3,4，5，6；

k=2:“p1”=“a”不等于“p6”=“c”

k=3:“p1p2”=“ab”不等于“p5p6”=“bc”,

k=4：“p1p2p3”=“aba”不等于“p4p5p6”=“abc”,

k=5:“p1p2p3p4”=“abaa”不等于“p3p4p5p6”=“aabc”,

k=6:“p1p2p3p4p5”=“abaab”不等于“p2p3p4p5p6”=“baabc”,

next[7]=1

j12345678模式串

abaabcacnext[j]011223

1j=8

時滿足1<k<j的有k=2，3,4，5，6，7；

k=2:"p1"="a"等于

"p7"="a"

k=3:"p1p2"="ab"不等于"p6p7"="ca",

k=4："p1p2p3"="aba"不等于"p5p6p7"="bca",

k=5:"p1p2p3p4"="abaa"不等于"p4p5p6p7"="abca",k=6:“p1p2p3p4p5”=“abaab”不等于"p3p4p5p6p7"="aabca",k=7:"p1p2p3p4p5p6"="abaabc"不等于"p2p3p4p5p6p7"="baabca",

next[8]=2

j12345678模式串

abaabcacnext[j]01122312[問題1]已知next[j]后，INDEX(s,p)算法的實現(xiàn)(1)：當Si

=Pj

或j=0時，則i++；j++；(2)：當Si≠Pj

時，i不變，讓j=next[j]，轉(zhuǎn)到(1)；a

c

abaabca

a

baabcac例：主串S=“acabaabcaabaabcac”

，

模式串T=“abaabcac”a

b

(∵j=2,∴讓j=next[2]=1)i=2a

(∵j=1,∴讓j=next[1]=0，下次讓i++，j++(=1)；)abaabcac

(∵j=8，∴讓j=next[8]=2)i=3

i=10

(a)

b

(∵j=2，∴讓j=next[2]=1)abaabcac改進算法(KMP算法)：int

index_kmp(SSring

S，SStringT)//利用模式串t的next函數(shù)值求T在主串S中首次出的位置{i=1；j=1；while(i≤S[0]&&j≤T[0])

if(j==0

||

S[i]==T[j]){i++；j++};elsej=next[j]；if(j>T[0])

return(i-T[0])；elsereturn(0)}//index_kmp

(1)由定義得知next[1]=0(2)

已知

next[j]=k，如何求next[j+1]?

由于next[j]=k，則有下面的等式成立：

“p1…pk-1”=“pj-k+1…pj-1”

①若

pk=pj

則有：“p1…pk”=“pj-k+1…pj”

next[j+1]=next[j]+1=k+1p1p2……pk-1

……

pj-k+1……pj-1

pj

pj+1……pn[問題2]

如何求next[j]函數(shù)：(b)

若

pk≠pj

，

則將求函數(shù)next的問題看成是一個模式匹配的過程。由于已有“p1…pk-1”=“pj-k+1…pj-1”則當pj

≠pk時，將模式串向右滑動，使第next[k]個字符和主串中的第j個字符相比較。若next[k]=k′，且pj=pk′

則：next[j+1]=k′+1=next[k]+1若pj

≠pk′，則使第next[k′]個字符和pj對齊，…依此類推。S1S2……Si-j+1……Si-j+k-1……Si-k+1……Si-1

Si…

≠

P1P2……Pk-1

……

Pj-k+1……Pj-1

Pj

≠

k=next[j]

P1……Pk-1

Pk

當Pj≠Pk時，Pj應(yīng)與那一個P比較？設(shè)與Pk’比較：則P1P2……Pk-1

……

Pj-kj+1……Pj-1

Pj

P1………Pk’-1

Pk’

即：k’=next[k]voidget_next(Sstring

T，int&next[])//求模式串T的next值并存入數(shù)組next[1..T[0]]中{

j=1；k=0；next[j]=k；//初始化while(j<T[0])

if(T[j]==T[k]||k==0)

{

k++；j++；

next[j]=k；//next[j+1]=k+1

}elsek=next[k];}//get_next

j12345678模式串

abaabcacnext[j]①初始化：k=0，j=1，

next[1]=0；②∵k=0,∴k++后k=1，j++后

j=2，next[2]=1③

∵t[2]≠t[1],∴k=next[k]=0，∴k++后k=1，j++(3),

next[3]=1④∵t[3]=t[1],∴k++后k=2，j++后

j=4,next[4]

=2⑤∵t[4]≠t[2],∴k=next[k]=1,∵t[4]=t[1],∴k=2，j=5,next[5]=2⑥∵t[5]=t[2],∴k++后k=3，j++后j=6,next[6]=3⑦∵t[6]≠t[3],∴k=next[k]=1,即：k=1，∵t[6]≠t[1]

,

∴k=next[k]=next[1]=0

，∵

k=0,

∴k=1，j=7,next[7]=1⑧∵t[7]=t[1],∴k++后k=2，j++后

j=8，

next[8]

=201122312前面定義的next函數(shù)尚有缺陷。例如：

j12345模式串：

aaaab

next[j]01