數(shù)據(jù)結(jié)構(gòu)與算法串

14.1串定義4.2串表示和實(shí)現(xiàn)第4章串*串模式匹配算法4.3

串應(yīng)用舉例：簡(jiǎn)單行編輯器4.4總結(jié)與提升數(shù)據(jù)結(jié)構(gòu)與算法串第1頁(yè)24.1串定義是由零個(gè)或多個(gè)字符組成有限序列。

S=a0a1a2…an-1

(n≥0)子串：第4章串串中任意個(gè)連續(xù)字符組成子序列。主串：包含子串串對(duì)應(yīng)地稱為主串。位置：字符在序列中序號(hào)。子串在主串中位置則以子串第一個(gè)字符在主串中位置來表示。相等：兩個(gè)串長(zhǎng)度相等，而且對(duì)應(yīng)位置字符都相等?？沾c空白串?dāng)?shù)據(jù)結(jié)構(gòu)與算法串第2頁(yè)34.1串定義串抽象數(shù)據(jù)類型定義第4章串ADTString{

數(shù)據(jù)元素：D={ai|ai∈CharacterSet,記為V,i=1,2,…，n;n≥0}

數(shù)據(jù)關(guān)系：R＝｛<ai,ai+1>|ai,ai+1∈V，i=1,2,…,n-1;n-1≥0

｝

基本操作：

（1）StrAssign(S,chars)

（2）StrInsert(S,pos,T)

（3）StrDelete(S,pos,len)

……}ADT

String

串邏輯結(jié)構(gòu)和線性表極為相同，區(qū)分僅在于串?dāng)?shù)據(jù)對(duì)象約束為字符集。

串基本操作和線性表有很大差異：

在線性表操作中，大多以“單個(gè)元素”作為操作對(duì)象；

在串基本操作中，通常以“串整體”作為操作對(duì)象。數(shù)據(jù)結(jié)構(gòu)與算法串第3頁(yè)44.1串定義基本操作：第4章串StrInsert(S,pos,T)初始條件：串S和T存在，1≤pos≤StrLength(S)+1。

操作結(jié)果：在串S第pos個(gè)字符之前插入串T。StrInsert(S,pos,T)比如：S=chater，T=rac，則執(zhí)行StrInsert(S,4,T)之后S=

character數(shù)據(jù)結(jié)構(gòu)與算法串第4頁(yè)54.1串定義基本操作：第4章串StrDelete(S,pos,len)初始條件：串S存在1≤pos≤StrLength(S)。

操作結(jié)果：從串S中刪除第pos個(gè)字符起長(zhǎng)度為len子串。

StrDelete(S,pos,len)比如：S=character，則執(zhí)行StrDelete(S,4,3)之后S=chater數(shù)據(jù)結(jié)構(gòu)與算法串第5頁(yè)64.1串定義基本操作：第4章串StrCat(S,T)初始條件：串S和T存在。

操作結(jié)果：返回由S和T聯(lián)接而成新串。StrCat(S,T)比如：StrCat(man,kind)=mankind數(shù)據(jù)結(jié)構(gòu)與算法串第6頁(yè)74.1串定義基本操作：第4章串SubString(Sub,S,pos,len)初始條件：串S存在，1≤pos≤Length(S)

且0≤len≤Length(S)-pos+1。操作結(jié)果：用Sub返回串S第pos個(gè)字符起長(zhǎng)度為len子串。SubString(Sub,S,pos,len)比如：SubString(sub1,commander,4,3)sub1=manSubString(sub2,

commander,4,7)sub2=?SubString(sub3,beijing,7,2)=?sub3=?起始位置和子串長(zhǎng)度之間存在約束關(guān)系!數(shù)據(jù)結(jié)構(gòu)與算法串第7頁(yè)84.1串定義基本操作：第4章串StrIndex(S,pos,T)

初始條件：主串S和T存在，T是非空串操作結(jié)果：若主串S中存在和串T值相同子串,則返回它在主串S中從第pos個(gè)字符開始第一次出現(xiàn)位置；不然函數(shù)值為0。StrIndex(S,pos,T)比如：S=abcaabcaaabc,T=bcaStrIndex(S,1,T)=2StrIndex(S,4,T)=6數(shù)據(jù)結(jié)構(gòu)與算法串第8頁(yè)94.1串定義基本操作：第4章串StrReplace(S,T,V)

