數(shù)據(jù)結(jié)構(gòu)與算法分析第四章字符串

Chapter4

String串的定義n(n>=0)個(gè)字符的有限序列S=‘a(chǎn)1,a2,……,an’

串名:s

串值:ai(1<=i<=n)

串長(zhǎng):n術(shù)語(yǔ)空串n=0的串子串串中若干相鄰字符組成的子序列主串包含子串的串空格串僅含有空格字符的串(n不為0)串相等設(shè)s1=‘a(chǎn)11,…,an1’s2=‘a(chǎn)12,…,an2’

若n1=n2且ai1=ai2（1<=i<=n1)

則s1=s2串的抽象數(shù)據(jù)類(lèi)型ADTString{

數(shù)據(jù)對(duì)象：D＝{ai|ai∈CharacterSet,i=1,2,...,n,n≥0}數(shù)據(jù)關(guān)系：R1＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}基本操作:

StrAssign(&T,chars)

StrCopy(&T,S)

DestroyString(&S)

StrEmpty(S)

StrCompare(S,T)

StrLength(S)

Concat(&T,S1,S2)SubString(&Sub,S,pos,len)

Index(S,T,pos)

Replace(&S,T,V)StrInsert(&S,pos,T)

StrDelete(&S,pos,len)

ClearString(&S)}ADTString

StrAssign(&T,chars)

初始條件：chars是字符串常量操作結(jié)果：把chars賦為T(mén)的值

StrCopy(&T,S)

初始條件：串S存在操作結(jié)果：由串S復(fù)制得串T

DestroyString(&S)

初始條件：串S存在操作結(jié)果：串S被銷(xiāo)毀

StrEmpty(S)

始條件：串S存在

操作結(jié)果：若S為空串，則返回

TRUE，否則返回

FALSE表示空串，空串的長(zhǎng)度為零

StrCompare(S,T)

初始條件：串S和T存在

操作結(jié)果：若ST，則返回值

0

若ST，則返回值

0

若ST，則返回值

0例如：StrCompare(data,state)<0StrCompare(cat,case)>0

StrLength(S)

初始條件：串S存在

操作結(jié)果：返回S的元素個(gè)數(shù)，

稱(chēng)為串的長(zhǎng)度

Concat(&T,S1,S2)

初始條件：串S1和S2存在

操作結(jié)果：用T返回由S1和S2

聯(lián)接而成的新串例如：Concate(T,man,kind)

求得T=mankind

SubString(&Sub,S,pos,len)初始條件：串S存在，1≤pos≤StrLength(S)

且0≤len≤StrLength(S)-pos+1操作結(jié)果：用Sub返回串S的第pos個(gè)字符起長(zhǎng)度為len的子串例如：

SubString(sub,commander,4,3)

求得sub=manSubString(sub,commander,1,9)求得sub=commanderSubString(sub,commander,9,1)求得sub=r子串為“串”中的一個(gè)字符子序列SubString(sub,commander,4,7)sub=?SubString(sub,beijing,7,2)=?sub=?SubString(student,5,0)=起始位置和子串長(zhǎng)度之間存在約束關(guān)系長(zhǎng)度為0的子串為“合法”串

Index(S,T,pos)

初始條件：串S和T存在，T是非空串，

1≤pos≤StrLength(S)

操作結(jié)果：若主串S中存在和串T值

相同的子串,則返回它在主

串S中第pos個(gè)

字符之后第一次出現(xiàn)的位

置；否則函數(shù)值為0

假設(shè)S=abcaabcaaabc,T=bca

Index(S,T,1)=2Index(S,T,3)=6Index(S,T,8)=0

“子串在主串中的位置”意指子串中的第一個(gè)字符在主串中的位序Replace(&S,T,V)

初始條件：串S,T和V均已存在，

且T是非空串

操作結(jié)果：用V替換主串S中出現(xiàn)

的所有與（模式串）T

相等的不重疊的子串假設(shè)S=abcaabcaaabca，T=bca若V=x，則經(jīng)置換后得到

S=axaxaax若V=bc，則經(jīng)置換后得到S=abcabcaabc

