數(shù)據(jù)結(jié)構(gòu)課件數(shù)據(jù)結(jié)構(gòu)課件串

第四章

串串類型的定義串的表示和實現(xiàn)串的模式匹配算法串操作應(yīng)用舉例14.1.1串的邏輯結(jié)構(gòu)定義串——是由零個或多個字符組成的有限序列。一般記為：S=‘a(chǎn)1a2…an’長度——串中字符的(n數(shù)>=目0)?？沾銈€字符的串，用符號φ來表示空串。子串——串中任意個連續(xù)的字符組成的子序列。主串——包含子串的串。位置——字符在序列中的序號為該字符在串中的位置例：a=‘bei’

b=‘jing’c=‘beijing’d=‘bei

jing’則：a,b,c,d的長度分別為：3、4、7、8。a、b是c和d的子串。a在c和d中的位置都是1。b在c中的位置是4，在d中的位置是52相等——當(dāng)兩個串的長度相等，并且各個對應(yīng)位置的字符都相等，則稱兩個串是相等的?？崭翊梢粋€或多個空格組成的串稱為空格串。注意：串值必須用一對單引號括起來，但單引號本身不屬于串。例：

x=‘123’;

x=123;

tsing=‘tsing’3串的抽象數(shù)據(jù)類型的定義：

ADT

