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

數(shù)據(jù)結(jié)構(gòu)南昌工程學(xué)院數(shù)據(jù)結(jié)構(gòu)第1頁

4.1 串類型定義

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

**4.3 串模式匹配算法

**4.4 串操作應(yīng)用舉例

目錄第四章串?dāng)?shù)據(jù)結(jié)構(gòu)第2頁知識(shí)點(diǎn)串相關(guān)概念和術(shù)語串基本運(yùn)算功效串次序存放方法（包含緊縮格式和非緊縮格式）和鏈接存放方法串匹配運(yùn)算難點(diǎn)串匹配運(yùn)算算法要求熟練掌握串邏輯結(jié)構(gòu)、存放結(jié)構(gòu)及串上基本運(yùn)算，并能設(shè)計(jì)簡(jiǎn)單算法了解串匹配運(yùn)算算法基本思想數(shù)據(jù)結(jié)構(gòu)第3頁4.1 串類型定義串基本概念

串(String)是零個(gè)或多個(gè)字符組成有限序列。普通記作S=“a1a2a3…an”，其中S是串名，雙引號(hào)括起來字符序列是串值；ai(1≦i≦n)能夠是字母、數(shù)字或其它字符；串中所包含字符個(gè)數(shù)稱為該串長(zhǎng)度。長(zhǎng)度為零串稱為空串(EmptyString)，它不包含任何字符。通常將僅由一個(gè)或多個(gè)空格組成串稱為空白串(BlankString)注意：空串和空白串不一樣，比如“”和“”分別表示長(zhǎng)度為1空白串和長(zhǎng)度為0空串。串中任意個(gè)連續(xù)字符組成子序列稱為該串子串，包含子串串對(duì)應(yīng)地稱為主串。通常將子串在主串中首次出現(xiàn)時(shí)該子串首字符對(duì)應(yīng)主串中序號(hào)，定義為子串在主串中序號(hào)（或位置）。數(shù)據(jù)結(jié)構(gòu)第4頁比如，設(shè)A和B分別為A=“Thisisastring”B=“is”則B是A子串，A為主串。B在A中出現(xiàn)了兩次，其中首次出現(xiàn)所對(duì)應(yīng)主串位置是3。所以，稱B在A中序號(hào)（或位置）為3

尤其地，空串是任意串子串，任意串是其本身子串。通常在程序中使用串可分為兩種：串變量和串常量。串常量和整常數(shù)、實(shí)常數(shù)一樣，在程序中只能被引用但不能不能改變其值，即只能讀不能寫。通常串常量是由直接量來表示，比如語句Error(“overflow”)中“overflow”是直接量。串變量和其它類型變量一樣，其取值是能夠改變。數(shù)據(jù)結(jié)構(gòu)第5頁串抽象數(shù)據(jù)定義

串抽象數(shù)據(jù)類型定義見書P71串基本操作對(duì)于串基本操作，許多高級(jí)語言均提供了對(duì)應(yīng)運(yùn)算或標(biāo)準(zhǔn)庫函數(shù)來實(shí)現(xiàn)。下面僅介紹幾個(gè)在C語言中慣用串運(yùn)算。定義以下幾個(gè)變量：chars1[20]=“dirtreeformat”,s2[20]=“file.mem”;chars3[30],*p;intresult;（1）求串長(zhǎng)(length)intstrlen(chars);//求串長(zhǎng)度比如：printf(“%d”,strlen(s1));輸出13數(shù)據(jù)結(jié)構(gòu)第6頁（2）串復(fù)制(copy)char*strcpy(charto,charfrom);該函數(shù)將串from復(fù)制到串to中，而且返回一個(gè)指向串to開始處指針。比如：strcpy(s3,s1);//s3=“dirtreeformat”(3)聯(lián)接(concatenation)charstrcat(charto,charfrom)該函數(shù)將串from復(fù)制到串to末尾，而且返回一個(gè)指向串to開始處指針。比如：strcat(s3,”/”)strcat(s3,s2);//s3=“dirtreeformat/file.mem”數(shù)據(jù)結(jié)構(gòu)第7頁(4)串比較（compare)intstrcmp(chars1,chars2);該函數(shù)比較串s1和串s2大小，當(dāng)返回值小于0，等于0或大于0時(shí)分別表示s1<s2\s1=s2或s1>s2比如：result=strcmp(“baker”,”Baker”)result>0result=strcmp(“12”,”12”);result=0result=strcmp(“Joe”,”Joseph”);result<0（5）字符定位(index)char*strchr(chars,charc);該函數(shù)是找c在字符串中第一次出現(xiàn)位置，若找到則返回該位置，不然返回NULL。比如：p=strchr(s2,”.”);p指向“file”之后位置if(p)strcpy(p,”.cpp”);s2=“file.cpp”