StrInsert(&S,pos,T)

初始條件：串S和T存在，

1≤pos≤StrLength(S)＋1

操作結(jié)果：在串S的第pos個(gè)字符之前插入串T例如：S=chater，T=rac，則執(zhí)行StrInsert(S,4,T)之后得到

S=character

StrDelete(&S,pos,len)

初始條件：串S存在

1≤pos≤StrLength(S)-len+1

操作結(jié)果：從串S中刪除第pos個(gè)字符

起長(zhǎng)度為len的子串

ClearString(&S)

初始條件：串S存在

操作結(jié)果：將S清為空串

在上述抽象數(shù)據(jù)類(lèi)型定義的13種操作中串賦值StrAssign、等六種操作串復(fù)制Strcopy、構(gòu)成串類(lèi)型串比較StrCompare、的最小操作求串長(zhǎng)StrLength、子集串聯(lián)接Concat

求子串SubString即：這些操作不可能利用其他串操作來(lái)實(shí)現(xiàn)，反之，其他串操作(除串清除ClearString和串銷(xiāo)毀DestroyString外）可在這個(gè)最小操作子集上實(shí)現(xiàn)StrCompare(SubString(S,i,StrLength(T)),T)?0

例如，可利用串比較、求串長(zhǎng)和求子串等操作實(shí)現(xiàn)定位函數(shù)Index(S,T,pos)。

S串

T串

T串iposn-m+1算法的基本思想為：intIndex(StringS,StringT,intpos){//T為非空串。若主串S中第pos個(gè)字符之后存在與T相等的子串，則返回第一個(gè)這樣的子串在S中的位置，否則返回0if(pos>0){n=StrLength(S);m=StrLength(T);i=pos;

while(i<=n-m+1){SubString(sub,S,i,m);if(StrCompare(sub,T)!=0)++i;elsereturni;}//while}//ifreturn0;//S中不存在與T相等的子串}//Index又如串的置換函數(shù)：

S串

T串

V串

V串pospos

subinews串sub

串的邏輯結(jié)構(gòu)和線(xiàn)性表極為相似，區(qū)別僅在于串的數(shù)據(jù)對(duì)象約束為字符集

串的基本操作和線(xiàn)性表有很大差別

在線(xiàn)性表的基本操作中，大多以“單個(gè)元素”作為操作對(duì)象在串的基本操作中，通常以“串的整體”作為操作對(duì)象

在程序設(shè)計(jì)語(yǔ)言中，串只是作為輸入或輸出的常量出現(xiàn)，則只需存儲(chǔ)此串的串值，即字符序列即可。但在多數(shù)非數(shù)值處理的程序中，串也以變量的形式出現(xiàn)串的表示和實(shí)現(xiàn)串的存儲(chǔ)結(jié)構(gòu)對(duì)串的存儲(chǔ)方式取決于我們對(duì)串所進(jìn)行的運(yùn)算，如果在程序設(shè)計(jì)語(yǔ)言中，串的運(yùn)算只是作為輸入或輸出的常量出現(xiàn)，則此時(shí)只需存儲(chǔ)該串的字符序列，這就是串值的存儲(chǔ)。此外，一個(gè)字符序列還可賦給一個(gè)串變量，操作運(yùn)算時(shí)通過(guò)串變量名訪(fǎng)問(wèn)串值。實(shí)現(xiàn)串名到串值的訪(fǎng)問(wèn)，在C++語(yǔ)言中可以有兩種方式：一是可以將串定義為字符型數(shù)組，數(shù)組名就是串名，串的存儲(chǔ)空間分配在編譯時(shí)完成，程序運(yùn)行時(shí)不能更改。這種方式為串的靜態(tài)存儲(chǔ)結(jié)構(gòu)。另一種是定義字符指針變量，存儲(chǔ)串值的首地址，通過(guò)字符指針變量名訪(fǎng)問(wèn)串值，串的存儲(chǔ)空間分配是在程序運(yùn)行時(shí)動(dòng)態(tài)分配的，這種方式稱(chēng)為串的動(dòng)態(tài)存儲(chǔ)結(jié)構(gòu)。

串值的存儲(chǔ)我們稱(chēng)串是一種特殊的線(xiàn)性表，因此串的存儲(chǔ)結(jié)構(gòu)表示也有兩種方法：靜態(tài)存儲(chǔ)采用順序存儲(chǔ)結(jié)構(gòu)，動(dòng)態(tài)存儲(chǔ)采用的是鏈?zhǔn)酱鎯?chǔ)和堆存儲(chǔ)結(jié)構(gòu)。1．串的靜態(tài)存儲(chǔ)結(jié)構(gòu)類(lèi)似于線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)，用一組地址連續(xù)的存儲(chǔ)單元存儲(chǔ)串值的字符序列。由于一個(gè)字符只占1個(gè)字節(jié)，而現(xiàn)在大多數(shù)計(jì)算機(jī)的存儲(chǔ)器地址是采用的字編址，一個(gè)字（即一個(gè)存儲(chǔ)單元）占多個(gè)字節(jié)，因此順序存儲(chǔ)結(jié)構(gòu)方式有兩種：（1）緊縮格式：即一個(gè)字節(jié)存儲(chǔ)一個(gè)字符。這種存儲(chǔ)方式可以在一個(gè)存儲(chǔ)單元中存放多個(gè)字符，充分地利用了存儲(chǔ)空間。但在串的操作運(yùn)算時(shí)，若要分離某一部分字符時(shí)，則變得非常麻煩。data└┘structure\0