String{數(shù)據(jù)對象：D={ai|ai(-CharacterSet,i=1,2,...,n,n>數(shù)據(jù)關(guān)系：R1={<ai-1,ai>|ai-1,ai(-D,i=2,...,n}基本操作：StrAssign(&T,chars)chars是字符常量。生成一個其值等于chars的串T。StrCopy(&T,S)串S存在則由串S復(fù)制得串TStrEmpty(S)串S存在則若S為空串,返回真否則返回假StrCompare(S,T)串S和T存在,若S>T,則返回值>0,若S=T,則返回值=0,若S<T,則返回值<04StrLength(S)串S存在返回S的元素個數(shù)稱為串的長度.ClearString(&S)串S存在將S清為空串Concat(&T,S1,S2)串S1和S2存在用T返回由S1和S2聯(lián)接而成的新串SubString(&Sub,S,pos,len)串S存在,1<=pos<=StrLength(S)且0<=len<=StrLength(S)-pos+1用Sub返回串S的第pos個字符起長度為len的子串Index(S,T,pos)串S和T存在,T是非空,1<=pos<=StrLength(S),若主串S中存在和串T值相同的子串,則返回它在主串S中第pos個字符之后第一次出現(xiàn)的位置,否則函數(shù)值為0Replace(&S,T,V)串S,T和V存在,T是非空串,用V替換主串S中出現(xiàn)的所有與T相等的不重疊的子串5StrInsert(&S,pos,T)串S和T存在,1<=pos<=StrLength(S)+1,在串S的第pos個字符之前插入串TStrDelete(&S,pos,len)串S存在,1<=pos<=StrLength(S)-len+1從串中刪除第pos字符起長度為len的子串DestroyString(&S)串S存在,則串S被銷毀}ADT

String6例子：設(shè)：s,t,v,a,b,c,d都為串名。a=‘bei’

b=‘jing’c=‘

’(1)dS=t‘rabsesijgin(g&’s,ss)和strcopy(&s,t)賦值操作。例：

strassign(s,‘a(chǎn)bcd’)

S=‘

abcd’例：strcopy(s,d)S=‘beijing’返回值<0返回值=0(2)strcompare(s,t)

判等函數(shù)。例：strcompare(a,b)strcompare(φ,φ)(3)strlength(s)

求長函數(shù)7(4)concat(&t,s1,s2)聯(lián)接函數(shù)。例

S1=‘S1S2…Sm’則:

concat(t,s1,s2)concat(t,s2,s1)s2=‘t1t2…tn’t=‘S1S2…Smt1t2…tn’t=‘t1t2…tnS1S2…Sm’(5)substring(&sub,s,pos,len)

求子串函數(shù)。if

1≦pos≦length(s)且0≦len≦length(s)-pos+1用sub返回從串s中第pos個字符起，長度為len的字符序列else

返回error例：substring(sub,d,1,3S)ub=‘bei’Substring(sub,d,4,0)sub=φ8(6)index(s,t,pos)

定位函數(shù)。if

在主串S中的第pos個位置之后存在和t相等的子串返回S中第一個這樣的子串在主串S中的位置。例：設(shè)

s=‘bbabbabba’

t=‘a(chǎn)b’v=‘c’則

replace(s,t,v)

s=‘bbcbcba’else

返回零例：index(d,b,1)=4index(d,c,1)=0index(d,b,5)=(7)replace(&s,t,v)

置換函數(shù)。以串v替換所有出現(xiàn)的和非空串t相等的不重疊的子串例：

replace(d,b,c)

d=‘bei

’9(8)strsert(&s,pos,t)

插入操作。elseif

1≦pos≦length(s)+1在串S的第pos個字符之前插入串t。返回error例：

strinsert(a,4,b)

a=‘beijing’(9)strdelete(&s,pos,len)

刪除操作。if

1≦pos≦length(s)-len+1從串S中刪除第pos個字符起長度為len的子串。else

返回error例：

strdelete(a,4,4)

a=‘bei’基本操作：strassign、strcompare、strlength、concat、substring10定位函數(shù)

index(s,t,pos)的算法實現(xiàn)：算法分析：S=‘a(chǎn)bdgjgutabcdhhuac’

t=‘a(chǎn)bc’Int

index

(string

s,string

t,int

pos)

{if

(pos>0)

{n=strlength(s);

m=strlength(t);

i=pos;while

(i<=n)

{substrimg(sub,S,i,m);if

(strcompare(sub,t)!=0)

++i;else

return

i;

}}return

0;}11作業(yè)：1.用5種串的基本操作（strassignsstrcomparesstrlengthssubstring）來邏輯實現(xiàn)strinsert(&s,pos,t)操作.Status

strinsert(string

s,int

pos

,string

t){

if

………..

Return

error;}(1)Substring(sub1,s,(2)substring(sub2,s,,,););concat(

s1,

,

);concat(s,

,

);return

ok;124.2串的表示和實現(xiàn)4.2.1定長順序存儲表示類似于線性表的順序存儲結(jié)構(gòu),用一組地址連續(xù)的存儲單元存儲串值的字符序列.用定長數(shù)組表示：

#define

MAXSTRLEN

255typedef

unsigned

char

SString[MAXSTRLEN+1]//0號單元存放串長13串長可用下標(biāo)為0的數(shù)組元素存儲,也可在串值后設(shè)特殊標(biāo)記a[0]

a[1]a[2]a[3]a[4]a[5]

...a[n]pascalcba3c\0cba141.串聯(lián)接的實現(xiàn)Concat(&T,S1,S2)假設(shè)S1,S2和T都是SString型的串變量,且串T是由串

S1聯(lián)結(jié)串S2得到的,即串T的值的前一段和串S1的值相等,串T的值的后一段和串S2的值相等,則只要進(jìn)行相應(yīng)的"

串值復(fù)制"操作即可,對超長部分實施"截斷"操作串可能有三種情況：（1）S1,S2串長和<=最大值S1S2T426adabebccddef15S1S2T668agabhbcicdjdekeflfgh(2)S1串長<最大串長;

S1,S2串長和>最大串長;(3)S1串長已=最大串長;TS2S1828aiabjbccddeeffgghh16算法描述如下:Status

Concat(SString

&T,SString

S1,SString

S2){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;}else

if

(S1[0]<MAXSTRSIZE){T[1..S1[0]]=S1[1..S1[0]];T[S1[0]+1..MAXSTRLEN]=S2[1..MAXSTRLEN-S1[0]];T[0]=MAXSTRLEN;

uncut=FALSE;}else{T[0..MAXSTRLEN]=S1[0..MAXSTRLEN];uncut=FALSE;}returnuncut;}172.求子串substring(&sub,S,pos,len)if

1≦pos≦length(s)且0≦len≦length(s)-pos+1用sub返回從串s中第pos個字符起，長度為len的字符序列else

返回errorStatus

substring(sstring

&sub,sstring

s,int

pos,if (pos<1||

pos>s[0]

||

len<0||

len>s[0]-pos+1)return

error;sub[1..len]=s[pos..pos+len-1];sub[0]=len;}18※4.2.2堆分配存儲表示這種存儲表示的特點(diǎn)是,仍以一組地址連續(xù)的存儲單元存放串值字符序列,但它們的存儲空間是在程序執(zhí)行過程中動態(tài)分配而得。在C語言中,存在一個稱之為堆的自存儲區(qū),并由C語言的動態(tài)分配函數(shù)malloc()和free()來利用函數(shù)malloc()為每個新產(chǎn)生的串分配一塊實際串長需存儲空間,為處理方便,約定串長也作為存儲結(jié)構(gòu)的一部分堆分配的存儲表示：typedef

struct{char

*ch;int

length;}HString；19ADT

string的堆分配存儲的表示和實現(xiàn)：堆分配存儲的表示；基本操作的函數(shù)原型說明；基本操作的算法描述；P76～77204.2.3串的塊鏈存儲表示例:

s=‘a(chǎn)bcdefghi’i

#

#

#

^heada

b

c

de

f

g

hheadabc…

i

^為了便于進(jìn)行串的操作，當(dāng)以鏈表存儲串值時，除頭指針外還可附設(shè)一個尾指針指示鏈表的最后一個結(jié)點(diǎn)并給出當(dāng)前串的長度，稱如此定義的串存儲結(jié)構(gòu)為塊鏈結(jié)構(gòu)。21塊鏈結(jié)構(gòu)串的C表示：#define

CHUKSIZE

80Typedef

struct

chunk

{char

ch[CHUKSIZE];*next;struct

chunk}chunk;Typedef

struct

{chunk

*head,*tail;Int

curlen;}Lstring;a

bc

d例：

Lstring

S;s.heads.tails.curlen

5e

#

^22串塊鏈結(jié)構(gòu)結(jié)點(diǎn)大小的選擇依據(jù)：存儲密度=串值所占的存儲位實際分配的存儲位heada

b

c

de

f

g

hheadabc…i

#

#

#

^i

^例：存儲密度=915=35存儲密度=918=12234.3串的模式匹配算法定位函數(shù)

index(s,t,pos)的算法實現(xiàn)：算法分析：S=‘a(chǎn)bdgjgutabcdhhuac’

t=‘a(chǎn)bc’Int

index

(string

s,string

t,int

pos)

{if

(pos>0)

{n=strlength(s);

m=strlength(t);

i=pos;while

(i<=n-m+1)

{substrimg(sub,S,i,m);if

(strcompare(sub,t)!=0)

++i;else

return

i;

}}return

0;}要求：采用SString結(jié)構(gòu)，24算法分析:

S=‘a(chǎn)bdgagutabcdhhuac’

t=‘a(chǎn)bc’用i和j分別指示主串s和模式t中當(dāng)前正待比較的字位置,從主串s的第pos字符起和模式t的第一個字符比較若相等,則繼續(xù)逐個比較后續(xù)字符,否則從主串的下一個符起再重新和模式的字符比較之。依次類推,直至模式匹配成功或匹配不成功.一級算法:i=pos;

j=1;while

(i<=s[0]

&&

j<=t[0])if

s[i]==t[j]

繼續(xù)比較后繼字符;else

重新開始匹配；25二級算法：{i=i-j+1+1;;j=1;}i=pos;whilej=1;(i<=s[0]

&&

j<=t[0])if

s[i]==t[j]

繼續(xù)比較后繼字符;else

重新開始匹配；{++i;

++j;

}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;}26if

j>t[0]else返回t在s的位置值

return(0);return(

i-t[0]);三級算法：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;}返回t在s的位置值或零；27Index(s,t,pos)的算法實現(xiàn)演：示Int

index

(sstring

s,sstring

t,int

pos)

{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]

return(

i-t[0]);else

return(0);}28i=3第二趟匹配：abtabcdhhuaci=2第三趟匹配：abtabcdhhuaci=3第四趟匹配：abtabcdhhuacabcj=3abcj=1abcj=1abc例：S=‘a(chǎn)btabcdhhuac’

t=‘a(chǎn)bc’index(s,t,1)的匹配過程i：=1,j=1第一趟匹配：abtabcdhhuaci=4

i=7j=1

j=429串操作應(yīng)用舉例文本編輯文本編輯——修改字符數(shù)據(jù)的形式或格式，包括串的查找、插入、刪除等基本操作。文本編輯可以用于源程序的輸入和修改（如圖一）:圖一30用于報刊和書籍的編輯排版以及辦公室的公文書信的起和潤色（如圖二）：圖二31在進(jìn)行文本編輯時，我們把整個文本看成是一個字符串，稱為文串，頁則是文本串的子串，行又是頁的子串。例如有下列一段源