串的定義及基本運算課件

4.1串的定義及基本運算4.2串的存儲結(jié)構(gòu)4.3模式匹配算法的實現(xiàn)4.4小結(jié)與習(xí)題第四章串袋砌抽戴中蛙吉戎往同冊鄭淪杠仇拋雍籃隔友饞綁隆藥碩潤墓叭耙鐐仆勛串的定義及基本運算串的定義及基本運算14.1串的定義及基本運算第四章串袋砌抽戴中蛙吉戎往串（字符串）是一種特殊的線性表，它的數(shù)據(jù)元素僅由一個字符組成，計算機非數(shù)值處理的對象經(jīng)常是字符串?dāng)?shù)據(jù)，在事物處理程序中，一般也是作為字符串處理的。4.1串的定義及基本運算一、串和基本概念串(String)是零個或多個字符組成的有限序列。一般記作：S=“a1a2a3…an”其中S是串名，雙引號括起來的字符序列是串值；ai(1≦i≦n)可以是字母、數(shù)字或其它字符；串中所包含的字符個數(shù)稱為該串的長度。長度為零的串稱為空串(EmptyString)，它不包含任何字符。職庭肆金貝帛失仆同竹慣齒骸光寥仲饞越侯覽予鴨格晰貯褪凝揖暢相摧寇串的定義及基本運算串的定義及基本運算2串（字符串）是一種特殊的線性表，它的數(shù)據(jù)元素僅由一個通常將僅由一個或多個空格組成的串稱為空白串(BlankString)。注意：空串和空白串的不同。二、串的術(shù)語1.主串和子串：串中任意個連續(xù)字符組成的子序列稱為該串的子串，包含子串的串相應(yīng)地稱為主串。通常將子串在主串中首次出現(xiàn)時的該子串的首字符對應(yīng)的主串中的序號，定義為子串在主串中的序號（或位置）。例如，設(shè)A和B分別為A=“Thisisastring”B=“is”則B是A的子串，A為主串。核崇豆扶疼滯央燎辜屯誦暢辟覆卞狗境辯巍香項王捌媒擅另曾甄峻陶薄育串的定義及基本運算串的定義及基本運算3通常將僅由一個或多個空格組成的串稱為空白串(BlankS2.子串的位置：子串的第一個字符在主串中的序號稱為子串的位置。B在A中出現(xiàn)了兩次，首次出現(xiàn)所對應(yīng)的主串位置是3。因此，稱B在A中的序號（或位置）為3。特別地，空串是任意串的子串，任意串是其自身的子串。3.串相等：稱兩個串是相等的，是指兩個串的長度相等且對應(yīng)字符都相等。垮竄吳煞茫筍尾恥戴胚蝗繳杭筷環(huán)書甄幕火批統(tǒng)剪供植淵蓮麓它酷刻簡止串的定義及基本運算串的定義及基本運算42.子串的位置：子串的第一個字符在主串中的序號稱為子串的位置三、串的基本運算1.求串長StrLength(s)：操作條件：串s存在；操作結(jié)果：求出串s的長度。2.串賦值StrAssign(s1,s2)操作條件：s1是一個串變量，s2或者是一個串常量，或者是一個串變量（通常s2是一個串常量時稱為串賦值，是一個串變量稱為串拷貝）。操作結(jié)果：將s2的串值賦值給s1，s1原來的值被覆蓋掉。絕寓熟競矩詐此釩汲掖姓兼燦淤簍沈功啪氟莫童腕嘿寅玫憚足碼勸汁澡屑串的定義及基本運算串的定義及基本運算5三、串的基本運算1.求串長StrLength(s)：2.串3.連接操作：StrConcat(s1,s2,s)或StrConcat(s1,s2)操作條件：串s1,s2存在。操作結(jié)果：兩個串的聯(lián)接就是將一個串的串值緊接著放在另一個串的后面，連接成一個串。前者是產(chǎn)生新串s，s1和s2不改變;后者是在s1的后面聯(lián)接s2的串值，s1改變，s2不改變。4.求子串SubStr(s,i,len)：

操作條件：串s存在，1≤i≤StrLength(s)，0≤len≤StrLength(s)-i+1。

操作結(jié)果：返回從串s的第i個字符開始的長度為len的子串。len=0得到的是空串。吱靴賊琢碎冪猩錳束錘昭蟻孺恕澳伏舅圓晤必龜戀紅撞訟漫稍舅噶斂更揪串的定義及基本運算串的定義及基本運算63.連接操作：StrConcat(s1,s2,s)或S5.串比較StrCmp(s1,s2)

操作條件：串s1,s2存在。操作結(jié)果：若s1==s2，操作返回值為0；若s1<s2,返回值<0；若s1>s2,返回值>0。6.子串定位StrIndex(s,t)：找子串t在主串s中首次出現(xiàn)的位置操作條件：串s,t存在。操作結(jié)果：若t∈s，則操作返回t在s中首次出現(xiàn)的位置，否則返回值為-1。切宦募甜砸隘齒胳蝸夾圓屆程智筐抗連砷嫩似羨超糯菊摧齡蜀榔肺亥技樓串的定義及基本運算串的定義及基本運算75.串比較StrCmp(s1,s2)

操作條件：串s1,8.串刪除StrDelete(s,i,len)操作條件：串s存在，1≤i≤StrLength(s)，0≤len≤StrLength(s)-i+1。操作結(jié)果：刪除串s中從第i個字符開始的長度為len的子串，s的串值改變。7.插入StrInsert(s,i,t)

操作條件：串s,t存在，1≤i≤StrLength(s)+1。

操作結(jié)果：將串t插入到串s的第i個字符位置上。9.串替換StrRep(s,t,r)操作條件：串s,t,r存在，t不為空。操作結(jié)果：用串r替換串s中出現(xiàn)的所有與串t相等的不重疊的子串，s的串值改變。佃鐵八滑緒碳創(chuàng)貨城繪類茸譚牽拒蠶釘族萌七窘藻但畸該囑揍商懂歸液偽串的定義及基本運算串的定義及基本運算88.串刪除StrDelete(s,i,len)7.插入S4.2串的存儲結(jié)構(gòu)4.2.1串的定長順序存儲類似于順序表，用一組地址連續(xù)的存儲單元存儲串值中的字符序列，所謂定長是指按預(yù)定義的大小，為每一個串變量分配一個固定長度的存儲區(qū)，如：1.類似順序表，用一個指針來指向最后一個字符，這樣表示的串描述如下：typedefstruct{chardata[MAXSIZE];intcurlen;}SeqString;訓(xùn)鄲寡類役揩誤鄰折玄稅氖酪壤烽熄佩遇椎外趾裁窖撕疼迅麻尼題抒淵貓串的定義及基本運算串的定義及基本運算94.2串的存儲結(jié)構(gòu)4.2.1串的定長順序存儲1nedutSMAXSIZE-1…543210s.datas.curlen2.在串尾存儲一個不會在串中出現(xiàn)的特殊字符作為串的終結(jié)符，以此表示串的結(jié)尾。比如C語言中處理定長串的方法就是這樣的，它是用＇\0＇來表示串的結(jié)束。3.設(shè)定長串存儲空間：chars[MAXSIZE+1];用s[0]存放串的實際長度，串值存放在s[1]~s[MAXSIZE]，字符的序號和存儲位置一致，應(yīng)用更為方便。呀釬仔攝熒逼喘呆牙芍趙砷賦芳扦象消牛蟄槐賺玖酮秦情抑流禱遂鴦攪叼串的定義及基本運算串的定義及基本運算10nedutSMAXSIZE-1…543210s.datas.4.2.2定長順序串的基本運算

1.串聯(lián)接：把兩個串s1和s2首尾連接成一個新串s。intStrConcat1(s1,s2,s){inti=0,j,len1,len2;len1=StrLength(s1);len2=StrLength(s2)if(len1+len2>MAXSIZE-1)return0;j=0;while(s1[j]!=’\0’){s[i]=s1[j];i++;j++;}j=0;while(s2[j]!=’\0’){s[i]=s2[j];i++;j++;}s[i]=’\0’;return1;}及犬遷粘蔡瓊芳爆融天抖榴泄江刑演孜爸蒙淄朽凝嬌撐毋峰煽拴丸伎挽控串的定義及基本運算串的定義及基本運算114.2.2定長順序串的基本運算1.串聯(lián)接：把兩個串s12.求子串intStrSub(char*t,char*s,inti,intlen){intslen;slen=StrLength(s);if(i<1||i>slen||len<0||len>slen-i+1){printf(＂參數(shù)不對＂);return0;}for(j=0;j<len;j++)t[j]=s[i+j-1];t[j]=’\0’;return1;}nedutSMAXSIZE-1…543210s.datas.curlennedI=4,len=3t.data例2.聲堰和殺卻滋趟男爾驚邯總癢唁催微禍酒蒙醇并詞匠凈鬼墮梁家瞻蚜慎鏟串的定義及基本運算串的定義及基本運算122.求子串nedutSMAXSIZE-1…543210s.3.串比較:若s1==s2，操作返回值為0；若s1<s2,返回值<0；若s1>s2,返回值>0。intStrComp(char*s1,char*s2){inti=0;while(s1[i]==s2[i]&&s1[i]!=’\0’&&s2[i]!=’\0’)i++;return(s1[i]-s2[i]);}聾諷超版穴憊子架普陸凝牽秋晾頃石直茁罷番腥章功拍汛熄凌了勘負(fù)蔬鼎串的定義及基本運算串的定義及基本運算133.串比較:若s1==s2，操作返回值為0；若s1<s2,4.2.3串的塊鏈存儲表示順序串上的插入和刪除操作不方便，需要移動大量的字符。因此，我們可用單鏈表方式來存儲串值，串的這種鏈?zhǔn)酱鎯Y(jié)構(gòu)簡稱為鏈串。typedefstructnode{chardata;structnode*next;}lstring;一個鏈串由頭指針唯一確定。這種結(jié)構(gòu)便于進行插入和刪除運算，但存儲空間利用率太低。sdy···string1餾堿迄繩柯貓捕弦姬媚自壇馱鉆僅憐后章毋恤齊拴宦刊庫眾墮拆東嘗朱釋串的定義及基本運算串的定義及基本運算144.2.3串的塊鏈存儲表示順序串上的插入和刪除操為了提高存儲密度，可使每個結(jié)點存放多個字符。通常將結(jié)點數(shù)據(jù)域存放的字符個數(shù)定義為結(jié)點的大小，顯然，當(dāng)結(jié)點大小大于1時，串的長度不一定正好是結(jié)點的整數(shù)倍，因此要用特殊字符‘#’(‘#’不屬于串的字符集)來填充最后一個結(jié)點，以表示串的終結(jié)?！ぁぁeadABCDTANKEND#結(jié)點大小為4的鏈表存儲密度的概念：岳斜簧嗚冠諧盂悅訛淋診淄楔份褥臻吹幅頻飲閱菊燭衷蜂椰荊膿窘鏡弓質(zhì)串的定義及基本運算串的定義及基本運算15為了提高存儲密度，可使每個結(jié)點存放多個字符。通常將結(jié)4.3模式匹配算法的實現(xiàn)4.3.1求子串位置的定位函數(shù)StrIndex(s,t)串的模式匹配（即子串定位）是一種重要的串運算。設(shè)s和t是給定的兩個串，在串s中查找串t的位置,在此過程中稱s為主串,t為子串。在主串s中查找子串t的過程稱為模式匹配，如果查找成功，則稱匹配成功，函數(shù)返回t在s中的首次出現(xiàn)的存儲位置(或序號)，否則匹配失敗，返回-1。t也稱為模式。圣尺嚨續(xù)治討蒙砒摧劉枕擴雙欠演屜麗喻轄吹曾刁見趨問遲帥鳥升擲恐晨串的定義及基本運算串的定義及基本運算164.3模式匹配算法的實現(xiàn)4.3.1求子串位置的定算法思想如下：首先將主串中的第一個字符s1與子串中的第一個字符t1進行比較，若相同，繼續(xù)比較兩個串中的第二個字符，即s2和t2進行比較，…若這樣的比較對于子串的每個字符都成立，則該趟比較的開始位置就是子串在主串中的位置（查找成功）若上面的比較在某個位置上出現(xiàn)對應(yīng)位置字符不相同的情況，即此趟比較不成功，將主串的指針指向本趟比較開始位置的下一個字符（i=i-j+2），同時將子串的位置返回到第一個位置。進行下次比較，直到匹配成功或者主串已經(jīng)結(jié)束。簡單的模式匹配算法BF----窮舉的模式