圖4-1串值的緊縮格式存儲(chǔ)

圖4-1所示是以4個(gè)字節(jié)為一個(gè)存儲(chǔ)單元的存儲(chǔ)結(jié)構(gòu)，每個(gè)存儲(chǔ)單元可以存放4個(gè)字符。對(duì)于給定的串s=〃data└┘structure〃，在C++語(yǔ)言中采用字符＇\0＇作串值的結(jié)束符。串s的串值連同結(jié)束符的長(zhǎng)度共15，只需4個(gè)存儲(chǔ)單元。串值的緊縮格式存儲(chǔ)

由上述討論可知，串的順序存儲(chǔ)結(jié)構(gòu)有兩大不足之處：一是需事先預(yù)定義串的最大長(zhǎng)度，這在程序運(yùn)行前是很難估計(jì)的。二是由于定義了串的最大長(zhǎng)度，使得串的某些操作受限，如串的聯(lián)接運(yùn)算等。（2）非緊縮格式：這種方式是以一個(gè)存儲(chǔ)單元為單位，每個(gè)存儲(chǔ)單元僅存放一個(gè)字符。這種存儲(chǔ)方式的空間利用率較低，如一個(gè)存儲(chǔ)單元有4個(gè)字節(jié)，則空間利用率僅為25%。但這種存儲(chǔ)方式中不需要分離字符，因而程序處理字符的速度高。2．串的動(dòng)態(tài)存儲(chǔ)結(jié)構(gòu)我們知道，串的各種運(yùn)算與串的存儲(chǔ)結(jié)構(gòu)有著很大的關(guān)系，在隨機(jī)取子串時(shí)，順序存儲(chǔ)方式操作起來(lái)比較方便，而對(duì)串進(jìn)行插入、刪除等操作時(shí)，就會(huì)變得很復(fù)雜。因此，有必要采用串的動(dòng)態(tài)存儲(chǔ)方式。串的動(dòng)態(tài)存儲(chǔ)方式采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)和堆存儲(chǔ)結(jié)構(gòu)兩種形式：（1）鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)串的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中每個(gè)結(jié)點(diǎn)包含字符域和結(jié)點(diǎn)鏈接指針域，字符域用于存放字符，指針域用于存放指向下一個(gè)結(jié)點(diǎn)的指針，因此，串可用單鏈表表示。用單鏈表存放串，每個(gè)結(jié)點(diǎn)僅存儲(chǔ)一個(gè)字符，因此，每個(gè)結(jié)點(diǎn)的指針域所占空間比字符域所占空間要大得多。為了提高空間的利用率，我們可以使每個(gè)結(jié)點(diǎn)存放多個(gè)字符，稱(chēng)為塊鏈結(jié)構(gòu)每個(gè)結(jié)點(diǎn)存放4個(gè)字符。（2）堆存儲(chǔ)結(jié)構(gòu)堆存儲(chǔ)結(jié)構(gòu)的特點(diǎn)是，仍以一組空間足夠大的、地址連續(xù)的存儲(chǔ)單元存放串值字符序列，但它們的存儲(chǔ)空間是在程序執(zhí)行過(guò)程中動(dòng)態(tài)分配的。每當(dāng)產(chǎn)生一個(gè)新串時(shí)，系統(tǒng)就從剩余空間的起始處為串值分配一個(gè)長(zhǎng)度和串值長(zhǎng)度相等的存儲(chǔ)空間。串名的存儲(chǔ)映象串名的存儲(chǔ)映象就是建立了串名和串值之間的對(duì)應(yīng)關(guān)系的一個(gè)符號(hào)表。在這個(gè)表中的項(xiàng)目可以依據(jù)實(shí)際需要來(lái)設(shè)置，以能方便地存取串值為原則。如：s1=〃data〃s2=〃structure〃若符號(hào)表中每行包含有串名、串值的始地址、尾地址，也可以不設(shè)尾地址，而設(shè)置串和長(zhǎng)度值。