上述串操作是最基本，其中后四個(gè)還有變種形式：strncpy，strncat，strncmp，strnchr。串其余操作可由這些基本操作組合而成。數(shù)據(jù)結(jié)構(gòu)第8頁例1、求子串求子串過程即為復(fù)制字符序列過程，將串S中第pos個(gè)字符開始長(zhǎng)度為len字符復(fù)制到串T中。voidsubstr(stringsub,strings,intpos,intlen){if(pos<0||pos>strlen(s)-1||len<0)error(“parametererror”)strncpy(sub,&s[pos],len);}例2、串定位index(s,t,pos)在主串中取從第i個(gè)字符起、長(zhǎng)度和串T相等子串和T比較，若相等，則求得函數(shù)值為i，不然值增1直至S中不存在和串T相等子串為止。

數(shù)據(jù)結(jié)構(gòu)第9頁intindex(strings,stringt,intpos){if(pos>0){n=strlen(s);m=strlen(t);i=pos;while(i<n-m+1){substr(sub,s,i,m);if(strcmp(sub,t)!=0)++i;elsereturn(i);}}return(0);}數(shù)據(jù)結(jié)構(gòu)第10頁4.2 串表示和實(shí)現(xiàn)因?yàn)榇翘厥饩€性表，故其存放結(jié)構(gòu)與線性表存放結(jié)構(gòu)類似。只不過因?yàn)榻M成串結(jié)點(diǎn)是單個(gè)字符。串有三種機(jī)內(nèi)表示方法，下面分別介紹。定長(zhǎng)次序存放表示定長(zhǎng)次序存放表示,也稱為靜態(tài)存放分配順應(yīng)表。它是用一組連續(xù)存放單元來存放串中字符序列。所謂定長(zhǎng)次序存放結(jié)構(gòu)，是直接使用定長(zhǎng)字符數(shù)組來定義，數(shù)組上界預(yù)先給出：

數(shù)據(jù)結(jié)構(gòu)第11頁普通可使用一個(gè)不會(huì)出現(xiàn)在串中特殊字符在串值尾部來表示串結(jié)束。比如，C語言中以字符‵\0′表示串值終止，這就是為何在上述定義中，串空間最大值maxstrlen為256，但最多只能存放255個(gè)字符原因，因?yàn)楸仨毩粢粋€(gè)字節(jié)來存放‵\0′字符。若不設(shè)終止符，可用一個(gè)整數(shù)來表示串長(zhǎng)度，那么該長(zhǎng)度減1位置就是串值最終一個(gè)字符位置。此時(shí)次序串類型定義和次序表類似：typedefstruct{charch[maxstrlen];intlength;}sstring;//其優(yōu)點(diǎn)是包括到串長(zhǎng)操作時(shí)速度快。數(shù)據(jù)結(jié)構(gòu)第12頁堆分配存放表示這種存放表示特點(diǎn)是，仍以一組地址連續(xù)存放單元存放串值字符序列，但它們存放空間是在程序執(zhí)行過程中動(dòng)態(tài)分配而得。所以也稱為動(dòng)態(tài)存放分配次序表。在C語言中，利用動(dòng)態(tài)存放管理函數(shù)，來依據(jù)實(shí)際需要?jiǎng)討B(tài)分配和釋放字符數(shù)組空間。這么定義次序串類型也有兩種形式。

typedefchar*string;//c中串庫相當(dāng)于這類型定義typedefstruct{char*ch;intlength;}hsring;數(shù)據(jù)結(jié)構(gòu)第13頁statussinsert(hstrings,intpos,hstringt){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];s.ch[pos-1..pos+t.length-2]=t.ch[0..t.length-1];s.length+=t.length;}returnok;}數(shù)據(jù)結(jié)構(gòu)第14頁intstrlen(hstrings){returns.length;}statusclearstring(hstrings){if(s.ch){free(s.ch);s.ch=NULL;}s.length=0;}statusstrassign(hstringt,char*chars){//生成一個(gè)其值等于串常量chars串tif(t.ch)free(t.ch);for(i=0,(c=chars;c;++i),++c);if(!i){t.ch=null;t.length=0;}else{if(!(t.ch=(char*)malloc(I*sizeof(char))))exit(overflow);t.ch[0..i-1]=chars[0..i-1];t.length=i;}}數(shù)據(jù)結(jié)構(gòu)第15頁intstrcmp(hstrings,hstringt){for(i=0;i<s.length&&i<t.length;++i)if(s.ch[i]!=t.ch[i])return(s.ch[i]-t.ch[i]);returns.length-t.length;}statusconcat(hstringt,hstrings1,hstrings2){if(!(t.ch)=(char*)malloc(s1.length+s2.length)*sizeof(char)))exit(overflow);t.ch[0..s1.length-1]=s1.ch[0..s1.length-1];t.length=s1.length+s2.length;t.ch[s1.length..t.length-1]=s2.ch[0..s2.length-1];}數(shù)據(jù)結(jié)構(gòu)第16頁Statussubstr(hstringsub,hstrings,intpos,intlen){if(pos<1||pos>s.length||len<0||len>s.length-pos+1)returnerror;if(sub.ch)free(sub.ch);if(!len){sub.ch=null;sub.length=0;}else{sub.ch=(char*)malloc(len*sizeof(char));sub.ch[0..len-1]=s[pos-1..pos+len-2];s.length=len;}}數(shù)據(jù)結(jié)構(gòu)第17頁串鏈?zhǔn)酱娣沤Y(jié)構(gòu)