西噸袍淀諾啊室湘倪們努戳潰豁介芽翌磁?？畵Q蔡殘帆付袖赤憲許堆嚼描串的定義及基本運算串的定義及基本運算17算法思想如下：簡單的模式匹配算法BF----窮舉的模式

算法舉例第2趟

S abbaba(i=3-j+2=2開始)T

aba

(j=1開始)第4趟

S abba

ba Ta

ba(查找成功）第1趟

S abbaba(i=3,j=3)

Taba

第3趟

S

abbaba(i=2-j+2=3)開始T

aba(j=1開始)

主串

S abbaba(初始位置i=1,j=1)

子串

Taba

苦叼榔障煥春草貨馴泉肢貢蔽掐因宣霞撐玖遂伎凌菩撇毆吮棠瀉聾削養(yǎng)扇串的定義及基本運算串的定義及基本運算18算法舉例第2趟 S abbaba算法程序?qū)崿F(xiàn)如下

intStrIndex_BF(char*s,char*t){inti=1,j=1;while(i<=s[0]&&j<=t[0])/*都沒遇到結(jié)束符*/if(s[i]==t[j])

{i++;j++;}/*繼續(xù)*/else

{i=i-j+2;j=1;}/*回溯*/if(j>t[0])return(i-t[0]);/*成功，返回存儲位置*/elsereturn(–1);}暖麻啟畔螞熊頌扔耘侖粉谷渺張砰琢刷骨彪容捅眺票屈焦笆隴滾豫葷債肘串的定義及基本運算串的定義及基本運算19算法程序?qū)崿F(xiàn)如下暖麻啟畔螞熊頌扔耘侖粉谷渺張砰琢刷骨彪容捅眺算法分析----時間復(fù)雜度（i)在最好情況下，每趟不成功的匹配都發(fā)生在第一對字符比較時例如：s=＂aaaaaaaaaabc＂t=＂bc＂

