第4章 串電子課件

第4章串本章講解字符串。要求理解字符串的概念；掌握順序串和鏈串的存儲(chǔ)結(jié)構(gòu)和基本操作；掌握BF和KMP模式匹配算法；靈活應(yīng)用字符串。四川的臘肉還是很有名的。春節(jié)前，各種臘肉一串一串被掛起賣，品類也多，如香腸、三線肉、排骨、香舌、豬肝等等，它們都可以被稱為串，但品類不同串的類型也就不同，好比其它串就是其它串，香腸串看作字符串吧。提綱4.1串基本概念4.2順序串4.3鏈串4.4串的模式匹配4.5串應(yīng)用4.6串學(xué)習(xí)總結(jié)4.1串基本概念

4.1串基本概念串的抽象數(shù)據(jù)接口IString描述4.2順序串以順序存儲(chǔ)結(jié)構(gòu)進(jìn)行存儲(chǔ)的串稱為順序串。4.2.1順序串存儲(chǔ)結(jié)構(gòu)順序串存儲(chǔ)結(jié)構(gòu)采用順序存儲(chǔ)方式，同順序表存儲(chǔ)結(jié)構(gòu)，故順序串也可以用一維數(shù)組存儲(chǔ)，不同的是順序串中的元素是字符或者字符串，前者用字符數(shù)組char[]存儲(chǔ)，后者用字符串?dāng)?shù)組str[]存儲(chǔ)，我們主要探討的是前者。如圖4.1所示。4.2.1順序串存儲(chǔ)結(jié)構(gòu)舉例：肉聯(lián)廠有臺(tái)豬肉識(shí)別機(jī)器，如果是豬肉就傳送過去做成火腿腸，如果是牛肉、羊肉、兔肉等就打回。在這個(gè)例子中，火腿腸嚴(yán)格要求是豬肉，好比字符數(shù)組或字符串?dāng)?shù)組嚴(yán)格要求其內(nèi)的元素是字符或字符串一樣的道理。4.2.2順序串基本操作順序串類SqString描述4.2.2順序串基本操作讀取第i個(gè)元素順序串讀取第i個(gè)元素操作是指獲得字符串中位置序號為i的字符。4.2.2順序串基本操作【算法4.1】讀取順序串第i個(gè)元素。思路:利用數(shù)組的隨機(jī)訪問特點(diǎn)，在i合法情況下直接返回第i個(gè)位置的字符。代碼見算法4.14.2.2順序串基本操作2.求子串順序串求子串操作是指求字符串中1個(gè)指定區(qū)間的字符串。4.2.2順序串基本操作【算法4.2】求字符串中從指定開始位置begin到結(jié)束位置end-1的子串。思路:（1）判斷begin和end參數(shù)的合法性，若不合法返回異常否則執(zhí)行（2）；

（2）從begin位置開始遍歷，讀取的字符放入1個(gè)字符數(shù)組temp[]中；

（3）重復(fù)（2），直到遍歷完end-1位置處的字符；

（4）將用temp[]構(gòu)造1個(gè)字符串，并返回該字符串。代碼見算法4.24.2.2順序串基本操作【思考與練習(xí)4.1】利用算法4.1是否可以實(shí)現(xiàn)算法4.2，若可以請寫出實(shí)現(xiàn)算法。答：可以。將算法4.2中for循環(huán)中的語句改成：tmp[i-begin]=new算法4_1().algorithm4_1(i);調(diào)用4.1算法即可。4.2.2順序串基本操作3.插入子串順序串插入子串操作是指在指定位置之前插入指定字符串。4.2.2順序串基本操作【算法4.3】在字符串的第i個(gè)字符之前插入子串str。思路:（1）判斷i的合法性，若不合法返回異常，否則執(zhí)行（2）；

（2）擴(kuò)容子串的長度；

（3）從i位置的字符開始到最后1個(gè)字符，向后移動(dòng)子串長度個(gè)位置；

（4）將子串str插入到i位置；

（5）字符串長度增加子串長度。代碼見算法4.34.2.2順序串基本操作4.刪除子串順序串刪除子串操作是指將字符串中指定區(qū)間的字符串刪掉。4.2.2順序串基本操作

