2023/2/171數(shù)據(jù)結(jié)構(gòu)(DataStructure)2023/2/172第四章串4.1串類型的定義4.2串的表示和實(shí)現(xiàn)

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

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

4.2.3串的塊鏈存儲(chǔ)表示4.3

串的模式匹配算法2023/2/173一、串及其基本概念串的定義：串(String)是零個(gè)或多個(gè)字符組成的有限序列。一般記作S=“a1a2a3…an”，其中S是串名，雙引號(hào)括起來的字符序列是串值；ai(1≦i≦n)可以是字母、數(shù)字或其它字符。串的長度：串中所包含的字符個(gè)數(shù)稱為該串的長度。空串：長度為零的串稱為空串(EmptyString)，它不包含任何字符?？崭翊簩H由一個(gè)或多個(gè)空格組成的串稱為空格串(BlankString)。注意：空串和空格串的不同，例如“

”和“”分別表示長度為1的空格串和長度為0的空串。4.1串類型的定義2023/2/174子串與主串：串中任意個(gè)連續(xù)字符組成的子序列稱為該串的子串，包含子串的串相應(yīng)地稱為主串。通常將子串在主串中首次出現(xiàn)時(shí)的該子串的首字符對(duì)應(yīng)的主串中的序號(hào)，定義為子串在主串中的位置。例如，設(shè)A=“Thisisastring”B=“is”則B是A的子串，A為主串。B在A中出現(xiàn)了兩次，其中首次出現(xiàn)所對(duì)應(yīng)的主串位置是3。因此，稱B在A中的位置為3。相等：當(dāng)且僅當(dāng)兩個(gè)串的長度相等，并且每個(gè)對(duì)應(yīng)位置的字符都相等時(shí)，稱兩個(gè)串相等。例如，A=“BEIJING”B=“BEIJING”，則串A與串B相等。串常量和串變量：串常量和整常數(shù)、實(shí)常數(shù)一樣，在程序中只能被引用但不能改變其值，即只能讀不能寫。串變量的值在程序中可以改變，即可以讀也可以寫。4.1串類型的定義2023/2/175二、串的抽象數(shù)據(jù)定義ADTString{

數(shù)據(jù)對(duì)象：D={ai|ai∈ElemSet,i=1,2,…,n,n≧0}

數(shù)據(jù)關(guān)系：R1={<ai-1,ai>|ai-1,ai∈D,i=2,…,n}

基本操作：

StrAssign(&T,chars)//生成一個(gè)其值等于chars的串T。

StrCopy(&T,S)

//由串S復(fù)制得串T。

Strcompare(S,T)

//若S>T則返回值>0,S<T返回值>0,否則返回值=0。

Concat(&T,S1,S2)

//由S1和S2聯(lián)結(jié)得到新串T。

SubString(&Sub,S,pos,len)//取S中pos位置起始的長度為len的子串。

Index(S,T,pos)//返回串T在S中pos位置之后第一次出現(xiàn)的位置，或0。

}ADTStack4.1串類型的定義2023/2/1764.1串類型的定義三、串的基本操作

對(duì)于串的基本操作，許多高級(jí)語言均提供了相應(yīng)的運(yùn)算或標(biāo)準(zhǔn)庫函數(shù)來實(shí)現(xiàn)。下面僅介紹幾種在C語言中常用的串運(yùn)算。

定義下列幾個(gè)變量：chars1[20]=“dirtreeformat”, s2[20]=“file.txt”;chars3[30],*p;intresult;2023/2/1771求串長(length)intstrlen(char*s);//求串的長度例如：printf(“%d”,strlen(s1));輸出132串復(fù)制(copy)char*strcopy(char*to,char*from);

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

該函數(shù)將串from復(fù)制到串to的末尾，并且返回一個(gè)指向串to

的開始處的指針。例如：strcat(s3,“/”)strcat(s3,s2);//s3=“dirtreeformat/file.txt”4.1串類型的定義2023/2/1784串比較（compare)intstrcmp(char*s1,char*s2);

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

例如：result=strcmp(“baker”,“Baker”);//result>0result=strcmp(“12”,“12”);//result=0result=strcmp(“Jos”,“Joseph”);//result<05字符定位(locate)charstrchr(char*s,charc);