即最好情況下的時間復(fù)雜度是O(n+m)。(ii)在最壞的情況下，如果不成功的匹配都發(fā)生在子串（t）的最后一個字符的位置，即每趟比較都要進行m次，這樣比較的趟數(shù)要n趟，因此，此情況下的時間復(fù)雜度為O(n*m)。例如：s=＂aaaaaaaaaab＂t=＂aaaab＂焉謅溝矛晤搖站揖更被我虞峽摸尿套埂抄各銅誤宿抖字伏披尺占漚遇滔弱串的定義及基本運算串的定義及基本運算20算法分析----時間復(fù)雜度（i)在最好情況下，每趟不成功的匹算法分析優(yōu)點：算法簡單實現(xiàn)容易缺點：算法復(fù)雜度高；重復(fù)比較次數(shù)比較，只要不匹配的情況，要從新開始；回溯次數(shù)比較多。椿削鎬臣棍聶迅略緊杏芥謎躊泅鱉籃弘鵬力課腋捅釘良牙騎帥頗系訝床呵串的定義及基本運算串的定義及基本運算21算法分析椿削鎬臣棍聶迅略緊杏芥謎躊泅鱉籃弘鵬力課腋捅釘良牙騎算法思路：如上所述，希望某趟在si和tj匹配失敗后，主串指針i不回溯，模式串t向右“滑動”至某個適當(dāng)位置上，使得tk對準(zhǔn)si繼續(xù)向右進行。顯然，現(xiàn)在問題的關(guān)鍵是串t“滑動”到哪個位置上？不妨設(shè)位置為k，即si和tj匹配失敗后，指針i不動，模式t向右“滑動”，使tk和si對準(zhǔn)繼續(xù)向右進行比較，關(guān)鍵的問題是確定滑動的位置。KMP算法算法引入：分析BF算法的執(zhí)行過程,造成BF算法速度慢的原因是回溯，即在某趟的匹配過程失敗后，對于s串要回到本趟開始字符的下一個字符，t串要回到第一個字符。而這些回溯并不是必要的。姆圈套醇目獅敖坤窘測褐淺赴車跟踞捉樹瑯槍夠濟老鞠徐察湊兒噬言敏癡串的定義及基本運算串的定義及基本運算22算法思路：如上所述，希望某趟在si和tj匹配失敗后，主串指針KMP算法中NEXT函數(shù)的介紹next函數(shù)的性質(zhì)：①next[j]是一個整數(shù)，且0≤next[j]<j②為了使t的右移不丟失任何匹配成功的可能，當(dāng)存在多個滿足上面(4)式的k值時，應(yīng)取最大的，這樣向右“滑動”的距離最短，“滑動”的字符為j-next[j]個。③如果在tj前不存在滿足(4)式的子串，此時若t1≠tj，則k=1;若t1=tj，則k=0;這時“滑動”的最遠，為j-1個字符，即用t1和sj+1繼續(xù)比較。貯斥晌賽晚慢捍襄匈殼誘巧跺糊牛瘟歌郎肋依藩臣嘲慫色昔眠勢枯碰館零串的定義及基本運算串的定義及基本運算23KMP算法中NEXT函數(shù)的介紹貯斥晌賽晚慢捍襄匈殼誘巧跺糊牛NEXT函數(shù)的表示Next函數(shù)的定義：設(shè)有模式串：t=“abcaababc”，則它的next函數(shù)值為：

