4￥-four(天津科技大學(xué))

第四章串4.1串類型的定義4.2串的表示和實(shí)現(xiàn)

4.2.1定長(zhǎng)順序存儲(chǔ)表示

4.2.2堆分配存儲(chǔ)表示

4.2.3串的塊鏈存儲(chǔ)表示4.3串的模式匹配算法4.4串操作應(yīng)用舉例—文本編輯1/22/20251第四章串4.1串類型的定義基本概念

串(String)是由零個(gè)或多個(gè)字符組成的有限序列。一般記作S=‘a(chǎn)1a2a3…an’，其中S是串名，單引號(hào)括起來(lái)的字符序列是串值；ai(1≦i≦n)可以是字母、數(shù)字或其它字符；串中所包含的字符個(gè)數(shù)稱為該串的長(zhǎng)度。

空串(EmptyString)：長(zhǎng)度為零的串。它不包含任何字符。

空格串(BlankString)：由一個(gè)或多個(gè)空格組成的串。注意：空串和空格串的不同。1/22/20252第四章串基本概念（續(xù)）子串：串中任意個(gè)連續(xù)字符組成的子序列。主串：包含子串的串。通常將子串在主串中首次出現(xiàn)時(shí)的該子串的首字符對(duì)應(yīng)的主串中的序號(hào)，定義為子串在主串中的序號(hào)（或位置）。例如，設(shè)A和B分別為

A=“Thisisastring”B=“is”

則B是A的子串，A為主串。B在A中出現(xiàn)了兩次，其中首次出現(xiàn)所對(duì)應(yīng)的主串位置是3。因此，稱B在A中的序號(hào)（或位置）為3。特別地，空串是任意串的子串，任意串是其自身的子串。1/22/20253第四章串基本概念（續(xù)）通常在程序中使用的串可分為兩種：串變量和串常量。串常量和整常數(shù)、實(shí)常數(shù)一樣，在程序中只能被引用但不能不能改變其值，即只能讀不能寫。通常串常量是由直接量來(lái)表示的，例如語(yǔ)句Error(“overflow”)中“overflow”是直接量。但有的語(yǔ)言允許對(duì)串常量命名，以使程序易讀、易寫。如C++中，可定義

constcharpath[]=“dir/bin/appl”;

這里path是一個(gè)串常量，對(duì)它只能讀不能寫。串變量和其它類型的變量一樣，其取值是可以改變的。1/22/20254第四章串串的抽象數(shù)據(jù)類型定義串的抽象數(shù)據(jù)類型定義見教材P71

串的基本操作(13個(gè))：StrAssign,Strcopy,StrEmpty,StrCompare,StrLength,ClearString,Concat,SubString,Index,Replace,StrInsert,StrDelete,DestroyString

許多高級(jí)語(yǔ)言均提供了串基本操作相應(yīng)的運(yùn)算或標(biāo)準(zhǔn)庫(kù)函數(shù)來(lái)實(shí)現(xiàn)。下面僅介紹幾種在C語(yǔ)言中常用的串運(yùn)算，其它的串操作見教材及參考書。1/22/20255第四章串串變量及基本操作：

chars1[20]=“dirtreeformat”,s2[20]=“file.mem”;chars3[30],*p;

intresult;求串長(zhǎng)(length)

int

strlen(chars);//求串的長(zhǎng)度例如：cout<<strlen(s1);輸出131/22/20256第四章串基本操作（續(xù)）（2）串復(fù)制(copy)char*strcopy(charto,charfrom);

該函數(shù)將串from復(fù)制到串to中，并且返回一個(gè)指向串to的開始處的指針。例如：strcopy(s3,s1);//s3=“dirtreeformat”(3)聯(lián)接(concatenation)charconcat(charto,charfrom)

該函數(shù)將串from復(fù)制到串to的末尾，并且返回一個(gè)指向串to的開始處的指針。1/22/20257第四章串基本操作（續(xù)）例如：concat(s3,”/”)concat(s3,s2);//s3=“dirtreeformat/file.mem”(4)串比較（compare)

intstrcompare(chars1,chars2);

該函數(shù)比較串s1和串s2的大小，當(dāng)返回值小于0，等于0或大于0時(shí)分別表示s1<s2、s1=s2或s1>s2

例如：

result=strcompare(“baker”,”Baker”)result>0result=strcompare(“12”,”12”);result=0result=strcompare(“Joe”,”Joseph”);result<01/22/20258第四章串基本操作（續(xù)）（5）字符定位(index)charstrchr(chars,charc);