對(duì)于鏈?zhǔn)酱鎯?chǔ)串值的方式，如果要建立串變量的符號(hào)表，則只需要存入一個(gè)鏈表的表頭指針即可。

串的定長(zhǎng)順序存儲(chǔ)表示串的堆分配存儲(chǔ)表示串的塊鏈存儲(chǔ)表示

#defineMAXSTRLEN255//用戶(hù)可在255以?xún)?nèi)定義最大串長(zhǎng)

typedefunsignedcharSstring[MAXSTRLEN+1];//0號(hào)單元存放串的長(zhǎng)度串的定長(zhǎng)順序存儲(chǔ)表示

按這種串的表示方法實(shí)現(xiàn)的串的運(yùn)算時(shí)，其基本操作為“字符序列的復(fù)制”串的實(shí)際長(zhǎng)度可在這個(gè)予定義長(zhǎng)度的范圍內(nèi)隨意設(shè)定，超過(guò)予定義長(zhǎng)度的串值則被舍去，稱(chēng)之為“截?cái)唷碧攸c(diǎn):例如串的聯(lián)接算法中需分三種情況處理Concat(SStringS1,SStringS2,SString&T){

returnuncut;}//Concat

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];uncut=TRUE;}

if(S1[0]+S2[0]<=MAXSTRLEN){//未截?cái)?/p>

elseif(S1[0]<MAXSTRSIZE){//截?cái)?/p>

else{//截?cái)?僅取S1)T[1..S1[0]]=S1[1..S1[0]];T[S1[0]+1..MAXSTRLEN]=S2[1..MAXSTRLEN－S1[0]];T[0]=MAXSTRLEN;uncut=FALSE;}

T[0..MAXSTRLEN]=S1[0..MAXSTRLEN];T[0]==S1[0]==MAXSTRLEN;uncut=FALSE;}

clsssString{char*ch;//若是非空串，則按串長(zhǎng)分

//配存儲(chǔ)區(qū)，否則ch為NULLintlength;//串長(zhǎng)度

}串的堆分配存儲(chǔ)表示Concat(String&S,StringS1,StringS2){//用S返回由S1和S2聯(lián)接而成的新串if(S.ch)deleteS.ch;//釋放舊空間

if(!(S.ch=newchar[S1.length+S2.length]))exit(OVERFLOW);S.length=S1.length+S2.length;S.ch[0..S1.length-1]=S1.ch[0..S1.length-1];S.ch[S1.length..S.length-1]=S2.ch[0..S2.length-1];returnOK;}//ConcatSubString(String&Sub,StringS,intpos,intlen){//用Sub返回串S的第pos個(gè)字符起長(zhǎng)度為len的子串if(pos<1||pos>S.length||len<0||len>S.length-pos+1)returnERROR;

if(Sub.ch)deleteSub.ch;//釋放舊空間

if(!len)//空子串

{Sub.ch=NULL;Sub.length=0;}else{Sub.ch=newchar[len];Sub.ch[0..len-1]=S[pos-1..pos+len-2];Sub.length=len;}//完整子串

returnOK;}//SubString串的塊鏈存儲(chǔ)表示也可用鏈表來(lái)存儲(chǔ)串值，由于串的數(shù)據(jù)元素是一個(gè)字符，它只有8位二進(jìn)制數(shù)，因此用鏈表存儲(chǔ)時(shí)，通常一個(gè)結(jié)點(diǎn)中存放的不是一個(gè)字符，而是一個(gè)子串存儲(chǔ)密度

=

數(shù)據(jù)元素所占存儲(chǔ)位實(shí)際分配的存儲(chǔ)位

例如:在編輯系統(tǒng)中，整個(gè)文本編輯區(qū)可以看成是一個(gè)串，每一行是一個(gè)子串，構(gòu)成一個(gè)結(jié)點(diǎn)。即:同一行的串用定長(zhǎng)結(jié)構(gòu)(80個(gè)字符),行和行之間用指針相聯(lián)接實(shí)際應(yīng)用時(shí)，可以根據(jù)問(wèn)題所需來(lái)設(shè)置結(jié)點(diǎn)的大小

這是串的一種重要操作，很多軟件，若有“編輯”菜單項(xiàng)的話(huà)，則其中必有“查找”子菜單項(xiàng)串的模式匹配算法簡(jiǎn)單算法首尾匹配算法KMP(D.E.Knuth,V.R.Pratt,J.H.Morris)算法intIndex(SStringS,SStringT,intpos){//返回子串T在主串S中第pos個(gè)字符

//之后的位置。若不存在，則函數(shù)值

//為0。其中，T非空，

//1≤pos≤StrLength(S)i=pos;j=1;簡(jiǎn)單算法while(i<=S[0]&&j<=T[0]){if(S[i]==T[j]){++i;++j;}//繼續(xù)比較后繼字符

else{i=i-j+2;j=1;}}//指針后退重新開(kāi)始匹配

if(j>T[0])returni-T[0];elsereturn0;}//Index串的模式匹配定義在串中尋找子串（第一個(gè)字符）在串中的位置詞匯在模式匹配中，子串稱(chēng)為模式，串稱(chēng)為目標(biāo)。示例目標(biāo)T:“Beijing”模式P:“jin”匹配結(jié)果=3