4.2.2順序串基本操作5.比較字符串大小順序串比較字符串大小操作是指依次比較2個(gè)字符串中的字符ASCII編碼大小，直到比較完而返回相應(yīng)結(jié)果。4.2.2順序串基本操作

4.2.2順序串基本操作【思考與練習(xí)4.2】下面的算法也是比較2個(gè)字符串大?。ó?dāng)前字符串與str字符串比較），請指出算法的不完整性在哪里？答：假設(shè)str1=“abc”，str2=“abcdefg”，執(zhí)行上面的算法，返回0說明2字符串相等，與實(shí)際不符。4.3鏈串以鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)進(jìn)行存儲(chǔ)的串稱為鏈串。4.3.1鏈串存儲(chǔ)結(jié)構(gòu)鏈串存儲(chǔ)結(jié)構(gòu)采用鏈?zhǔn)酱鎯?chǔ)方式，同鏈表存儲(chǔ)結(jié)構(gòu)。鏈串中的元素既可以是字符也可以是字符串，前者結(jié)點(diǎn)大小為1但存儲(chǔ)密度較小，后者結(jié)點(diǎn)大小大于1且存儲(chǔ)密度大，但是刪除、增加、替換操作時(shí)可能會(huì)帶來大量字符移動(dòng)，所以我們主要探討的是前者。用帶頭結(jié)點(diǎn)的單鏈表表示鏈串如圖4.2所示。4.3.2鏈串基本操作鏈串結(jié)點(diǎn)類LinkNode描述鏈串類LinkString描述4.3.2鏈串基本操作插入子串鏈串插入子串操作是指在串指定位置插入子串，構(gòu)成新的字符串。4.3.2鏈串基本操作【算法4.6】在鏈串i位置處插入子串。思路:（1）建1空鏈串s；

（2）遍歷原串，每次將結(jié)點(diǎn)尾插到s，直到i位置結(jié)點(diǎn)結(jié)束插入；

（3）將待插入串尾插到s；

（4）將原串余下結(jié)點(diǎn)尾插到s；

（5）返回s。代碼見算法4.64.3.2鏈串基本操作

4.3.2鏈串基本操作2.字符串相等比較鏈串字符串相等比較操作是指判斷2個(gè)鏈串是否一樣。4.3.2鏈串基本操作【算法4.7】比較2個(gè)鏈串s和t是否相等，若相等返回true，否則返回false。思路:（1）比較s和t長度，若不相等則返回false，否則執(zhí)行（2）；

（2）依次遍歷s和t，一旦遇到不相等則返回false；

（3）遍歷過程中若沒有返回false，遍歷結(jié)束之后返回true。代碼見算法4.74.4串的模式匹配串的模式匹配，又稱串匹配，是指子串的定位運(yùn)算。假設(shè)有2個(gè)串s和t，s為主串也稱正文串，t為子串也稱模式串。在主串s中查找與模式串t相匹配的子串，如果查找成功，返回匹配的子串第1個(gè)字符在主串中的位置。串的模式匹配算法最常見的有2種：BF算法和KMP算法。4.4.1BF算法BF(BruteForce)算法屬蠻力、暴力、窮舉算法，就是窮舉主串s中的所有子串，與模式串t進(jìn)行比較，判斷是否存在相等。例如，設(shè)主串s="aaaaab"，模式串t="aaab"，比較過程如圖4.3所示。也可以這樣理解：將t看作s的“移動(dòng)窗口”，若失配則繼續(xù)移動(dòng)，直到匹配或超出范圍。4.4.1BF算法【算法4.8】順序串的BF模式匹配算法。思路:（1）從主串s="s0s1…sn-1"的第1個(gè)字符開始和模式串t="t0t1…tm-1"中的第1個(gè)字符比較，若相等則繼續(xù)逐個(gè)比較后續(xù)字符，否則執(zhí)行（2）；

（2）從主串s的第2個(gè)字符開始重新與模式串t的第1個(gè)字符進(jìn)行比較；

（3）依此類推；

（4）若從主串s的第i個(gè)字符開始，每個(gè)字符依次和模式串t中的對應(yīng)字符相等，則匹配成功，返回i；否則返回-1。代碼見算法4.84.4.1BF算法【算法4.9】鏈串的BF模式匹配算法。思路:（1）返回值i置為0，p指向s首結(jié)點(diǎn)，p1指向p結(jié)點(diǎn)，q指向t首結(jié)點(diǎn)；

