串類型的定義

第四章串4.1串類型的定義4.2串的表示和實現(xiàn)4.2.1定長順序存儲表示4.2.2堆分配存儲表示4.2.3串的塊鏈存儲表示4.3串的模式匹配一、串及串的基本概念

串(String)即字符串，是由零個或多個字符組成的有限序列，是數(shù)據(jù)元素為單個字符的特殊線性表。記為：

S=‘a(chǎn)1a2…an’(n≥0)

串名串值（用‘’括起來）隱含結(jié)束符‘/0’，即ASCII碼NULL4.1串類型的定義串長：串中字符個數(shù)（n≥0）.n=0時稱為空串，記?？崭翊河梢粋€或多個空格符組成的串。子串：串S中任意個連續(xù)的字符序列叫S的子串;S叫主串。子串位置：子串的第一個字符在主串中的序號。串相等：串長度相等，且對應(yīng)位置上字符也相等。術(shù)語：1.空串和空格串有無區(qū)別？

有區(qū)別?？沾?NullString)是指長度為零的串；而空格串(BlankString)是指包含一個或多個空格的字符串.2.現(xiàn)有以下4個字符串：

a=‘BEI’ b=‘JING’c=‘BEIJING’d=‘BEIJING’問：①他們各自的長度？

②b是哪個串的子串？它在主串中的位置是多少？例：ADTString{數(shù)據(jù)對象:

D={ai|ai∈CharacterSet,i=1,2,…，n,n≥0}數(shù)據(jù)關(guān)系:

R={<ai-1,ai>|ai-1,ai∈D,i=2,…，n}基本操作：//有13個

二、串的抽象數(shù)據(jù)類型定義StrCopy(&T,S)

初始條件：串S存在。

操作結(jié)果：由串S復(fù)制得串T。二、串的抽象數(shù)據(jù)類型定義

StrAssign(&T,chars)

初始條件：chars是字符串常量。

操作結(jié)果：生成一個值為chars的串T。StrEmpty(S)

初始條件：串S存在。

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

否則返回FALSE。二、串的抽象數(shù)據(jù)類型定義

DestroyString(&S)

初始條件：串S存在。

操作結(jié)果：串S被銷毀。例如：StrCompare(data,state)<0StrCompare(cat,case)>0StrCompare(S,T)

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

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

若ST，則返回值0；

若ST，則返回值0。二、串的抽象數(shù)據(jù)類型定義StrLength(S)

初始條件：串S存在。

操作結(jié)果：返回S的元素個數(shù),稱為串的長度。二、串的抽象數(shù)據(jù)類型定義Concat(&T,S1,S2)

初始條件：串S1和S2存在。

操作結(jié)果：用T返回由S1和S2聯(lián)接而成的新串。

或Concat(S1,S2)

用S1返回由S1和S2聯(lián)接而成的新串。例如：S1=man,S2=kindConcat(T，S1，S2)

求得T=mankind或Concat(S1,S2)

求得S1=mankind二、串的抽象數(shù)據(jù)類型定義

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

且0≤len≤StrLength(S)-pos+1。操作結(jié)果：用Sub返回串S的第pos個字符起長度為len的子串。例如：SubString(sub,commander,4,3)

求得sub=man;二、串的抽象數(shù)據(jù)類型定義Index(S,T,pos)//求子串序號

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

1≤pos≤StrLength(S)。

操作結(jié)果：若主串S中存在和串T值相同的子串,則返回T在主串S中第pos個字符之后第一次出現(xiàn)的位置;

否則函數(shù)值為0。

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

Index(S,T,1)=2;Index(S,T,3)=6;Index(S,T,8)=0;二、串的抽象數(shù)據(jù)類型定義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二、串的抽象數(shù)據(jù)類型定義StrInsert(&S,pos,T)

初始條件：串S和T存在，1≤pos≤StrLength(S)＋1。

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

S=character二、串的抽象數(shù)據(jù)類型定義StrDelete(&S,pos,len)

初始條件：串S存在1≤pos≤StrLength(S)-len+1。

操作結(jié)果：從串S中刪除第pos個字符起長度為len的子串。

ClearString(&S)

初始條件：串S存在。

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

二、串的抽象數(shù)據(jù)類型定義對于串的基本操作集可以有不同的定義方法。在上述抽象數(shù)據(jù)類型定義的13種操作中，串賦值StrAssign、串比較StrCompare、求串長StrLength、串聯(lián)接Concat以及求子串SubString等五種操作構(gòu)成串類型的最小操作子集，這些操作不可能利用其它串操作來實現(xiàn).其它串操作可在這個最小操作子集上實現(xiàn)。二、串的抽象數(shù)據(jù)類型定義intIndex(StringS,StringT,intpos){

if(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串的邏輯結(jié)構(gòu)和線性表極為相似，區(qū)別僅在于串的數(shù)據(jù)對象約束為字符集。

串的基本操作和線性表有很大差別。在線性表的基本操作中，大多以“單個元素”作為操作對象；在串的基本操作中，通常以“串的整體”作為操作對象。4.2 串的表示和實現(xiàn)定長順序存儲表示——用一組地址連續(xù)的存儲單元存儲串值的字符序列堆分配存儲表示——用一組地址連續(xù)的存儲單元存儲串值的字符序列,但存儲空間是在程序執(zhí)行過程中動態(tài)分配而得。串的塊鏈存儲表示——鏈?zhǔn)椒绞酱鎯Υ腥N表示方法：順序存儲鏈?zhǔn)酱鎯τ靡唤M連續(xù)的存儲單元來存放串，直接使用定長的字符數(shù)組來定義，數(shù)組的上界預(yù)先給出，故稱為靜態(tài)存儲分配。例如：#defineMAXSTRLEN255//用戶可用的最大串長

typedefunsignedcharSString[MAXSTRLEN＋1];

SStringS;//S是一個可容納255個字符的順序串。一、定長順序存儲一般用SString[0]來存放串長信息；C語言約定在串尾加結(jié)束符‘\0’，但不計入串長；若字符串超過MAXSTRLEN,

則自動截斷（因為靜態(tài)數(shù)組存不進去）。算法描述兩串連接Concat(&T,S1,S2)(算法4.2)用T返回S1和S2連接成的新串.

StatusConcat(SString&T,SStringS1,SStringS2,){

//用T返回由S1和S2聯(lián)接而成的新串。若未截斷,則返回TRUE，否則FALSE。

returnuncut;}//Concat串的聯(lián)接算法中需分三種情況處理：

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)