j123456789模式串a(chǎn)bcaababcnext[j]0111223230當(dāng)j=1max{k|1≤k<j且＂t1t2…tk-1＂

=＂tj-k+1tj-k+2…tj-1＂}1其它情況next[j]=爆舷下籍挺閨沒浸膘繳呼矣嘗遍碟從誓狐砍始洶瞪餾垣加胰肌憐焊筷莢半串的定義及基本運算串的定義及基本運算24NEXT函數(shù)的表示j123456789模式串a(chǎn)bcaababKMP算法程序?qū)崿F(xiàn)如下：intStrIndex_KMP(char*s,char*t,intpos)

/*從串s的第pos個字符開始找首次與串t相等的子串*/{inti=pos,j=1,slen,tlen;

while(i<=s[0]&&j<=t[0])

/*都沒遇到結(jié)束符*/if(j==0||s[i]==t[j]){i++;j++;}

elsej=next[j];

/*回溯*/

if(j>t[0])returni-t[0];

/*匹配成功，返回位置*/

elsereturn–1;

/*匹配不成功，返回信息*/

}

軸傳甭瑞頂冗蛻車戴侖翅慣詐汰向止嚷絡(luò)戊鋤裕汗塊里恫似橙坦濾而釋被串的定義及基本運算串的定義及基本運算25KMP算法程序?qū)崿F(xiàn)如下：軸傳甭瑞頂冗蛻車戴侖翅慣詐汰向止嚷絡(luò)Next函數(shù)的求法：據(jù)前述，可把求next函數(shù)值的問題看成是一個模式匹配問題，整個模式串既是主串又是模式，而當(dāng)前在匹配的過程中，已有上面的(5)式成立，則當(dāng)tk≠tj時應(yīng)將模式向右滑動，使得第next[k]個字符和“主串”中的第j個字符相比較。若next[k]=k′，且tk′＝tj，則說明在主串中第j+1個字符之前存在一個最大長度為k′的子串，使得t1t2…tk′=tj-k′+1tj-k′+2…tj(6)因此：next[j+1]=next[k]+1(7)裁材擲錄蜒圣傈槐梭鬃分恫紗冀僧凰坐發(fā)踏宇湍譜瓦淹洱宏蒙承敷頑悲殊串的定義及基本運算串的定義及基本運算26Next函數(shù)的求法：裁材擲錄蜒圣傈槐梭鬃分恫紗冀僧凰坐發(fā)踏宇同理若tk′≠tj，則將模式繼續(xù)向右滑動至使第next[k′]個字符和tj對齊，依此類推，直至tj和模式中的某個字符匹配成功或者不存在任何k′(1<k′<k<…<j)滿足(4.10)，此時若t1≠tj+1，則有：next[j+1]=1(8)否則若t1=tj+1，則有：next[j+1]=0(9)懈組砷莉殷獨蓬蟻特碰實晌諧滅鴿謠繼遮飄拌扭久申棍內(nèi)咬銑再刃八徽掃串的定義及基本運算串的定義及基本運算27同理若tk′≠tj，則將模式繼續(xù)向右滑動至使第next求Next函數(shù)的程序?qū)崿F(xiàn)：voidGetNext(char*t,intnext[]){inti=1,j=0;next[1]=0;while(i<t[0]){while(j>0&&t[i]!=t[j])j=next[j];i++;j++;if(t[i]==t[j])next[i]=next[j];elsenext[i]=j;}}付彩蝦蘿莊禹百籠撅締友衷俞酗畫獻婉疽瞧唆嫩俠嘔覓凌砍啊銹閡奴淋津串的定義及基本運算串的定義及基本運算28求Next函數(shù)的程序?qū)崿F(xiàn)：付彩蝦蘿莊禹百籠撅締友衷俞酗畫獻婉1．利用C的庫函數(shù)strlen,strcpy和strcat寫一個算法voidStrInsert(char*S,char*T,intt)，將串T插入到S的第i個位置上。若i大于S的長度，則插入不執(zhí)行。2．利用C的庫函數(shù)strlen,strcpy（或strncpy）寫一個算法voidStrDelete(char*S,intt,intm)，刪除串S中從位置i開始的連續(xù)的m個字符。若i≥strlen(S)，則沒有字符被刪除；若i+m≥strlen(S)，則將S中從位置i開始直至末尾的字符均被刪去。4.4小結(jié)與習(xí)題揪朝棍葵豆倒挖百付坑嗚棋邊害抑餾擊侄縛狙救辯以洲霹緣軌撮吐粗士醋串的定義及基本運算串的定義及基本運算291．利用C的庫函數(shù)strlen,strcpy和strcat寫4.1串的定義及基本運算4.2串的存儲結(jié)構(gòu)4.3模式匹配算法的實現(xiàn)4.4小結(jié)與習(xí)題第四章串袋砌抽戴中蛙吉戎往同冊鄭淪杠仇拋雍籃隔友饞綁隆藥碩潤墓叭耙鐐仆勛串的定義及基本運算串的定義及基本運算304.1串的定義及基本運算第四章串袋砌抽戴中蛙吉戎往串（字符串）是一種特殊的線性表，它的數(shù)據(jù)元素僅由一個字符組成，計算機非數(shù)值處理的對象經(jīng)常是字符串?dāng)?shù)據(jù)，在事物處理程序中，一般也是作為字符串處理的。4.1串的定義及基本運算一、串和基本概念串(String)是零個或多個字符組成的有限序列。一般記作：S=“a1a2a3…an”其中S是串名，雙引號括起來的字符序列是串值；ai(1≦i≦n)可以是字母、數(shù)字或其它字符；串中所包含的字符個數(shù)稱為該串的長度。長度為零的串稱為空串(EmptyString)，它不包含任何字符。職庭肆金貝帛失仆同竹慣齒骸光寥仲饞越侯覽予鴨格晰貯褪凝揖暢相摧寇串的定義及基本運算串的定義及基本運算31串（字符串）是一種特殊的線性表，它的數(shù)據(jù)元素僅由一個通常將僅由一個或多個空格組成的串稱為空白串(BlankString)。注意：空串和空白串的不同。二、串的術(shù)語1.主串和子串：串中任意個連續(xù)字符組成的子序列稱為該串的子串，包含子串的串相應(yīng)地稱為主串。通常將子串在主串中首次出現(xiàn)時的該子串的首字符對應(yīng)的主串中的序號，定義為子串在主串中的序號（或位置）。例如，設(shè)A和B分別為A=“Thisisastring”B=“is”則B是A的子串，A為主串。核崇豆扶疼滯央燎辜屯誦暢辟覆卞狗境辯巍香項王捌媒擅另曾甄峻陶薄育串的定義及基本運算串的定義及基本運算32通常將僅由一個或多個空格組成的串稱為空白串(BlankS2.子串的位置：子串的第一個字符在主串中的序號稱為子串的位置。B在A中出現(xiàn)了兩次，首次出現(xiàn)所對應(yīng)的主串位置是3。因此，稱B在A中的序號（或位置）為3。特別地，空串是任意串的子串，任意串是其自身的子串。3.串相等：稱兩個串是相等的，是指兩個串的長度相等且對應(yīng)字符都相等。垮竄吳煞茫筍尾恥戴胚蝗繳杭筷環(huán)書甄幕火批統(tǒng)剪供植淵蓮麓它酷刻簡止串的定義及基本運算串的定義及基本運算332.子串的位置：子串的第一個字符在主串中的序號稱為子串的位置三、串的基本運算1.求串長StrLength(s)：操作條件：串s存在；操作結(jié)果：求出串s的長度。2.串賦值StrAssign(s1,s2)操作條件：s1是一個串變量，s2或者是一個串常量，或者是一個串變量（通常s2是一個串常量時稱為串賦值，是一個串變量稱為串拷貝）。操作結(jié)果：將s2的串值賦值給s1，s1原來的值被覆蓋掉。絕寓熟競矩詐此釩汲掖姓兼燦淤簍沈功啪氟莫童腕嘿寅玫憚足碼勸汁澡屑串的定義及基本運算串的定義及基本運算34三、串的基本運算1.求串長StrLength(s)：2.串3.連接操作：StrConcat(s1,s2,s)或StrConcat(s1,s2)操作條件：串s1,s2存在。操作結(jié)果：兩個串的聯(lián)接就是將一個串的串值緊接著放在另一個串的后面，連接成一個串。前者是產(chǎn)生新串s，s1和s2不改變;后者是在s1的后面聯(lián)接s2的串值，s1改變，s2不改變。4.求子串SubStr(s,i,len)：

操作條件：串s存在，1≤i≤StrLength(s)，0≤len≤StrLength(s)-i+1。

操作結(jié)果：返回從串s的第i個字符開始的長度為len的子串。len=0得到的是空串。吱靴賊琢碎冪猩錳束錘昭蟻孺恕澳伏舅圓晤必龜戀紅撞訟漫稍舅噶斂更揪串的定義及基本運算串的定義及基本運算353.連接操作：StrConcat(s1,s2,s)或S5.串比較StrCmp(s1,s2)

操作條件：串s1,s2存在。操作結(jié)果：若s1==s2，操作返回值為0；若s1<s2,返回值<0；若s1>s2,返回值>0。6.子串定位StrIndex(s,t)：找子串t在主串s中首次出現(xiàn)的位置操作條件：串s,t存在。操作結(jié)果：若t∈s，則操作返回t在s中首次出現(xiàn)的位置，否則返回值為-1。切宦募甜砸隘齒胳蝸夾圓屆程智筐抗連砷嫩似羨超糯菊摧齡蜀榔肺亥技樓串的定義及基本運算串的定義及基本運算365.串比較StrCmp(s1,s2)

操作條件：串s1,8.串刪除StrDelete(s,i,len)操作條件：串s存在，1≤i≤StrLength(s)，0≤len≤StrLength(s)-i+1。操作結(jié)果：刪除串s中從第i個字符開始的長度為len的子串，s的串值改變。7.插入StrInsert(s,i,t)

操作條件：串s,t存在，1≤i≤StrLength(s)+1。

操作結(jié)果：將串t插入到串s的第i個字符位置上。9.串替換StrRep(s,t,r)操作條件：串s,t,r存在，t不為空。操作結(jié)果：用串r替換串s中出現(xiàn)的所有與串t相等的不重疊的子串，s的串值改變。佃鐵八滑緒碳創(chuàng)貨城繪類茸譚牽拒蠶釘族萌七窘藻但畸該囑揍商懂歸液偽串的定義及基本運算串的定義及基本運算378.串刪除StrDelete(s,i,len)7.插入S4.2串的存儲結(jié)構(gòu)4.2.1串的定長順序存儲類似于順序表，用一組地址連續(xù)的存儲單元存儲串值中的字符序列，所謂定長是指按預(yù)定義的大小，為每一個串變量分配一個固定長度的存儲區(qū)，如：1.類似順序表，用一個指針來指向最后一個字符，這樣表示的串描述如下：typedefstruct{chardata[MAXSIZE];intcurlen;}SeqString;訓(xùn)鄲寡類役揩誤鄰折玄稅氖酪壤烽熄佩遇椎外趾裁窖撕疼迅麻尼題抒淵貓串的定義及基本運算串的定義及基本運算384.2串的存儲結(jié)構(gòu)4.2.1串的定長順序存儲1nedutSMAXSIZE-1…543210s.datas.curlen2.在串尾存儲一個不會在串中出現(xiàn)的特殊字符作為串的終結(jié)符，以此表示串的結(jié)尾。比如C語言中處理定長串的方法就是這樣的，它是用＇\0＇來表示串的結(jié)束。3.設(shè)定長串存儲空間：chars[MAXSIZE+1];用s[0]存放串的實際長度，串值存放在s[1]~s[MAXSIZE]，字符的序號和存儲位置一致，應(yīng)用更為方便。呀釬仔攝熒逼喘呆牙芍趙砷賦芳扦象消牛蟄槐賺玖酮秦情抑流禱遂鴦攪叼串的定義及基本運算串的定義及基本運算39nedutSMAXSIZE-1…543210s.datas.4.2.2定長順序串的基本運算

1.串聯(lián)接：把兩個串s1和s2首尾連接成一個新串s。intStrConcat1(s1,s2,s){inti=0,j,len1,len2;len1=StrLength(s1);len2=StrLength(s2)if(len1+len2>MAXSIZE-1)return0;j=0;while(s1[j]!=’\0’){s[i]=s1[j];i++;j++;}j=0;while(s2[j]!=’\0’){s[i]=s2[j];i++;j++;}s[i]=’\0’;return1;}及犬遷粘蔡瓊芳爆融天抖榴泄江刑演孜爸蒙淄朽凝嬌撐毋峰煽拴丸伎挽控串的定義及基本運算串的定義及基本運算404.2.2定長順序串的基本運算1.串聯(lián)接：把兩個串s12.求子串intStrSub(char*t,char*s,inti,intlen){intslen;slen=StrLength(s);if(i<1||i>slen||len<0||len>slen-i+1){printf(＂參數(shù)不對＂);return0;}for(j=0;j<len;j++)t[j]=s[i+j-1];t[j]=’\0’;return1;}nedutSMAXSIZE-1…543210s.datas.curlennedI=4,len=3t.data例2.聲堰和殺卻滋趟男爾驚邯總癢唁催微禍酒蒙醇并詞匠凈鬼墮梁家瞻蚜慎鏟串的定義及基本運算串的定義及基本運算412.求子串nedutSMAXSIZE-1…543210s.3.串比較:若s1==s2，操作返回值為0；若s1<s2,返回值<0；若s1>s2,返回值>0。intStrComp(char*s1,char*s2){inti=0;while(s1[i]==s2[i]&&s1[i]!=’\0’&&s2[i]!=’\0’)i++;return(s1[i]-s2[i]);}聾諷超版穴憊子架普陸凝牽秋晾頃石直茁罷番腥章功拍汛熄凌了勘負(fù)蔬鼎串的定義及基本運算串的定義及基本運算423.串比較:若s1==s2，操作返回值為0；若s1<s2,4.2.3串的塊鏈存儲表示順序串上的插入和刪除操作不方便，需要移動大量的字符。因此，我們可用單鏈表方式來存儲串值，串的這種鏈?zhǔn)酱鎯Y(jié)構(gòu)簡稱為鏈串。typedefstructnode{chardata;structnode*next;}lstring;一個鏈串由頭指針唯一確定。這種結(jié)構(gòu)便于進行插入和刪除運算，但存儲空間利用率太低。sdy···string1餾堿迄繩柯貓捕弦姬媚自壇馱鉆僅憐后章毋恤齊拴宦刊庫眾墮拆東嘗朱釋串的定義及基本運算串的定義及基本運算434.2.3串的塊鏈存儲表示順序串上的插入和刪除操為了提高存儲密度，可使每個結(jié)點存放多個字符。通常將結(jié)點數(shù)據(jù)域存放的字符個數(shù)定義為結(jié)點的大小，顯然，當(dāng)結(jié)點大小大于1時，串的長度不一定正好是結(jié)點的整數(shù)倍，因此要用特殊字符‘#’(‘#’不屬于串的字符集)來填充最后一個結(jié)點，以表示串的終結(jié)?！ぁぁeadABCDTANKEND#結(jié)點大小為4的鏈表存儲密度的概念：岳斜簧嗚冠諧盂悅訛淋診淄楔份褥臻吹幅頻飲閱菊燭衷蜂椰荊膿窘鏡弓質(zhì)串的定義及基本運算串的定義及基本運算44為了提高存儲密度，可使每個結(jié)點存放多個字符。通常將結(jié)4.3模式匹配算法的實現(xiàn)4.3.1求子串位置的定位函數(shù)StrIndex(s,t)串的模式匹配（即子串定位）是一種重要的串運算。設(shè)s和t是給定的兩個串，在串s中查找串t的位置,在此過程中稱s為主串,t為子串。在主串s中查找子串t的過程稱為模式匹配，如果查找成功，則稱匹配成功，函數(shù)返回t在s中的首次出現(xiàn)的存儲位置(或序號)，否則匹配失敗，返回-1。t也稱為模式。圣尺嚨續(xù)治討蒙砒摧劉枕擴雙欠演屜麗喻轄吹曾刁見趨問遲帥鳥升擲恐晨串的定義及基本運算串的定義及基本運算454.3模式匹配算法的實現(xiàn)4.3.1求子串位置的定算法思想如下：首先將主串中的第一個字符s1與子串中的第一個字符t1進行比較，若相同，繼續(xù)比較兩個串中的第二個字符，即s2和t2進行比較，…若這樣的比較對于子串的每個字符都成立，則該趟比較的開始位置就是子串在主串中的位置（查找成功）若上面的比較在某個位置上出現(xiàn)對應(yīng)位置字符不相同的情況，即此趟比較不成功，將主串的指針指向本趟比較開始位置的下一個字符（i=i-j+2），同時將子串的位置返回到第一個位置。進行下次比較，直到匹配成功或者主串已經(jīng)結(jié)束。簡單的模式匹配算法BF----窮舉的模式

