數(shù)據(jù)結(jié)構(gòu)串市公開課一等獎(jiǎng)省賽課獲獎(jiǎng)?wù)n件

1第4章串

一、基本內(nèi)容：本章基本內(nèi)容是：串概念、串存放結(jié)構(gòu)和串基本操作。二、學(xué)習(xí)關(guān)鍵點(diǎn)：1.熟悉串基本操作定義及利用這些操作實(shí)現(xiàn)串各種操作方法.2.熟練掌握在串定長次序存放結(jié)構(gòu)上實(shí)現(xiàn)串各種操作方法.3.掌握串堆存放結(jié)構(gòu)以及在其上實(shí)現(xiàn)串操作基本方法.4.了解串模式匹配算法及其改進(jìn)KMP算法.數(shù)據(jù)結(jié)構(gòu)串第1頁24.1串類型定義

串（String）是由零個(gè)或多個(gè)字符組成有限序列。通常記作：Ｓ=‘c1c2…cn’(n≥0)其中，Ｓ是串名；串中ci（１≤i≤n）能夠是字母、數(shù)字、空格或其它字符。用引號括起來部分是串值，即串S內(nèi)容，注意引號本身不屬于串。串相關(guān)概念以下：

數(shù)據(jù)結(jié)構(gòu)串第2頁34.1串類型定義(1)串長度串中字符個(gè)數(shù)稱為串長度，如上面串Ｓ長度為n。(2)空串不含有任何字符串稱為空串(ＮullString)，空串長度為零。本教材用符號“Φ”表示空串。

(3)空格串由一個(gè)或多個(gè)空格組成串稱為空格串（BlankString）,

空格串長度為串中空格個(gè)數(shù)。注意空格串不等于空串。數(shù)據(jù)結(jié)構(gòu)串第3頁44.1串類型定義(4)子串與主串串中任意多個(gè)連續(xù)字符組成子序列稱為該串子串；包含子串串稱為主串。(5)串中位置

字符在序列中序號稱為該字符在串中位置。(6)串相等

兩個(gè)字符串相等，是指兩個(gè)字符串值相等，也就是說這兩個(gè)字符串不但長度相等，而且對應(yīng)位置上字符也相等。

數(shù)據(jù)結(jié)構(gòu)串第4頁54.1串類型定義（７）串比較兩個(gè)串比較實(shí)際上是ASCII碼比較。兩個(gè)串從第一個(gè)位置上字符開始進(jìn)行比較，當(dāng)?shù)谝淮纬霈F(xiàn)ASCII碼大串為大，若比較過程中出現(xiàn)一個(gè)字符串結(jié)束情況，則另一個(gè)串為較大者。數(shù)據(jù)結(jié)構(gòu)串第5頁6注：串操作是以“串整體”為操作對象。注：串值必須用一對單引號括起來，但單引號本身不屬于串，它作用只是為了防止與變量名或數(shù)常量混同而已。注：子串在主串中位置以子串第一個(gè)字符在主串中位置來表示。數(shù)據(jù)結(jié)構(gòu)串第6頁74.1串類型定義對于串基本操作大致有以下幾個(gè)：（1）StrAssign(&T,

chars)

串賦值，將串值chars賦值給串T。（2）StrCopy(&T,S)

串復(fù)制，將一個(gè)串s賦給串T。（3）StrEmpty(s)

判串空，判斷串s是否為空。

數(shù)據(jù)結(jié)構(gòu)串第7頁84.1串類型定義（4）StrCompare(s,t)

串比較，若s>t，則返回值>0；若s=t，

則返回值=0；若s<t，則返回值<0。（5）StrLength(s)

求串長，返回串s長度。（6）StrEqual(s,t)

判斷串相等，兩個(gè)串s和t相等時(shí)候返回1；不然返回0。

