數據結構第4章(新)

數據結構0第4章串4.1串類型的定義4.2串的表示和實現(xiàn)4.3串的模式匹配算法數據結構14.1串類型的定義1.基本概念串(字符串)String：是零個或多個字符組成的有限序列。一般記為：S=‘a1a2...an’(n≥0)

棧、隊列：操作受限的線性表。串：取值范圍受限的線性表，數據對象約束為字符集。其中S是串的名字,用單引號括起來的字符序列是串的值，ai(1≤i≤n)可以是字母、數字或其它字符。串的長度：串中字符的個數n?？沾?NullString)：n=0時的串稱為空串，用符號“

”表示。數據結構2下面是一些串的例子：

（1）a=‘LIMING’

（2）b=‘PEJINGUNIUERCITY’

（3）c=‘DATASTRUCTURE’

（4）d=‘’

（5）e=‘’

說明：串中包含的字符個數，稱為串的長度。

長度為0的串稱為空串，它不包括任何字符，上面（4）中的串d是空串,，(5)中的e是包含一個空格符的空格串；串中所包含的字符可以是字母、數字或其他字符，這依賴于具體計算機所允許的字符集。另外,通常以字符在序列中的序號為該字符在串中的位置數據結構3子串：串中任意個連續(xù)的字符組成的子序列稱為該串的子串?！?/p>

”為任意串的子串。主串：包含子串的串相應地稱為主串。

S為一長度為n的串，其中的字符各不相同，則S的所有子串的個數：

S中互異的非平凡子串（非空且不同于S本身）的個數：特別地，空串是任意串的子串，任意串是其自身的子串。數據結構4位置：字符在串中的序號稱為該字符在串中的位置。子串在主串中的位置則以子串的第一個字符在主串中的位置來表示。

A=‘ChinaBeijing’,B=‘Beijing’,C=‘China’,則它們的長度分別為13、7和5。B和C是A的子串,B在A中的位置是7,C在A中的位置是1。串相等：當且僅當兩個串的值相等時,稱這兩個串是相等的，即只有當兩個串的長度相等,并且每個對應位置的字符都相等時才相等?？崭翊河梢粋€或多個空格組成的串。與空串不同。數據結構52.串的基本運算:

串賦值StrAssign(&T,chars)

初始條件:chars是字符串常量。操作結果:生成一個值等于chars的串T。串比較StrCompare(S,T)

初始條件:串S和T存在。操作結果:若S>T,則返回值>0;如S=T,則返回值=0;

若S<T,則返回值<0。"串值大小"是按"詞典次序"進行比較的;只有在兩個串的長度相等且每個字符一一對等的情況下稱兩個串相等。

數據結構6求串長StrLength(S)

初始條件:串S存在。操作結果:返回串S的長度,即串S中的元素個數。串聯(lián)接Concat(&T,S1,S2)

初始條件:串S1和S2存在。操作結果:將T返回由S1和S2聯(lián)接而成的新串。"串聯(lián)接"操作的結果是生成一個新的串，其值是"將第二的串的第一個字符緊接在第一個串的最后一個字符之后"得到的字符序列。

數據結構7求子串SubString(&Sub,S,pos,len)

初始條件:串S存在,1≤pos≤StrLength(S)且

1≤len≤StrLength(S)-pos+1。操作結果:用Sub返回串S的第pos個字符起長度為len的子串。"子串"指串中任意個連續(xù)的字符組成的子序列。如：操作SubString(Sub,"commander",4,3)得到的結果是Sub="man"。顯然必須在滿足初始條件中規(guī)定的"起始位置"和"長度"之間的約束關系時才能求得一個合法的子串。允許len的下限為0是由于空串也是合法串，但實際上求長度為0的子串是沒有意義的。數據結構8定位函數intIndex(StringS,StringT,intpos)//T為非空串。若主串S中第pos個字符之后存在與T相等的子//串，則返回第一個這樣的子串在S中的位置，否則返回0。{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;}}return0;}數據結構94.2串的表示和實現(xiàn)1.定長順序存儲表示（定長順序串）＃defineMAXSTRLEN255typedefunsignedcharSString[MAXSTRLEN+1];定長順序串的存儲分配是在編譯時完成的。與前面所講的線性表的順序存儲結構類似,用一組地址連續(xù)的存儲單元存儲串的字符序列。串長的表示：①以下標為0的數組分量存放串的實際長度；②串值后加入一個不計入串長的結束標記字符，C中“\0”表串值的終結，其ASCⅡ碼值為0。超出予定義長度的串值被舍去，稱之為“截斷”。數據結構10串聯(lián)接Concat(SString&T,SString

