計(jì)算機(jī)課件 串

第四章串

學(xué)時(shí)：4學(xué)時(shí)

本章主要內(nèi)容:

1.串的有關(guān)概念及ADT定義；

2.串的三種存儲(chǔ)結(jié)構(gòu)急主要操作算法實(shí)現(xiàn);

3.串的兩種匹配算法。

本章重點(diǎn)難點(diǎn)：

1.順序串和堆串兩種存儲(chǔ)結(jié)構(gòu)；

2.串的KMP匹配算法；

3.Next[j]和nextval[i]的計(jì)算

4.1串類型的定義

4.2串的表示和實(shí)現(xiàn)

4.3串的模式匹配算法

4.1串類型的定義

串即字符串，是由零個(gè)或多個(gè)字符組成的有限序列,

是數(shù)據(jù)元素為單個(gè)字符的特殊線性表。

記為:a」(n>0)

Tnr

串名串值（用''括起來(lái)

隱含結(jié)束符

‘\0"即

[ASCII碼NUL,

若干術(shù)語(yǔ):

串長(zhǎng)：串中字符的個(gè)數(shù)(n>0).n=0時(shí)稱為空串0。

空白串：由一個(gè)或多個(gè)空格符組成的串。

問(wèn)：空串和空白串有無(wú)區(qū)別？

答：有區(qū)別。

空串(NullString)是指長(zhǎng)度為零的串;

而空白串(BlankString),是指包含一個(gè)或多個(gè)空白

字符'9(空格鍵)的字符串.

子串：串S中任意個(gè)連續(xù)的字符序列叫S的子串。

子串位置：子串的第一個(gè)字符在主串中的序號(hào)。

字符位置：字符在串中的序號(hào)。

串相等：串長(zhǎng)度相等，且對(duì)應(yīng)位置上字符相等。

“空串是任意串的子串；任意串s都是S本身的子串,

除S本身外，S的其他子串稱為S的真子串?！?/p>

串的抽象數(shù)據(jù)類型定義

ADTString{

Objects:D={ai|ai￡CharacterSet,i=l,2V..,n,n>0}

Relations:Rl={<ai-l,ai>|ai-l,aiWD,i=2,??.，n)

functions:

fStrAssign(&T,chars)〃串賦值，生成值為chars的串T

最

小StrCompare(S,T)〃串比較，若S>T,返回值大于。…

操StrLength(S)〃求串長(zhǎng)，即返回串S中的元素個(gè)數(shù)

作

子Concat(&T,SI,S2)//串連接，用T返回S1+S2的新串

集SubString(&Sub,S,pos,len)//求S中pos起長(zhǎng)度為len的子串

Index(S,T,pos)//子串定位函數(shù)(模式匹配)，返回位置

Replace(&S,T,V)〃用子串V替換子串T

}ADTString

例1:設(shè)s=UAMASTUDENT%t='GOOD',

q='WORKER'。求:

StrLength(s)=14//返回子串T在pos

->U弘Q要

StrLength(t)=4

SubString(&sub,s,8,7)='STUDE

SubString(&sub,t,2,1)=OReplace(&S5T,V)

//用子串V換子串T

Index(s,6A5)=3

Index(s,t)=0(s中沒(méi)有

Replace(&s「STUDENT',q)=qAMAWORKER9

問(wèn)題：當(dāng)sAMASTUDEN「時(shí)，

INDEX(s,'A',pos)=3,若想搜索后面那個(gè)N

怎么辦？

解答：INDEX(s,返回的只是“第一次”出現(xiàn)

的位置。

如果還要搜索后面的A,貝》pos變量要跟著變才行。

也就是說(shuō)，要把得到的“第一次”位置再代入INDEX

(sJA"pos)函數(shù)中循環(huán)操作才行。

4.2串的表示和實(shí)現(xiàn)

首先強(qiáng)調(diào)：串與線性表的運(yùn)算有所不同，是以“串的整體”作

為操作對(duì)象，例如查找某子串，在主串某位置上插入一個(gè)子串

等。串有三種機(jī)內(nèi)表示方法：

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

順序J——用一組地址連續(xù)的存儲(chǔ)單元存儲(chǔ)串值的字

存儲(chǔ)符序列，屬靜態(tài)存儲(chǔ)方式。

堆分配存儲(chǔ)表示

----用一組地址連續(xù)的存儲(chǔ)單元存儲(chǔ)串值的字

符序列，但存儲(chǔ)空間是在程序執(zhí)行過(guò)程中動(dòng)態(tài)

分配而得。

鏈?zhǔn)健龃膲K鏈存儲(chǔ)表示

存儲(chǔ)——鏈?zhǔn)椒绞酱鎯?chǔ)

定長(zhǎng)順序存儲(chǔ)特點(diǎn)：用一組連續(xù)的存儲(chǔ)單元來(lái)存放串,

直接使用定長(zhǎng)的字符數(shù)組來(lái)定義，數(shù)組的上界預(yù)先給出，

故稱為靜態(tài)存儲(chǔ)分配。

例如：

#defineMaxstrlen255//用戶可用的最大串長(zhǎng)

typedefunsignedcharSString[Maxstrlen+1];

SStrings;//s是一個(gè)可容納255個(gè)字符的順序串。

注：

?一般用SString[O]來(lái)存放串長(zhǎng)信息（如pascal語(yǔ)言）;

?C語(yǔ)言約定在串尾加結(jié)束符6\0\以利操作加速，但不

計(jì)入串長(zhǎng)

?若字符串超過(guò)Maxstrlen則自動(dòng)截?cái)唷?/p>

例：用順序存儲(chǔ)方式編寫求子串函數(shù)SubString(&Sub,S,pos,len)

poslen

StatusSubString(SString&sub9SStringS,intpos,intlen)

{if(pos<l||pos>S[0]||len<0||len>S[0]-pos+l)returnERROR;

//若pos和len參數(shù)越界，則告警

Sub[l.......len]=S[pos.......pos+len-1];

Sub[01=len:returnOK:

討論：想存放超長(zhǎng)字符串怎么辦?

改用動(dòng)態(tài)分配的一維數(shù)組----

堆分配存儲(chǔ)特點(diǎn)：仍用一組連續(xù)的存儲(chǔ)單元來(lái)存放串，

但存儲(chǔ)空間是在程序執(zhí)行過(guò)程中動(dòng)態(tài)分配而得。

思路：利用malloc函數(shù)合理預(yù)設(shè)串長(zhǎng)空間。

特點(diǎn)：若在操作中串值改變，還可以利用realloc函數(shù)

按新串長(zhǎng)度增加空間（即動(dòng)態(tài)數(shù)組概念）。

堆T的存儲(chǔ)結(jié)構(gòu)描述：

Typedefstruct{

char*ch;//若非空串，按串長(zhǎng)分配空間；否則ch=NULL

intlength;〃串長(zhǎng)度____________

}HString.T.ch

■T.length

泰山學(xué)院

例1:久建堆函數(shù)

StatusStrAssign(HString&T,char*chars)C是指針變量，可以自增!

事即每次后移一個(gè)數(shù)據(jù)單

{//生成一個(gè)串T,T值一串常量charyGo

if(T.ch)free(T.ch);空間

for(i=0,c=chars;;++k++c);//求chars的串長(zhǎng)度i

if(!i){T.ch=NULL;T.length=0;

else{

if(!(T.ch=(charw)malloc(i*sizeof(char))))

exit(OVERFLOW);

T.ch[0..i-l]=chars[0??i.m此處T.ch[0]沒(méi)有

用來(lái)裝串長(zhǎng)，因?yàn)?/p>

T.length=i;另有T.length分

}

returnOK;

例2:?用“堆”方式編寫串插入函數(shù)

StatusStrinsert(HString&S,intpos,HStringT)

{//在串S的第pos個(gè)字符之前(包括尾部)插入串T

if(pos<l||pos>S.length+l)returnERROR;//pos不合法則告警

if(T.length){//只要串T不空，就需要重新分配S空間，以便插入T

if(!(S.ch=(char*)realloc(S.ch,(S.length+T.length)*sizeof(char))))

exit(OVERFLOW);//若開(kāi)不了新空間，則退出

for(i=S.length-l;i>=pos-l;—i)S.ch[i+T.length]=S.chfi];

//為插入T而騰出pos之后的位置，即從S的pos位置起全部字符均后移

S.ch[pos-1...pos+T.length-2]=T.ch[O...T.length-l];//插入T,略/0

S.length+=T.length;//刷新S串長(zhǎng)度

}returnOK;

}//Strinsert

泰山學(xué)院

鏈?zhǔn)酱鎯?chǔ)特點(diǎn)：用鏈表存儲(chǔ)串值，易插入和刪除。

法L鏈表結(jié)點(diǎn)的數(shù)據(jù)分量長(zhǎng)度取1（個(gè)字符）

A17------'IBI7--------"ICIT-----------HINULL

法2：鏈表結(jié)點(diǎn)（數(shù)據(jù)域）大小取n（例如n二4）

head一^ABCD”-------7FGH?——，I###NULL

討論：法1存儲(chǔ)密度為"2；法2存儲(chǔ)密度為9〃5=3/5,

顯然，若數(shù)據(jù)元素很多，用法2存儲(chǔ)更優(yōu)一稱為塊鏈結(jié)構(gòu)

塊鏈類型的定義

typedefstruct{〃其次定義用鏈?zhǔn)酱鎯?chǔ)的串類型

Chunk*head;//頭指針

Chunk氣ail;//尾指針

intcurLen;//結(jié)點(diǎn)個(gè)數(shù)

}Lstring;//串類型只用一次，前面可以不加Lstring

