工學第三章串ppt課件-wenkub
2022-11-18 20:42:07 本頁面
【正文】 si …… 主串 S i tj 模式 T j tj … BF算法的基本思想圖解 第 3章 特殊線性表 ——串 第 3章 特殊線性表 ——串 1. 在串 S和串 T中設比較的起始下標 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。下面我們介紹兩種串的模式匹配算法。 a b c d e f g a e b f c g d 第 3章 特殊線性表 ——串 模式匹配 定義：給定兩個串 S=“s1s2… sn” 和 T=“t1t2… tm”， 在主串 S中尋找子串 T的過程稱 為 模式匹配 。 一個結點只存儲一個字符 。 0 1 2 3 4 5 6 7 8 … … MaxSize1 a b c d e f g h i 空 閑 9 串的順序存儲方式 1 第 3章 特殊線性表 ——串 用一個變量來表示串的實際長度 方案一 在串尾存儲一個不會在串中出現(xiàn)的特殊字符作為串的終結符 ， 表示串的結尾 。 ⑼ StrRep (s， t， r)： 串替換 ， 在串 s中用串 r替換所有與串 t相等的子串 。 ⑹ StrIndex (s， t)： 子串定位 ， 返回子串 t在主串 s中首次出現(xiàn)的位置 。 ⑵ StrAssign (s1， s2)： 串賦值 ， 將 s2的串值賦值給串 s1。 給定兩個串： X=x1x2… xn Y=y1y2… ym 則當 n=m且 x1=y1， … ， xn=ym時 ， 稱 X=Y； 當下列條件之一成立時 ， 稱 X＜ Y： ⑴ n＜ m， 且 xi=yi（ i=1， 2， … ， n） ； ⑵ 存在某個 k≤ min(m， n)， 使得 xi=yi（ i=1， 2， … ，k1） ， xk＜ yk。擴展 ASCII碼由 8 位二進制數(shù)表示一個字符，總共可以表示 256 個字符，足夠表示英語和一些特殊符號，但無法滿足國際需要。 (5)元素的特殊性：數(shù)據(jù)元素是字符 。 子串在主串中的位置：子串的第一個字符在主串中的序號 。 空串記作 “ ” ； 非空串通常記作 ： S=“s1 s2 …… sn” 其中： S是串名；雙引號是定界符 ；雙引號引起來的部分是串 值 。 第 3章 特殊線性表 ——串 串的邏輯結構 1. 串的定義 串是零個或多個字符組成的有限序列 。 空格串 ：只包含空格的串。 si（ 1≤ i≤ n） 是一個任意字符 。 S1=ab12cd S2=“ab12 S3= S4=“φφφ ” 串的長度？ 第 3章 特殊線性表 ——串 理解串的定義有以下要點： (1)si(1≤i≤n) 是一個抽象符號 ， 代表任意字符 。 注意不是符號 ， 串的數(shù)據(jù)元素均取自某個字符集 。Unicode由 16 位二進制數(shù)表示一個字符，總共可以表示 216個字符，即 6萬 5千多個字符，能夠表示世界上所有語言的所有字符，包括亞洲國家的表意字符。 在計算機中 ， 字符編碼通常用 ASCII碼 ， 字符的比較就是ASCII碼之間的比較 。 ⑶ StrConcat (s1， s2， s)： 串的連接 ， 將串 s2放在串 s1的后面連接成一個新串 s。 若 t不是 s的子串 ， 則返回 0。 第 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 個字符 ,形成子串并返回。 方案二 用數(shù)組的 0號單元存放串的長度 ， 串值從 1號單元開始存放 。 令一個結點存儲多個 字符 。 T稱為模式 。 第 3章 特殊線性表 ——串
教學課件相關推薦
鄂ICP備17016276號-1