（2）p1和q結(jié)點(diǎn)字符相等時(shí)同步后移，若q為null則返回i，否則執(zhí)行（3）；

（3）p移向s下1個(gè)結(jié)點(diǎn)，p1指向p結(jié)點(diǎn)，q指向t首結(jié)點(diǎn)，i增1；

（4）重復(fù)（2）、（3），直到遍歷完s；

（5）若沒有匹配則返回-1。代碼見算法4.94.4.2KMP算法

4.4.2KMP算法

4.4.2KMP算法

4.4.2KMP算法3.求next[]數(shù)組在求next[]數(shù)組前，先來理解2個(gè)概念：字符串的前綴和后綴。前綴：從第1個(gè)字符開始求連續(xù)的字符串但不包含本身，這些字符串構(gòu)成了前綴，顯然前綴不包含最后1個(gè)字符；后綴：從最后1個(gè)字符開始求連續(xù)的字符串但不包含本身，這些字符串構(gòu)成了后綴，顯然后綴不包含第1個(gè)字符。4.4.2KMP算法

4.4.2KMP算法

4.4.2KMP算法4.4.2KMP算法設(shè)主串s="ababcabcacbab"，模式串t="abcac"。給出KMP進(jìn)行模式匹配的過程。答：KMP模式匹配只需3趟完成，其過程如圖4.6所示。4.4.2KMP算法

4.5串應(yīng)用串尤其字符串的應(yīng)用十分廣泛，幾乎項(xiàng)目中都要用到Java語言中的字符串類：String類，可見一斑。下面舉些典型例子加深學(xué)習(xí)。4.5串應(yīng)用【例4.1】病毒檢測。疫情爆發(fā)，有種病毒其DNA序列呈環(huán)形，而人類的DNA序列呈線性，例如病毒DNA序列為“aabb”，患者DNA序列為“eabbacab”，該患者感染了病毒，因?yàn)榄h(huán)形的“aabb”可以分解為“aabb”、“abba”、“bbaa”、“baab”，患者DNA序列中含有“abba”，故患者為感染者。設(shè)計(jì)1個(gè)算法來檢測患者是否為感染者。4.5串應(yīng)用思路：（1）用1個(gè)循環(huán)隊(duì)列存儲(chǔ)病毒DNA序列；（2）通過出隊(duì)入隊(duì)和遍歷操作循環(huán)隊(duì)列，求出病毒所有DNA序列；（3）用KMP模式匹配算法，檢測每1種病毒DNA序列是否存在于患者DNA序列中；（4）若檢測到有1個(gè)病毒序列存在于患者中，則輸出true，否則輸出false。代碼見應(yīng)用4.14.5串應(yīng)用【進(jìn)一步思考】例4.1算法中求環(huán)形病毒DNA所有序列還可以用到哪些數(shù)據(jù)結(jié)構(gòu)？答：循環(huán)單鏈表；數(shù)組（模運(yùn)算）；棧（入棧順序不變，出棧順序考慮），等。4.5串應(yīng)用【例4.2】順序串s由數(shù)字和小寫字母組成，設(shè)計(jì)1個(gè)算法將所有數(shù)字放在前面，所有字母放在后面。思路：（1）雙指針i和j設(shè)置，初始值分別指向s的首字符和尾字符；（2）i從前向后找小寫字母，j從后向前找數(shù)字字符；（3）它們都找到之后，交換字符；（4）重復(fù)（2）、（3），直到i大于等于j。代碼見

應(yīng)用4.24.5串應(yīng)用【進(jìn)一步思考】例4.2算法如果用單指針實(shí)現(xiàn)，其思路是什么？答：指針從頭開始遍歷：若遇數(shù)字則繼續(xù)移動(dòng)，若遇字母則將其插入到s末尾后繼續(xù)移動(dòng)。重復(fù)上述過程，直到遍歷了s的n個(gè)長度。4.5串應(yīng)用【例4.3】求1個(gè)字符串s中第1個(gè)最長平臺(tái)，所謂平臺(tái)是指連續(xù)相同的字符。思路：（1）雙指針設(shè)置：i和j初始位置分別指向s首字符和第2個(gè)字符；（2）比較i和j所指向的字符，若不等則i指針移動(dòng)特定距離，j指針仍為其后繼指針，