第1趟

T abbaba窮舉的模式

P aba

匹配過(guò)程

第2趟

T abbaba P aba

第3趟

T abbaba P aba

第4趟

T abbaba Paba

intString::Find(String&pat)const{//窮舉的模式匹配

char*p=pat.ch,*s=ch;

inti=0;

if(*p&&*s) //當(dāng)兩串未檢測(cè)完

while(i<=curLen

-pat.curLen)

if(*p++==*s++)//比較串字符

if(!*p)

return

i;//相等

else{

i++;s=ch+i;p=pat.ch;} //對(duì)應(yīng)字符不相等，對(duì)齊目標(biāo)的 //下一位置，繼續(xù)比較

return

-1;

}

目標(biāo)

T

t0

t1

t2……tm-1…tn-1

模式

pat

p0

p1

p2……pm-1

目標(biāo)

T

t0

t1

t2……tm-1

tm…tn-1

模式

pat

p0

p1……pm-2pm-1

目標(biāo)

T

t0

t1……ti

ti+1……ti+m-2

ti+m-1…tn-1 ‖‖‖‖

模式

pat

p0

p1……pm-2pm-1改進(jìn)的模式匹配窮舉的模式匹配算法時(shí)間代價(jià)：最壞情況比較n-m+1趟，每趟比較m次，