數(shù)據(jù)結(jié)構(gòu)串第8頁94.1串類型定義（7）Concat(&T,s1,s2)用T返回串s1和串s2連接結(jié)果。（8）SubString(&Sub,s,pos,len)用Sub返回串s第pos個(gè)字符開始長度為len子串。（9）Index(s,t,pos)返回子串t在主串S中第pos個(gè)字符之后第一次出現(xiàn)位置；若子串t不在主串S中，則函數(shù)值為0。（10）StrInsert(&s,pos,t)將串t插入到s第pos個(gè)位置。數(shù)據(jù)結(jié)構(gòu)串第9頁104.1串類型定義（11）StrDelete(&s,pos,len)

子串刪除，刪除串s中第pos個(gè)字符開始為len子串。（12）Replace(&s,t,v)

子串替換，將串s中全部串t出現(xiàn)位置均替換為v。（13）ClearString(&s)

將s清為空串。（14）DestroyString(&s)

串s被銷毀。數(shù)據(jù)結(jié)構(gòu)串第10頁114.2串表示和實(shí)現(xiàn)

因?yàn)榇翘厥饩€性表，故其存放結(jié)構(gòu)與線性表存放結(jié)構(gòu)類似。只不過因?yàn)榻M成串結(jié)點(diǎn)是單個(gè)字符。串有三種機(jī)內(nèi)表示方法:定長次序存放表示,堆分配存放表示,串鏈?zhǔn)酱娣沤Y(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)串第11頁124.2.1定長次序存放表示

定長次序存放表示,也稱為靜態(tài)存放分配。它是用一組連續(xù)存放單元來存放串中字符序列。每個(gè)串預(yù)先分配一個(gè)固定長度存放區(qū)域。所謂定長次序存放結(jié)構(gòu)，是直接使用定長字符數(shù)組來定義，數(shù)組上界預(yù)先給出：#defineMAXSTRLEN255typedefunsignedcharsstring[MAXSTRLEN+1];sstrings;//s是一個(gè)可容納255個(gè)字符次序串,0號單元存放串長度。實(shí)際串長可在所分配固定長度區(qū)域內(nèi)變動以下標(biāo)為0數(shù)組分量存放串實(shí)際長度——PASCAL；在串值后加入”\0”表示結(jié)束，此時(shí)串長為隱含值——C數(shù)據(jù)結(jié)構(gòu)串第12頁13串聯(lián)結(jié)StatusConcat(sstring&t,sstrings1,sstrings2){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;}elseif(s1[0])<=MAXSTRLEN{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.[1..MAXSTRLEN]=s1[1..MAXSTRLEN];t.[0]=MAXSTRLEN;uncut=FALSE;}returnuncut;}數(shù)據(jù)結(jié)構(gòu)串第13頁14求子串StatusSubstring(sstring&sub,sstrings,intpos,intlen){if(pos<1||pos>s[0]||len<0||len>s.[0]-pos+1)returnERROR;sub[1..len]=s[pos..pos+len-1];sub[0]=len;returnOK;}數(shù)據(jù)結(jié)構(gòu)串第14頁154.2.2堆分配存放表示以一組地址連續(xù)存放單元存放串值字符序列；存放空間動態(tài)分配，用malloc()和free()來管理；P75示例數(shù)據(jù)結(jié)構(gòu)串第15頁164.2.3串塊鏈存放表示串鏈?zhǔn)酱娣欧绞浇Y(jié)點(diǎn)大?。阂粋€(gè)或多個(gè)字符P78圖4.2(a)(b)存放密度=串值所占存放位/實(shí)際分配存放位數(shù)據(jù)結(jié)構(gòu)串第16頁17串基本操作串插入StatusStrInsert(HString&S,intpos,HStringT)串賦值StatusStrAssign(HString&S,char*chars)求串長intStrLength(HStringS)串比較intStrCompare(HStringS,HStringT)串聯(lián)接StatusConcat(HString&S,HStringS1,HStringS2)求子串StatusSubString(HString&Sub,HStringS,intpos,intlen)串清空StatusClearString(HString&S)串定位刪除置換數(shù)據(jù)結(jié)構(gòu)串第17頁18StatusStrInsert(HString&S,intpos,HStringT)（75頁）//在串S第pos個(gè)位置前插入串S{ inti; if(pos<1||pos>S.length+1)returnERROR; if(T.length){ if(!(S.ch=(char*)realloc(S.ch,(S.length+T.length)*sizeof(char)))) exit(OVERFLOW); for(i=S.length-1;i>=pos-1;--i){ S.ch[i+T.length]=S.ch[i]; } for(i=0;i<=T.length-1;i++) S.ch[pos-1+i]=T.ch[i]; S.length+=T.length; }returnOK;}數(shù)據(jù)結(jié)構(gòu)串第18頁19StatusStrAssign(HString&S,char*chars)