該函數(shù)是找c在字符串中第一次出現(xiàn)的位置，若找到則返回該位置，否則返回NULL。例如：p=strchr(s2,“.”);//p指向“file”之后的位置

if(p)strcopy(p,“.cpp”);//s2=“file.cpp”4.1串類型的定義2023/2/179例1、求子串求子串的過程即為復(fù)制字符序列的過程，將串S中的第pos個(gè)字符開始長度為len的字符復(fù)制到串T中。

voidsubstr(char*sub,char*s,intpos,intlen){if(pos<0||pos>strlen(s)-1||len<0||len>strlen(s)-pos)error(“parametererror”)；

strncpy(sub,s,pos,len)；

}例2、串的定位index(char*s,char*t,intpos)

求串T在主串S中第pos個(gè)字符之后的位置。方法：從主串S的第pos個(gè)字符開始，取長度和串T相等的子串和T比較，若相等，則求得函數(shù)值為pos。否則子串位置增1繼續(xù)與T比較，直至找到與T相等的子串或確定S中不存在和串T相等的子串為止。4.1串類型的定義2023/2/1710

intindex(char*s,char*t,intpos){if(pos>0){n=strlen(s);m=strlen(t);i=pos;while(i<n-m+1){substr(sub,s,i,m);if(strcompare(sub,t)!=0) ++i;elsereturn(i);}}return(0);}4.1串類型的定義2023/2/1711

定長順序存儲(chǔ)表示,也稱為靜態(tài)存儲(chǔ)分配的順應(yīng)表。它是用一組連續(xù)的存儲(chǔ)單元來存放串中的字符序列。所謂定長順序存儲(chǔ)結(jié)構(gòu)，是直接使用定長的字符數(shù)組來定義，數(shù)組的上界預(yù)先給出：

#definemaxstrlen255typedefcharSString[maxstrlen+1];//0分量存放串長4.2串的表示和實(shí)現(xiàn)4.2.1定長順序存儲(chǔ)表示

StatusSubString(SString&Sub,SStringS,intpos,intlen){if(pos<1||pos>S[0]||len<0||len>S[0]-pos+1) returnERROR;Sub[1..len]=S[pos..pos+len-1];Sub[0]=len;retrunOK;}2023/2/1712

StatusConcat(SString&T,SStringS1,SStringS2){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];returnTRUE;}elseif(S1[0]<maxstrlen){T[1..S1[0]]=S1[1..S1[0]];T[S1[0]+1..maxstrlen]=S2[1..maxstrlen-S1[0]];T[0]=maxstrlen;returnFALSE;}else{T[0..maxstrlen]=S1[0..maxstrlen]; returnFALSE;}}4.2串的表示和實(shí)現(xiàn)2023/2/1713

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

typedefstruct{char*ch;intlength;}HString;4.2.2堆(Heap)分配存儲(chǔ)表示4.2串的表示和實(shí)現(xiàn)2023/2/1714

Statusstrassign(HStringt,char*chars){

//生成一個(gè)其值等于串常量chars的串tif(t.ch)free(t.ch);for(i=0,c=chars;c;++i,++c);//求chars的長度

if(!i){t.ch=NULL;t.length=0;}else{if(!(t.ch=(char*)malloc(i*sizeof(char))))exit(overflow);

t.ch[0..i-1]=chars[0..i-1];t.length=i;}}

4.2串的表示和實(shí)現(xiàn)2023/2/1715

intstrlen(HStrings){returns.length;}

Statusclearstring(HStrings){if(s.ch){free(s.ch);s.ch=NULL;}s.length=0;}