初始條件：串S,T和V均已存在，且T是非空串。操作結(jié)果：用V替換主串S中出現(xiàn)全部與（模式串）T相等不重合子串。StrReplace(S,T,V)比如：S=abcaabcaaabca,T=bca,V=xS=axaxaax數(shù)據(jù)結(jié)構(gòu)與算法串第9頁(yè)10對(duì)于串基本操作集能夠有不一樣定義方法，在使用高級(jí)程序設(shè)計(jì)語(yǔ)言中串類型時(shí)，應(yīng)以該語(yǔ)言參考手冊(cè)為準(zhǔn)。4.1串定義基本操作第4章串

gets(str)輸入一個(gè)串；

puts(str)

輸出一個(gè)串；

strcat(str1,str2)串聯(lián)接函數(shù)；

strcpy(str1,str2,k)串復(fù)制函數(shù)；

strcmp(str1,str2)串比較函數(shù)；

strlen(str)求串長(zhǎng)函數(shù)；比如：C語(yǔ)言函數(shù)庫(kù)（包含在庫(kù)文件string.h中)提供以下串處理函數(shù)：返回?cái)?shù)據(jù)結(jié)構(gòu)與算法串第10頁(yè)114.2串表示和實(shí)現(xiàn)第4章串定長(zhǎng)次序存放表示——用一組地址連續(xù)存放單元存放串值字符序列，屬靜態(tài)存放方式。堆分配存放表示——用一組地址連續(xù)存放單元存放串值字符序列,但存放空間是在程序執(zhí)行過程中動(dòng)態(tài)分配而得。串塊鏈存放表示——鏈?zhǔn)椒绞酱娣艖T用實(shí)現(xiàn)方法：次序存放鏈?zhǔn)酱娣艛?shù)據(jù)結(jié)構(gòu)與算法串第11頁(yè)12①定長(zhǎng)次序串4.2串表示和實(shí)現(xiàn)慣用實(shí)現(xiàn)方法：第4章串存放表示：靜態(tài)數(shù)組結(jié)構(gòu)#defineMAXLEN255typedefstruct{charch[MAXLEN];intlen;}SString;

定長(zhǎng)次序串是將串設(shè)計(jì)成一個(gè)結(jié)構(gòu)類型,串存放分配是在編譯時(shí)完成。

串實(shí)際長(zhǎng)度可在預(yù)定義長(zhǎng)度范圍內(nèi)隨意設(shè)定，超出預(yù)定義長(zhǎng)度串值則被舍去,稱之為截?cái)?。?shù)據(jù)結(jié)構(gòu)與算法串第12頁(yè)13①定長(zhǎng)次序串4.2串表示和實(shí)現(xiàn)慣用實(shí)現(xiàn)方法：第4章串基本操作：

插入、刪除、復(fù)制、判空、比較、求串長(zhǎng)、清空、連接、求子串。數(shù)據(jù)結(jié)構(gòu)與算法串第13頁(yè)串插入函數(shù)StrInsert(SString*s,intpos,SStringt)

/*pos為插入位置下標(biāo)*/{inti;if(pos<0||pos>s->len) return(0);

s->len=s->len+t.len;

if(s->len+t.len<=MAXLEN) {

for(i=s->len+t.len-1;i>=t.len+pos;i--)

s->ch[i]=s->ch[i-t.len];

for(i=0;i<t.len;i++) s->ch[i+pos]=t.ch[i]; }①定長(zhǎng)次序串4.2串表示和實(shí)現(xiàn)慣用實(shí)現(xiàn)方法：第4章串?dāng)?shù)據(jù)結(jié)構(gòu)與算法串第14頁(yè)