S1,SString

S2)S1[0]+S2[0]≤MAXSTRLEN，T是正確的結果。S1[0]<MAXSTRLEN，而S1[0]+S2[0]>MAXSTRLE

則S2會有部分字符被舍棄。(3)S1[0]=MAXSTRLEN，則S2的全部字符被舍棄，T與S1相等。思考:課本是否有錯誤,是否遺漏了S1[0]>MAXSTRLEN數據結構11StatusConcat(SString&T,SStringS1,SStringS2){//S1,S2聯(lián)接后成為新串送入T,0下標變量存

//放串的長度。if(s1[0]+s2[0]<=MAXSTRLEN){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;}

S1S2

TT[0]MAXSTRLEN1558?數據結構12elseif(s1[0]<MAXSTRLEN){T[1..S1[0]]=S1[1..S1[0]];T[S1[0]+1..MAXSTRLEN]=S2[1..MAXSTRLEN-S1[0]];T[0]=MAXSTRLEN;uncut=FALSE;}

S1S2

TMAXSTRLEN1058?數據結構13else{T[1..MAXSTRLEN]=S1[1..MAXSTRLEN];T[0]=MAXSTRLEN;uncut=FALSE;}returnuncut;}//Concat高級語言中，可以觀察到串在存儲空間不夠時會自動截取，并不報錯，故這里并不擴展空間。T

S1S2

MAXSTRLEN:558?數據結構14求子串Status

SubString(SString&Sub,SStringS,intpos,intlen){if(pos<0||pos>S[0]||len<0||len>S[0]-pos+1)returnERROR;Sub[1..len]=S[pos..pos+len-1];Sub[0]=len;returnOK;}

“字符序列的復制”數據結構15思考：StrCopy如何實現(xiàn)？StatusStrCopy(SString&T,SStringS){}數據結構16S.lengthnS.ch01pos-1n-1n+m-1S.lengthn+mS.lengthn01pos-1n-1S.chT.chT.lengthm0

1m-1為串S重新分配存儲空間,并將S復制到新空間將S的第pos個字符及后面的字符后移，為插入T騰出位置插入T修改串長串插入：在串S的第pos個字符前插入串T數據結構17串插入StatusStrInsert(HString&S,intpos,HStringT)//在串S的pos個字符之前插入串T{if(pos<1||pos>S.length+1)returnERROR;//插入位置不適

if(T.length){if(!(S.ch=(char*)realloc(S.ch,(S.length+T.length)*sizeof(char)))exit(OVERFLOW);for(i=S.length-1;i>=pos-1;--i)S.ch[i+T.length]=S.ch[i];S.ch[pos-1..pos+T.length-2]=T.ch[0..T.length-1];S.length+=T.length;}returnOK;}數據結構182.堆分配存儲表示（堆串）在C語言中，已經有一個稱為“堆”的自由存儲空間，并可用malloc（）和free（）函數完成動態(tài)存儲管理。typedefstruct{char*ch；

intlength；}HString；

比較：

#defineMAXSTRLEN255typedefunsignedcharSString[MAXSTRLEN+1];

數據結構193.串的塊鏈存儲表示（鏈串）＃defineCHUNKSIZE<大小>typedefstructChunk{charch[CHUNKSIZE];structChunk*next;}Chunk;typedefstruct{Chunk*head;Chunk*tail;intcurlen;}LString;數據結構20存儲密度大，一些操作（如插入，刪除）有所不便，引起大量字符移動，適合于在串基本保持靜態(tài)使用方式時采用；存儲密度小，運算處理方便，但存儲空間量大，若處理過程中，需大量內外存交換，會影響總效率；串的字符集的大小，也會影響串值存儲方式的選取。數據結構21總結（1）空串與空格串是不相同的，空串的長度為0，空格串的長度為包含的空格個數。（2）串是有限個字符的序列，是一種取值范圍受限的特殊的線性表。數據結構221.樸素模式匹配算法求子串位置的定位函數Index(S,T,pos).模式匹配：子串的定位操作通常稱作串的模式匹配。目標串：主串S。模式串：子串T。匹配成功：若存在T的每個字符依次和S中的一個連續(xù)字符序列相等，則稱匹配成功。返回T中第一個字符在S中的位置。匹配不成功：返回0。4.3串的模式匹配算法數據結構23第1趟 S abbabaT aba

第2趟 S abbaba T aba

第3趟

S abbaba T aba