次序串上插入和刪除操作不方便，需要移動(dòng)大量字符。所以，我們可用單鏈表方式來存放串值，串這種鏈?zhǔn)酱娣沤Y(jié)構(gòu)簡(jiǎn)稱為鏈串。typedefstructnode{chardata;structnode*next;}lstring;

一個(gè)鏈串由頭指針唯一確定。這種結(jié)構(gòu)便于進(jìn)行插入和刪除運(yùn)算，但存放空間利用率太低。數(shù)據(jù)結(jié)構(gòu)第18頁為了提升存放密度，可使每個(gè)結(jié)點(diǎn)存放多個(gè)字符。通常將結(jié)點(diǎn)數(shù)據(jù)域存放字符個(gè)數(shù)定義為結(jié)點(diǎn)大小，顯然，當(dāng)結(jié)點(diǎn)大小大于1時(shí)，串長(zhǎng)度不一定恰好是結(jié)點(diǎn)整數(shù)倍，所以要用特殊字符來填充最終一個(gè)結(jié)點(diǎn)，以表示串終止。

對(duì)于結(jié)點(diǎn)大小不為1鏈串，其類型定為義只需對(duì)上述結(jié)點(diǎn)類型做簡(jiǎn)單修改即可。#definenodesize80typedefstructnode{chardata[nodesize];structnode*next;}lstring;數(shù)據(jù)結(jié)構(gòu)第19頁4.3 串模式匹配算法子串定位運(yùn)算又稱為模式匹配(PatternMatching)或串匹配(StringMatching)，此運(yùn)算應(yīng)用在非常廣泛。比如，在文本編輯程序中，我們經(jīng)常要查找某一特定單詞在文本中出現(xiàn)位置。顯然，解此問題有效算法能極大地提升文本編輯程序響應(yīng)性能。在串匹配中，普通將主串稱為目標(biāo)串，子串稱之為模式串。設(shè)S為目標(biāo)串，T為模式串，且不妨設(shè)：S=“s0s1s2…sn-1”T=“t0t1…tm-1”串匹配實(shí)際上是對(duì)于正當(dāng)位置0≦i≦n-m依次將目標(biāo)串中子串s[i..i+m-1]和模式串t[0..m-1]進(jìn)行比較，若s[i..i+m-1]=t[0..m-1]，則稱從位置i開始匹配成功，亦稱模式t在目標(biāo)s中出現(xiàn)；若s[i..i+m-1]≠t[0..m-1]，則稱從位置i開始匹配失敗。上述位置i又稱為位移，當(dāng)s[i..i+m-1]=t[0..m-1]時(shí)，i稱為有效位移；當(dāng)s[i..i+m-1]≠t[0..m-1]時(shí)，i稱為無效位移。這么，串匹配問題可簡(jiǎn)化為是找出某給定模式T在一給定目標(biāo)T中首次出現(xiàn)有效位移。數(shù)據(jù)結(jié)構(gòu)第20頁串匹配算法很多，首先我們介紹一個(gè)樸素匹配算法：BF法模式匹配(見演示）串直接匹配算法功效是:在串S中查找和串T值相同子串。算法思想是：P書79頁。