s->len=MAXLEN; else {

if(pos+t.len<=MAXLEN) {

for(i=MAXLEN-1;i>t.len+pos-1;i--)

s->ch[i]=s->ch[i-t.len];

for(i=0;i<t.len;i++)

s->ch[i+pos]=t.ch[i]; }

s->ch[i+pos]=t.ch[i];

s->len=MAXLEN;else

{for(i=0;i<MAXLEN-pos;i++) } return(1); }}

①定長(zhǎng)次序串4.2串表示和實(shí)現(xiàn)慣用實(shí)現(xiàn)方法：第4章串串插入函數(shù)數(shù)據(jù)結(jié)構(gòu)與算法串第15頁(yè)16①定長(zhǎng)次序串4.2串表示和實(shí)現(xiàn)慣用實(shí)現(xiàn)方法：第4章串intStrDelete(SString*s;intpos,len)/*在串s中刪除從序號(hào)pos起len個(gè)字符*/{inti;if(pos<0||pos>(s->len-len))return(0);for(i=pos+len;i<s->len;i++)s->ch[i-len]=s->ch[i];s->len=s->len-len;return(1);}串刪除函數(shù):數(shù)據(jù)結(jié)構(gòu)與算法串第16頁(yè)17①定長(zhǎng)次序串4.2串表示和實(shí)現(xiàn)慣用實(shí)現(xiàn)方法：第4章串串復(fù)制函數(shù):voidStrCopy(SString*s,SStringt)/*將串t值復(fù)制到串s中*/{inti;for(i=0;i<t.len;i++)s->ch[i]=t.ch[i];s->len=t.len;}數(shù)據(jù)結(jié)構(gòu)與算法串第17頁(yè)18①定長(zhǎng)次序串4.2串表示和實(shí)現(xiàn)慣用實(shí)現(xiàn)方法：第4章串串比較函數(shù):intStrCompare(SStrings,SStringt)/*若串s和t相等,則返回0;若s>t,返回值大于0;若s<t返回值小于0.*/{inti;for(i=0;i<s.len&&i<t.len;i++)if(s.ch[i]!=t.ch[i])return(s.ch[i]-t.ch[i]);return(s.len-t.len);}

數(shù)據(jù)結(jié)構(gòu)與算法串第18頁(yè)StrCat(SString*s,SStringt){inti,flag;

if(s->len+t.len<=MAXLEN){for(i=s->len;i<s->len+t.len;i++)

s->ch[i]=t.ch[i-s->len];

s->len+=t.len;flag=1;}

elseif(s->len<MAXLEN)

{for(i=s->len;i<MAXLEN;i++)

s->ch[i]=t.ch[i-s->len];

s->len=MAXLEN;flag=0;}

elseflag=0;

return(flag);}連接函數(shù)①定長(zhǎng)次序串4.2串表示和實(shí)現(xiàn)慣用實(shí)現(xiàn)方法：第4章串?dāng)?shù)據(jù)結(jié)構(gòu)與算法串第19頁(yè)SubString(SString*sub,SStrings,intpos,intlen)/*將串s中下標(biāo)pos起len個(gè)字符復(fù)制到sub中*/{inti;if(pos<0||pos>s.len||len<1||len>s.len-pos){sub->len=0;return(0);}else{for(i=0;i<len;i++)sub->ch[i]=s.ch[i+pos];sub->len=len;return(1);}}求子串函數(shù)①定長(zhǎng)次序串4.2串表示和實(shí)現(xiàn)慣用實(shí)現(xiàn)方法：第4章串?dāng)?shù)據(jù)結(jié)構(gòu)與算法串第20頁(yè)StrIndex(SStrings,SStringt,intpos)/*求串t在串s中位置*/{inti,j,start;

if(t.len==0)return(0);

start=pos;i=start;j=0;

while(i<s.len&&j<t.len)

if(s.ch[i]==t.ch[j]){i++;j++;}

else{start++;i=start;j=0;}

if(j>=t.len)return(start);

elsereturn(-1);}定位函數(shù)（模式匹配）①定長(zhǎng)次序串4.2串表示和實(shí)現(xiàn)慣用實(shí)現(xiàn)方法：第4章串?dāng)?shù)據(jù)結(jié)構(gòu)與算法串第21頁(yè)22②堆串4.2串表示和實(shí)現(xiàn)慣用實(shí)現(xiàn)方法：第4章串

