數(shù)據(jù)結(jié)構(gòu)第四章串PPT課件

1,第四章串,2,開始學(xué)習(xí)本講前要知道：,從數(shù)據(jù)結(jié)構(gòu)角度看，串也屬于線性結(jié)構(gòu)，具有線性結(jié)構(gòu)的共同特征；學(xué)習(xí)本章時，要注意到串所具有的線性結(jié)構(gòu)的共性，更要掌握其個性；串的特殊性主要是：串的元素是字符；本講具體內(nèi)容見本章目錄。,3,本章目錄,4.1串類型的定義4.2串的表示和實現(xiàn)4.2.1串的順序存儲結(jié)構(gòu)4.2.2串的鏈式存儲結(jié)構(gòu)4.3串的模式匹配4.3.1樸素的模式匹配算法4.3.2KMP算法4.4串的應(yīng)用舉例*4.5算法設(shè)計舉例,4,知識點和難點重點,知識點基本概念串操作模式匹配難點重點根據(jù)給定操作，編寫其它操作的算法(如，根據(jù)前5個基本操作，編寫index,replace操作KMP算法模式串的next和nextval函數(shù)值手工模擬KMP算法的執(zhí)行過程串的其它算法。,5,4.1串的基本概念及其操作,4.1.1串的基本概念串是由n（n0）個字符組成的有限序列。表示為s=“a0a1a2an-1”長度為零的串稱為空串由一個或多個空格組成的串稱為空格串。由串中任意連續(xù)字符組成的子序列稱為子串，而包含子串的串稱為該子串的主串。單個字符在字符串中的序號稱為該字符在串中的位置，而子串的第一個字符在主串中的位置稱為子串的位置。若兩個串的長度相等且對應(yīng)位置上的字符也相等，則稱兩個串相等。,6,4.1.1串的基本概念,例如，四個字符串S1=S2=“”S3=“DataStructure”S4=“Struct”與線性表相比串有其特殊性：串的數(shù)據(jù)元素只能是字符類型；串以子串為操作單位。,7,自測題1,下面關(guān)于串的的敘述中，哪一個是不正確的？A串是字符的有限序列B空串是由空格構(gòu)成的串C模式匹配是串的一種重要運算D串既可以采用順序存儲，也可以采用鏈式存儲,8,自測題2,串是一種特殊的線性表，下面哪個敘述體現(xiàn)了這種特殊性？A.數(shù)據(jù)元素是一個字符B.可以順序存儲C.數(shù)據(jù)元素可以是多個字符D.可以鏈接存儲,9,自測題3,串的長度是指（）【北京工商大學(xué)2001一.6（3分）】A串中所含不同字母的個數(shù)B串中所含字符的個數(shù)C串中所含不同字符的個數(shù)D串中所含非空格字符的個數(shù),10,自測題4,設(shè)S為一個長度為n的字符串，其中的字符各不相同，則S中的互異的非平凡子串（非空且不同于S本身）的個數(shù)為（）?！局锌圃河嬎闼?997】A2n-1Bn2C(n2/2)+(n/2)D(n2/2)+(n/2)-1E.(n2/2)-(n/2)-1F.其他情況,11,4.1.2串的抽象數(shù)據(jù)類型,12,4.2串的順序存儲結(jié)構(gòu),4.2.1串的定長順序存儲表示采用靜態(tài)內(nèi)存分配方式，分配一組地址連續(xù)的存儲單元，用來存放串的字符序列。串的定長順序存儲表示用C語言描述：#defineSTRSIZE100typedefstructcharchSTRSIZE;intlength;SqString;,13,4.2.1串的定長順序存儲表示,（1）初始化串intInitString(SqString*S,char*str)inti,len=0;char*c=str;while(*c!=0)len+;c+;/*求str的長度*/S-length=len;/*置串的當前長度值*/for(i=0;ilength;i+)/*賦值串值*/S-chi=stri;return1;,14,4.2.1串的定長順序存儲表示,（2）串插入操作步驟：判斷指定的插入位置是否合法。根據(jù)串長決定是否作截斷處理：若插入后的串長小于STRSIZE，則正常插入；若插入后的串長大于STRSIZE，且串T可以全部插入，則主串S被部分截斷；否則串T和串S都要被部分截斷。插入位置后的所有字符依次后移子串的長度。插入子串。修改串長域。,15,4.2.1串的定長順序存儲表示,intStrInsert(SqString*S,intpos,SqStringT)inti;if(posS-length)printf(插入位置不合法，其取值范圍應(yīng)該是0,length);return0;/*插入后串長小于等于STRSIZE，則正常插入*/if(S-length+T.lengthlength-1;i=pos-1;i-)S-chi+T.length=S-chi;for(i=0;ichi+pos=T.chi;/*插入*/S-length+=T.length;/*設(shè)置串長*/,16,4.2.1串的定長順序存儲表示,/*串長大于STRSIZE，則串T全部插入，串S部分截斷*/elseif(T.length+posT.length+pos-1;i-)S-chi=S-chi-T.length;/*插入位置后字符后移*/for(i=0;ichi+pos=T.chi;/*插入*/S-length=STRSIZE;/*串長大于STRSIZE,并且串T部分也要被截斷*/elsefor(i=0;ichi+pos=T.chi;S-length=STRSIZE;return1;,17,4.2.1串的定長順序存儲表示,（3）串刪除操作步驟：判斷所刪串是否為空串。判斷指定的刪除位置及刪除長度是否合法。刪除位置后的所有字符依次前移子串的長度。修改串長域。,18,4.2.1串的定長順序存儲表示,intStrDelete(SqString*S,intpos,intlen)inti;if(S-lengthS-length)printf(刪除位置及刪除長度不合法！);return0;/*當刪除長度超過串長度，則只刪到串尾即可*/if(pos+lenS-length)len=S-length-pos+1;for(i=pos+len;ilength;i+)/*前移，刪除*/S-chi-len=S-chi;S-length-=len;/*改變串長*/return1;,19,4.2.1串的定長順序存儲表示,（4）求子串intSubStr(SqStringS,intpos,intlen,SqString*T)inti;if(S.lengthS.length)printf(子串位置及子串長度不合法！);return0;/*當子串長度超過主串長度，則只取到串尾即可*/if(pos+lenS.length)len=S.length-pos+1;for(i=0;ichi=S.chi+pos;T-length=len;return1;,20,4.2.1串的定長順序存儲表示,（5）串連接必須考慮串截斷的問題：若串連接后，串的長度小于串的最大長度，則把T串連接到S串的尾部；若串連接后，串的長度大于串的最大長度但S串小于串的最大長度，則對T串超出部分進行截斷，截斷后連接到S串的尾部；若S串等于串的最大長度，則T串全部被截斷，不做連接操作。,21,4.2.1串的定長順序存儲表示,intConcat(SqString*S,SqStringT)inti;/*串的長度小于串的最大長度*/if(S-length+T.lengthchi+S-length=T.chi;S-length+=T.length;/*串的長度大于串的最大長度但S串小于串的最大長度*/elseif(S-lengthlength;ichi=T.chi-S-length;S-length=STRSIZE;return1;,22,4.2.1串的定長順序存儲表示,【例4-2】已知串S=“String”和串T=“Operation”，請用串的基本操作（不包括連接算法）實現(xiàn)連接串S和串T的算法。intconcat(SqString*s,SqStringt)StrInsert(s,s-length,t);/*使用算法4-2在S串的尾部插入串T*/return1;,23,寫出一個遞歸算法來實現(xiàn)字符串逆序存儲。【中科院研究生院2004四(7分)】voidInvertStore(charA)/字符串逆序存儲的遞歸算法。charch;staticinti=0;scanf(%c,/字符串結(jié)尾標記/結(jié)束算法,算法舉例:字符串逆序存儲,24,4.2.2串的堆存儲表示,采用動態(tài)內(nèi)存分配方式，分配一組地址連續(xù)的存儲單元，用來存放串的字符序列。C語言描述：typedefstructchar*ch;intlength;SqVString;,堆存貯表示采用動態(tài)申請內(nèi)存方法，就意味著可以隨時擴展存貯空間，因而不存在截斷串的問題。,25,4.2.2串的堆存儲表示,（2）串插入操作步驟：判斷指定的插入位置是否合法。若不合法，則算法結(jié)束。重新分配串的存儲空間，使之有足夠空間容納被插入的子串。插入位置后的所有字符依次后移子串的長度。插入子串。修改串長域。,26,4.2.2串的堆存儲表示,intStrInsert(SqVString*S,intpos,SqVStringT)inti,len;if(posS-length)printf(插入位置不合法，取值范圍0,length);return0;len=S-length+T.length;/*計算插入后的串長*/S-ch=(char*)realloc(S-ch,len*sizeof(char);if(!S-ch)printf(分配空間出錯);return0;for(i=S-length-1;i=pos;i-)/*騰出插入子串的空間*/S-chi+T.length=S-chi;for(i=0;ichi+pos=T.chi;S-length=len;return1;,27,4.2.2串的堆存儲表示,（3）串刪除操作步驟：判斷所刪串是否為空串。判斷指定的刪除位置及刪除長度是否合法。為臨時串分配空間。把刪除位置前的所有字符復(fù)制到臨時串。把被刪串的后半部分復(fù)制到臨時串。釋放原有串。把臨時串作為刪除后的串。,28,4.2.2串的堆存儲表示,intStrDelete(SqVString*S,intpos,intlen)inti,size;char*str;if(posS-length|S-lengthlength-len;if(sizechi;for(i=pos+len;ilength;i+)stri-len=S-chi;free(S-ch);S-length=size;S-ch=str;return1;,29,4.2.2串的堆存儲表示,【例4-3】設(shè)計一個串替換算法。在串S中，將第pos個字符開始的len個字符構(gòu)成的子串用串T替換。intStrReplace(SqVString*S,intpos,intlen,SqVStringT)inti,size;char*str;if(posS-length|pos+len-1S-length)printf(參數(shù)不合法！);return0;size=S-length-len+T.length;/*計算替換后的串長*/str=(char*)malloc(size*sizeof(char);/*為臨時串分配空間*/if(!str)printf(分配空間出錯);return0;for(i=0;ichi;for(i=0;ilength;i+)stri+len-1=S-chi+1;free(S-ch);S-length=size;S-ch=str;return1;,30,4.3串的鏈式存儲結(jié)構(gòu),是用鏈表存儲串值的字符序列。結(jié)點大?。好總€結(jié)點存放一個字符或多個字符結(jié)點大小為1的串的存儲結(jié)構(gòu)：typedefstructNodechardata;structNode*next;SNode,*PSNode;typedefSNode*LinkString;,31,4.3串的鏈式存儲結(jié)構(gòu),結(jié)點大小大于1的串的存儲結(jié)構(gòu)：#defineNODESIZE10typedefstructNodechardataNODESIZE;structNode*next;SSNode,*PSSNode;typedefSSNode*SLinkString;,32,4.3串的鏈式存儲結(jié)構(gòu),（2）串插入intStrInsert(LinkString*S,intpos,LinkStringT)intj=0;LinkStringp,r;p=*S;if(!*S)*S=T;return1;while(p,33,4.3串的鏈式存儲結(jié)構(gòu),（3）串刪除intStrDelete(LinkString*S,intpos,intlen)intj=1,k=0;PSNodep=NULL,q=NULL,r;p=*S;while(p,34,4.3串的鏈式存儲結(jié)構(gòu),【例4-4】設(shè)計一個算法判斷串S是否為有序串，即串中的字符為遞增或遞減排列。intSortedString(LinkStringS)PSNodep,q=NULL;p=S;q=p-next;while(q,.,35,4.4串的模式匹配算法模式匹配(PatternMatching)又稱為子串定位運算或串匹配(StringMatching)，此運算的應(yīng)用在非常廣泛。例如，在文本編輯程序中，我們經(jīng)常要查找某一特定單詞在文本中出現(xiàn)的位置。顯然，解此問題的有效算法能極大地提高文本編輯程序的響應(yīng)性能。在串匹配中，一般將主串稱為目標串，子串稱之為模式串。設(shè)S為目標串，T為模式串，且不妨設(shè)：S=“s0s1s2sn-1”T=“t0t1tm-1”串的匹配實際上是對于合法的位置0in-m依次將目標串中的子串si.i+m-1和模式串t0.m-1進行比較，若si.i+m-1=t0.m-1，,.,36,則稱從位置i開始的匹配成功，亦稱模式t在目標s中出現(xiàn)；若si.i+m-1t0.m-1，則稱從位置i開始的匹配失敗。上述的位置i又稱為位移，當si.i+m-1=t0.m-1時，i稱為有效位移；當si.i+m-1t0.m-1時，i稱為無效位移。這樣，串匹配問題可簡化為是找出某給定模式T在一給定目標T中首次出現(xiàn)的有效位移。串匹配的算法很多，這里我們只討論一種最簡單的稱為樸素的串匹配算法。其基本思想是用一個循環(huán)來依次檢查n-m+1個合法的位移i(0in-m)是否為有效位移。,37,Brute-Force算法,基本思想：從主串S=“s0s1sn-1”的第一個字符起，與模式串T=“t0t1tm-1”的第一個字符比較。若相等，則依次比較后續(xù)字符；否則，從主串的第二個字符起，重新與模式串中的字符比較。重復(fù)這個過程，直至模式串中的每個字符依次與主串中的一個連續(xù)字符序列相等，則匹配成功；否則匹配失敗【例4-5】設(shè)主串S=“cbaccbacbbb”，模式串T=“cbacb”，請在主串S中尋找模式串T。,38,樸素的模式匹配,主串S=ababcabcacbab，模式串T=abcac,i=2第一趟匹配：ababcabcacbababcj=2i=1第二趟匹配：ababcabcacbabaj=0i=6第三趟匹配：ababcabcacbababcacj=4i=3第四趟匹配：ababcabcacbabaj=0i=4第五趟匹配：ababcabcacbabaj=0i=10第六趟匹配：ababcabcacbababcac（成功）j=5,.,39,Brute-Force算法關(guān)鍵部分：for(i=0;i=n-m;i+)if(Si.i+m-1=T0.m-1)returni;intindex(SqStrings,SqStringt)inti,j,k;intm=s.length;intn=t.length;for(i=0;i=n-m;i+)j=0;k=i;while(jstrj-1)+i;+j;nexti=j;elsej=nextj;whileGetNext,53,next函數(shù)的改進,問題的提出模式串P=aaaab，其next函數(shù)值為01234，若主串為aaabaaabaaaab，當i4，j4時sipj，由nextj的指示還需進行i4、j3，i4、j2，i4、j1等三次比較。實際上，由于模式中第1、2、3個字符和第4個字符都相等，因此這種比較是不必要的，可以將模式串一次向右滑動4個字符直接進行i5、j1的比較。也就是說，若nextj=k，當si與pj失配且pjpk，則下一步不需將主串中的si與pk比較，而是直接與nextk進行比較。由以上思想對next函數(shù)進行改進，得到nextval函數(shù)如下,54,求nextval函數(shù)的算法,voidGetNextVal(STRING*P,intnextval)求模式串P的next函數(shù)修正值存入數(shù)組nextval。i=1;nextval1=0;j=0;while(ilength)if(j=0|P-stri-1=P-strj-1)+i;+j;if(P-stri-1!=P-strj-1)nextvali=j;elsenextvali=nextvalj;elsej=nextvalj;GetNextVal,55,利用nextval求模式匹配舉例,（1）p的nextval函數(shù)值為0110132。（2）利用KMP(改進