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