數(shù)據(jù)結(jié)構(gòu)第21頁IntindexBF(SstringS,SstringT){i=1;j=1;while(i<=S[0]&&j<=T[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)第22頁這種改進(jìn)算法是D.E.Knuth與V.R.Pratt和J.H.Morris同時(shí)發(fā)覺，所以人們稱它為克努特—莫里斯—普拉特操作（簡(jiǎn)稱為KMP算法）這種算法改進(jìn)在于：每當(dāng)一趟匹配過程中出現(xiàn)字符比較不等時(shí)，不需回溯i指針，而是利用已經(jīng)得到“部分匹配”結(jié)果將模式向右“滑動(dòng)”盡可能遠(yuǎn)一段距離后，繼續(xù)進(jìn)行比較。

模式匹配一個(gè)改進(jìn)算法：KMP法模式匹配數(shù)據(jù)結(jié)構(gòu)第23頁TabbabaPaba(a)P3T3將i右移一位TabbabaPaba(b)P1T2將i右移一位TabbabaPaba(c)P1T3將i右移一位TabbabaPaba(d)匹配成功舉例：T=“abbaba”P=“aba”我們仔細(xì)分析左邊圖例：由(a)可知：P1=T1，P2=T2，P3T3又由P1P2能夠推出P1T2所以將i右移一位后(b)比較一定不等，所以(b)就沒有必要做，這就在利用部分已匹配結(jié)果了。再由P1=P3，能夠推出P1T3，所以將i再右移一位后（c）比較也一定不等，所以（c）也沒有必要做。所以，由(a)便可直接到(d)，從P1和T4開始進(jìn)行比較，這么匹配過程對(duì)T而言就消除了回溯（i值沒有回溯）。123456數(shù)據(jù)結(jié)構(gòu)第24頁看書中P80頁例子：i=3第一趟匹配ababcabcacbababcacj=3i=3j=7第二趟匹配ababcabcacbababcacj=1j=5i=7第三趟匹配ababcabcacbab(a)bcacj=2數(shù)據(jù)結(jié)構(gòu)第25頁為了實(shí)現(xiàn)上述無回溯匹配算法，關(guān)鍵在于當(dāng)匹配過程中，一旦Pj和Ti比較不等，即substr(P,1,j-1)=substr(T,i-j+1,j-1)PjTi

說明白點(diǎn)就是，當(dāng)Pj和Ti比較不等時(shí)，我們應(yīng)該用P中哪個(gè)字符和Ti進(jìn)行比較？我們假設(shè)一下應(yīng)該與P中第k個(gè)字符比較（記作Pk）,顯然有k<j而且對(duì)不一樣j，k值也不相同。有趣是，Knuth等人發(fā)覺這個(gè)k值僅依賴于模式P本身前i個(gè)字符組成，而與目標(biāo)T無關(guān)。數(shù)據(jù)結(jié)構(gòu)第26頁現(xiàn)在我們利用next[j]表示與j對(duì)應(yīng)k值，其意義在于：若next[j]>0表示一旦匹配過程中Pj與Ti比較不等，可用P中next[j]為下標(biāo)字符與Ti進(jìn)行比較；若next[j]=0表示P中任何字符都無須再與Ti進(jìn)行比較。

對(duì)任何模式P，只要我們能確定next[j]值，就能夠用來加速匹配過程。當(dāng)PjTi時(shí)，讓Tj（或Tj+1）直接與next[j]表示位置繼續(xù)比較下去。數(shù)據(jù)結(jié)構(gòu)第27頁KMP匹配算法（偽語言表示）初始化：i=1;j=1;循環(huán)：當(dāng)i<=S[0]&&j<=T[0]假如T[i]==S[j]則i=i+1;j=j+1;不然若next[j]>0則j=next[j];不然i=1;i=i+1;見書P82頁算法4.6是完整算法。

且看部分顯示（后半部匹配顯示）數(shù)據(jù)結(jié)構(gòu)第28頁現(xiàn)在大家應(yīng)該知道，假如要實(shí)現(xiàn)KMP算法（快速匹配或無回溯算法）關(guān)鍵就是怎樣正確地計(jì)算next數(shù)組值。為此我們首先來分析next[j]性質(zhì)，找出next[j]必須滿足條件，然后再給出next數(shù)組生成算法就比較輕易了解了。（1）從前面引入來看，顯然next[j]是一個(gè)整數(shù)，而且滿足0next[j]j（2）匹配過程中，一旦Pj和Ti比較不等，按next[j]意義，讓Ti與Pk（若k=next[j]0）繼續(xù)比較,為確保繼續(xù)比較是有效，這個(gè)k值是關(guān)鍵，也即應(yīng)有

P1=Ti-k+1,P2=Ti-k+2,….,Pk-1=Ti-1數(shù)據(jù)結(jié)構(gòu)第29頁TT1T2T3……..Ti-j+1……..Ti-k+1…….Ti-1TiTi+1………….PP1……..Pj-k+1……...Pj-1PjPj+1………….

?P1……..Pk-1PkPk+1………….

P1=Ti-k+1,P2=Ti-k+2,….,Pk-1=Ti-1因?yàn)樵赑j

Ti發(fā)生之前已經(jīng)有P1=Ti-k+1,P2=Ti-k+2,….,Pk-1=Ti-1,所以上述條件等價(jià)于

P1=Pj-k+1,P2=Pj-k+2,….,Pk-1=Pj-1也就是說,k取值應(yīng)使P1P2…Pj-1頭尾k-1個(gè)字符組成子串相等，即substr(P,1,k-1)=substr(P,j-k+1,k-1)數(shù)據(jù)結(jié)構(gòu)第30頁（3）為了使不丟失任何匹配成功可能，當(dāng)存在多個(gè)滿足第（2）條件