工學(xué)第三章串ppt課件-展示頁(yè)
2024-11-12 20:42本頁(yè)面
【正文】 串中的位置 (3)有限性：組成串的字符個(gè)數(shù)是有限的 。 (5)元素的特殊性：數(shù)據(jù)元素是字符 。 第 3章 特殊線性表 ——串 串的數(shù)據(jù)對(duì)象約束為某個(gè)字符集。擴(kuò)展 ASCII碼由 8 位二進(jìn)制數(shù)表示一個(gè)字符，總共可以表示 256 個(gè)字符，足夠表示英語(yǔ)和一些特殊符號(hào)，但無(wú)法滿足國(guó)際需要。為了保持兼容性， Unicode字符集中的前 256個(gè)字符與擴(kuò)展 ASCII碼完全相同。 給定兩個(gè)串： X=x1x2… xn Y=y1y2… ym 則當(dāng) n=m且 x1=y1， … ， xn=ym時(shí) ， 稱 X=Y； 當(dāng)下列條件之一成立時(shí) ， 稱 X＜ Y： ⑴ n＜ m， 且 xi=yi（ i=1， 2， … ， n） ； ⑵ 存在某個(gè) k≤ min(m， n)， 使得 xi=yi（ i=1， 2， … ，k1） ， xk＜ yk。 3. 串的抽象數(shù)據(jù)類(lèi)型定義 串的基本操作通常以 “ 串的整體 ” 作為操作對(duì)象。 ⑵ StrAssign (s1， s2)： 串賦值 ， 將 s2的串值賦值給串 s1。 ⑷ SubStr (s， i， len)： 求子串 ， 返回從串 s的第 i個(gè)字符開(kāi)始取長(zhǎng)為 len 的子串 。 ⑹ StrIndex (s， t)： 子串定位 ， 返回子串 t在主串 s中首次出現(xiàn)的位置 。 ⑺ StrInsert (s， i， t)： 串插入 ， 將串 t插入到串 s的第i個(gè)位置 。 ⑼ StrRep (s， t， r)： 串替換 ， 在串 s中用串 r替換所有與串 t相等的子串 。 第 3章 特殊線性表 ——串 串的存儲(chǔ)結(jié)構(gòu) 1. 串的順序存儲(chǔ)結(jié)構(gòu) 定義 ： 串的順序存儲(chǔ)結(jié)構(gòu)是用數(shù)組來(lái)存儲(chǔ)串中的字符序列。 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é)尾 。 方案三 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） 非壓縮形式 。 一個(gè)結(jié)點(diǎn)只存儲(chǔ)一個(gè)字符 。 優(yōu)缺點(diǎn)？ 非壓縮形式：操作方便 ， 但存儲(chǔ)率低； 壓縮形式：存儲(chǔ)率高 ， 但操作復(fù)雜 。 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在 S中的位置，如果匹配失敗，返回 0。下面我們介紹兩種串的模式匹配算法。 基本思想 是：從主串 S的第一個(gè)字符開(kāi)始和模式 T的第一個(gè)字符進(jìn)行比較，若相等，則繼續(xù)比較兩者的后續(xù)字符；否則，從主串 S的第二個(gè)字符開(kāi)始和模式 T的第一個(gè)字符進(jìn)行比較，重復(fù)上述過(guò)程，若 T中的字符全部比較完畢，則說(shuō)明本趟匹配成功；否則匹配失敗。 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è)比較的起始下
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1