該函數(shù)是找c在字符串中第一次出現(xiàn)的位置，若找到則返回該位置，否則返回NULL。

例如：p=strchr(s2,”.”);p指向“file”之后的位置

if(p)strcpy(p,”.cpp”);s2=“file.cpp”最小操作子集：串賦值StrAssign、串比較Strcompare、求串長(zhǎng)StrLength、串聯(lián)接concat和求子串SubString。串的其余操作可由這些基本操作組合而成。1/22/20259第四章串4.2串的表示和實(shí)現(xiàn)因?yàn)榇翘厥獾木€性表，故其存儲(chǔ)結(jié)構(gòu)與線性表的存儲(chǔ)結(jié)構(gòu)類似。只不過(guò)由于組成串的結(jié)點(diǎn)是單個(gè)字符。串有三種機(jī)內(nèi)表示方法，下面分別介紹。1定長(zhǎng)順序存儲(chǔ)表示定長(zhǎng)順序存儲(chǔ)表示,也稱為靜態(tài)存儲(chǔ)分配的順序表。它是用一組連續(xù)的存儲(chǔ)單元來(lái)存放串中的字符序列。所謂定長(zhǎng)順序存儲(chǔ)結(jié)構(gòu)，是直接使用定長(zhǎng)的字符數(shù)組來(lái)定義，數(shù)組的上界預(yù)先給出：

#definemaxstrlen255

typedefcharsstring[maxstrlen+1];

sstrings;//s是一個(gè)可容納255個(gè)字符的順序串。1/22/202510第四章串串的結(jié)束標(biāo)記

一般可使用一個(gè)不會(huì)出現(xiàn)在串中的特殊字符在串值的尾部來(lái)表示串的結(jié)束。例如，C語(yǔ)言中以字符‵\0′表示串值的終結(jié)，這就是為什么在上述定義中，串空間最大值maxstrlen為256，但最多只能存放255個(gè)字符的原因，因?yàn)楸仨毩粢粋€(gè)字節(jié)來(lái)存放‵\0′字符。若不設(shè)終結(jié)符，可用一個(gè)整數(shù)來(lái)表示串的長(zhǎng)度，那么該長(zhǎng)度減1的位置就是串值的最后一個(gè)字符的位置。1/22/202511第四章串順序串的類型定義順序串的類型定義和順序表類似：

typedef

struct{charch[maxstrlen];

intlength;}sstring;//其優(yōu)點(diǎn)是涉及到串長(zhǎng)操作時(shí)速度快。1/22/202512第四章串順序存儲(chǔ)時(shí)串操作的實(shí)現(xiàn)

串聯(lián)接Concat(T,S1,S2)

求子串SubString(sub,s,pos,len)

注：串聯(lián)接操作可能出現(xiàn)“截?cái)唷爆F(xiàn)象1/22/202513第四章串2堆分配存儲(chǔ)表示

這種存儲(chǔ)表示的特點(diǎn)是，仍以一組地址連續(xù)的存儲(chǔ)單元存放串值字符序列，但它們的存儲(chǔ)空間是在程序執(zhí)行過(guò)程中動(dòng)態(tài)分配而得。所以也稱為動(dòng)態(tài)存儲(chǔ)分配的順序表。在C語(yǔ)言中，利用動(dòng)態(tài)存儲(chǔ)管理函數(shù)，來(lái)根據(jù)實(shí)際需要?jiǎng)討B(tài)分配和釋放字符數(shù)組空間。

typedef

struct{char*ch;//若是非空串，則按串長(zhǎng)分配存儲(chǔ)區(qū)，否則ch為null

intlength;//串長(zhǎng)度

}hsring;1/22/202514第四章串3串的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)順序串上的插入和刪除操作不方便，需要移動(dòng)大量的字符。因此，我們可用單鏈表方式來(lái)存儲(chǔ)串值，串的這種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)簡(jiǎn)稱為鏈串。

typedef

structnode{chardata;

structnode*next;}lstring;