很多實(shí)用串處理系統(tǒng)中,采取堆結(jié)構(gòu),它特點(diǎn)是:系統(tǒng)將一個(gè)很大連續(xù)存放空間作為串公用空間,每當(dāng)建立新串時(shí),系統(tǒng)從中分配一個(gè)和串長(zhǎng)相同連續(xù)空間存放串值,它們地址是在程序執(zhí)行中動(dòng)態(tài)分配.

系統(tǒng)中全部串名存放映像組成一個(gè)符號(hào)表。其中l(wèi)en域指示串長(zhǎng)度,start域指示串起始位置。借助此結(jié)構(gòu)能夠在串名和串值之間建立一個(gè)對(duì)應(yīng)關(guān)系，稱為串名存放映像。數(shù)據(jù)結(jié)構(gòu)與算法串第22頁(yè)23②堆串4.2串表示和實(shí)現(xiàn)慣用實(shí)現(xiàn)方法：第4章串a(chǎn)='aprogram'，b='string'，c='process'，free=23。aprogramstringprocessHeap[MAXSIZE]free=23符號(hào)名lenstarta90b79c716符號(hào)表堆串存放映象示例數(shù)據(jù)結(jié)構(gòu)與算法串第23頁(yè)24②堆串4.2串表示和實(shí)現(xiàn)慣用實(shí)現(xiàn)方法：第4章串存放表示：typedefstruct{char*ch;intlen;}HString;用C語(yǔ)言中“堆”實(shí)現(xiàn)堆串,可用malloc()和free()完成動(dòng)態(tài)存放管理。其定義為:其中l(wèi)en域指示串長(zhǎng)度，ch域指示串起始地址。數(shù)據(jù)結(jié)構(gòu)與算法串第24頁(yè)25堆串基本操作

堆串操作實(shí)現(xiàn)基本方法為：先為新生成串分配一個(gè)存放空間，然后進(jìn)行串值復(fù)制。②堆串4.2串表示和實(shí)現(xiàn)慣用實(shí)現(xiàn)方法：第4章串

賦值、插入、刪除

。數(shù)據(jù)結(jié)構(gòu)與算法串第25頁(yè)26②堆串4.2串表示和實(shí)現(xiàn)慣用實(shí)現(xiàn)方法：第4章串StrCopy(HString*s，t)/*將串t值復(fù)制到串s中*/{inti;s->ch=(char*)malloc(t.len);if(s->ch==NULL)return(0);for(i=0;i<t.len;i++)s->ch[i]=t.ch[i];s->len=t.len;return(1);}串復(fù)制函數(shù)數(shù)據(jù)結(jié)構(gòu)與算法串第26頁(yè)

串賦值函數(shù)StrAssign(HString*s,char*tval)

/*將字符串常量tval值賦給串s*/{intlen，i=0;if(s->ch!=NULL)free(s->ch);while(tval[i]!='\0')i++;len=i;if(len){s->ch=(char*)malloc(len);if(s->ch==NULL)return(0);for(i=0;i<len;i++)s->ch[i]=tval[i];}elses->ch=NULL;s->len=len;return(1);}②堆串4.2串表示和實(shí)現(xiàn)慣用實(shí)現(xiàn)方法：第4章串?dāng)?shù)據(jù)結(jié)構(gòu)與算法串第27頁(yè)StrInsert(HString*s,intpos,HString*t)/*在串s中下標(biāo)為pos字符之前插入串t*/{inti;char*temp;if(pos<0||pos>s->len||s->len==0)return(0);temp=(char*)malloc(s->len+t.len);if(temp==NULL)return(0);for(i=0;i<pos;i++)temp[i]=s->ch[i];for(i=0;i<t->len;i++)temp[i+pos]=t->ch[i];for(i=pos;i<s->len;i++)temp[i+t->len]=s->ch[i];s->len+=t->len;free(s->ch);s->ch=temp;return(1);}