intstrcompare(HStrings,HStringt){for(i=0;i<s.length&&i<t.length;++i)if(s.ch[i]!=t.ch[i])return(s.ch[i]-t.ch[i]);//>0or<0returns.length-t.length;//=0;>0or<0}4.2串的表示和實(shí)現(xiàn)2023/2/1716

Statusconcat(HStringt,HStrings1,HStrings2){if(t.ch)free(t.ch);if(!(t.ch=(char*)malloc((s1.length+s2.length)*sizeof(char))))exit(overflow);t.ch[0..s1.length-1]=s1.ch[0..s1.length-1];t.length=s1.length+s2.length;t.ch[s1.length..t.length-1]=s2.ch[0..s2.length-1];returnOK;}4.2串的表示和實(shí)現(xiàn)2023/2/1717

Statussubstr(HStringsub,HStrings,intpos,intlen){if(pos<1||pos>s.length||len<0||len>s.length-pos+1)returnERROR;if(sub.ch)free(sub.ch);if(!len){sub.ch=NULL;sub.length=0;}else{sub.ch=(char*)malloc(len*sizeof(char));sub.ch[0..len-1]=s[pos-1..pos+len-2];//從0開始

s.length=len;}returnOK;}4.2串的表示和實(shí)現(xiàn)2023/2/1718

順序串上的插入和刪除操作不方便，需要移動(dòng)大量的字符。因此，可用單鏈表方式來存儲(chǔ)串值，串的這種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)簡(jiǎn)稱為鏈串。一個(gè)鏈串由頭指針唯一確定。這種結(jié)構(gòu)便于進(jìn)行插入和刪除運(yùn)算，但存儲(chǔ)空間利用率太低。ABCDEFGHI###^headheadABCI^4.2.3串的塊鏈存儲(chǔ)表示4.2串的表示和實(shí)現(xiàn)2023/2/17194.3串的模式匹配算法……Si-j+1

Si-j+2

……

Si-1

Si

Si+1……

P1

P2

……

Pj-1

Pj………失配位置P1

P2

……

Pj-1

Pj……下次匹配位置e.g:S=abcabcabcdP=abcabcdabcabcd

模式右移一位4.3.1求子串位置的定位函數(shù)Index()模式匹配：求子串（模式串）在主串的位置?；痉椒ǎ簭闹付ㄎ恢瞄_始逐個(gè)比較主串與模式串的字符，一旦發(fā)現(xiàn)出現(xiàn)字符不匹配，則整個(gè)模式相對(duì)于原來的位置右移一位。如下圖所示：2023/2/1720最基本的模式匹配程序：intIndex(SStringS,SStringT,intpos)//在主串S的第POS個(gè)字符之后，尋找模式T的匹配位置{i=pos;j=1;while(i<=S[0]&&j<=T[0])//0號(hào)單元存放串長

{if(S[i]==T[j]){++i;++j;}else{i=i-j+2;j=1;}}if(j>T[0])returni-T[0]//T在S中的匹配起始位置

elsereturn0;}4.3串的模式匹配算法2023/2/1721S=aaaaaaaaabP=aaba、b不等模式右移一位S=aaaaaaaaabP=aaba、b不等模式右移一位S=aaaaaaaaabP=aaba、b不等模式右移一位S=aaaaaaaaabP=aaba、b不等模式右移一位S=aaaaaaaaabP=aabS=aaaaaaaaabP=aabS=aaaaaaaaabP=aabS=aaaaaaaaabP=aaba、b不等模式右移一位a、b不等模式右移一位a、b不等模式右移一位

完全匹配

n-m+1匹配起始位置4.3串的模式匹配算法4.3.2Knuth-Morris-Pratt模式匹配算法（KMP算法）

說明基本模式匹配算法在最壞情況下時(shí)間復(fù)雜度為O（n*m）的實(shí)例（n為主串長度，m為模式長度）。每比較m次，移動(dòng)模式一次。最后在主串的n-m+1找到子串，比較（n-m+1）*m次。2023/2/1722S=abcabcabcdP=abcabcd

S=abcabcabcdP=abcabcd

S=abcabcabcdP=abcabcd

S=abcabcabcdP=abcabcd

失配點(diǎn)右移一位，仍失配又右移一位，仍失配再右移一位，三次比較之后，再進(jìn)行斷點(diǎn)處的比較，比較成功！問題:能否省去上述三次比較，直接進(jìn)行S7和P4之間的比較呢？本次比較省去？本次比較省去？三次比較省去？4.3串的模式匹配算法說明KMP算法的實(shí)例：2023/2/1723ijS=abcabcabcdP=abcabcd

S=abcabcabcdP=abcabcd

失配點(diǎn)直接尋找新匹配位置ij…Si-j+1

Si-j+2

……

Si-1

Si

Si+