#defineCHUNKSIZE80〃每塊大小，可由用戶定義

typedefstructChunk{//首先定義結(jié)點(diǎn)類型

charch[CHUNKSIZE];//每個(gè)結(jié)點(diǎn)中的數(shù)據(jù)域

structChunk*next;//每個(gè)結(jié)點(diǎn)中的指針域

}Chunk;

4.3串的模式匹配算法

算法目的：確定主串中所含子串第一次出現(xiàn)的位置(定位)

定位問(wèn)題稱為串的模式匹配(PatternMatching),即子串定位運(yùn)

算，它是串處理系統(tǒng)中最重要的操作之一。

典型函數(shù)為Index(S,T,pos).

算法種類:

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

?KMP算?

單回溯，速度慢1

避免回溯，匹配速度快,

BF算法的實(shí)現(xiàn)一即編寫Index(S,T,pos)函數(shù)

例1：S=6ababcabcacbab5,T=6abcac\pos=l,

求：串T在串S中第pos個(gè)字符之后的位置。

BF算法設(shè)計(jì)思想：

?將主串S的第pos個(gè)字符和模式T的第1個(gè)字符比較，

若相等，繼續(xù)逐個(gè)比較后續(xù)字符；

若不等，從主串S的下一字符(pos+1)起，重新與T第一