串插入函數(shù)②堆串4.2串表示和實(shí)現(xiàn)慣用實(shí)現(xiàn)方法：第4章串?dāng)?shù)據(jù)結(jié)構(gòu)與算法串第28頁(yè)StrDelete(HString*s,intpos,intlen)/*在串s中刪除從下標(biāo)pos起len個(gè)字符*/{inti;char*temp;if(pos<0||pos>(s->len-len))return(0);temp=(char*)malloc(s->len-len);if(temp==NULL)return(0);for(i=0;i<pos;i++)temp[i]=s->ch[i];for(i=pos;i<s->len-len;i++)temp[i]=s->ch[i+len];s->len=s->len-len;free(s->ch);s->ch=temp;return(1);}

串刪除函數(shù)②堆串4.2串表示和實(shí)現(xiàn)慣用實(shí)現(xiàn)方法：第4章串?dāng)?shù)據(jù)結(jié)構(gòu)與算法串第29頁(yè)30③塊鏈串4.2串表示和實(shí)現(xiàn)慣用實(shí)現(xiàn)方法：第4章串存放表示：可用鏈表來存放串值，因?yàn)榇當(dāng)?shù)據(jù)元素是一個(gè)字符，它只有8位二進(jìn)制數(shù)，所以用鏈表存放時(shí)，通常一個(gè)結(jié)點(diǎn)中存放不是一個(gè)字符，而是一個(gè)定長(zhǎng)子串,鏈表中最終一個(gè)結(jié)點(diǎn)不一定被占滿。存放密度

=數(shù)據(jù)元素所占存放位實(shí)際分配存放位abcdefghi###^數(shù)據(jù)結(jié)構(gòu)與算法串第30頁(yè)31#defineBLOCK_SIZE4

typedefstructBlock

{charch[BLOCK_SIZE];

structBlock

*next;

}Block;

typedefstruct{

Block*head,*tail;

intcurlen;

}BLString;塊鏈串存放結(jié)構(gòu)定義：實(shí)際應(yīng)用時(shí),能夠依據(jù)問題所需來設(shè)置結(jié)點(diǎn)大小。4.2串表示和實(shí)現(xiàn)第4章串返回?cái)?shù)據(jù)結(jié)構(gòu)與算法串第31頁(yè)

文本編輯程序用于源程序輸入和修改、公文書信、報(bào)刊和書籍編輯排版等。慣用文本編輯程序有Edit，WPS，Word等。

可將文本看成是一個(gè)大字符串，文本編輯就相當(dāng)于對(duì)字符串處理。

為編輯方便，可將文本用分頁(yè)符和分行符分成若干頁(yè)，每頁(yè)若干行。

可采取堆串結(jié)構(gòu)存放文本，同時(shí)建立頁(yè)表和行表，存放每頁(yè)、每行起始位置和長(zhǎng)度。并設(shè)置頁(yè)指針、行指針和字符指針，分別指示當(dāng)前頁(yè)、行和字符，4.3串應(yīng)用舉例:簡(jiǎn)單行編輯器第4章串?dāng)?shù)據(jù)結(jié)構(gòu)與算法串第32頁(yè)例現(xiàn)有funcmax(x,y:integer):integer;pascalvarz:integer;

程序：beginifx>ythenz:=x;elsez:=y;return(z);

其堆串：

end;funcmax(x,y:Integer):Integer;↙varz:integer;↙begIn↙Ifx>ythenz:=x;↙elsez:=y;↙return(z);↙end;↙4.3串應(yīng)用舉例:簡(jiǎn)單行編輯器第4章串?dāng)?shù)據(jù)結(jié)構(gòu)與算法串第33頁(yè)

funcmax(x,y:Integer):Integer;↙varz:integer;↙begIn↙Ifx>ythenz:=x;↙elsez:=y;↙return(z);↙end;↙

頁(yè)表：行表：

頁(yè)號(hào)起始位置長(zhǎng)度

行號(hào)起始位置長(zhǎng)度

10107

1031

23115插入、刪除就要引發(fā)頁(yè)表、

3466行表修改。

45221

57314

68714