生成一個(gè)值等于chars串S(76頁){

inti,j;char*c;

for(i=0,c=chars;*c;++i,++c); if(!i){S.ch=NULL;S.length=0;} else{ if(!(S.ch=(char*)malloc(i*sizeof(char)))) exit(OVERFLOW); for(j=0;j<=i-1;j++){ S.ch[j]=chars[j];} S.length=i; }

returnOK;}數(shù)據(jù)結(jié)構(gòu)串第19頁20intStrLength(HStringS)

求串長度{ returnS.length;}數(shù)據(jù)結(jié)構(gòu)串第20頁21intStrCompare(HStringS,HStringT)

比較兩個(gè)串，若相等返回0{ inti; for(i=0;i<S.length&&i<T.length;++i) if(S.ch[i]!=T.ch[i])returnS.ch[i]-T.ch[i]; returnS.length-T.length;}數(shù)據(jù)結(jié)構(gòu)串第21頁22StatusConcat(HString&S,HStringS1,HStringS2)

用S返回由S1和S2聯(lián)接而成新串{ intj; if(!(S.ch=(char*)malloc((S1.length+S2.length)*sizeof(char)))) exit(OVERFLOW); for(j=0;j<=S1.length-1;j++){ S.ch[j]=S1.ch[j];} S.length=S1.length+S2.length; for(j=0;j<=S2.length-1;j++){ S.ch[S1.length+j]=S2.ch[j];} returnOK;}數(shù)據(jù)結(jié)構(gòu)串第22頁23StatusSubString(HString&Sub,HStringS,intpos,intlen)

用Sub返回串S第pos個(gè)字符開始長度為len子串{ if(pos<1||pos>S.length||len<0||len>S.length-pos+1) returnERROR; if(!len){Sub.ch=NULL;Sub.length=0;} else{ Sub.ch=(char*)malloc(len*sizeof(char)); for(intj=0;j<=len-1;j++){ Sub.ch[j]=S.ch[pos-1+j];} Sub.length=len; } returnOK;}數(shù)據(jù)結(jié)構(gòu)串第23頁24StatusClearString(HString&S)

將S清為空串{ if(S.ch){free(S.ch);S.ch=NULL;} S.length=0; returnOK;}數(shù)據(jù)結(jié)構(gòu)串第24頁254.3串模式匹配算法定義在串中尋找子串（第一個(gè)字符）在串中位置詞匯在模式匹配中，子串稱為模式，串稱為目標(biāo)。示例

目標(biāo)S:“Beijing”

模式P:“jin”

匹配結(jié)果

=4

數(shù)據(jù)結(jié)構(gòu)串第25頁261.窮舉模式匹配設(shè)S=s1,s2,…,sn(主串)P=p1,p2,…,pm(模式串)i為指向S中字符指針，j為指向P中字符指針匹配失?。簊i≠pj時(shí)，(si-j+1

…si-1)=(p1

…pj-1)回溯：i=i-j+2;j=1重復(fù)回溯太多，O(m*n)數(shù)據(jù)結(jié)構(gòu)串第26頁27第1趟

