計算機課件 串

第四章串

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

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

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

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

3.串的兩種匹配算法。

本章重點難點：

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

2.串的KMP匹配算法；

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

4.1串類型的定義

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

4.3串的模式匹配算法

4.1串類型的定義

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

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

記為:a」(n>0)

Tnr

串名串值（用''括起來

隱含結(jié)束符

‘\0"即

[ASCII碼NUL,

若干術(shù)語:

串長：串中字符的個數(shù)(n>0).n=0時稱為空串0。

空白串：由一個或多個空格符組成的串。

問：空串和空白串有無區(qū)別？

答：有區(qū)別。

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

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

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

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

子串位置：子串的第一個字符在主串中的序號。

字符位置：字符在串中的序號。

串相等：串長度相等，且對應(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,返回值大于?！?/p>

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

作

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

集SubString(&Sub,S,pos,len)//求S中pos起長度為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中沒有

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

問題：當(dāng)sAMASTUDEN「時，

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

怎么辦？

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

的位置。

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

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

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

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

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

為操作對象，例如查找某子串，在主串某位置上插入一個子串

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

?定長順序存儲表示

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

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

堆分配存儲表示

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

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

分配而得。

鏈式■串的塊鏈存儲表示

存儲——鏈式方式存儲

定長順序存儲特點：用一組連續(xù)的存儲單元來存放串,

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

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

例如：

#defineMaxstrlen255//用戶可用的最大串長

typedefunsignedcharSString[Maxstrlen+1];

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

注：

?一般用SString[O]來存放串長信息（如pascal語言）;

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

計入串長

?若字符串超過Maxstrlen則自動截斷。

例：用順序存儲方式編寫求子串函數(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:

討論：想存放超長字符串怎么辦?

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

堆分配存儲特點：仍用一組連續(xù)的存儲單元來存放串，

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

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

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

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

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

Typedefstruct{

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

intlength;〃串長度____________

}HString.T.ch

■T.length

泰山學(xué)院

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

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

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

{//生成一個串T,T值一串常量charyGo

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

for(i=0,c=chars;;++k++c);//求chars的串長度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]沒有

用來裝串長，因為

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

}

returnOK;

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

StatusStrinsert(HString&S,intpos,HStringT)

{//在串S的第pos個字符之前(包括尾部)插入串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);//若開不了新空間，則退出

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串長度

}returnOK;

}//Strinsert

泰山學(xué)院

鏈式存儲特點：用鏈表存儲串值，易插入和刪除。

法L鏈表結(jié)點的數(shù)據(jù)分量長度取1（個字符）

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

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

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

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

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

塊鏈類型的定義

typedefstruct{〃其次定義用鏈式存儲的串類型

Chunk*head;//頭指針

Chunk氣ail;//尾指針

intcurLen;//結(jié)點個數(shù)

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

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

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

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

structChunk*next;//每個結(jié)點中的指針域

}Chunk;

4.3串的模式匹配算法

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

定位問題稱為串的模式匹配(PatternMatching),即子串定位運

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

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

算法種類:

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

?KMP算?

單回溯，速度慢1

避免回溯，匹配速度快,

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

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

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

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

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

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

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

個字符比較。

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

為S中與T匹配的子序列第一個字符的序號，即匹配成功。

否則，匹配失敗，返回值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下一首位，重新開始匹配

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

elsereturnO;

}//Index匹配成功后指針仍要回溯！因為要返回的

是被匹配的首個字符位置。

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

討論：

若n為主串長度，為子串長度，則串的BF匹配算法最壞的情

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

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

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

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

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

請看KMP算法!

KMP算法（特點：速度快）

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

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

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

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

kMP算法

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

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

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

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