《工學(xué)第三章串》ppt課件-全文預(yù)覽
【正文】 1） next[ j ]有何物理意義？ next[j]函數(shù)表征著模式 T中最大相同首子串和尾子串（真子串）的長度。 如何在匹配不成功時主串不回溯？ 主串不回溯，模式就需要向右滑動一段距離。 i j i j i j i j i j 第 3章 特殊線性表 ——串 若 n為主串長度， m為子串長度，則串的 BF匹配算法最壞的情況下需要比較字符的總次數(shù)為 (nm+1)*m＝ O(n*m) BF算法的時間復(fù)雜度 最好的情況是： 一配就中！只比較了 m次，即O(n+m)。 j=1。j=T[0]) { if (S[i]==T[j]) { i++。 j=1。 j=1。amp。 模式匹配問題的特點： ⑴ 算法的一次執(zhí)行時間不容忽視：問題規(guī)模通常很大，常常需要在大量信息中進(jìn)行匹配； ⑵ 算法改進(jìn)所取得的積累效益不容忽視：模式匹配操作經(jīng)常被調(diào)用，執(zhí)行頻率高。 假設(shè)串采用順序存儲結(jié)構(gòu)，串的長度存放在數(shù)組的0號單元，串值從 1號單元開始存放。 因為它是一種順序和鏈接相結(jié)合的結(jié)構(gòu) ， 實質(zhì)上是將字符序列分成若干等長的組 ， 每個組占用一個結(jié)點 ， 當(dāng)要改變串長的時候 ，可能涉及到結(jié)點的增加和刪除問題 。 （ 2） 壓縮形式 。 在串的順序存儲中 ， 如何標(biāo)識一個串的實際長度 ？ 用數(shù)組來存放串，其存儲結(jié)構(gòu)與順序表相同，但串的操作是把串作為一個整體，從而有其與順序表不同的操作特性。 ⑻ StrDelete (s， i， len)： 串刪除 ， 刪除串 s中從第 i個字符開始連續(xù) len個字符 。 第 3章 特殊線性表 ——串 ⑸ StrCmp (s1， s2)： 串比較 ， 若 s1=s2， 返回 0；若s1s2, 返回 1；若 s1s2, 返回 1。 第 3章 特殊線性表 ——串 ⑴ StrLength (s)： 求串 s的長度 。 第 3章 特殊線性表 ——串 2. 串的比較 串的比較是通過組成串的 字符 之間的比較來進(jìn)行的 。 微機上常用的字符集是標(biāo)準(zhǔn) ASCII碼，由 7 位二進(jìn)制數(shù)表示一個字符，總共可以表示 128 個字符。 (4)順序性：相鄰字符之間具有前驅(qū)后繼關(guān)系 。 主串：包 含子串的串 。 空串 ：長度為 0的串。第 3章 特殊線性表 —棧、隊列和串 本章的基本內(nèi)容是： ⑴棧和隊列的定義及操作特性； ⑵棧和隊列的兩種存儲方法和基本運算的實現(xiàn)； ⑶串的基本概念和操作； ⑷串的常用存儲方法； ⑸串的模式匹配算法。 串的長度 ：串中所包含的字符個數(shù)。 第 3章 特殊線性表 ——串 子串： 串中任意個連續(xù)的字符組成的子序列。 (2)si在串中出現(xiàn)的序號 i稱為該字符在串中的位置 (3)有限性：組成串的字符個數(shù)是有限的 。 第 3章 特殊線性表 ——串 串的數(shù)據(jù)對象約束為某個字符集。為了保持兼容性， Unicode字符集中的前 256個字符與擴展 ASCII碼完全相同。 3. 串的抽象數(shù)據(jù)類型定義 串的基本操作通常以 “ 串的整體 ” 作為操作對象。 ⑷ SubStr (s， i， len)： 求子串 ， 返回從串 s的第 i個字符開始取長為 len 的子串 。 ⑺ StrInsert (s， i， t)： 串插入 ， 將串 t插入到串 s的第i個位置 。 第 3章 特殊線性表 ——串 串的存儲結(jié)構(gòu) 1. 串的順序存儲結(jié)構(gòu) 定義 ： 串的順序存儲結(jié)構(gòu)是用數(shù)組來存儲串中的字符序列。 方案三 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） 非壓縮形式 。 優(yōu)缺點？ 非壓縮形式：操作方便 ， 但存儲率低； 壓縮形式：存儲率高 ， 但操作復(fù)雜 。如果匹配成功，返回 T在 S中的位置，如果匹配失敗，返回 0。 基本思想 是：從主串 S的第一個字符開始和模式 T的第一個字符進(jìn)行比較，若相等，則繼續(xù)比較兩者的后續(xù)字符；否則，從主串 S的第二個字符開始和模式 T的第一個字符進(jìn)行比較，重復(fù)上述過程，若 T中的字符全部比較完畢，則說明本趟匹配成功；否則匹配失敗。 //設(shè)置比較的起始下標(biāo) while ((i=S[0]) amp。}
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1