S abbaba窮舉模式

P aba 匹配過程

第2趟

S abbaba P aba

第3趟

S abbaba P aba

第4趟

S abbaba Paba

數(shù)據(jù)結(jié)構(gòu)串第27頁28求子串位置定位函數(shù)intIndex(SStringS,SStringT,intpos){//窮舉模式匹配

inti=pos; intj=1; while(i<=S[0]&&j<=T[0]){//當(dāng)兩串未檢測完，S[0]、S[0]為串長

if(S[i]==T[j]){++i;++j;} else{i=i-j+2;j=1;} } if(j>T[0])returni-T[0];//匹配成功

elsereturn0;}數(shù)據(jù)結(jié)構(gòu)串第28頁292.KMP快速模式匹配D.E.Knuth,J.H.Morris,V.R.Pratt同時(shí)發(fā)覺無回溯模式匹配數(shù)據(jù)結(jié)構(gòu)串第29頁30Ss1…

si-j-1si-j

si-j+1si-j+2…

si-1si

si+1…

sn

‖‖‖‖P

p1p2…

pj-1pjpj+1…pm

則有

si-j+1si-j+2

…

si-1=p1p2…pj-1(1)

為使模式P與目標(biāo)S匹配，必須滿足

p1p2…pj-1pj

…pm=si-j+1si-j+2…

si-1si

…

si-j+m

假如

p1…pj-2

p2p3…pj-1

(2)

由(1)(2)則立刻能夠斷定

p1…pj-2

si-j+2si-j+3…

si-1

下一趟必不匹配數(shù)據(jù)結(jié)構(gòu)串第30頁31一樣，若

p1p2…pj-3

p3p4…pj-1則再下一趟也不匹配，因?yàn)橛?/p>

p1…pj-3

si-j+3…

si-1直到對于某一個(gè)“k”值，使得

p1…pk

pj-k

pi-k+1

…pj-1且

p1…pk-1=pj-k+1

pj-k+2…pj-1則

p1…pk-1=si-k+1

si-k+2

…

si-1

‖‖‖

pj-k+1

pj-k+3…

pj-1模式右滑j-k位數(shù)據(jù)結(jié)構(gòu)串第31頁32next數(shù)組值假設(shè)當(dāng)模式中第j個(gè)字符與主串中對應(yīng)字符“失配”時(shí)，能夠拿第k個(gè)字符來繼續(xù)比較，則令next[j]=knext函數(shù)定義：

0當(dāng)j=1時(shí)next[j]=Max{k|1<k<j且’p1…pk-1’=

‘pj-k+1…pj-1’}當(dāng)此集合不空時(shí)

1其它情況數(shù)據(jù)結(jié)構(gòu)串第32頁33手工求next數(shù)組方法序號j12345678模式Pabaabcack1122312Pk==Pj≠=≠=≠=≠next[j]01122312Nextval[j]01021302數(shù)據(jù)結(jié)構(gòu)串第33頁34利用KMP算法匹配過程第1趟目標(biāo)acabaabaabcacaabc

模式

abaabcac

next(2)=1第2趟目標(biāo)acabaabaabcacaabc

模式

abaabcacnext(1)=0第3趟目標(biāo)acabaabaabcacaabc

模式

abaabcac

next(6)=3第4趟目標(biāo)acabaabaabcacaabc

模式

(ab)aabcac

數(shù)據(jù)結(jié)構(gòu)串第34頁35KMP算法intIndex_KMP(SStringS,SStringT,int*next){ inti,j; i=1;j=1; while(i<=S[0]&&j<=T[0]){ if(j==0||S[i]==T[j]){++i;++j;} elsej=next[j]; } if(j>T[0])returni-T[0]; elsereturn0;}數(shù)據(jù)結(jié)構(gòu)串第35頁36求next數(shù)組步驟(1)nex