個(gè)字符比較。

?直到主串S的一個(gè)連續(xù)子串字符序列與模式T相等。返回值

為S中與T匹配的子序列第一個(gè)字符的序號(hào)，即匹配成功。

否則，匹配失敗，返回值0.

例2:S=6ababcabcacbab5,T=6abcac\求Index(S,T,5)

Intidt(SStringS,SStringT,intpos){\[pos=5|

i=pos;j=l;S=6ababcabcacbab9

while(i<=S[0]&&j<=T[0]){丁二'斗bca

if(S[i]==T[j]){++i,++j}〃繼續(xù)比較后續(xù)字符J

else{i=i-j+24j=l;}〃指針回溯至U下一首位，重新開(kāi)始匹配

if(j>T[OJ)returni-T[OJ;〃子串結(jié)束，說(shuō)明匹配成功

elsereturnO;

}//Index匹配成功后指針仍要回溯！因?yàn)橐祷氐?/p>

是被匹配的首個(gè)字符位置。

BF算法的時(shí)間復(fù)雜度

討論：

若n為主串長(zhǎng)度，為子串長(zhǎng)度，則串的BF匹配算法最壞的情

況下需要比較字符的總次數(shù)為=O(n*m)

一般的情況是：O(n+m)

推導(dǎo)方法：要從最好到最壞情況統(tǒng)計(jì)總的比較次

數(shù)，然后取平均。為了解決這樣的情況，出現(xiàn)了更

加優(yōu)化的算法：

請(qǐng)看KMP算法!

KMP算法（特點(diǎn)：速度快）

①KMP算法設(shè)計(jì)思想

②KMP算法的推導(dǎo)過(guò)程

③KMP算法的實(shí)現(xiàn)（關(guān)鍵技術(shù)：計(jì)算next[j]）

④KMP算法的時(shí)間復(fù)雜度

kMP算法

KMP算法的時(shí)間復(fù)雜度可以達(dá)到O(m+n)。

定義：模式串的next函數(shù)

fo當(dāng)j=1時(shí)〕

Max{k|1<k<j

next[j]二1\

且'P1P2…Pk-l'='Pj-k+l…Pj/}

1其它情況

intIndexKMP(SStringS,SStringT,intpos){

//1<pos<StrLength(S)

i=pos;j=1;

while(i<=S[0]&&jv=T[0]){

if(j=O||S[i]==