{//未截斷

elseif

(S1[0]<MAXSTRLEN{//截斷

else{//截斷(僅取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];uncut=FALSE;

}求子串SubString(&Sub,S,pos,len)將串S中從第pos個字符開始長度為len的字符序列復(fù)制到串Sub中（注：串Sub的預(yù)留長度與S一樣）求子串函數(shù)SubString(&Sub,S,pos,len)

StatusSubString(SString&sub,SStringS,intpos,intlen){if(pos<1||pos>S[0]||len<0||len>S[0]-pos+1)returnERROR;//pos和len不合法則告警

Sub[1……len]=S[pos…pos+len-1];Sub[0]=len;returnOK;}s=‘a(chǎn)1,a2,……..,an’poslen討論：想存放超長字符串怎么辦？——靜態(tài)數(shù)組有缺陷！改用動態(tài)分配的一維數(shù)組——“堆”！思路：利用malloc函數(shù)合理預(yù)設(shè)串長空間。特點：

若在操作中串值改變，還可以利用realloc函數(shù)按新串長度增加(堆砌)空間。Typedefstruct{char*ch;//

若非空串,按串長分配空間;否則ch=NULLintlength;//串長度}HString仍用一組連續(xù)的存儲單元來存放串，但存儲空間是在程序執(zhí)行過程中動態(tài)分配而得。二、堆分配存儲StatusStrInsert(HString&S,intpos,HStringT){

//在串S的第pos個字符之前（包括尾部）插入串Tif(pos<1||pos>S.length+1)returnERROR;//pos不合法則告警

if(T.length){//只要串T不空，就需要重新分配S空間，以便插入TS.ch=(char*)realloc(S.ch,(S.length+T.length)*sizeof(char))；for(i=S.length-1;i>=pos-1;--i)//為插入T而騰出pos之后的位置

S.ch[i+T.length]=S.ch[i];//從S的pos位置起全部字符均后移

S.ch[pos-1…pos+T.length-2]=T.ch[0…T.length-1];//插入T，略/0

S.length+=T.length;//刷新S串長度} returnOK;}//StrInsert例：用“堆”實現(xiàn)串插入操作(教材P75)

StatusStrAssign(HString&T,char*chars){ if(T.ch)free(T.ch); for(i=0,c=chars;c;++i,++c);//求串chars的長度

if(!i){T.ch=NULL;T.length=0;} else{ T.ch=(char*)malloc(i*sizeof(char))； T.ch[0..i-1]=chars[0..i-1];

T.length=i; } returnOK;}//StrAssign附：堆分配存儲表示直到終值為“假”停止，串尾特征是‘/0’＝NULL=0討論：方法1存儲密度為

；方法2存儲密度為

；若數(shù)據(jù)元素很多，用方法2存儲更優(yōu)—稱為塊鏈結(jié)構(gòu)三、鏈?zhǔn)酱鎯Γ河面湵泶鎯Υ担撞迦牒蛣h除。方法1：鏈表結(jié)點（數(shù)據(jù)域）大小取1方法2：鏈表結(jié)點（數(shù)據(jù)域）大小取n(例如n=4)1/51/2

A

B

C

I

NULLheadheadABCDEFGHI###NULL#defineCHUNKSIZE80

//可由用戶定義的塊大小typedefstructChunk{//首先定義結(jié)點類型

charch[CHUNKSIZE];//結(jié)點中的數(shù)據(jù)域

structChunk*next;//結(jié)點中的指針域}Chunk;塊鏈類型定義：typedefstruct{//其次定義用鏈?zhǔn)酱鎯Φ拇愋?/p>

Chunk*head;//頭指針

Chunk*tail;//尾指針

intcurLen;//串的當(dāng)前長度}LString;算法目的：確定主串中所含子串第一次出現(xiàn)的位置（定位）——即如何實現(xiàn)Index(S,T,pos)函數(shù)4.3串的模式匹配算法模式匹配(PatternMatching)即子串定位運算（Index函數(shù)）。注：S稱為被匹配的串，T稱為模式串。若S包含串T，則稱“匹配成功”,否則稱“匹配不成功”。

BF算法(又稱古典或經(jīng)典的、樸素的、窮舉的)

KMP算法（特點：速度快）算法種類：S=‘a(chǎn)babcabcacbab’T=‘a(chǎn)bcac’pos=54.3串的模式匹配算法返回值為6①設(shè)計思想：將主串的第pos個字符和模式串的第1個字符比較，若相等，繼續(xù)逐個比較后續(xù)字符；若不等，從主串的下一字符起，重新與模式的第一個字符比較。直到主串的一個連續(xù)子串字符序列與模式串相等。返回值為S中與T匹配的子串中第一個字符的序號，即匹配成功。否則，匹配失敗，返回值0.一.BF算法②BF算法的實現(xiàn)S=‘a(chǎn)babcabcacbab’T=‘a(chǎn)bcac’pos=5IntIndex(SStringS,SStringT,intpos){i=pos;j=1;while(i<=S[0]&&j<=T[0]){if(S[i]==T[j]){++i;++j;}//繼續(xù)比較后續(xù)字符

else{i=i-j+2;j=1;}//指針回溯到下一首位，重新開始匹配 }

if(j>T[0])returni-T[0];//子串結(jié)束，說明匹配成功

elsereturn0;}//Index相當(dāng)于子串向右滑動一個字符位置匹配成功后指針仍要回溯！因為要返回的是被匹配的首個字符位置。ij討論：BF匹配算法最壞的情況下需要比較字符的總次數(shù)例：S=aaaaaaab,T=aab,pos=1n=8,m=3最壞情況是：主串前面8-3個位置都部分匹配到子串的最后一位，即這5位比較了3次，最后3位也各比較了一次，還要加上3！比較字符的次數(shù)為：5*3+3=18次若n為主串長度，m為子串長度，則串的BF匹配算法最壞的情況下需要比較字符的總次數(shù)為(n-m+1)*m＝O(n*m)最壞情況是：主串前面n-m個位置都部分匹配到子串的最后一位，即這n-m位比較了m次，別忘了最后m位也各比較了一次，還要加上m！BF匹配算法的最壞時間復(fù)雜度但一般情況下BF算法的時間復(fù)雜度為O(n+m)二、KMP算法（特點：速度快）①

KMP算法設(shè)計思想②KMP算法的推導(dǎo)過程③

KMP算法的實現(xiàn)

（關(guān)鍵技術(shù):計算next[j]）④

KMP算法的時間復(fù)雜度主串S的指針i不必回溯！模式T的指針k向前滑動?？商崴俚絆(n+m)?、貹MP算法設(shè)計思想S=‘a(chǎn)babcabcacbab’T=‘a(chǎn)bcac’S=‘a(chǎn)b

abcabcacbab’T=‘a(chǎn)bcac’S=‘a(chǎn)b

abca

bcacbab’T=‘a(chǎn)

bcac’Index_kmp的返回值應(yīng)為i=6需要解決的問題：如何由“記憶”結(jié)果計算出主串S第i個字符應(yīng)該與模式T中哪個字符再比較？即確定模式T中的新比較起點k.iiikk

ab

aa

b

c②KMP算法的推導(dǎo)過程解釋:設(shè)主串為S=‘S1S2…Sn’,

模式串為T=‘T1T2…Tm’S1S2…Si-j+1Si-j+2…Si-k+1…Si-j+kSi-j+k+1…Si-2Si-1SiSi+1…T1T2…Tj-k+1…TkTk+1…Tj-2Tj-1

Tj=

=

=

=

=

=

=

≠

T1…

Tk-(j-k)Tk-(j-k-1)…Tk-2Tk-1TkS1S2…Si-j+1Si-j+2…Si-k+1…Si-j+kSi-j+k+1….Si-2Si-1SiSi+1…=

=

=

=

=

所以‘T1T2…Tk-1

’=‘Tj-k+1Tj-k+2…Tj-1’

Si與

Tj

處失配設(shè)T向前滑動j-k,Si與Tk比較②KMP算法的推導(dǎo)過程(續(xù)）：根據(jù)模式串T的規(guī)律：‘T1…Tk-1’=‘Tj-(k-1)…Tj-1’和已知的當(dāng)前失配位置j，可以歸納出計算新起點

k的表達式。令next[j]=k，則next[j]表明當(dāng)?shù)趈個字符與主串中相應(yīng)字符“失配”時，在模式中需要重新和主串中字符進行比較的字符的位置。next[j]＝0當(dāng)j＝1時max

{

k

|1<k<j且‘T1…Tk-1’=‘Tj-(k-1)…Tj-1’}1其他情況例：模式串T：abaabcac

可能失配位

j：12345678新匹配位next[j]:next[j]＝0當(dāng)j＝1時max{k|1<k<j且‘T1…Tk-1’=‘Tj-(k-1)…Tj-1’}1其他情況01122312討論：j=1時,next[j]≡

0；因為屬于“j=1”;剛才已歸納：j=3時,k={2}，只需查看‘T1’=‘T2’；因不滿足，屬于其他情況j=4時,k={2,3}，k=2時查看‘T1’=‘T3’,k=3時查看‘T1T2’=‘T2T3’

j=5時,k={2,3,4}，k=2時查看‘T1’=‘T4’(滿足)k=3時查看‘T1T2’=‘T3T4’(不滿足)

k=4時查看‘T1T2T3’=‘T2T3T4’

j=2時,next[j]≡

1；因為屬于“其他情況”；例：模式串T：ababaaca

可能失配位

j：12345678新匹配位next[j]:01123411討論：j=1時,next[j]≡

0；因為屬于“j=1”;j=2時,next[j]≡

1；因為屬于“其他情況”；j=3時,k={2}，只需查看‘T1’=‘T2’；屬于其他情況j=4時,k={2,3}，要查看‘T1’=‘T3’,‘T1T2’=‘T2T3’j=5時,k={2,3,4}，要查看T1=T4,T1T2=T3T4,T1T2T3=T2T3T4

j=6時,k={2,3,4,5}，要查看‘T1’=‘T5’、‘T1T2’=‘T4T5’、

‘T1T2T3’=‘T3T4T5’,‘T1T2T3T4’=‘T2T3T4T5’計算next[j]的算法如下void

get_next(SStringT,int&next[]){

//next函數(shù)值存入數(shù)組nexti=1;j=0;next[1]=0;while(i<T[0]){if(j==0||T[i]==T[j]){++i;++j;next[i]=j;}elsej=next[j];}}//get_next計算next[j]的時間為O(m)演示程序第一步，先把模式T所有可能的失配點j所對應(yīng)的next[j]計算出來；第二步：執(zhí)行定位函數(shù)index_kmp（與BF算法模塊非常相似）③KMP算法的實現(xiàn)—即Index()操作的實現(xiàn)

（見教材P82）

Int

Index_KMP(SStringS,SStringT,intpos){

i=pos;j=1;while(i<=S[0]&&j<=T[0]){

if(j==0||

S[i]==T[j]){++i；++j;}

//不失配則繼續(xù)比較后續(xù)字符

else{j=next[j];}//S的i指針不回溯，從T的k位置開始匹配}

if(j>T[0])return

i-T[0];//子串結(jié)束，說明匹配成功

elsereturn0;}//Index_KMP演示程序next函數(shù)的改進算法前面定義的next函數(shù)在某些情況下還是有缺陷例如：模式aaaab與主串a(chǎn)aabaaaab匹配情況：模式：aaaabj：12345

nex