第4趟 S abbaba Taba

窮舉的模式匹配過程i=i-j+2;j=1;↑j↓i數據結構24子串定位intIndex(SStringS,SStringT,intpos){i=pos;j=1;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])returni-T[0];elsereturn0;}數據結構25樸素模式匹配算法的時間復雜度主串長n；子串長m?？赡芷ヅ涑晒Φ奈恢茫?~n-m+1)。①最好的情況下，第i個位置匹配成功，比較了（i-1+m）次，平均比較次數：最好情況下算法的平均時間復雜度O(n+m)。②最壞的情況下，第i個位置匹配成功，比較了（i*m）次，平均比較次數：設n>>m，最壞情況下的平均時間復雜度為O(n*m)。數據結構26分析算法的思想：

從主串S的第pos個字符起和模式的第一個字符比較，若相等，繼續(xù)比較后續(xù)字符，否則從主串的下一個字符起再重新和模式的字符比較。以此類推，直到模式T中的每個字符依次和主串S中的一個連續(xù)的字符序列相等，則匹配成功，函數返回T首字符在S中的位置；否則匹配不成功。問題：當主串與模式串存在多次部分匹配時，就顯得效率低下。如0、1串在T=“00001”,S=“0000000000001”時，每次都有四次的多余比較，而0、1串又是普遍存在的。4.3串的模式匹配算法數據結構272.模式匹配的改進算法-KMP算法

KMP算法是D.E.Knuth、J.H.Morris和V.R.Pratt共同提出的,簡稱KMP算法。該算法主要是消除了主串指針的回溯,從而使算法效率有了某種程度的提高。因p1≠p2,s2=p2,必有s2≠p1,又因p1=p3,s3=p3,所以必有s3=p1。因此,第二次匹配可直接從i=4,j=2開始。數據結構28改進：每趟匹配過程中出現(xiàn)字符比較不等時，不回溯主指針i，利用已得到的“部分匹配”結果將模式向右滑動盡可能遠的一段距離，繼續(xù)進行比較。數據結構29s1s2s3…si-j+1si-j+2…si-2si-1sisi+1‖‖‖‖≠

p1p2…pj-2pj-1pjpj+1(在j處匹配不成功)‖‖

p1…pk-1pkpk+1①“pj-k+1pj-k+2…pj-1”=“si-k+1si-k+2…si-1”（部分匹配）②“p1p2…pk-1”=“si-k+1si-k+2…si-1”(k為下一次要與i匹配的位置)③“p1p2…pk-1”=“pj-k+1pj-k+2…pj-1”(真子串）數據結構30

max{k|1<k<j,且“p1…pk-1”=“pj-k+1…pj-1”}

當此集合非空時

0當j=1時

1其他情況next[j]=為此,定義next[j]函數，表明當模式中第j個字符與主串中相應字符“失配”時，在模式中需重新和主串中該字符進行比較的字符的位置。數據結構31

0當j=1時

Next[j]=M{k|1<k<j且‘p1p2…pk-1’=‘pj-k+1pj-k+2…pj-1’}1其它情況例：j12345678

模式串abaabcacnext[j]01122312練習：求下列串的next函數值串：s=“abacabaaad”

0112123422數據結構32voidget_next(charT[],intnext[])

{

//求模式串T的next函數值并存入數組next。

i=1;next[1]=0;j=0;

while(T[j]!='\0'){

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

{++i;++j;next[i]=j;}

elsej=next[j];

}

}//get_next

數據結構33intIndex_KMP(SStringS,SStringT,intpos){i=pos,j=1;while(i<S[0]&&j<T[0]){if(j==0||S[i]==T[j]){i++;j++;}else

j=next[j];/*i不變,j后退*/}if(j>T[0])returni-T[0];/*匹配成功*/elsereturn0; /*返回不匹配標志*/}數據結構343、模式匹配的KMP算法

i=2

第一趟主串:acabaabaabcacaabc

子串

abj=2next[2]=1i=2第二趟主串:acabaabaabcacaabc

子串aj=1next[1]=0i=3i=8第三趟主串:acabaabaabcacaabc

子串abaabcj=1j=6next[6]=3i=8i=14第四趟主串:acabaabaabcacaabc

子串abaabcacj=3j=9圖4.9利用模式的next函數進行匹配的過程示例參看演示程序

j12345678模式串abaabcacnext[j]01122312數據結構35j1234567891011121314151617模式串abcaabbcabcaabdab0next[j]1112231123456712數據結構36next函數的改進j12345模式aaaabnext