《工學(xué)第三章串》ppt課件-文庫(kù)吧
2025-10-05 20:42 本頁(yè)面
【正文】 用數(shù)組來(lái)存儲(chǔ)串中的字符序列。 在串的順序存儲(chǔ)中 ， 如何標(biāo)識(shí)一個(gè)串的實(shí)際長(zhǎng)度 ？ 用數(shù)組來(lái)存放串，其存儲(chǔ)結(jié)構(gòu)與順序表相同，但串的操作是把串作為一個(gè)整體，從而有其與順序表不同的操作特性。 0 1 2 3 4 5 6 7 8 … … MaxSize1 a b c d e f g h i 空 閑 9 串的順序存儲(chǔ)方式 1 第 3章 特殊線性表 ——串 用一個(gè)變量來(lái)表示串的實(shí)際長(zhǎng)度 方案一 在串尾存儲(chǔ)一個(gè)不會(huì)在串中出現(xiàn)的特殊字符作為串的終結(jié)符 ， 表示串的結(jié)尾 。 方案二 用數(shù)組的 0號(hào)單元存放串的長(zhǎng)度 ， 串值從 1號(hào)單元開(kāi)始存放 。 方案三 0 1 2 3 4 5 6 7 8 9 … … … MaxSize1 b c d h i \0 空 閑串的順序存儲(chǔ)方式 2 2 4 6 7 8 9 … … … axSize 9 a b c d e f g h i 空 閑 串的順序存儲(chǔ)方式 3 第 3章 特殊線性表 ——串 2. 串的鏈接存儲(chǔ)結(jié)構(gòu) （ 1） 非壓縮形式 。 （ 2） 壓縮形式 。 一個(gè)結(jié)點(diǎn)只存儲(chǔ)一個(gè)字符 。 令一個(gè)結(jié)點(diǎn)存儲(chǔ)多個(gè) 字符 。 優(yōu)缺點(diǎn)？ 非壓縮形式：操作方便 ， 但存儲(chǔ)率低； 壓縮形式：存儲(chǔ)率高 ， 但操作復(fù)雜 。 因?yàn)樗且环N順序和鏈接相結(jié)合的結(jié)構(gòu) ， 實(shí)質(zhì)上是將字符序列分成若干等長(zhǎng)的組 ， 每個(gè)組占用一個(gè)結(jié)點(diǎn) ， 當(dāng)要改變串長(zhǎng)的時(shí)候 ，可能涉及到結(jié)點(diǎn)的增加和刪除問(wèn)題 。 a b c d e f g a e b f c g d 第 3章 特殊線性表 ——串 模式匹配 定義：給定兩個(gè)串 S=“s1s2… sn” 和 T=“t1t2… tm”， 在主串 S中尋找子串 T的過(guò)程稱 為 模式匹配 。 T稱為模式 。如果匹配成功，返回 T在 S中的位置，如果匹配失敗，返回 0。 假設(shè)串采用順序存儲(chǔ)結(jié)構(gòu)，串的長(zhǎng)度存放在數(shù)組的0號(hào)單元，串值從 1號(hào)單元開(kāi)始存放。下面我們介紹兩種串的模式匹配算法。 第 3章 特殊線性表 ——串 １．樸素的模式匹配算法 該算法簡(jiǎn)稱 BF算法。 基本思想 是：從主串 S的第一個(gè)字符開(kāi)始和模式 T的第一個(gè)字符進(jìn)行比較，若相等，則繼續(xù)比較兩者的后續(xù)字符；否則，從主串 S的第二個(gè)字符開(kāi)始和模式 T的第一個(gè)字符進(jìn)行比較，重復(fù)上述過(guò)程，若 T中的字符全部比較完畢，則說(shuō)明本趟匹配成功；否則匹配失敗。 模式匹配問(wèn)題的特點(diǎn)： ⑴ 算法的一次執(zhí)行時(shí)間不容忽視：?jiǎn)栴}規(guī)模通常很大，常常需要在大量信息中進(jìn)行匹配； ⑵ 算法改進(jìn)所取得的積累效益不容忽視：模式匹配操作經(jīng)常被調(diào)用，執(zhí)行頻率高。 si …… …… tj 模式 T 主串 S … i j 回溯 i 回溯 j BF算法的基本思想圖解 本趟匹配開(kāi)始位置 第 3章 特殊線性表 ——串 si …… 主串 S 模式 T j i tj … BF算法的基本思想圖解 第 3章 特殊線性表 ——串 si …… 主串 S i tj 模式 T j tj … BF算法的基本思想圖解 第 3章 特殊線性表 ——串 第 3章 特殊線性表 ——串 1. 在串 S和串 T中設(shè)比較的起始下標(biāo) i和 j； 2. 循環(huán)直到 S中所剩字符個(gè)數(shù)小于 T的長(zhǎng)度或 T的所有字符均比較完 如果 S[i]=T[j]， 繼續(xù)比較 S和 T的下一個(gè)字符；否則 將 i和 j回溯 ， 準(zhǔn)備下一趟比較； 3. 如果 T中所有字符均比較完 ， 則匹配成功 ， 返回匹配的起始比較下標(biāo)；否則 ， 匹配失敗 ， 返回 0； BF算法用偽代碼 : 第 3章 特殊線性表 ——串 int BF(char S[ ], char T[ ]) { i=1。 j=1。 //設(shè)置比較的起始下標(biāo) while ((i=S[0]) amp。amp。 (j=T[0]))
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1