一個(gè)鏈串由頭指針唯一確定。這種結(jié)構(gòu)便于進(jìn)行插入和刪除運(yùn)算，但存儲(chǔ)空間利用率太低。1/22/202515第四章串結(jié)點(diǎn)的大小由于串結(jié)構(gòu)的特殊性，可使每個(gè)結(jié)點(diǎn)存放多個(gè)字符。通常將結(jié)點(diǎn)數(shù)據(jù)域存放的字符個(gè)數(shù)定義為結(jié)點(diǎn)的大小，顯然，當(dāng)結(jié)點(diǎn)大小大于1時(shí)，串的長(zhǎng)度不一定正好是結(jié)點(diǎn)的整數(shù)倍，因此要用特殊字符來(lái)填充最后一個(gè)結(jié)點(diǎn)，以表示串的終結(jié)?！璣headABCIBCDEFGHI###^headA1/22/202516第四章串塊鏈結(jié)構(gòu)（設(shè)頭、尾指針）對(duì)于結(jié)點(diǎn)大小不為1的鏈串，其類型定義只需對(duì)上述的結(jié)點(diǎn)類型做簡(jiǎn)單的修改即可。

#definenodesize80

typedef

structnode{chardata[nodesize];

structnode*next;}node;

typedef

struct

lstring{node*head,*tail;

int

curlen;}lstring;1/22/202517第四章串存儲(chǔ)密度的概念

存儲(chǔ)密度小，運(yùn)算處理方便，存儲(chǔ)占用量大；存儲(chǔ)密度大，情況則相反。串的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)隊(duì)某些串操作（如聯(lián)接等）有一定的方便，但總的說(shuō)來(lái)不如另外兩種存儲(chǔ)結(jié)構(gòu)靈活。存儲(chǔ)密度=串值所占的存儲(chǔ)位實(shí)際分配的存儲(chǔ)位1/22/202518第四章串4.3串的模式匹配算法子串定位運(yùn)算又稱為模式匹配(PatternMatching)或串匹配(StringMatching)，此運(yùn)算的應(yīng)用非常廣泛。在文本編輯程序中，我們經(jīng)常要查找某一特定單詞在文本中出現(xiàn)的位置。顯然，解此問(wèn)題的有效算法能極大地提高文本編輯程序的響應(yīng)性能。在串匹配中，一般將主串稱為目標(biāo)串，子串稱之為模式串。1/22/202519第四章串模式匹配（續(xù)）設(shè)S為目標(biāo)串，T為模式串，且不妨設(shè)：

S=“s0s1s2…sn-1”T=“t0t1…tm-1”

串的匹配實(shí)際上是對(duì)于合法的位置0≦i≦n-m依次將目標(biāo)串中的子串s[i..i+m-1]和模式串t[0..m-1]進(jìn)行比較，若s[i..i+m-1]=t[0..m-1]，則稱從位置i開始的匹配成功，亦稱模式t在目標(biāo)s中出現(xiàn).1/22/202520第四章串模式匹配（續(xù)）若s[i..i+m-1]≠t[0..m-1]，則稱從位置i開始的匹配失敗。上述的位置i又稱為位移，當(dāng)s[i..i+m-1]=t[0..m-1]時(shí)，i稱為有效位移；當(dāng)s[i..i+m-1]≠t[0..m-1]時(shí)，i稱為無(wú)效位移。這樣，串匹配問(wèn)題可簡(jiǎn)化為是找出某給定模式T在一給定目標(biāo)T中首次出現(xiàn)的有效位移。

1/22/202521第四章串模式匹配算法串匹配的算法很多，這里我們只討論一種最簡(jiǎn)單的稱為樸素的串匹配算法。其基本思想是用一個(gè)循環(huán)來(lái)依次檢查n-m+1個(gè)合法的位移i(0≦I≦n-m)是否為有效位移，其算法段為：

for(i=0;i<=n-m;i++){if(S[i..i+m-1]=T[0..m-1])returni;}1/22/202522第四章串模式匹配算法匹配過(guò)程設(shè)目標(biāo)串為ababcabcacbab，模式串為abcac第一趟ababcabcacbababc第二趟ababcabcacbaba第三趟ababcabcacbababcac第四趟ababcabcacbaba第五趟ababcabcacbaba第六趟ababcabcacbababcac1/22/202523第四章串KMP算法—模式匹配的改進(jìn)算法算法是由D.E.Knuth、V.R.Pratt和J.H.Morris同時(shí)發(fā)現(xiàn)，因而得名。改進(jìn)在于：利用已經(jīng)得到的部分匹配結(jié)果將模式向右“滑動(dòng)”盡可能遠(yuǎn)的一段距離。算法可以在O(n+m)的時(shí)間數(shù)量級(jí)上完成。第一趟ababcabcacbababc第二趟ababcabcacbababcac第三趟ababcabcacbab