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

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

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

S=a0a1a2…an-1

(n≥0)子串：第4章串串中任意個連續(xù)字符組成子序列。主串：包含子串串對應(yīng)地稱為主串。位置：字符在序列中序號。子串在主串中位置則以子串第一個字符在主串中位置來表示。相等：兩個串長度相等，而且對應(yīng)位置字符都相等。空串與空白串數(shù)據(jù)結(jié)構(gòu)與算法串第2頁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ū)分僅在于串數(shù)據(jù)對象約束為字符集。

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

在線性表操作中，大多以“單個元素”作為操作對象；

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

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

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

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

StrDelete(S,pos,len)比如：S=character，則執(zhí)行StrDelete(S,4,3)之后S=chater數(shù)據(jù)結(jié)構(gòu)與算法串第5頁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頁74.1串定義基本操作：第4章串SubString(Sub,S,pos,len)初始條件：串S存在，1≤pos≤Length(S)

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

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

初始條件：主串S和T存在，T是非空串操作結(jié)果：若主串S中存在和串T值相同子串,則返回它在主串S中從第pos個字符開始第一次出現(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頁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頁10對于串基本操作集能夠有不一樣定義方法，在使用高級程序設(shè)計語言中串類型時，應(yīng)以該語言參考手冊為準。4.1串定義基本操作第4章串

gets(str)輸入一個串；

puts(str)

輸出一個串；

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

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

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

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

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

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

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

/*pos為插入位置下標*/{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]; }①定長次序串4.2串表示和實現(xiàn)慣用實現(xiàn)方法：第4章串數(shù)據(jù)結(jié)構(gòu)與算法串第14頁

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); }}

①定長次序串4.2串表示和實現(xiàn)慣用實現(xiàn)方法：第4章串串插入函數(shù)數(shù)據(jù)結(jié)構(gòu)與算法串第15頁16①定長次序串4.2串表示和實現(xiàn)慣用實現(xiàn)方法：第4章串intStrDelete(SString*s;intpos,len)/*在串s中刪除從序號pos起len個字符*/{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頁17①定長次序串4.2串表示和實現(xiàn)慣用實現(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頁18①定長次序串4.2串表示和實現(xiàn)慣用實現(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頁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ù)①定長次序串4.2串表示和實現(xiàn)慣用實現(xiàn)方法：第4章串數(shù)據(jù)結(jié)構(gòu)與算法串第19頁SubString(SString*sub,SStrings,intpos,intlen)/*將串s中下標pos起len個字符復(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ù)①定長次序串4.2串表示和實現(xiàn)慣用實現(xiàn)方法：第4章串數(shù)據(jù)結(jié)構(gòu)與算法串第20頁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ù)（模式匹配）①定長次序串4.2串表示和實現(xiàn)慣用實現(xiàn)方法：第4章串數(shù)據(jù)結(jié)構(gòu)與算法串第21頁22②堆串4.2串表示和實現(xiàn)慣用實現(xiàn)方法：第4章串

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

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

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

賦值、插入、刪除

。數(shù)據(jù)結(jié)構(gòu)與算法串第25頁26②堆串4.2串表示和實現(xiàn)慣用實現(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頁

串賦值函數(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串表示和實現(xiàn)慣用實現(xiàn)方法：第4章串數(shù)據(jù)結(jié)構(gòu)與算法串第27頁StrInsert(HString*s,intpos,HString*t)/*在串s中下標為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串表示和實現(xiàn)慣用實現(xiàn)方法：第4章串數(shù)據(jù)結(jié)構(gòu)與算法串第28頁StrDelete(HString*s,intpos,intlen)/*在串s中刪除從下標pos起len個字符*/{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串表示和實現(xiàn)慣用實現(xiàn)方法：第4章串數(shù)據(jù)結(jié)構(gòu)與算法串第29頁30③塊鏈串4.2串表示和實現(xiàn)慣用實現(xiàn)方法：第4章串存放表示：可用鏈表來存放串值，因為串數(shù)據(jù)元素是一個字符，它只有8位二進制數(shù)，所以用鏈表存放時，通常一個結(jié)點中存放不是一個字符，而是一個定長子串,鏈表中最終一個結(jié)點不一定被占滿。存放密度

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

typedefstructBlock

{charch[BLOCK_SIZE];

structBlock

*next;

}Block;

typedefstruct{

Block*head,*tail;

intcurlen;

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

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

可將文本看成是一個大字符串，文本編輯就相當于對字符串處理。

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

可采取堆串結(jié)構(gòu)存放文本，同時建立頁表和行表，存放每頁、每行起始位置和長度。并設(shè)置頁指針、行指針和字符指針，分別指示當前頁、行和字符，4.3串應(yīng)用舉例:簡單行編輯器第4章串數(shù)據(jù)結(jié)構(gòu)與算法串第32頁例現(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)用舉例:簡單行編輯器第4章串數(shù)據(jù)結(jié)構(gòu)與算法串第33頁

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

頁表：行表：

頁號起始位置長度

行號起始位置長度

10107

1031

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

3466行表修改。

45221

57314

68714

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

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

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

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

01k-1

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

Next[j]=k作用:

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

j01234567

模式串

abaabcac

next[j]

-10011201ijk

模式串P

主串

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

next數(shù)據(jù)結(jié)構(gòu)與算法串第37頁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])/*對應(yīng)字符相等,繼續(xù)比較下一字符*/

{i++;j++;}

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

elsereturn(-1);

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

比較操作時間復(fù)雜度:O(n+m)數(shù)據(jù)結(jié)構(gòu)與算法串第38頁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];

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

模式串

求next