71015返回?cái)?shù)據(jù)結(jié)構(gòu)與算法串第34頁(yè)主要知識(shí)點(diǎn)：1.串是一個(gè)特定線性表，其特殊性就在于組成線性表每個(gè)元素就是一個(gè)單字符。2.串慣用存放方式有三種：次序串，堆串和塊鏈串。3.次序串以一維數(shù)組作為存放結(jié)構(gòu)，運(yùn)算實(shí)現(xiàn)類同次序表。塊鏈串以鏈表作為存放結(jié)構(gòu)，運(yùn)算實(shí)現(xiàn)類同鏈表。4.串模式匹配算法是本章重點(diǎn)，簡(jiǎn)單模式匹配算法處理思緒簡(jiǎn)單，因?yàn)檫M(jìn)行了帶回溯處理，時(shí)間復(fù)雜度較高。改進(jìn)KMP模式匹配算法計(jì)算滑支位置，因而失配后無回溯，匹配速度較高。4.4總結(jié)與提升第4章串返回?cái)?shù)據(jù)結(jié)構(gòu)與算法串第35頁(yè)

算法思緒:每當(dāng)一趟匹配過程出現(xiàn)s[i]<>t[j]時(shí),不需回溯i指針,而是利用已經(jīng)得到匹配結(jié)果將模式向右滑動(dòng)盡可能遠(yuǎn),再繼續(xù)比較。

依據(jù)模式串字符間規(guī)律結(jié)構(gòu)一個(gè)next(j)函數(shù),表示第j個(gè)字符與主串失配時(shí),在模式中需重新比較字符位置。

KMP算法時(shí)間復(fù)雜度能夠到達(dá)O(m+n)*模式匹配KMP算法第4章串?dāng)?shù)據(jù)結(jié)構(gòu)與算法串第36頁(yè)j-k+1j-1失配時(shí)若有：則模式串向右滑動(dòng),k對(duì)應(yīng)到j(luò)即可,next(j)=k。'pp…p'='p…p'

01k-1

Next[j]=k含義:在模式串子串P0…Pj中,頭串與尾串相等最大長(zhǎng)度為k。

Next[j]=k作用:

在Pj與主串比較失配時(shí)，無需回溯主串比較指針i，而是讓i保持不變，繼續(xù)與模式串中Pk比較即可。定義：模式串next函數(shù)

j01234567

模式串

abaabcac

next[j]

-10011201ijk

模式串P

主串

模式串Pkjj-kj-1其它情況0max{k|1<k<j且當(dāng)j=0時(shí)-1[j]='pp…p'='pp'}01k-1…

next數(shù)據(jù)結(jié)構(gòu)與算法串第37頁(yè)intStrIndex_KMP(SStrings,intpos,SStringt)

/*利用next函數(shù)，求主串s中pos位置起,串t第一次出現(xiàn)位置*/

{inti,j;

if(t.len==0)return(0);/*空串是任意字符串子串*/

i=pos;j=0;

while(i<s.len&&j<t.len)

if(j==-1||s.ch[i]==t.ch[j])/*對(duì)應(yīng)字符相等,繼續(xù)比較下一字符*/

{i++;j++;}

elsej=next[j];/*字符失配,則用next函數(shù)值更新j值,而i值不變*/if(j>=t.len)return(i-j);/*成功,返回主串當(dāng)前起始匹配位置*/

elsereturn(-1);

}j=-1表示以前比較是首字符且不匹配應(yīng)從主串后繼字符起從頭比較基本操作:

比較操作時(shí)間復(fù)雜度:O(n+m)數(shù)據(jù)結(jié)構(gòu)與算法串第38頁(yè)acabaabaabcacaabcabaabcaci=7j=2abaabcaci=7j=5abaabcaci=2j=0abaabcaci=1j=0abaabcaci=1j=1abaabcaci=0j=0

j

01234567

模式串

abaabcac

next[j]

-10011201abaabcaci=13j=8while(i<s.len&&j<t.len)

if(j==-1||s.ch[i]==t.ch[j])

{i++;j++;}{繼續(xù)比較后繼字符}

elsej=next[j];

{模式串向右移動(dòng)}數(shù)據(jù)結(jié)構(gòu)與算法串第39頁(yè)jk

模式串

求next