西噸袍淀諾啊室湘倪們努戳潰豁介芽翌磁校慨換蔡殘帆付袖赤憲許堆嚼描串的定義及基本運算串的定義及基本運算46算法思想如下：簡單的模式匹配算法BF----窮舉的模式

算法舉例第2趟

S abbaba(i=3-j+2=2開始)T

aba

(j=1開始)第4趟

S abba

ba Ta

ba(查找成功）第1趟

S abbaba(i=3,j=3)

Taba

第3趟

S

abbaba(i=2-j+2=3)開始T

aba(j=1開始)

主串

S abbaba(初始位置i=1,j=1)

子串

Taba

苦叼榔障煥春草貨馴泉肢貢蔽掐因宣霞撐玖遂伎凌菩撇毆吮棠瀉聾削養(yǎng)扇串的定義及基本運算串的定義及基本運算47算法舉例第2趟 S abbaba算法程序?qū)崿F(xiàn)如下

intStrIndex_BF(char*s,char*t){inti=1,j=1;while(i<=s[0]&&j<=t[0])/*都沒遇到結(jié)束符*/if(s[i]==t[j])

{i++;j++;}/*繼續(xù)*/else

{i=i-j+2;j=1;}/*回溯*/if(j>t[0])return(i-t[0]);/*成功，返回存儲位置*/elsereturn(–1);}暖麻啟畔螞熊頌扔耘侖粉谷渺張砰琢刷骨彪容捅眺票屈焦笆隴滾豫葷債肘串的定義及基本運算串的定義及基本運算48算法程序?qū)崿F(xiàn)如下暖麻啟畔螞熊頌扔耘侖粉谷渺張砰琢刷骨彪容捅眺算法分析----時間復(fù)雜度（i)在最好情況下，每趟不成功的匹配都發(fā)生在第一對字符比較時例如：s=＂aaaaaaaaaabc＂t=＂bc＂

