工學第三章串ppt課件-文庫吧資料
2024-11-09 20:42本頁面
【正文】 F匹配算法最壞的情況下需要比較字符的總次數(shù)為 (nm+1)*m＝ O(n*m) BF算法的時間復雜度 最好的情況是： 一配就中！只比較了 m次，即O(n+m)。 else return 0。 j=1。 } else { start++。j=T[0]) { if (S[i]==T[j]) { i++。 while (i=S[0]amp。 j=1。 //返回本趟匹配 else return 0。 j=1。 j++。amp。 j=1。 模式匹配問題的特點： ⑴ 算法的一次執(zhí)行時間不容忽視：問題規(guī)模通常很大，常常需要在大量信息中進行匹配； ⑵ 算法改進所取得的積累效益不容忽視：模式匹配操作經(jīng)常被調(diào)用，執(zhí)行頻率高。 第 3章 特殊線性表 ——串 １．樸素的模式匹配算法 該算法簡稱 BF算法。 假設串采用順序存儲結(jié)構(gòu)，串的長度存放在數(shù)組的0號單元，串值從 1號單元開始存放。 T稱為模式 。 因為它是一種順序和鏈接相結(jié)合的結(jié)構(gòu) ， 實質(zhì)上是將字符序列分成若干等長的組 ， 每個組占用一個結(jié)點 ， 當要改變串長的時候 ，可能涉及到結(jié)點的增加和刪除問題 。 令一個結(jié)點存儲多個 字符 。 （ 2） 壓縮形式 。 方案二 用數(shù)組的 0號單元存放串的長度 ， 串值從 1號單元開始存放 。 在串的順序存儲中 ， 如何標識一個串的實際長度 ？ 用數(shù)組來存放串，其存儲結(jié)構(gòu)與順序表相同，但串的操作是把串作為一個整體，從而有其與順序表不同的操作特性。 第 3章 特殊線性表 ——串 SubStr (s， i， len)求子串 算法示例 i n f i n i t y i = 3, len = 3 f i n i n f i n i t y i = 6, len = 4 i t y 超出 從串 s中第 i 個字符起連續(xù)取 長為 len 個字符 ,形成子串并返回。 ⑻ StrDelete (s， i， len)： 串刪除 ， 刪除串 s中從第 i個字符開始連續(xù) len個字符 。 若 t不是 s的子串 ， 則返回 0。 第 3章 特殊線性表 ——串 ⑸ StrCmp (s1， s2)： 串比較 ， 若 s1=s2， 返回 0；若s1s2, 返回 1；若 s1s2, 返回 1。 ⑶ StrConcat (s1， s2， s)： 串的連接 ， 將串 s2放在串 s1的后面連接成一個新串 s。 第 3章 特殊線性表 ——串 ⑴ StrLength (s)： 求串 s的長度 。 在計算機中 ， 字符編碼通常用 ASCII碼 ， 字符的比較就是ASCII碼之間的比較 。 第 3章 特殊線性表 ——串 2. 串的比較 串的比較是通過組成串的 字符 之間的比較來進行的 。Unicode由 16 位二進制數(shù)表示一個字符，總共可以表示 216個字符，即 6萬 5千多個字符，能夠表示世界上所有語言的所有字符，包括亞洲國家的表意字符。 微機上常用的字符集是標準 ASCII碼，由 7 位二進制數(shù)表示一個字符，總共可以表示 128 個字符。 注意不是符號 ， 串的數(shù)據(jù)元素均取自某個字符集 。 (4)順序性：相鄰字符之間具有前驅(qū)后繼關(guān)系 。 S1=ab12cd S2=“ab12 S3= S4=“φφφ ” 串的長度？ 第 3章 特殊線性表 ——串 理解串的定義有以下要點： (1)si(1≤i≤n) 是一個抽象符號 ， 代表任意字符 。 主串：包 含子串的串 。 si（ 1≤ i≤ n） 是一個任意字符 。 空串 ：長度為 0的串。 空格串 ：只包含空格的串。第 3章 特殊線性表 —棧、隊列和串 本章的基本內(nèi)容是： ⑴棧和隊列的定義及操作特性； ⑵棧和隊列的兩種存儲方法和基本運算的實現(xiàn)； ⑶串的基本概念和操作； ⑷串的常用存儲方法； ⑸串的模式匹配算法。 第 3章 特殊線性表 ——串 串的邏輯結(jié)構(gòu) 1. 串的定義 串是零個或多個字符組成的有限序列 。 串的長度 ：串中所包含的字符個數(shù)。 空串記作 “ ” ； 非空串通常記作 ： S=“s1 s2 …… sn” 其中： S是串名；雙引號是定界符 ；雙引號引起來的部分是串 值 。 第 3章 特殊線性表 ——串 子串： 串中任意個連續(xù)的字符組成的子序列。 子串在主串中的位置：子串的第一個字符在主串中的序號 。 (2)si在串中出現(xiàn)的序號 i稱為該字符在
教學課件相關(guān)推薦
鄂ICP備17016276號-1