總比較次數(shù)達(dá)(n-m+1)*m原因在于每趟重新比較時(shí)，目標(biāo)串的檢測(cè)指針要回退。改進(jìn)的模式匹配算法可使目標(biāo)串的檢測(cè)指針每趟不回退。改進(jìn)的模式匹配(KMP)算法的時(shí)間代價(jià)：若每趟第一個(gè)不匹配，比較n-m+1趟，總比較次數(shù)最壞達(dá)(n-m)+m=n若每趟第m個(gè)不匹配，總比較次數(shù)最壞亦達(dá)到n

Tt0

t1…ts-1

ts

ts+1

ts+2…ts+j-1

ts+j

ts+j+1…tn-1‖‖‖‖‖P

p0

p1

p2…pj-1

pjpj+1

則有

tsts+1

ts+2…ts+j

=p0

p1

p2…pj(1)

為使模式P與目標(biāo)T匹配，必須滿(mǎn)足

p0

p1

p2…pj-1…pm-1=ts+1

ts+2

ts+3…ts+j…ts+m

如果

p0

p1…pj-1

p1

p2…pj (2)

則立刻可以斷定

p0

p1…pj-1

ts+1

ts+2…ts+j

下一趟必不匹配同樣，若

p0

p1…pj-2

p2

p3…pj則再下一趟也不匹配，因?yàn)橛?/p>

p0

p1…pj-2

ts+2

ts+3…ts+j直到對(duì)于某一個(gè)“k”值，使得

p0

p1…pk+1

pj-k-1

pj-k

…pj

且

p0

p1…pk

=

pj-k

pj-k+1…pj則

p0

p1…pk

=ts+j-k

ts+j-k+1…ts+j‖‖‖

pj-k

pj-k+1…pjk的確定方法當(dāng)比較到模式第j個(gè)字符失配時(shí)，k的值與模式的前j個(gè)字符有關(guān)，與目標(biāo)無(wú)關(guān)。利用失效函數(shù)

f(j)可描述。利用失效函數(shù)f(j)的匹配處理如果j=0，則目標(biāo)指針加1，模式指針回到p0。如果j>0，則目標(biāo)指針不變，模式指針回到

pf(j-1)+1。若設(shè)

模式

P=p0p1…pm-2pm-1示例：確定失效函數(shù)

f(j)

運(yùn)用KMP算法的匹配過(guò)程第1趟目標(biāo)

acabaabaabcacaabc

模式

abaabcac

j=1

j=f(j-1)+1=0第2趟目標(biāo)acabaabaabcacaabc

模式

abaabcac

j=5

j=f(j-1)+1=2第3趟目標(biāo)acabaabaabcacaabc

模式

(ab)aabcac

int

String::fastFind(Stringpat)const{//帶失效函數(shù)的KMP匹配算法

int

posP=0,

posT=0;

int

lengthP=pat.curLen,lengthT=curLen;

while(posP<lengthP&&posT<lengthT)

if(pat.ch[posP]==ch[posT]){

posP++;posT++;//相等繼續(xù)比較

}elseif(posP==0)posT++;//不相等

elseposP=pat.f[posP-1]+1;

if(posP<lengthP)return

-1;

else

return

posT-lengthP; }計(jì)算失效函數(shù)f[j]的方法首先確定f[0]=-1，再利用f[j]求f[j+1]。其中,f(1)[j]=f[j],

f

(m)[j]=f[f

(m-1)[j]]

f[0]=

-1;j=1時(shí),f[0]+1=0,p0

p1,f[1]=-1;j=2時(shí),f[1]+1=0,p0

=p2,f[2]=f[1]+1=0;j=3時(shí),f[2]+1=1,p1

p3,

f[1]+1=0,p0

=p3,f[3]=f[1]+1=0;j=4時(shí),f[3]+1=1,p1

=p4,f[4]=f[3]+1=1;void

String::fail(){//計(jì)算失效函數(shù)

int

lengthP=curLen;

f[0]=

-1;//直接賦值

for(intj=1;j<lengthP;j++){//依次求f[j]

inti=f[j-1];

while(*(ch+j)

!=*(ch+i+1)

&&i>=0)

i=f[i]; //遞推

if(*(ch+j