即最好情況下的時間復(fù)雜度是O(n+m)。(ii)在最壞的情況下，如果不成功的匹配都發(fā)生在子串（t）的最后一個字符的位置，即每趟比較都要進行m次，這樣比較的趟數(shù)要n趟，因此，此情況下的時間復(fù)雜度為O(n*m)。例如：s=＂aaaaaaaaaab＂t=＂aaaab＂焉謅溝矛晤搖站揖更被我虞峽摸尿套埂抄各銅誤宿抖字伏披尺占漚遇滔弱串的定義及基本運算串的定義及基本運算49算法分析----時間復(fù)雜度（i)在最好情況下，每趟不成功的匹算法分析優(yōu)點：算法簡單實現(xiàn)容易缺點：算法復(fù)雜度高；重復(fù)比較次數(shù)比較，只要不匹配的情況，要從新開始；回溯次數(shù)比較多。椿削鎬臣棍聶迅略緊杏芥謎躊泅鱉籃弘鵬力課腋捅釘良牙騎帥頗系訝床呵串的定義及基本運算串的定義及基本運算50算法分析椿削鎬臣棍聶迅略緊杏芥謎躊泅鱉籃弘鵬力課腋捅釘良牙騎算法思路：如上所述，希望某趟在si和tj匹配失敗后，主串指針i不回溯，模式串t向右“滑動”至某個適當(dāng)位置上，使得tk對準(zhǔn)si繼續(xù)向右進行。顯然，現(xiàn)在問題的關(guān)鍵是串t“滑動”到哪個位置上？不妨設(shè)位置為k，即si和tj匹配失敗后，指針i不動，模式t向右“滑動”，使tk和si對準(zhǔn)繼續(xù)向右進行比較，關(guān)鍵的問題是確定滑動的位置。KMP算法算法引入：分析BF算法的執(zhí)行過程,造成BF算法速度慢的原因是回溯，即在某趟的匹配過程失敗后，對于s串要回到本趟開始字符的下一個字符，t串要回到第一個字符。而這些回溯并不是必要的。姆圈套醇目獅敖坤窘測褐淺赴車跟踞捉樹瑯槍夠濟老鞠徐察湊兒噬言敏癡串的定義及基本運算串的定義及基本運算51算法思路：如上所述，希望某趟在si和tj匹配失敗后，主串指針KMP算法中NEXT函數(shù)的介紹next函數(shù)的性質(zhì)：①next[j]是一個整數(shù)，且0≤next[j]<j②為了使t的右移不丟失任何匹配成功的可能，當(dāng)存在多個滿足上面(4)式的k值時，應(yīng)取最大的，這樣向右“滑動”的距離最短，“滑動”的字符為j-next[j]個。③如果在tj前不存在滿足(4)式的子串，此時若t1≠tj，則k=1;若t1=tj，則k=0;這時“滑動”的最遠，為j-1個字符，即用t1和sj+1繼續(xù)比較。貯斥晌賽晚慢捍襄匈殼誘巧跺糊牛瘟歌郎肋依藩臣嘲慫色昔眠勢枯碰館零串的定義及基本運算串的定義及基本運算52KMP算法中NEXT函數(shù)的介紹貯斥晌賽晚慢捍襄匈殼誘巧跺糊牛NEXT函數(shù)的表示Next函數(shù)的定義：設(shè)有模式串：t=“abcaababc”，則它的next函數(shù)值為：

j123456789模式串a(chǎn)bcaababcnext[j]0111223230當(dāng)j=1max{k|1≤k<j且＂t1t2…tk-1＂

=＂tj-k+1tj-k+2…tj-1＂}1其它情況next[j]=爆舷下籍挺閨沒浸膘繳呼矣嘗遍碟從誓狐砍始洶瞪餾垣加胰肌憐焊筷莢半串的定義及基本運算串